References on Circuit Lower Bounds Preamble

Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than the latter, but Goldwasser and Sipser showed that they have the same power (with respect to language recognition). Hence, in this post, I'll used the two concepts interchangeably.

Let $IP[k]$ be the class of languages admitting an interactive proof system with $k$ rounds. Babai proved that $IP[O(1)] \subseteq \Pi_2^P$. (A relativizable result.)

At first, it was not know whether unbounded number of rounds can increase the power of IP. In particular, it was shown to have contradictory relativizations: Fortnow and Sipser showed that for some oracle $A$, it holds that $coNP^A \not\subset IP[poly]^A$. (Therefore, relative to $A$, $IP[poly]$ is not a superclass of $PH$.)

On the other hand, the following paper:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

shows that, for some oracle $B$, we have $IP[poly]^B \not\subset PH^B$. (Therefore, $IP[poly]^B \neq IP[O(1)]^B$ since as stated above, the latter is a subclass of $\Pi_2^{P,B}$.)

The Question

The paper by Aiello, Goldwaseer, and Hastad (cited above) states:

  The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [FSS], [Y] and [H1].

where [FSS], [Y] and [H1] are:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

I found the papers very old and extremely hard to follow. I read Chapter 14 of Arora & Barak's book, yet apparently it does not cover everything I need.

  What references on "Circuit Lower Bounds" do you suggest?

(I specially need survey-like references; those which are newer and do not need a lot of expertise are more preferable.)

What you want is a good reference to understand the exponential lower bounds for $AC^0$ circuits computing the PARITY function.

Now you haven't stated whether you actually want to understand the proof, or just understand things at a high level, the way a survey article would explain things.

A survey article I recently read and liked is "The complexity of finite functions" by Boppana and Sipser.

If you really want to sit down and understand the proof, then you can either read proofs based on the Switching lemma (which appear in the papers you cited - [FSS], [Y] and [H1]), or the Razborov-Smolensky proof.

For proofs using the Switching Lemma, Håstad's Ph.D. thesis is a good read, if a bit hard to follow if you're new to the area. A better exposition of the proof is in "Introduction to circuit complexity and a guide to Håstad's proof" by Allan Heydon. The only problem with it is that I can't find it online, and I have a hard copy. I really recommend it if you're new to circuit complexity.

For the Razborov-Smolensky approach, just google for it and you'll get a bunch of lecture notes. I understood the lower bound from these three lecture notes: Sanjeev Arora, Madhu Sudan and Kristoﬀer Arnsfelt Hansen.


Fast high-dimensional K-nearest neighbors I'm aware of this question
https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm
But it's not the same question as I'm asking. Because, Octree and its generalization are only applicable to very small $D$, and they increase exponentially with regard to it. But I'm interested in very high dimensional cases, like $D>1000$. Assume we have a cloud of $N$ points in a $D$ dimensional space. But they might have a lower inherent dimension $d$, i.e., they lie on a $d$ dimensional manifold. Now, what is the most efficient way to compute K-nearest neighbors for each point? I've researched this topic a little bit, but most of the literature focuses on KNN clustering which is slightly different from what I'm asking. First, I don't have any labels here and those methods which rely on labels to reduce complexity are not of any interest. Second, many methods focus on reducing query processing time, which means they pre-process the data, build a database, and quickly process new queries. But I'm interested in reducing the overall time complexity rather than queries. What is the state-of-the-art method and its time complexity?

UPDATE:
One might assume that these points are uniformly spread in a hyper-cube. I suppose anything which holds for uniform distribution, to a lesser extent will hold for a smoothly changing distribution.

For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\alpha)$ for some $\alpha < 1$.

On the other hand you can do better if you are ok with approximation. Locality sensitive hashing can be used to achieve subquadratic in $N$ running times while reporting points which are not much further than the nearest neighbors.

For subsets of Euclidean space with doubling dimension $d$ (which captures the lower-dimensional manifold situation), Indyk and Naor show that there is an embedding into $O(d)$ dimensions (in fact a random projection in the style of the Johnson-Lindenstrauss lemma) which approximately preserves nearest neighbors. If $d$ is small enough you could first apply the embedding, then use a nearest neighbor data structure for low dimension.

You could also try the random projection trees (RP-trees) of Dasgupta and Freund. They are a natural variant of kd-trees in which the cut in each level is done in a random direction, rather than a coordinate direction. I don't think there are any known provable guarantee for how well RP-trees do on nearest neighbor problems, but the paper I have linked does prove that the trees adapt nicely to doubling dimension, so there is hope. The guarantee they give is that, if a point set inside a cell has doubling dimension $d$, then the descendants of the cell $O(d\log d)$ levels down the tree have diameter at most half that of the cell.


Major open problems on polynomial kernel (non) existence We are not able to settle the (non-)existence of a polynomial kernel for a parameterized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non-existence of a polynomial kernel under reasonable complexity-theoretic assumptions). So we are searching for major open problems that could be used in a parameter-preserving reduction to "underline its hardness".

What are major parameterized NP-complete problems for which it is unknown if they have a polynomial kernel ? Is there a survey/technical report on the subject?

An example could be ODD CYCLE TRANSVERSAL (OCT), the task of making an undirected graph bipartite by deleting as few vertices as possible, parameterized by the number of allowed vertex deletions (though Stefan Kratsch and Magnus Wahlström recently showed a randomized polynomial kernel for OCT)

Currently, I would say the 3 major open cases are:

Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution
Planar Vertex Deletion (make a graph planar by deleting at most k vertices)
Edge Multiway cut (given an undirected graph and a list of terminals, delete at most k edges to ensure all the terminals end up in a different connected component)

For all of these, the relevant parameter is the size of the solution. You can have a look at the open problem list from the 2013 Workshop on Kernelization ( http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf ) for others. Pointers to other (but older) open problem lists in parameterized complexity can be found here: http://fpt.wikidot.com/open-problems .


Does there exist a hardest DCFL? Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$.  Does there exist a similar statement with DCFL, possibly with some restriction on the morphisms allowed?

(See, e.g., M. Autebert, J. Berstel, and L. Boasson. Context-free languages and
pushdown automata. In R. Rozenberg and A. Salomaa, editors,
Handbook of Formal Languages, volume I, chapter 3. Springer Verlag, 1997.)

An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper.

  We show that every context-free language can be expressed as $h^{-1}(L_0)$ or $h^{-1}(L_0-\{e\})$ for a homomorphism $h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By way of contrast, the family of deterministic context-free languages is not a principal AFDL [7].

The paper 7 is the conference version of the paper. In the conference version, Theorem 4.2 states that "The family of deterministic context-free languages is not a principal AFDL".

However some analogue characterization may still be possible. Okhotin provided homomorphic characterizations of conjunctive and Boolean grammars. For DCFL's the problem seems to be open. The following is the conclusion of Okhotin's paper (from 2013).

  Every family of languages closed under inverse homomorphisms can potentially
  have an analogue of Greibach’s inverse homomorphic characterization.
  The question is, which families have it? Could it exist for linear, deterministic
  or unambiguous variants of ordinary (context-free) grammars? Could
  there be such a characterization for linear conjunctive grammars, unambiguous
  conjunctive grammars, etc.?


Is it a bad idea to critique someone's paper in my first publication? I am currently facing a situation that I am not sure how to handle.

Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in a very reputable journal (IEEE Transactions on Information Theory) that proposed a new algorithm that consists of $2$ sub-algorithms, $A_1, A_2$ that are both used to solve the problem. Here is the caveat, Algorithm $A_1$ was shown to eventually converge without any run time gurantee (shown to converge with finite number of steps), while $A_2$ was shown to take $O(n^5)$.

My paper is essentially replacing $A_1$ with a new algorithm which is guaranteed to terminate correctly in $O(n\log n)$, hence bringing the overall time complexity when combined with $A_2$ to $O(n^6\log n)$.

So far, so good. I am fairly certain the paper can get accepted into the same journal since the new algorithm is highly non trivial and provides lots of new insight on the problem. However, 2 weeks ago, I was wrapping up everything and decided to give algorithm $A_2$ another read as well as its proofs. That's when I faced some problems.

One of the proofs in that paper is faulty, beyond repair. The author did a very big jump, and I managed to come up with a counter example essentially showing that the theorem he "proved" is false. I tried to fix his algorithm, but I couldn't. So I tried approaching it from a new perspective using his method, and I managed to get a new algorithm that replaces the faulty $A_2$, but it ran in $O(n^6)$.

Here is my problem, my advisor thinks I should definitely include this in my paper as I've essentially replaced both algorithms $A_1, A_2$. However, If I just say I have an $O(n^6)$ when there is an $O(n^5)$ known, its going to raise eye brows. The only way I can pass this is if I actually take jabs at $A_2$ and show that its actually wrong, but I feel that "attacking" a paper in my first publication is a really bad idea.

Any ideas?

EDIT: Contacted the author and he acknowledged the mistake. He agreed to be mentioned in the new paper and he showed quite the interest in the $O(n\log n)$ algorithm. He also contacted IEEE Transactions to see if they can add a correcting note. This went way smoother than I thought it would. Thanks everyone!

I think the same standards apply, regardless of whether it's your 1st or 100th publication. If you think you've found a mistake in a published paper, a common courtesy is to first contact the paper's authors for a clarification, as Noam suggested in the comments. If the authors confirm that it's indeed a mistake, you can indicate that in the paper (cite it as "private communication"); this should make the review process smoother.

When pointing out people's mistakes in print, gentle understatement is a good practice. "There appears to be a mistake in the proof" should be gentle enough. Having a counterexample certainly helps.


Is the relation decidable? Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?

Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases.


What's wrong with this LEAN proof? I'm learning to use the LEAN theorem prover and I got stuck in a proof of a simple fact in first-order logic:
$$ p(x) \rightarrow \forall x p(x) $$
My code is the following:

variables (A : Type) (p q : A → Prop)
example (x : A) : p x → (∀ x, p x) :=
assume H : p x,
take x : A,
show p x, from H

but it keeps saying that H has type p x_1, instead of what I expected, which is type p x.

Your example is not true, that's why you cannot prove it. If we assume your example is true (which we do using the sorry tactic), then we can prove false. The proof goes as follows. We first pick x to be 0 and p to be the property that a number n is equal to 0. So p x is p 0 is 0 == 0 which is obviously true. Your example now provides us with the proof that p holds for all numbers. We pick 1, which is a contradiction because 0 <> 1.

variables (A : Type) (p : A → Prop)

lemma lma (x : A) : p x → (∀ x', p x') :=
  assume H : p x,
  take x' : A,
  sorry

lemma inconsistent : false :=
  assert h : 0 == 0 → (∀ x, x == 0), from (lma num (λ n, n==0) 0),
  assert e : 1 == 0, begin
    refine (h _ 1),
    reflexivity
  end,
  show false, by cases e

The formula that you posted is also false in first order logic, even ∀ x, p x → (∀ x, p x) is not a true statement. Note that your example is different from the true statement (∀ x, p x) → (∀ x, p x).

The error message that you see stems from the fact that you are trying to use the hypothesis p x where the hypothesis p x' is expected (you are confusing the xes)


To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade? As I understand it, a fundamental of Chaum's mix-net is that, absent an external adversary who can analyse traffic on links within the network, no mix can link the source and destination of any message unless it collaborates with every other mix participating in the cascade through which that message passes.

Most of the mix-net projects about which I have read (both those that have been implemented and those that remain theoretical) mitigate such a "collaboration attack" by introducing randomness into path selection: thus an adversary must collaborate with a significant proportion of all mixes throughout the network in order to achieve a high probability that those in any given cascade will all be collaborators.  Various techniques have been suggested to further frustrate an adversary who attempts to so bias the network, such as viewing all mixes on a single subnet as potential collaborators.

If one is certain (at least, as much as one can ever be) that some particular mixes are honest (i.e. not collaborating with an adversary), it would at first glance appear desirable to ensure that at least one such honest mix is included in every cascade used for one's messages so as to significantly reduce (if not completely eliminate) the threat of such "collaboration attacks".

However, forcing all one's messages to pass through a subset of the network that is defined by one's trust relationships leaks information about those relationships.  Over time, an adversary might be able to use such information to link together all one's messages or even identify oneself.

My question is: how can one measure this trade-off?  Is there existing research that already has considered it (I have not been able to find any yet)?

Where senders are themselves also acting as mixes in the presence of sufficient inbound cover traffic, does the inclusion of known honest mixes in downstream cascades for their own messages actually provide any additional anonymity given that those messages could arguably have been forwarded for another party?

I haven't seen a paper that addresses your (first) question specifically. One extreme example of a mix node that you trust is yourself, if you are participating in the network as well as using it. One paper that talks about the trade-offs of using yourself as a node in a mix network is: On the Economics of Anonymity. It sort of addresses your second question.

While Tor is not exactly a mix network, I believe it carefully chooses entry nodes based on individuals the network maintainers trust. In this case, all users have the same "trust network" and so it avoids the problem you are proposing to study. The drawback is you personally must trust the same nodes.

As to your specific question, I haven't seen a paper that specifically addresses what you want but I also do not follow the area closely. Most papers on Mix Networks are catalogued here: http://freehaven.net/anonbib/ and so you could thumb through the titles for something that might be related.

Finally, I'm not sure you'll find the adversary has much power unless if they can observe large portions of the network, in which case there are more effective attacks (especially in Tor-like anonymity networks which don't actually mix or obfuscate packet timing).


When does (or should) Theoretical CS care about intuitionistic proofs? From what I understand (which is very little, so please correct me where I err!), theory of programming languages is often concerned with "intuitionistic" proofs. In my own interpretation, the approach requires us to take seriously the consequences of computation on logic and provability. A proof cannot exist unless there exists an algorithm constructing the consequences from the hypotheses. We might reject as an axiom the principle of the excluded middle, for instance, because it exhibits some object, which is either $X$ or $\lnot X$, nonconstructively.

The above philosophy might lead us to prefer intuitionistically valid proofs over ones that are not. However, I have not seen any concern about actually using intuitionistic logic in papers in other areas of theoretical CS. We seem happy to prove our results using classical logic. For example, one might imagine using the principle of the excluded middle to prove that an algorithm is correct. In other words, we care about and take seriously a computationally-limited universe in our results, but not necessarily in our proofs of these results.

1. Are researchers in theoretical CS ever concerned about writing intuitionistically valid proofs? I could easily imagine a subfield of theoretical computer science that seeks to understand when TCS results, especially algorithmic ones, hold in intuitionistic logic (or more interestingly, when they don't). But I have not yet come across any.

2. Is there any philosophical argument that they should? It seems like one could claim that computer science results ought to be proven intuitionistically when possible, and we ought to know which results require e.g. PEM. Has anyone tried to make such an argument? Or perhaps there is a consensus that this question is just not very important?

3. As a side question, I am curious to know examples of cases where this actually matters: Are there important TCS results known to hold in classical logic but not in intuitionistic logic? Or suspected not to hold in intuitionistic logic.

Apologies for the softness of the question! It may require rewording or reinterpretation after hearing from the experts.

It is is worth thinking about WHY intuistionistic logic is the natural logic for computation, since all too often people get lost in the technical details and fail to grasp the essence of the issue.

Very simply, classical logic is a logic of perfect information: all statements within the system are assumed to be known or knowable as unambiguously true or false.

Intuistionistic logic, on the other hand, has room for statements with unknown and unknowable truth values.  This is essential for computation, since, thanks to the undecidability of termination in the general case, it will not always be certain what the truth value of some statements will be, or even whether or not a truth value can ever be assigned to certain statements.

Beyond this, it turns out that even in strongly normalizing environments, where termination is always guaranteed, classical logic is still problematic, since double negation elimination $\neg\neg P \implies P$ ultimately boils down to being able to pull a value "out of thin air" rather than directly computing it.

In my opinion, these "semantic" reasons are a much more important motivation for the use of  intuistionistic logic for computation than any other technical reasons one could marshal.


Need a term for a graph-theoretic/metric concept Let $(X,d)$ be a metric space, and define $\rho$ to be the largest distance of any $x\in X$ to its nearest neighbor.

Formally,
$$ \rho = \sup_{x \in X}~ d(x, X \setminus \{x\}). $$

Does this quantity have a name? It's zero in continuous spaces and is only interesting in discrete ones.

Sloan calls this the "covering radius" when distributing points on a sphere.  http://www2.research.att.com/~njas/coverings/


Computing the DAG of a program given source code or AST I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG).

Is there an algorithm for taking code (or Abstract syntax trees) from a language, say Python, and generating a DAG for it? I've been searching for a paper related to this for a long time and haven't found anything on google scholar.

Intuitively, I'd say that it's not possible, since some languages (such as Python) can change just about everything at run-time, and thus to determine the behavior and dependencies of a given program you would have to run it first for every possible set of inputs.

EDIT: I'm using DAG in this sense as the Directed Acyclic Graph for the dependencies (i.e. which parts depend on which other parts)

I assume you're looking for ways to compute the Control Flow Graph of a given program.

This graph depends (obviously) on the actual operational semantics of the language you are interested in, and so cannot be computed from the AST alone, in the sense that some knowledge of the language semantics themselves are needed.

For a given language it is possible to build the CFG given the AST of the parsed program, and indeed this is usually a very important step in compilers to perform flow analysis. This can be found in chapter 17 of Appel or in chapter 7 of Muchnick.


Parameterized complexity from P to NP-hard and back again I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, for example $k$-SAT has a single phase transition from $k \in \{1,2\}$ (where the problem is in P) to $k \ge 3$ (where the problem is NP-complete). I'm interested in problems where there are phase transitions in both directions (from easy to hard and vice-versa) as $k$ increases.

My question is somewhat similar to the one asked at Hardness Jumps in Computational Complexity, and in fact some of the responses there are relevant to my question.

Examples I am aware of:

$k$-colorability of planar graphs: In P except when $k=3$, where it is NP-complete.
Steiner tree with $k$ terminals: In P when $k=2$ (collapses to shortest $s$-$t$ path) and when $k=n$ (collapses to MST), but NP-hard "in between". I don't know if these phase transitions are sharp (e.g., P for $k_0$ but NP-hard for $k_0+1$). Also the transitions of $k$ depend on the size of input instance, unlike my other examples.
Counting satisfying assignments of a planar formula modulo $n$: In P when $n$ is a Mersenne prime number $n=2^k-1$, and #P-complete for most(?)/all other values of $n$ (from Aaron Sterling in this thread). Lots of phase transitions!
Induced subgraph detection: The problem is not parametrized by an integer but a graph. There exist graphs $H_1 \subseteq H_2 \subseteq H_3$ (where $\subseteq$ denotes a certain kind of subgraph relation), for which determining whether $H_i \subseteq G$ for a given graph $G$ is in P for $i\in \{1,3\}$ but NP-complete for $i=2$. (from Hsien-Chih Chang in the same thread).

One field with lots of non-monotonicity of problem complexity is property testing. Let $\mathcal{G}_n$ be the set of all $n$-vertex graphs, and call $P \subseteq \mathcal{G}_n$ a graph property. A generic problem is to determine whether a graph $G$ has property $P$ (i.e. $G \in P$) or is `far' from having property $P$ in some sense. Depending on what $P$ is, and what kind of query access you have to the graph, the problem can be quite difficult.

But it is easy to see that the problem is non-monotone, in that if we have $S \subset P \subset T$, the fact that $P$ is easily testable does not imply either that $S$ is easily testable or that $T$ is.

To see this, it is enough to observe that $P = \mathcal{G}_n$ and $P = \emptyset$ are both trivially testable, but that for some properties, there exist strong lower bounds.


Finding a random regular graph with degree d I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.

For $d \in 2\mathbb{N} +1$ this trivially is impossible as no such graph exists: The number of incidences (connections between vertices and edges) is given by $|V|\cdot d = d^3 = 8k^3 + 12k^2 + 6k + 1$ (for some $k$). As the number of incidences is always double the number of edges $|E| = d^3/2$ is a contradiction.

This argument however, doesn't work for $d \in 2\mathbb{N}$.

My first guess was just constructing a random graph would do, however, this can get stuck in a local maximum. For instance in $d = 2$:

+---+    example for
|  /     an incomplete
| /      graph that
|/       cannot be
+   +    completed

A similar example can be constructed for $d = 4$ leaving up to two unconnectable vertices (essentially by using a 4-HyperCube).

I strongly suspect that for each $d$ the number of valid graphs significantly outweigh the number of incomplete graphs, but I would like to know how likely it is to end up with an incomplete graph. And if there is a better way to find these graphs than the random algorithm above (which could perhaps be fixed by breaking apart incomplete graphs, but that would not be guaranteed to terminate).

The standard simple way of generating random regular graphs is:

while the degree < d

choose a random perfect matching from the edges still possible to add to the graph
If no matching is possible, restart the process.

The problem with this is that the higher edge degree you want, the more likely it is for the algorithm to get stuck. I see many papers limiting themself to $|V|>d^3$, so I don't know if this process will work for you.


Lowerbound for the minimum distance between points in a "nice" triangulation Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. That is, every face is a triangle.

Suppose that the resulting triangulation has the property that the smallest angle is greater than some constant $\phi$.

Given this, can we compute a lowerbound $f(n)$ on the minimum distance between the points?

The short answer is: no, there is no such lower bound.

Let $p$ be a positive integer.
Let $\epsilon = \frac{1}{p}$.

Put points at coordinates $(i \epsilon, j \epsilon)$ for $i,j \in \{ 0 \dots p \}$, and at coordinates $(i \epsilon + \frac{\epsilon}{2}, j \epsilon + \frac{\epsilon}{2})$ for $i,j \in \{ 1 \dots p \}$.
You end up with $n = (p+1)^2 + p^2$ points, and a triangulation in which all triangles are both right and isosceles. So all angles are either $\frac{\pi}{2}$ or $\frac{\pi}{4}$, and the minimal distance between two points is $\frac{\epsilon}{\sqrt{2}}$.


Best communication complexity lower bound of disjointness It is well known that no deterministic two-party protocol can solve disjointness problem (DISJ) on $n$-bit inputs without sending $n+1$ bits in the worst case (see, e.g., the book by Kushilevitz and Nisan). For bounded-error randomized protocols, a lower bound of $\delta n$, for some constant $\delta$, has also been shown in a seminal paper by Razborov [Razborov92]. My question is:

  What is the best known explicit value of $\delta$ currently (both upper and lower bounds)?

Also, is there any belief on the actual value of $\delta$?

[Razborov92] Alexander A. Razborov: On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2): 385-390 (1992) doi:10.1016/0304-3975(92)90260-M

In a recent paper, Braverman, Garg, Pankratov, and Weinstein compute the value of $\delta$ to be exactly some constant around 0.4827, up to sublinear factors. This gives a tight bound on the communication complexity of disjointness.

The constant itself was found using a computer algebra system, and as far as I'm aware can't be expressed simply.


A mathematical problem in software watermarking I am wondering if there are any existing works/ideas that are related to the following problem. A solution of this problem can be probably useful in software watermarking.

Given,

Two sets $\mathcal{W}$ and $\mathcal{H}$ (whose sizes are typically between 10 and 50)
A bijection $f: \mathcal{W} \rightarrow \mathcal{H}$

The problem is to construct a function $\mathcal{F}$. The domain of $\mathcal{F}$ is the set of sequences of elements of $\mathcal{W}$, and the codomain is the set of sequences of elements of $\mathcal{H}$. The desired properties of $\mathcal{F}$ are given below.

Notation:
$S_i$ represent the $i^{th}$ element of sequence $S$.

Definition:
$\mathcal{F}$ behaves normally $\ $for a sequence $WS$ of length $N$ iff $\mathcal{F}(WS) = HS$, length of $HS$ is $N$, and $HS_i = f(WS_i)$ for $1 \leq i \leq N$.

Construct $\mathcal{F}$ and compute a sequence $P$ (of elements of $W$) of length $N$ such that:

1) $\mathcal{F}$ behaves normally for almost all sequences of elements of $W$

2) $\mathcal{F}$ and $P$ satisfy following constraints

$\ $  a) $\mathcal{F}(P) = Q$, length of $Q$ is $N$

$\ $  b) $Q_i = f(P_i)$ for $1 \leq i < N$  (i.e., $\mathcal{F}$ behaves normally for the $P$’s prefix of length $N-1$)

$\ $  c) $Q_N \neq f(P_N)$

$\ $  d) it is computationally hard to discover the sequence $P$ with the knowledge of $\mathcal{F}$'s implementation and the bijection $f$.

There is a straightforward solution, using known techniques for obfuscating point functions.

Background. First, go read the following papers:

Positive Results and Techniques for Obfuscation. Benjamin Lynn, Manoj Prabhakaran, Amit Sahai.  Eurocrypt 2004.
On Obfuscating Point Functions.  Hoeteck Wee.  STOC 2005.

Don't come back until you've read those papers, as my solution uses their scheme as a building block.  Short summary: "A point function is a Boolean function that assumes the value 1 at exactly one point."  A point function can be obfuscated in practice (e.g., in the random oracle model).

My solution. Choose the sequence $P$ randomly.  Define the auxiliary function $g$ by $g(P)=1$ and $g(P')=0$ for all other sequences $P'$ over $W$.  Note that $g$ is a point function.  Now let $\hat{g}$ be an obfuscation of $f$, e.g., using the techniques described above.  Choose $Q$ arbitrarily.   Finally, define $F$ as follows: on input $X$, $F$ first checks whether $\hat{g}(X)=1$, and if yes, outputs $Q$, otherwise it behaves normally (i.e., outputs $f(X_1),f(X_2),\dots,f(X_N)$.  This meets all of the requirements you identified.  You can modify this construction in a straightforward way to hide $Q$ as well, if you wish to.

Comment. I'm pretty skeptical whether this will be useful for building an obfuscation scheme that will be secure in practice; my suspicion is that it will not be useful.  You might be able to get some theoretical results, but I don't think those theoretical results will prove very useful in practice, because I expect there will be attacks that will work by violating the assumptions made in your security theorem  (e.g., the attacker will use dynamic analysis to find $P$, and then all security is lost).


Is there a set theoretic way to look at SQL? I have been learning about SQL and at times it feels like set theory.  A statement like SELECT * FROM myTable is like a set $\{ x: x \in \text{myTable} \}$.

A table could be defined as any subset of the Cartesian product.  We could define a table called zipcodes with a schema city STRING(30), state CHAR(2),  zip INTEGER(5)  then in set theory we could define the zipcodes stable as:
$$ zicodes \subseteq \text{cities} \times \text{states} \times \text{zips} \simeq \{a, \dots, Z\}^{30} \times \{a, \dots, Z\} \times \{1, \dots, 10^5\}$$
So any table is a subset of a cartesian product.

My theory has limitations, since you can't store all of $\mathbb{R}$ as a SQL database (e.g. by cantor diagonalization) since $|\mathbb{R}| > |\mathbb{Z}|$ in cardinality.

In any case, do any theories of SQL exist that compare it to set theory?

It is common wisdom that database field is firmly grounded in the two math disciplines: predicate logic and set theory. However, this is very fuzzy observation, and reality is more subtle.

The structure of the basic building block - relation - is described in set language, but that's about it. This is not really very insightful, because the whole mathematics is written in set language. The fact that probably caught your attention is that the foundation of SQL - relational algebra - has distinct Boolean flavor.

Please also note that SQL actually operates not with relations but multirelations which are bags(multisets) of tuples(rows). Therefore, its algebra is not a [boolean] algebra of sets. There were various attempts at rigorous theory of multirelations, with provenance semiring being the most recent development


Formalizing the "no formula for primes" intuition I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:

Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-bit primes.

Currently I believe the best algorithm has conjectured complexity $\tilde{O}(n^3)$: run the $\tilde{O}(n^2)$ Lucas-Lehmer test on $O(n)$ Mersenne numbers.  We could go from $n^3$ to $n^2$ using the same sample-and-check strategy if a faster $\tilde{O}(n)$ checking algorithm is found.  (This argument for the choice of 2 as exponent due to Paul Christiano.)

However, if a "formula for primes" existed, and was sufficiently simple, the fact that arithmetic is quasilinear means that we might get a quasilinear time prime generation algorithm, or $\tilde{O}(n)$.  Conjecturing that the minimum exponent is 2 roughly approximates "the best strategy is sample-and-check".

Two questions:

Is there any heuristic evidence beyond the algorithms discovered so far about the optimum primality testing exponent, or the optimal exponent for generating primes?
Are there other attempts at formalizing the "no formula for primes" intuition?

I should clarify that of course I know that settling the conjecture is hopeless: I’m looking for heuristics only.

[Certainly not a complete answer, but too long for a comment]

Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but here it's about whether there's a formula that's sufficiently simple that you could use it to help decide whether a given DFA accepts any primes.)

In another direction, given that your conjecture is about the difference between cubic and quadratic, it might be reasonable to think about whether the problem is complete for cubic time under sub-cubic reductions (see Vassilevska Williams & Williams). It looks tricky, or even unlikely, since it's so different from the other "cubic-complete" problems, like all-pairs shortest paths, triangle detection, etc., but could be worth considering nonetheless. Their framework was in the context of deterministic algorithms, but it shouldn't be too hard to adapt to randomized...


Permuting the columns of a 0/1-matrix to avoid short segments Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment short if its length is at most $\log n$. It is not difficult to show that under a random permutation of the columns, the number of short segments is at most $O(\log^4n)$. Can you design a deterministic $O(n)$ time algorithm that takes the positions of $n$ stars as an input and outputs a permutation of the columns such that the number of short segments is at most $O(n/\log n)$?

The algorithm below runs in time $O(n\log n)$, but not $O(n)$. On the other hand, it permutes the columns in such a way that there are only $O(\log^2n \cdot\log\log n)$ short segments in the end.

Let us at first describe $O(n\log n)$-time algorithm for the case when $n + 1$ is prime. Then we may identify columns $\{1, 2, \ldots, n\}$ with elements of $(\mathbb{F}_{n + 1})^*$. The idea is to consider permutations of the form $x\mapsto \gamma x$ for $\gamma\in(\mathbb{F}_{n + 1})^*$. We will show that at least one $\gamma$ is good for us and how to find such $\gamma$ in $O(n\log n)$ time.

We start by finding $x^{-1}$ for every $x\in(\mathbb{F}_{n + 1})^*$. For each $x$ this takes $O(\log n)$ time by Euclidean algorithm, in total $O(n\log n)$.

Then assume that positions of stars are
$$(a_1, b_1), \ldots, (a_n, b_n).$$
Let $L$ be the list of all $(i, j)$ such that $i\neq j$ and $a_i = a_j$ (pairs of stars which are from the same row). The size of $L$ is $O(t_1^2 + \ldots + t_n^2)$, where $t_i$ is the number of stars from the $i^{th}$ row. Since $t_i\le\log n$, we have
$$|L| = O(t_1^2 + \ldots + t_n^2) = O((t_1 + \ldots + t_n)\cdot \log n) = O(n\log n).$$

We then create an array $M$ of size $n$, where $M[\rho]$ is equal to the number of $(i, j)\in L$ s.t. $\rho = b_i - b_j \pmod{n + 1}$. Clearly, computing $M$ takes $O(|L|) =O(n\log n)$ time.

Then we define another array $W$ of size $n$. Namely, $W[\gamma]$ is defined as follows
$$W[\gamma] = \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho].$$

Now let us prove that $W[\gamma]$ is an upper bound on the number of short segments after permuting columns according to $x\mapsto \gamma x$. Indeed, the number of short segments is at most the number of $(i, j)\in L$ such that for some $u, v\in\{1, 2, \ldots, n\}, u\neq v, |u - v| \le \log n$ it holds that $\gamma b_i = u\pmod{n + 1}, \gamma b_j = v\pmod{n + 1}$. In turn, this is at most the number of $(i, j) \in L$ s.t. for some $k\in [-\log n, \log n], k\neq 0$ it holds that $\gamma(b_i - b_j) = k \pmod{n + 1}$. This is exactly $\sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho]$.

Now it only remains to note that
$$W[\gamma] =  \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} M[\gamma^{-1} k]$$
Here we use the fact  that $n + 1$ is prime. Since we have all $\gamma^{-1}$ precomputed, it takes only $O(n\log n)$ time to compute $W$.  On the other hand for fixed $k$ all $\gamma^{-1} k$ are different, i.e. $\sum\limits_{\gamma} W[\gamma] \le 2\log n \sum\limits_{\rho} M[\rho] = 2\log n \cdot |L| = O(n\log^2 n)$.   Hence there exists $\gamma$ such that $W[\gamma] = O(n\log^2 n/n) = O(\log^2 n)$. We find any such $\gamma$ and permute columns according to $x\mapsto \gamma x$.

The problem in general case is that now not all $\gamma$'s from $\mathbb{Z}_{n + 1}\setminus \{0\}$ are reversible. However, there are $\Omega(n/\log\log n)$ of them, so we start our algorithm by finding all reversible $\gamma\in\mathbb{Z}_{n + 1}\setminus \{0\}$  in $O(n\log n)$ time (once again, Euclidean algorithm helps). We then do exactly the same thing but only for reversible $\gamma$'s. In the end we will have a slightly worse upper bound on the smallest $W[\gamma]$, namely $O(\log^2(n)\log\log n)$ (because we take into account only $\Omega(n/\log\log n)$ of $\gamma$'s).


Seeking Scott's original LCF paper Is the following manuscript publically available?

  Dana Scott, 1969, A theory of computable functions of higher type. Unpublished seminar notes, 7 pages, University of Oxford.

There is a discussion of this paper in section 8.1.2, Types as sets, in Cardone & Hindley, 2006 History of Lambda-calculus and Combinatory Logic; additionally section 10.1, Domain theory, traces back to this manuscript some crucial order-theoretic insights.

Published as:

Scott, D. A Type-Theoretical Alternative to ISWIM, CUCH, OWHY.
   Theoretical Computer Science, vol. 121 (1993), pp. 411 - 440.

See also:

Scott, D. Some Reflections on Strachey and his Work. in: A Special Issue
   Dedicated to Christopher Strachey, edited by O. Danvy and
   C. Talcott.  Higer-Order and Symbolic Computation, vol. 13 (2000),
   pp. 103-114.

and:

Gordon D. Plotkin, Set-theoretical and other elementary models of the λ-calculus,
   Theoretical Computer Science, vol. 121 (1993), pp. 351-409.


What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$? What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?
What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{(n-n^\alpha)}poly(nm)$ time?

I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from Cody Murray and Ryan Williams' STOC 2018 paper.

In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $C$ on $n$ variables and the promise that either (a) $C$ is unsatisfiable, or (b) $C$ has at least $2^n/4$ satisfying assignments, determine which of (a) and (b) is the case. This problem is easily solved with randomness, so this hypothesis is perhaps more likely than a faster algorithm for Circuit Satisfiability.

Ryan has a very nice talk on this thread of work; a recording in two parts is available here and here.


Associative hash mixing Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths and the question of how it may be extended to the wider class of purely functional sequences based on trees.

The problem is the following: You want to test for almost certain structural equality in O(1) time by means of strong hashing. If the hash function is structurally recursive, i.e. hash (x:xs) = mix x (hash xs), then you can transparently cache hash values on lists and update them in O(1) time when an element is consed onto an existing list. Most algorithms for hashing lists are structurally recursive, so this approach is eminently usable in practice.

But suppose instead of singly-linked lists you have tree-based sequences that support concatenating two sequences of length O(n) in O(log n) time. For the hash caching to work here, the hash mixing function must be associative in order to respect the degrees of freedom a tree has in representing the same linear sequence. The mixer should take the hash values of the subtrees and calculate the hash value of the whole tree.

This is where I was six months ago when I spent a day mulling over and researching this problem. It seems to have received no attention in the literature on data structures. I did come across the Tillich-Zemor hashing algorithm from cryptography. It relies on 2x2 matrix multiplication (which is associative) where bits 0 and 1 correspond to the two generators of a subalgebra with entries in a Galois field.

My question is, what have I missed? There must be papers of relevance in both the literature on cryptography and data structures that I failed to find in my search. Any comments on this problem and possible venues to explore would be greatly appreciated.

Edit: I am interested in this question on both the soft and cryptographically strong ends of the spectrum. On the softer side it can be used for hash tables where collisions should be avoided but aren't catastrophic. On the stronger side it can be used for equality testing.

Added: After reading Per’s comments, I think that this answer is just a (poor) variation of the Tillich-Zemor hashing algorithm which is already mentioned in the question.  I withdraw this answer, but I leave it hoping that it (and the comments) may be informative for some readers.

Edit: An earlier revision of this answer suggested to use a monoid operation on [m], but as Per pointed out in a comment, it is desirable to use a group operation.

This answer is about building a hash function for hash tables which is easy to implement.  A provable guarantee on the quality is not expected.

Assuming that you already have a hash function for each element of a sequence to a finite set [m]={1, …, m}, how about interpreting each element of [m] as an element in a finite group G and using the group operation on G?  You can use any mapping from [m] to G, but it is desirable that the mapping be injective so that we do not lose the information in the hash value of each element.  It is also desirable that the group not be commutative so that the hash function can catch the difference in the order of the elements in a sequence.

I do not know much about finite groups which allow fast operations, but I guess that such groups are known in coding theory.  Using the symmetric group of order at least m may not be so bad.


The computational complexity of spectral norm of a matrix How hard is computing the spectral norm of a matrix? This paper says,

  ... it suffices to say that, except for few particular cases, the Matrix
  Norm problem is NP-hard.

I expected that the relevant chapter 2 would describe those exceptional cases but failed to find it.

Can anyone suggest a more definitive reference for computational complexity of spectral norm of a matrix?

The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\mathcal{P}_{2,1}$. For example, $\mathcal{P}_{\infty,1}$ (even restricted to positive semidefinite matrices) is a generalization of MAX CUT. Since $\|B'B\|_{\infty,1} = \|B\|_{\infty,2}^2$, $\mathcal{P}_{\infty,2}$ is also hard. Finally, $\mathcal{P}_{2,1}$ is as hard as $\mathcal{P}_{\infty,2}$ as part of the more general observation (proved in section 1.3.1) that $\mathcal{P}_{p,r}$ is as hard as $\mathcal{P}_{1/(1-1/r), 1/(1-1/p)}$.

The thesis goes on to prove that $\mathcal{P}_{p,r}$ is hard whenever $p > r$ - this is the chapter you were reading (chapter 2).

Section 1.3.1 described some easy cases: $\mathcal{P}_{1,\ast}$, the symmetric $\mathcal{P}_{\ast,\infty}$, and the case that MCH mentioned, $\mathcal{P}_{2,2}$. Section 1.3.3 covers some approximability results, several novel of which are described in section 1.4 and the remaining chapters.

The title of section 1.3.2 appears in the table of contents (page iii) - just a hint for next time.


Difference between Strict Consistency and Sequential Consistency I understand strict and sequential consistency independently fairly well.

Strict C basically enforces the actual order in which the instructions ran on the global clock.

Sequential Consistency basically enforces the order only on one processor.

I'm having trouble putting together some literature though.
http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html describes sequential  consistency as allowing for memory 'lag'. It may take time for a write to propagate across all processors. But when it does, it reaches all of them at once which is fine. Thus, the following is valid under Sequential Consistency

P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1

What concerns me now is the following processes, which is something like Dekker's algorithm.

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

This should surely NOT be possible under Sequential consistency ( http://portal.acm.org/citation.cfm?id=1787234.1787255 pg 2). There is no total order that can give this result.

But it makes sense from the idea that sequential consistency allows writes to propagate slowly and one thread may not have any idea as to what other processors are up to.

What am I missing here?

You are not missing anything :)

Dekker's algorithm will not be sequentially consistent on distributed shared memory hierarchy based multiprocessor but it is very much possible as the memory updates propagate not in step with local memory (cache) update but asynchronously through Cache Coherence protocols like MESI (Weaker memory model).

On a uni-processor on which Dekker's algorithm this is not the case and it will be strictly consistent.


What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties? More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and negative integers (but still sparsely).

I am not sure how hard this is. Clearly the permanent of a general matrix can be negative so it cannot be written as the permanent of a matrix with non-negative entries.

However, there may be some kind of way to re-represent the permanent of the general matrix in terms of other permanents.

That is, Per(A) = Per(A1) +/- Per(A2) +/- Per(A3) +/-... for some matrices A1,A2,A3, or something like that.

This is related to the problem of rerepresenting weighted graphs as non-weighted graphs through the connection of the permanent and cycle covers on the adjacency graph.

The problem of computing the permanent of general matrices can indeed be reduced to the problem of computing the permanent of 0-1 matrices. This was shown in the paper that introduced the complexity class #P in 1979 [1] (which also showed that the problem is #P-complete).

There's a nice article that covers this on Wikipedia, based on a simpler proof published later [2].

As you mentioned sparse matrices particularly you may wish to know that if the matrix is the biadjacency matrix of a planar graph then the permanent can be computed in polynomial-time using the FKT algorithm. This is a consequence of the permanent of the biadjacency matrix of a bipartite graph being equal to the weighted sum of perfect matchings, as explained here. There's a previous question related to this.

[1] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci.,
8:189-201, 1979. Available here.
[2] A. Ben-Dor and S. Halevi. Zero-one permanent is #P-complete, a simpler proof. Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pages 108–117, 1993. Available from the author's webpage here.


Lexicographically minimal topological sort of a labeled DAG Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and where we are asked to compute the lexicographically smallest topological sort of $G$ in terms of $\lambda$. More precisely, a topological sort of $G$ is an enumeration of $V$ as $\mathbf{v} = v_1, \ldots, v_n$, such that for all $i \neq j$, whenever there is a path from $v_i$ to $v_j$ in $G$, then we must have $i < j$. The label of such a topological sort is the sequence of elements of $S$ obtained as $\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$. The lexicographical order on such sequences (which all have length $|V|$) is defined as $\mathbf{l} <_{\text{LEX}} \mathbf{l'}$ iff there is some position $i$ such that $l_i <_L l_i'$ and $l_j = l'_j$ for all $j < i$. Pay attention to the fact that each label in $S$ can be assigned to multiple vertices in $V$ (otherwise the problem is trivial).

This problem can be stated either in a computation variant ("compute the lexicographically minimal topological sort") or in a decision variant ("is this input word the minimal topological sort?"). My question is, what is the complexity of this problem? Is it in PTIME (or in FP, for the computation variant) or is it NP-hard? If the general problem is NP-hard, I am also interested about the version where the set $S$ of possible labels is fixed in advance (i.e., there are only a constant number of possible labels).

Remarks:

Here is a small real-world example to motivate the problem. We can see the DAG as representing tasks of a project (with a dependency relationship between them) and the labels are integers representing the number of days that each task takes. To finish the project, it will take me the same total amount of time no matter the order I choose for the tasks. However, I would like to impress my boss, and to do this I want to finish as many tasks as possible as fast as possible (in a greedy manner, even if it means being very slow at the end because the harder tasks remain). Choosing the lexicographically minimal order optimises the following criterion: I want to choose an order $o$ such that there is no other order $o'$ and a number of days $n$ where after $n$ days I would have finished more tasks with order $o'$ than with order $o$ (i.e., if my boss looks at time $n$, I give a better impression with $o'$), but for all $m < n$ I have finished no less tasks with order $o'$ than with order $o$.

To give some insight about the problem: I already know from previous answers that the following related problem is hard: "is there a topological sort which achieves the following sequence"? However, the fact here that I want a sequence which is minimal for this lexicographic order seems to constrain a lot the possible topological orders that may achieve it (in particular the reductions in those other answers no longer seem to work). Intuitively, there are much less situations where we have a choice to make.

Note that there seems to be interesting rephrasings of the problems in terms of set cover (when restricting the problem to DAGs that are bipartite, i.e., have height two): given a set of sets, enumerate them in a order $S_1, \ldots, S_n$ that minimises lexicographically the sequence $|S_1|$, $|S_2 \backslash S_1|$, $|S_3 \backslash (S_1 \cup S_2)|$, $\ldots$, $|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$. The problem can also be rephrased on undirected graphs (progressively expand a connected area of the graph following the order that minimizes the lexicographic sequence of the uncovered labels). However, because of the fact that the sequence has to be greedy at all times by definition of the lexicographic order, I can't get reductions (e.g., of Steiner tree) to work.

Thanks in advance for your ideas!

With multiple copies of the same label allowed, the problem is NP-hard, via a reduction from cliques in graphs. Given a graph $G$ in which you want to find a $k$-clique, make a DAG with a source vertex for each vertex of $G$, a sink vertex for each edge of $G$, and a directed edge $xy$ whenever $x$ is a vertex of $G$ that forms an endpoint of edge $y$. Give the vertices of $G$ the label value $1$ and the edges of $G$ the label value $0$.

Then, there is a $k$-clique in $G$ if and only if the lexicographically first topological order forms a sequence of $k$ $1$'s and $\tbinom{k}{2}$ $0$'s, with $i-1$ $0$'s following the $i$th $1$. E.g. a six-vertex clique would be represented by the sequence $110100100010000100000$. This is the lexicographically smallest sequence that could possibly begin a topological ordering of a labeled DAG given by this construction (replacing any of the $1$'s by $0$'s would give a sequence with more edges than could be found in a simple graph with that many vertices) and it can only be the beginning of a topological ordering when $G$ contains the desired clique.


Convolution without FFT What is the best upper and lower bound known for convolution without FFT?

Is FFT proven to be essential for time complexity reduction?
Is cancellation essential as well?

Take a look at Toom-Cook multiplication and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon>0$.


Running multiple rounds of a BQP computation, without multiple measurements? BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

Just like BPP, the choice of 1/3 in the definition is arbitrary because we could just have a "higher level" algorithm that runs the "basic algorithm" many times and take a majority vote to achieve higher probability of correctness.

I can imagine this as:

initialize qbits based on the input of length n
apply polynomial(n) quantum gates
measure output qbit
repeat steps 1-3, K times and report the majority measurement from step 3

Essentially, having a classical computing loop call a quantum routine K times.

Is it possible instead to somehow do ALL the computation on the quantum computer, and only make a single measurement at the end which is equivalent to this?

I'd hope for something like:

initialize qbits based on the input of length n
apply K * polynomial(n) quantum gates
measure just a single output qbit

Or is making multiple measurements absolutely necessary to the computational power here?

The principle of deferred measurement (see https://en.wikipedia.org/wiki/Deferred_Measurement_Principle) tells us that measurements in the middle of a quantum computation can be simulated by using additional quantum gates instead. In particular, instead of measuring a qubit, we can apply a CNOT gate to that qubit and another qubit (which is used only at this point of the computation).


Complexity of Parallelogram Range Minimum Query Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs?

More formally, answering the query

$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$

In terms of preprocessing, and answering the query where the array is static

This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ_P(a, b, c, d)$ on $G$.

Now run your favorite 2D-RMQ algorithm such as this. Perhaps you want to be very conservative with the extra space used though. In that case I suspect unpacking your favorite result will show that it helps to avoid writing $H$ down, and instead use an $O(1)$ function to produce values of $H$ by lookup into $G$.


How is Lambda Calculus a specific type of Term Writing system? Now we can see that Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda Calculus.

Now when John McCarthy created Lisp - he based it on the Lambda Calculus. This is by his own admission when he published "Recursive functions of symbolic expressions and their computation by machine, Part I". You can read it here.

Now we know that at the core of Mathematica is a Lisp-like system, but instead of being based purely on the Lambda Calculus, it is based on a term-rewriting system.

Here the author states state:

  Mathematica is fundamentally a term rewriting system... a more general concept than the Lambda Calculus behind Lisp.

It seems that the Lambda Calculus is a small part of a much more general category. (Quite eye-opening as a thought this was more of a foundational concept). I'm trying to read more about this to get some perspective on it.

My question is: How is Lambda Calculus a specific type of Term Writing system?

The answer is it depends what you mean by Term Rewrite System.

When it was introduced, the concept of Term Rewrite Systems, or TRSes, described what is now called first order TRSes, which is simply a set of computation rules of the form

$$ l\rightarrow r $$

where $l$ and $r$ are first order terms of the form

$$ t :=\ x\ \mid\ f(t_1,\ldots,t_n) $$

where $x$ is a variable and $f$ is a function symbol taken from some arbitrary, but fixed set $\Sigma$, called the signature, which also fixes a number of arguments for each $f\in\Sigma$.

There are a couple of common restrictions imposed on rules, e.g. $\mathrm{Var}(r)\subseteq\mathrm{Var}(l)$ but we don't need to go into them here.

With this definition, the usual lambda calculus, with the $\beta$ rule:
$$ (\lambda x. t)\ u \rightarrow t[u/x]$$
cannot be expressed, as the constructor "$\lambda$" binds the occurrence of $x$ in $t$ (application is fine though). One possible solution, and one which is older than the theory of rewriting systems itself, is to turn each $\lambda$ term into another kind of term, which does not involve binding.

One way is the famous $SK$ combinator calculus, which is a rewrite rule with the signature $\Sigma=\{S,\ K, \mathrm{app}\}$ and the rules
$$ \mathrm{app}(\mathrm{app}(K,x),y)\rightarrow x$$
and
$$\mathrm{app}(\mathrm{app}(\mathrm{app}(S, x), y), z)\rightarrow \mathrm{app}(\mathrm{app}(x, z),\mathrm{app}(y, z)) $$

There is another, more intuitive encoding which involves lambda terms with de Bruijn indices and explicit substitutions, but I won't go into it here.

Despite the first order encodings, it became clear that the technical issues with the reduction behavior of the $\lambda$ calculus were better addressed by extending the notion of TRS to include constructors with binders. This is often referred to by the term Higher Order Rewrite Systems. Terms are now taken of the form

$$ t\ :=\ x(t_1,\ldots, t_n)\ \mid\ f(x^1_1\ldots x^1_{i_1}.t_1,\ldots,x^n_1\ldots x^n_{i_n}.t_n) $$

Where again $f\in\Sigma$, but now each $x^i_j$ is bound in $t_i$. Signatures need to specify how many variables are bound by each argument. Now we can write $\mathrm{abs}(x.t)$ for the term representing $\lambda x.t$. With a little work, you can define appropriate notions of substitution.

Here there is less consensus about what constitutes a rewrite rule. One issue is that we want rewriting to be decidable, and so it needs to be decidable whether a left hand side matches a term. But this is usually taken to be modulo $\beta\eta$ which is believed to be decidable, but with only extremely complex and slow algorithms (and just $\beta$ is undecidable!).

Therefore left-hand sides are restricted to be in some nice subset, often the "Miller patterns". A number of results for the first-order case generalize, though there are a few nasty surprises.

It's also common to just take first order systems, and simply add $\lambda$ and application to the term structure, along with ad hoc $\beta$ and $\eta$ reductions. This yields rather reasonable systems, at the cost of (some) generality.

Of course the usual $\lambda$ calculus can be directly written in these systems. For example the $\beta$ rule:

$$\mathrm{app}(\mathrm{abs}(x.y(x)),z)\rightarrow y(z) $$

A pretty decent overview of the definitions and basic results is given by Nipkow and Prehofer here.


Reference request: Shortest homotopic curve via vertex releases Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic to $C$ if it has the same endpoints as $C$ and can be obtained from $C$ by modifying it continuously, without crossing any obstacle and without moving the endpoints. For curves the definition is the same except that there is no endpoint requirement.)

Here is a simple algorithm for finding $D$. Is there any reference to it in the literature?

Call a path vertex $v$ "unstable" if it does not touch any obstacle, or if it touches an obstacle but the obstacle lies on the side of $v$ at which the angle is larger than 180 degrees.

An unstable vertex can be "released" resulting in a shorter path, as follows: Let $v$ be an unstable vertex, and let $u$, $w$ be the previous and next vertices of $C$. Let $\Delta$ be the triangle $uvw$, and let $S$ be the set of obstacle vertices contained in $\Delta$. Let $u, z_1, \ldots, z_k, w$ be the sequence of vertices of the convex hull of $S\setminus\{v\}$ in order. Then we replace $v$ by $z_1, \ldots, z_k$. The new vertices $z_i$ will necessarily be stable, but $u$ and $w$ might change from stable to unstable or vice versa.

So then the algorithm is: As long as there is an unstable vertex, pick an arbitrary unstable vertex and release it.

This works also for self-intersecting paths or curves with no problem.

If we allow point obstacles, then we also need to keep information of the "wrap" angle of the curve around each obstacle point. Then the curve is unstable if and only if the wrap angle is between -180 and 180 degrees.

Is there any mention in the literature of this simple algorithm?

The standard approach (which might be more efficient, though perhaps more cumbersome) uses a "funnel", and involves triangulating the empty space. See for example these course notes by Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf

[Added: For the record, this algorithm was found in joint work with Sergey Avvakumov.]

This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm.

I'm not aware of any exposition of your simple algorithm in the literature.  This is actually a little surprising, given how many times the basic funnel algorithm has been rediscovered [Tompa, STOC 1980; Chazelle, FOCS 1982; Lee and Preparata, Networks 1984; Leiserson and Maley, STOC 1985].

Both your algorithm and the Hershberger-Snoeyink algorithm are examples of a folklore technique called curve shortening.  At a high level: If the curve can be shortened by a continuous motion, shorten the curve by a continuous motion.  The details are surprisingly irrelevant; you can shorten either by local discrete moves (like your algorithm) or by a global continuous deformation (as if the path were made of elastic).  In any space where curvature is nowhere positive, there is a unique shortest path in every homotopy class [Gromov].  Thus, assuming your shortening process actually converges, it necessarily converges to the unique shortest path homotopic to the given path.

This is exactly why the Hershberger-Snoeyink funnel algorithm works.  Each step in reducing the crossing sequence is shortening a subpath of the path to a line segment, and each step in the funnel algorithm is equivalent to shortening the path inside the next triangle of the sleeve.  (See my notes linked by OP for definitions.)

In particular, the sides of the funnel play exactly the same role as your convex hulls.  Moreover, the standard algorithm for extending the funnel through one triangle is identical to one iteration of the Graham scan convex hull algorithm, or Andrews' equivalent sort-and-repair algorithm, or the equivalent plane-sweep algorithm.

So while I agree that your algorithm is more elementary than Hershberger-Snoeyink, I'm not convinced that it's actually easier to implement.

(One thing that may not be clear in my notes is that the Hershberger-Snoeyink algorithm doesn't actually need to construct the sleeve; the funnel can be guided directly by the reduced crossing sequence.  The only point of the sleeve is to help visualize the algorithm.)

One advantage of the Hershberger-Snoeyink algorithm is that it has a single $O(n\log n)$-time preprocessing phase to compute a global triangulation, after which the running time is proportional the number of crossings, so the overall worst-case running time is $O(n\log n + kn)$, where $k$ is the complexity of the input path.  The analysis is straightforward.

I strongly suspect that the vertex-release algorithm can be polished to have the same running time, with the right combination of preprocessing, data structures, and choice of which unstable vertex to release at each iteration, but it's certainly not straightforward.  Naively, your algorithm needs to compute the convex hull of a subset of the points for each vertex release, which takes $O(n \log n)$ time, and the number of vertex releases could be as high as $\Omega(kn)$.  Suppose we want to simplify the black path in the following example:

For simplicity, suppose we repeatedly release the first unstable vertex on the black path.  The first release creates $\Omega(n)$ new path vertices; the next $\Omega(n)$ releases delete those vertices; and these releases remove one "tooth" from the black path.  (Yes, you can reduce the number of releases by choosing them more intelligently, but that complicates the algorithm.)

So assuming this $\Omega(kn)$ lower bound is tight, a naive implementation of this algorithm runs in $O(kn^2\log n)$ time.  You can remove a $O(\log n)$ factor by pre-sorting the points; then each step can be performed in $O(n)$ time via Graham's scan.

You might try speeding up the algorithm by releasing the vertex that makes "the most progress", but this is uncomfortably close to 2d simplex range searching, so this "improvement" could easily make the algorithm slower, not faster.  For example, deciding whether there is a "trivial" vertex release, which decreases the complexity of the path, is at least as hard as Hopcroft's point-line incidence problem, and therefore is unlikely to be solvable in $o(n^{4/3})$ time.  See [Cabello et al. 2004] and [Bespanyatnikh 2003] for similar hardness results and matching theoretical improvements to Hershberger-Snoeyink.

tl;dr: I would cite "folklore", at least for correctness.


Graph sparsification and eigenspaces I am currently trying to understand whether I can make some claims about the relation between eigenspaces of a sparsifier and the original matrix. In this context, let me first define a couple of entities.

Definition 1: Partial Ordering Among Matrices:
We say that two commuting matrix $\mathbf A,\mathbf B$ have a partial ordering $\mathbf A \preceq \mathbf B$ if the matrix $\mathbf B - \mathbf A$ is positive semidefinite, i.e. $\vec x^T (\mathbf B - \mathbf A) \vec x \geq 0 $ for all non-zero $\vec x$.
Now with this definition we can define an $\epsilon$-approximation of the graph to be $(1- \epsilon) \mathbf B \preceq \mathbf A \preceq (1+\epsilon) \mathbf B$, i.e. $\mathbf B$ is an $\epsilon$-approximation of $\mathbf A$ (definitions vary here slightly).

Spielman and Peng famously gave the first algorithm to spectrally sparsify a graph, i.e. given a graph $G=(V,E)$, the algorithm returns a graph $H$ such that $H$ is an $\epsilon$ spectral approximation of $G$, with average degree $\mathcal{O}(1/\epsilon^2)$ (~ sparsity).
These spectral sparsifiers can then in turn be used to solve e.g. Laplacian systems in nearly linear time (nowadays I believe linear time was achieved by Joannis Koutis et al., or others around M. B. Cohen).

Now the question I have is the following:
Usually when comparing the solution of linear systems, instead of inverting the matrix, some sort or polynomial is used to approximate the inverse. Hence, the eigenspaces of the (pseudo-)inverse and the polynomial is the same and we can easily show that the eigenvalues of the polynomial and the inverse are all $\epsilon$-close. How does this change for a general case, wehere $\mathbf B$ is a spectral sparsifier of $\mathbf A$? Can I say anything about the relationship between eigenspaces?

My idea was to use the eigenvalue decomposition of both matrices and project the basis of $\mathbf B$ into the basis of $\mathbf A$. However this doesn't seem to give me a more qualitative understanding. Are there any ways to bound the differences eigenspaces? It seems that in the worst case the sum of plus and minus terms could cancel out each other allowing for quite large ranges of distances (from the projections) between the actual eigenvectors of $\mathbf A$ and $\mathbf B$?

I am not sure how you measure distance between eigenspaces, but I do not think you can say anything non-trivial here without some assumption that the eigenvalues of $A$ are separated. For example, let $u$ and $v$ be two arbitrary unit vectors, and define $A = I + \varepsilon uu^\intercal$ and $B = I + \varepsilon vv^\intercal$. Then $(1-\varepsilon)B \preceq A \preceq (1+\varepsilon)B$. However, the leading eigenvector of $A$ is $u$ and the leading eigenvector of $B$ is $v$, and, since they were arbitrary, they can be as far apart as you want.


Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph? I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph.

Input: Given a graph G with non-negative vertex weights and valid but not important to be optimal coloring of G.
Task: Find the Maximum weight Independent Set.

Note that this problem is NP-hard (for k>2 where k is the number of coloring) [see here]

in Hochbaum's paper in 1996 "Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and related problems" in Theorem 3.2 he give an (2/k)-approximation algorithm for this problem.
Now, my question is: Is there any new results regarding this problem? Is there any lower bound for this problem? Of course in general for simple graph without coloring to find Independent Set, there is no constant factor unless P=NP. Now, Is it true that we cannot have a constant factor for this coloring case? anything related to this problem, it would be nice to mention it here.
Thank you!

If you have a graph with maximum degree $\Delta$, then the greedy algorithm finds a coloring with $\Delta+1$ colors, so for $k = \Delta+1$ the assumption that you are given a proper $k$-coloring does not change the complexity of the problem. It is known that independent set is NP-hard to approximate within factor $\Delta^{1 - o(1)}$, and Unique Games-hard to approximate within factor $\frac{\Delta}{O(\log^2\Delta)}$, which, for $k=\Delta$ is within a $\log \Delta$ factor from the upper bound you cite. (I prefer to write approximation factors as bigger than 1, so I am thinking of the upper bound you cite as $\frac{k}{2}$.)

However, it's still interesting to close these logarithmic gaps. This paper by Bansal may contain useful ideas.


Base-k representations of the co-domain of a polynomial - is it context-free? In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open:

Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for all $n \in \mathbb{N}$. Prove or disprove that the language of the base-k representations of all integers in $\{p(n) \mid n \geqslant 0\}$ is context-free if and only if the degree of $p$ is $\leqslant 1$.

What's its status now (as for Oct 2018)? Is it proven? What about some special cases?

Of course $k \geq 2$ here.

There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.

As far as I know, the problem is still open.  One direction of the implication is easy, of course.


Is there a non-deterministic version of the complexity class PP? From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)

Edit: Perhaps I phrased the question poorly: I was thinking more along the lines of BPP's relation to MA? Is there an equivalent version of an interactive proof system where Merlin needs only convince Arthur with probability >1/2?

PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $\leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $\geq 2/3$ and $\leq 1/3$ while RP corresponds to $\geq 1/2$ and $0$.

So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.


Consequences of Complete problems for NP intersects coNP What are the consequences of having complete problems in $NP\cap coNP$?

This is a (wide) open problem; as in, we know almost nothing. Specifically, because of the trickiness in proving $NP \cap coNP$-complete problems, we need very different proof techniques than currently exist. As such, a discussion of consequences should reasonably include a tangent on "What would it mean to have such powerful, new proof techniques?"

For a relatively recent discussion of the topic, there is David Johnson's 26th NP-Completeness column in the ACM Transactions on Algorithms from 2007 (PDF). Allow me to paraphrase some of what David says regarding the question of proving $NP \cap coNP$-complete problems' existence and add my thoughts:

Currently, we only have "weak," natural candidates for membership in $NP \cap coNP - P$ in the sense that the strongest evidence for their membership is that we haven't managed to find a polynomial time algorithm for them yet. He lists a couple candidates: SMALL FACTOR, SIMPLE STOCHASTIC GAME, and MEAN PAYOFF GAME. Some of the extra "weirdness" of these problems comes from the best heuristic run times for solving them, e.g. SMALL FACTOR, aka INTEGER FACTOR $\le k$, has a randomized time complexity of $poly(n) 2^{\sqrt{k log(k)}}$. (If complete problems exist in $NP \cap coNP - P$, then is such sub-exponential (neither purely exponential, nor quite polynomial) runtime endemic of the class?)

So specifically, we would want to prove something like: problem A is only in $P$ iff $NP \cap coNP = P$, i.e. a completeness result like Cook's theorem for 3SAT and $NP$. For $NP$, such proofs universally involve polynomial-time reductions (and fix your favorite, additional restrictions, e.g. Cook-reductions, Karp-reductions). As a result, under polynomial-time reduction techniques, it must be the case that there exists a polynomial-time recognizable representation of the class. For $NP$, we can use non-deterministic Turing machines that halt within a polynomial, $p(|x|)$, number of steps. As David points out, we have similar representations for other classes (where the status is more clear) such as $PSPACE$ and #$P$.

The difficulty, however, with providing a similar representation for $NP \cap coNP$ is that the "natural" analog allows us to embed the Halting Problem within the representation and is therefore undecidable. That is, consider the following attempt to represent $NP \cap coNP$ with two non-deterministic Turing machines that, purportedly, recognize complementary languages:

Question: Does a Turing Machine $M^*$ halt on input $x \in {0,1}^n$?

Construct two linear-time Turing machines $M_1$ and $M_2$ as follows. On input $y$, $M_1$ reads the input and always accepts. $M_2$ always rejects unless $|y| \ge |x|$ and $M^*$ accepts $x$ in steps $\le |y|$.

Therefore, $M_1$ and $M_2$ accept complementary languages iff $M^*$ does not halt on input $x$. Therefore, by contradiction, deciding if two polynomial-time Turing machines accept complementary languages is undecidable.

So, the "natural" representation of $NP \cap coNP$ problems is not polynomial-time recognizable. The question remains: How do you represent $NP \cap coNP$ problems such that they are polynomial-time recognizable?

There has been no significant work done on this issue, but its successful resolution is necessary to prove completeness in $NP \cap coNP$. Hence, I claim that the existence of a proof technique that can resolve the completeness of $NP \cap coNP$ will be the bigger story here -- not the "automatic" results of $NP \cap coNP$-complete problems (e.g. complexity classes, perhaps, collapsing) that we are already aware of (or rather, will be aware of, hypothetically in the future).


Relating univalence for a theory of cateogries to the skeleton concept Say I work in homotopy type theory and my sole objects of study are conventional categories.

Equivalences here are given by functors $F:{\bf D}\longrightarrow{\bf C}$ and  $G:{\bf C}\longrightarrow{\bf D}$ which provide equivalences of categories ${\bf C} \simeq {\bf D}$. There exist natural isomorphisms $\alpha:\mathrm{nat}(FG,1_{\bf C})$ and $\beta:\mathrm{nat}(GF,1_{\bf D})$ so that this functor and "inverse" functor are transformed to unit functor.

Now univalence relates equivalences to the identity type ${\bf C}={\bf D}$ of the intentional type theory I have chosen to talk about categories. Since I only deal with categories and those are equivalent if they have isomorphic skeletons, I wonder if I can express the univalence axiom in terms of passing to the skeleton of the categories.

Or, otherwise, can I define the identity type, i.e. the syntactic expression
${\bf C}={\bf D}:=\dots$
in a way which essentially says "there is a skeleton (or isomorphi) and ${\bf C}$ and ${\bf D}$ are both equivalent to it."?

(In the above I try to interpret the type theory in terms of concepts which are easier to define - the category theoretical notions. I think about this because morally, it seems to me that the axiom "corrects" intentional type theory by hard-coding the principle of equivalence, which is already a natural part of the formulation of category theoretical statements, e.g. specifying objects only in terms universal properties.)

I refer you to Chapter 9 of the HoTT book. In particular, a category is defined in such a way that isomorphic objects are equal, see Definition 9.1.6. As Example 9.1.15 points out, there really isn't a reasonable notion of "skeletality" in HoTT. This is so because equality is so weak that it already means "isomorphic".

Furthermore, Theorem 9.4.16 says

  Theorem 9.4.16: If $A$ and $B$ are categories then the function $$(A = B) \to (A \simeq B)$$ (defined by induction on the identity functor) is an equivalence of types.

The theorem tells us that the Univalence Axiom gives us a sort of cateory theorist's dream: equivalent categories are equal.

You ask whether you can reduce the Univalence axiom to a statement about categories. Attempts using skeletons won't work because there isn't a good way to say "skeletal". We could ask whether Theorem 9.4.16 implies the Univalence axiom. This is not going to be the case, as far as I can see, because a category has a $1$-type (groupoid) of objects and a $0$-type (set) of morphisms, so theorem 9.4.16 amounts to something like the Univalence axiom for 1-types, only.


Is there an equivalent to VC-dimension for density estimation as opposed to classification? VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute the capacity of a mixture of N Gaussians, etc?  And if so, are there corresponding theorems showing that this capacity-measure can be used to bound the generalization error for density estimation, or used for structural risk minimization (analogous to the classification setting)?
I did find this article which seems like it might come pretty close to answering my question, since they apply structural risk minimization (SRM) to gaussian mixture models, and it looks like they estimate the capacity using "annealed entropy" applied to a class of threshold-based indicator functions associated with the log-likelihood function. However, they don't provide references to theorems/bounds to show whether this is a principled way to assess the capacity of a probability density, but perhaps there is some known theorem that justifies this approach which they assume the reader already knows about?  They reference Vapnik's book for more details on annealed entropy.
Also, my understanding is that fat-shattering or pseudo-dimension can be used as a generalization of VC-dimension to the regression context, but I'm unclear whether these are applicable to density estimation.  And it looks like the paper linked above used annealed entropy rather than these regression-based capacity measures.

For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to estimate a distribution over $d$ in $\ell_1$ is equivalent to agnostically PAC-learning the concept class $2^{[d]}$).
For discrete distributions with infinite support, no PAC-type result can be given. Perhaps somewhat surprisingly, a fully empirical (and nearly optimal!) sample-dependent bound on the $\ell_1$ distance between the empirical and true distributions can be given, see:
https://arxiv.org/abs/2004.12680
(to appear in NIPS 2020).
For continuous distributions, the situation is more subtle. You basically can't estimate anything without some absolute continuity and smoothness assumptions; see, for example the impossibility results:
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=139691
https://www.sciencedirect.com/science/article/abs/pii/S0167715298002466
https://www.jstor.org/stable/2242068?seq=1
What's typically done is that we define a class of distributions with certain smoothness properties (Lipschitz, Hölder, Sobolev, Besov) and then design an algorithm that achieves a certain rate for this class, and then argue that no algorithm can achieve a better rate (making our algorithm "minimax" for that class).


Densest k subgraph problem for outerplanar graphs? The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$.

Does anyone know if there exists a polynomial-time algorithm for this problem under the restriction that $G$ is outerplanar? (Note: I am specifically asking for an algorithm, not a PTAS, and I want $G$ to be outerplanar, not $b$-outerplanar for some $b > 1$).

It can be solved in linear time in an even more general class of graphs: As shown in

N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V.T. Paschos
Exact and approximation algorithms for densest $k$-subgraph
WALCOM’13, LNCS, vol. 7748, Springer-Verlag (2013), pp. 114-125

the Densest-$k$-Subgraph problem can be solved in $O(2^{\mathrm{tw}(G)}\cdot k \cdot ((\mathrm{tw}(G)^2)+k)\cdot |X|)$ time when a tree decomposition $(X,T)$ of the input graph $G$ is given. Since outerplanar graphs have treewidth at most two, the Densest-$k$-Subgraph can be solved in $O(k^2 n)$ time on outerplanar graphs with $n$ vertices.


Is length uniform AC0 computable? Consider the following problem:

Input: A binary string $w$.
Output: $|w|$ as a binary number.

Is it possible to compute this
in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$
(or equivalently in $\mathsf{AltTime}(O(1),O(\lg n))$ or $\mathsf{FO}$)?

Like Emil says, the answer is yes, because the length (in binary) of the input string is actually computable by a deterministic logtime Turing machine, so is a fortiori in $\mathsf{FO}$.

You may find this stated as Lemma 13 of Buss's The Boolean formula value problem is in ALOGTIME.  The idea, attributed to Dowd, is to use the query tape to do binary search (under the convention that the machine gets an "out of range" response if the query tape contains a binary number exceeding the length of the input).  I cut-and-paste the proof for quick reference (the number $n$ referenced in the proof is the length of the input, i.e., the desired output; the "index tape" is what Emil and I called query tape):

  The [...] Turing machine proceeds as follows. First determine the least value of $i$ such that $n < 2^i$: this is easily done in $O(\log n)$ time since we assume that the index tape and its tape head are unaffected when the input tape is accessed. Once the value $2^i$ is obtained, written on the [index] tape, it is now easy to do a binary search to determine the value of $n$. Finally the index tape is copied to the output tape.

(NB: the paper actually says "Once the value $2^i$ is obtained, written on the input tape", etc., but it must be a typo, the computation described is obviously done by writing on the index/query tape. Besides, the input tape is usually read-only in this setting).


What's the strict definition of random coins in streaming algorithm? I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again later? Or it serves a random source that once you look at it, you will get a random bit?

Sometimes it makes difference on the space when the algorithm have to store the random bits in memory and look at it later. Or, are they just equivalent?

If you want something more formal, you can think of a streaming algorithm as a Turing machine with read-once random bits tape and working tapes whose total size is polylogarithmically bounded. So, you can store and reuse random bits, as long as you don't exceed your polylog memory bound.

From algorithms design perspective, designing and even understanding a streaming algorithm is usually a two-step process. First think of the streaming algorithm as a RAM that can magically reuse random bits, i.e. has access to a random oracle. Actually there are some papers that do propose algorithms in this random oracle model. But usually, the next step is to try to make the algorithm work with hash families with bounded independence rather than a true random oracle. The seed for such families is logarithmic in size, so you can afford to store it. For some fine examples of this, just check out the classical paper of Alon, Matias and Szegedy. Another, heavier hammer to use is Nisan's pseudorandom number generator, which also allows reducing the number of random bits needed to be stored down to polylogarithmic (but larger than you usually get from bounded independence). For an example of using Nisan's generator, look at Indyk's use of the Cauchy distribution to approximate the $\ell_1$-norm of a stream. Both papers are classic and good read.

Refs:
AMS: www.tau.ac.il/~nogaa/PDFS/amsz4.pdf

Indyk: people.csail.mit.edu/indyk/stream.ps


Can Hoare logic be used when objects are created or deleted? Hoare logic can be used for proving program correctness (e.g. for deriving correctness statements for the whole program from the statements for the individual commands or constructions; good summary is http://www.cis.upenn.edu/~bcpierce/sf/Hoare.html). The question is - is there any line of research where Hoare-style reasoning can be made for programs that creates and deletes objects.

One thought can be that this reasoning can be simulated by defining large pool of objects which have (for the purposes of correctness analysis) additional state attribute with values from the enumeration {not-created, created, destroyed}. But I guess that better approach should exist.

Are there any references or keywords for furher search into this matter.

There is a lot of work on Hoare Logic for object oriented programs, and for reasoning about memory allocation and deallocation. Some starting points:

A Syntax-Directed Hoare Logic for Object-Oriented Programming Concepts
Separation Logic, does not target OO-languages specifically but applies to the more fundamental problem of reasoning about heap-allocated data.
jStar: Bringing separation logic to Java


Reference Request: Error correction code for a random projection I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length.

I'm quite sure that this subject is well researched, and all I need is the correct search term.

I think the term is deletion channel. As the Wikipedia article says, this "should not be confused with the binary erasure channel".


How do you initialize your seed in the preferential attachment model? Suppose that we seed our network with $m$ vertices. Suppose that at each step we add a vertex and c edges adjacent to that vertex.

Should these initial $m$ vertices have no edges at the start of the growth procedure? Should they be an $m$-clique? Should they form a cycle?

It seems that in Barabasi and Albert's model, there are no edges. The problem here is that each vertex in the seed will have probability 0 of being selected as an endpoint of a new edge.

As you noted, any vertex with degree $0$ will have zero probability of being selected for attachment, and thus will always remain disconnected. Thus, only vertices of degree $1$ or higher matter in the initial network. In an experimental setting, it doesn't matter what connectivity you pick for your initial $m$ vertices (beyond the non-zero degree, constraint) since the network starts to forget its initial conditions pretty quickly (especially if all the initial vertices have the same degree). The two most popular implementations in practice are:

$1$ vertex connected to $m$ other vertices. This creates a distinguished vertex to start with (the high-degree vertex has a much higher chance of becoming a hub than the others), but otherwise the network is very typical.
$m + 1$ fully connected vertices. This creates a balance between any vertices being biased to become a hub, but has the unfortunate effect of artificially increasing the clustering coefficient of your network when it is young. This usually takes longer for the network to forget.

If you want more exact analytic results on the BA model, than you can't rely on the original heuristic arguments given in the Science paper, and I recommend looking at these lecture notes for a formal treatement. To prove things about the BA model, usually self-loops and multiple edges are allowed. In that case the network can be initialized as one vertex with $m$ self-loops.


A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise Consider the following definition:

  A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its tape.

But even allowing additional working tapes does not change the class of herey defined computable numbers. But does this definition makes sense? How can anybode read off one digit of $x$, as we cannot be sure that it is definite, i.e. it could be changed infinitely often in the run of the machine. So the result is just correct if we "wait an infinite amount" of time. But how to formalize this?

This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result in the usual computable numbers, or you're trying to surpass that.

First we have Turing's definition of computable real number, and it is the one others have been commenting on: a real number $x \in \mathbb{R}$ is said to be computable if any one of the following holds:

(Calculation fo approximations) There is a Turing machine $M$ which on input $n$ terminates outputs a pair of integers $(a, b)$ such that $|x - a/b| < 2^{-n}$.
(Calculation of digits) There exists a Turing machine $M$ which runs forever and writes out the digits of $x$ on an infinite write-once tape. That is, once it writes a digit, it cannot change it.
(Calculation of neighborhoods) There exists a Turing machine $M$ which on input $(p,q)$, where $p$ and $q$ are rational numbers, terminates if, and only if, $p < x < q$.

There are many other equivalent definitions.

We can also ask about various other kinds of computability, and we shall discover a hierachy of classes of reals, see for instance X. Zheng's Classification of the Computable Approximations by Divergence Boundings. One can also study subclasses of computable reals, see again X. Zheng's work.
For instance, we can try these:

(Mind-change computability) A real $x$ is computable with $k$ mind changes if there exists a Turing machine $M$ which runs forever and writes its digits on an output tape. While so doing, it may change its mind about any particular digits at most $k$ times, for some fixed $0 \leq k < \infty$. A variant allows computations where every digit eventually stabilizes, i.e, the number $k$ is not fixed to be the same for all digits.
(Oracle computation) A real $x$ is computable with oracle $A$ if there is an oracle Turing machine $M$ such that $M^A$ computes $x$ (in any of the senses above).
(Infinite-time Turing machine computation) A real $x$ is infinite-time Turing computable if there exists an infinite-time Turing machine $M$ which computes $x$ (in any of the senses above).
(Definable real number) A real $x$ is definable, say in the language of set theory, if there exists a formula $\phi$ such that $\phi(x)$ holds and, if $\phi(y)$ holds for any $y \in \mathbb{R}$ then $y = x$.

I am guessing you had in mind some sort of mind-change computability. It is stronger than the usual computability.