What is the computational complexity of the PageRank problem? I was just wondering what the complexity of the PageRank problem is.  A description can be found here:  http://en.wikipedia.org/wiki/PageRank .  (I am referring to the problem that is solved by the PageRank algorithm, i.e., the question of how one should reasonably distribute "ranking" throughout a graph in a way that is consistent with the model presented in the article I've linked to.)

I've always been curious as to whether or not there is a deterministic polynomial time algorithm that can do as well as the actual PageRank algorithm that Google uses.

It's clear to me that the problem is FNP at worst, as it's easy to verify if a given "arrangement" of rankings for a series of nodes is consistent and valid.  I'm not sure beyond that, though.  Is it NP-hard?  I cannot think of which NP-complete problem would reduce to it.

Thank you,

Philip

As pointed out on the wikipedia page you cite, PageRank is simply computing the eigenvector corresponding to the maximum eigenvalue of the (modified) adjacency matrix of the web graph.  Since this is simple linear algebra, it should definitely be in FP, if not much smaller classes.

Part of the issue with Google's implementation is that the web is so large that its adjacency matrix doesn't fit into the memory of any single (or even any 10,000) computers.  So although the complexity of PageRank is technically in FP, the scale at which Google is doing it doesn't really fit into the realm of traditional single-processor complexity.  To discuss the complexity of actually computing PageRank on a graph as large as the whole web, you'd at the very least have to consider some sort of distributed computation model.


Better lower bounds than 3n for non-boolean functions? Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results.

What are the best known lower bounds if the range of $f$ is $\{0,1\}^m$?  In particular, do we get anything better for $m = n$, or for $m = 2$?

According to the paper A $5n − o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function by  Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and Savage.


Is this multiprocessor scheduling problem with overlaps NP-Hard? The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the same processor, then the length of $J_i$ and $J_k$ is less than $L_i+L_k$), what is the minimum possible time required to schedule all jobs in $J$ on $m$ processors."

Is the above problem NP_hard? I'd be happy to get a reference or a description of a reduction.

Thanks!

Reduce Garey & Johnson problem [SS8], Multiprocessor Scheduling, to your problem.  This is NP-complete, even if $m=2$.  In this problem there are no overlaps, and a deadline is specified.  Your problem is therefore NP-hard, even in the case of zero overlaps.

If you require non-zero overlaps, then it is still possible to reduce Multiprocessor Scheduling to your problem, by increasing the length of each task by 1, and specifying all overlaps to be exactly 1.


What are some careers in theoretical computer science that do not require a PhD? I am an undergraduate, and have recently come to terms with the fact that I may not have the intellect to do research in theoretical computer science, or be able to be admitted into and complete a PhD program.  However, I would still like to be involved with theoretical computer science as I find it very interesting.  So far, the only careers in theoretical computer science that do not require a PhD that I can think of would be being a secretary or administrative assistant for the theory group in some university.  Are there any others?

I work at a national lab and in a directorate that employs many theoretical computer scientists, of which some do not have PhDs.

I think that what would differentiate or establish you would be a quality of your work.
If you are a talented theoretician, strong at algorithms and you can/have been publishing your work in reputable theoretical computer science journals then I do not see why place like national lab would not hire you.

PhD is a testimony of ones ability to pursue relevant and significant research on his or her own.


NC = P consequences? The Complexity Zoo points out in the entry on EXP that if L = P then PSPACE = EXP.  Since NPSPACE = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that $$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$$  We also know that L $\subseteq$ NL $\subseteq$ NC $\subseteq$ P via Ruzzo's resource-bounded alternating hierarchy.

If NC = P, does it follow that PSPACE = EXP?

A different interpretation of the question, in the spirit of Richard Lipton: is it more likely that some problems in P cannot be parallelized, than that no exponential-time procedure requires more than polynomial space?
I would also be interested in other "surprising" consequences of NC = P (the more unlikely the better).
Edit: Ryan's answer leads to a further question: what is the weakest hypothesis that is known to guarantee PSPACE = EXP?

W. Savitch. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.
W. L. Ruzzo. On uniform circuit complexity, Journal of Computer and System Sciences 22(3):365-383, 1971.

Edit (2014): updated old Zoo link and added links for all other classes.

Yes. $NC$ can be seen as the class of languages recognized by alternating Turing machines that use $O(\log n)$ space and $(\log n)^{O(1)}$ time. (This was first proved by Ruzzo.) $P$ is the class where alternating Turing machines use $O(\log n)$ space but can take up to $n^{O(1)}$ time. For brevity let's call these classes $ATISP[(\log n)^{O(1)},\log n] = NC$ and $ASPACE[O(\log n)] = P$.

Suppose the two classes are equal. Replacing the $n$ with $2^n$ in the above (i.e., applying standard translation lemmas), one obtains

$TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$.

If $TIME[2^{O(n)}] \subseteq PSPACE$ then $EXP = PSPACE$ as well, since there are $EXP$-complete languages in $TIME[2^{O(n)}]$.

Edit: Although the above answer is perhaps more educational, here's a simpler argument: $EXP = PSPACE$ already follows from "$P$ is contained in polylog space" and standard translation. Note "$P$ is contained in polylog space" is a much weaker hypothesis than $NC = P$.

More details: Since $NC$ circuit families have depth $(\log n)^c$ for some constant, every such circuit family can be evaluated in $O((\log n)^c)$ space. Hence $NC \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$. So $P = NC$ implies $P \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$. Applying translation (replacing $n$ with $2^n$) implies $TIME[2^{O(n)}] \subseteq PSPACE$. The existence of an $EXP$-complete language in $TIME[2^{O(n)}]$ finishes the argument.

Update: Addressing Andreas' additional question, I believe it should be possible to prove something like: $EXP=PSPACE$ iff for all $c$, every polynomially sparse language in $n^{O(\log^c n)}$ time is solvable in polylog space. (Being polynomially sparse means that there are at most $poly(n)$ strings of length $n$ in the language, for all $n$.) If true, the proof would probably go along the lines of Hartmanis, Immerman, and Sewelson's proof that $NE = E$ iff every polynomially sparse language in $NP$ is contained in $P$. (Note, $n^{O(\log^c n)}$ time in polylog space is still enough to imply $PSPACE=EXP$.)


minimizing size of regular expression for finite sets It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.

What are the results if the language is finite?

One can consider this problem in two models:

The input is all the strings in the language, and we measure the input size by the sum of the length of all strings.
The input is a DFA, and we measure the input size by the number of states of the DFA.

Kleene star is not useful in the finite case, so only $()$, $|$ and $\cdot$(concatenation) are used in the expression. Of course, the length of a regular expression seems arbitrary. Instead, one can give weight to each operation(include adding parenthesis), and ask to minimize the weight of the regular expression.

Edit: As adrianN noted, it's related to grammar based codes. It's NP-complete to produce the minimum length context free grammar to describe a finite set. It's not clear why minimum size context free grammar can imply much about minimum size regular expression. Maybe a clever rewrite rule can related these two, and prove that in the first model, the problem is in NP.

The following argument is essentially from (1): The decision versions of the two problems are contained in the second level of the polynomial hierarchy (more precisely: in the complexity class $\Sigma^P_2$), as follows. Guess a regular expression of size at most $k$, and check if it is equivalent to the given deterministic finite automaton (respectively: to the language given as a list of words).

I believe that no further results regarding your problems are known. For a similar-looking optimization problem, where the objective is to find a minimum equivalent nondeterministic finite automaton instead of a regular expression, the following results are known:

For input described as DFA, the minimum equivalent NFA problem is ${\bf DP}$-hard, see (1). Here, ${\bf DP}$ stands for "difference polynomial time"; this is the "Sigma" complexity class at the second level of the Boolean hierarchy.
For input described as a list of words, the minimum equivalent NFA problem is ${\bf NP}$-hard, see (2).
For $L \subseteq \{0,1\}^m$ and input described as a truth table, the minimum equivalent NFA problem is ${\bf NP}$-complete, see (2).

Beware: Unlike the setting of infinite languages, I do not see a straightforward reduction from the NFA minimization case to the problems from your question.

References:

(1) Hermann Gruber and Markus Holzer. Computational Complexity of NFA Minimization for Finite and Unary Languages. In: 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber and Markus Holzer. Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP. In: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.

Edit:
I think that grammar based codes are not so closely related: in that setup, the given language is a singleton set. But for such a singleton language $L=\{w\}$, the minimum size regular expression is (trivially) given by $w$.


Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography.

Show that no probabilistic polynomial-time algorithm $A$ can distinguish between a random function $f:\{0,1\}^n\to \{0,1\}^n$ and a random permutation $g:\{0,1\}^n\to \{0,1\}^n$ when in each case $A$ is given oracle access to the tested function. Distinguish here is of course except with a negligible probability.

Proof idea: $A$ can make at most $q(n)$ queries to the oracle for some polynomial $q(n)$. The chance that $A$ will find out that the given function is not injective is at most whatever probability comes out of the birthday problem of probability theory, but this is negligible in terms of $n$.

If $A$ does not find a collision among the $q(n)$ queries, then $A$ can't know where the $2^n-q(n)$ remaining elements are mapped, so the function can be any function out of

$$(2^n)^{2^n-q(n)}$$

possibilities of which $(2^n-q(n))!$ are permutations, which is a negligible fraction.

Now fix the algorithm and assume it's been given the function $F$ as an oracle. Say $A^F$ returns $1$ if $F$ is determined to be a random permutation by $A$ and $0$ if not. The problem is that I can't know anything about the strategy that $A$ uses and in order to rigorously prove the problem, I would need to show that

$$|P(A^f(n)=1)-P(A^g(n)=1)|\leq \epsilon(n),$$

where $\epsilon$ is a negligible function. How is this done in a mathematically precise way? Where (even though the book is very vague about this), the probability of each term is taken over the choice of $f$ and $g$ and whatever coin flips $A$ does.

A good reference is
Code-Based Game-Playing Proofs and the Security of Triple Encryption by Bellare & Rogaway. The statement that you are asking about is called the PRF/PRP switching lemma. This paper goes into significant detail about "standard" proofs of this lemma and the subtleties therein. It uses the switching lemma as an illustrative example to advocate for a "game-playing" paradigm for cryptographic proofs that is the "real" purpose of the paper.

Here is another paper (A Short Proof of the PRP/PRF Switching Lemma, Chang & Nandi) that claims a short self-contained proof as well.


Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ? This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question.

The classical proof of the undecidability of the halting problem depends on demonstrating a contradiction when trying to apply a hypothetical HALT decider to itself. I think that this is just denoting the impossibility of having a HALT decider that decides whether itself will halt or not, but doesn't give any information beyond that about the decidability of halting of any other cases.

So the question is

  Is there a proof that the halting problem is undecidable that doesn't depend on showing that HALT can not decide itself, nor depends on the diagonalization argument ?

Small edit: I will commit to the original phrasing of the question, which is asking for a proof that doesn't depend on diagonlization at all (rather than a just requiring it to not depend on diagonalization that depends on HALT).

Yes, there are such proofs in computability theory (a.k.a. recursion theory).

You can first show that the halting problem (the set $0'$) can be used to compute a set $G\subseteq\mathbb N$ that is 1-generic meaning that in a sense each $\Sigma^0_1$ fact about $G$ is decided by a finite prefix of $G$. Then it is easy to prove that such a set $G$ cannot be computable (i.e., decidable).

We could replace 1-generic here by 1-random, i.e., Martin-Löf random, for the same effect. This uses the Jockusch-Soare Low Basis Theorem.

(Warning: one might consider just showing that $0'$ computes Chaitin's $\Omega$, which is 1-random, but here we have to be careful about whether the proof that $\Omega$ is 1-random relies on the halting problem being undecidable! Therefore it's safer to just use the Low Basis Theorem).


What are infinite graphs good for? I have just read on the German Wikipedia that an infinite graph is a graph with an infinite number of nodes or an infinite number of edges. I only know applications and algorithms for finite graphs.

What are infinite graphs good for?

What are applications of those? I can't imagine algorithms that would work on infinite graphs, as you can't store an infinite graph. So you can't operate on it.

Many search problems in artificial intelligence (such as searching the game tree of a chess game, or searching for solutions to puzzles like the Rubik's cube, or more generally searching for sequences of actions to perform in order to accomplish some desired goal) are, in effect, algorithms on infinite graphs, even though the desired answer is a finite path. It is certainly possible to perform algorithms on such graphs, if they are represented implicitly.

But it is also true that mathematics may be useful even if it is not the mathematics of problems that can be solved by algorithms. Infinite graphs can be used to model birth and death processes (e.g. how do our rules for inheritance of names, and the rates at which people are born and die, lead to nonuniform distributions of family names among different human cultures?), to give a framework for approaching questions about mathematical symmetries (via Cayley graphs, which are often infinite), to provide models for reasoning about systems of logic (see Rado graph and saturated model), etc.


Generalization of Dilworth's theorem for labeled DAGs An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth's theorem in partial order theory, it is known that if DAG has no antichain of size $k \in \mathbb{N}$, then it can be decomposed in a union of at most $k-1$ disjoint chains, i.e., directed paths.

Now, I am interested in labeled DAGs, i.e., DAGs where each vertex $v$ carries a label $\lambda(v)$ in some fixed finite set $\Sigma$ of labels. Given an antichain $A \subseteq V$, I can define its labeled size as the minimal number of occurrences of the labels of $\Sigma$ in $A$, namely, $\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$. Is there an analogue of Dilworth's theorem in this context? In other words, if I assume that a DAG has no antichain of labeled size $k \in \mathbb{N}$, what can I assume about its structure? Can I decompose it in some special way? I am already puzzled by the case of $\Sigma = \{a, b\}$, but also interested in the case of a general finite label set.

To visualize this for $\Sigma = \{a, b\}$, saying that $G$ has no antichain of labeled size $k$ means that there is no antichain containing at least $k$ vertices labeled $a$ and $k$ vertices labeled $b$; there can be arbitrarily large antichains but they have to contain only $a$ elements or only $b$ elements, up to $k-1$ exceptions at most. It seems that disallowing large antichains should enforce that the DAG essentially "alternates" between parts of large width for $a$-labeled vertices, and large width for $b$-labeled vertices, but I have not been able to formalize this intuition. (Of course, a suitable structural characterization must talk about the labels of vertices in addition to the shape of the DAG, because already for $k \geq 1$ and on $\{a, b\}$ the condition is satisfied by completely arbitrary DAGs whenever all vertices carry the same label.)

With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled elements, large antichains of $b$-labeled elements, but no large antichains containing both many $a$-labeled and $b$-labeled elements, then there is a decomposition of $G$ as a partition $L_1, \ldots, L_n$, where:

the partition $L_1, ..., L_n$ is what we call a "layering", i.e.:

each $L_i$ is a convex set, i.e., if $x, y \in L_i$ and $x \leq z \leq y$ then $z \in L_i$
for all $i < j$, there is no $x \in L_i$ and $y \in L_j$ such that $y \leq x$

for any antichain $A$ of $G$, there is some $i$ such that $A$ is "almost contained" in $L_i$, i.e., $|A \setminus L_i|$ is less than a constant
for each $L_i$, one of the following is true:

$L_i$ contains a large antichain of $a$-labeled elements and contains no large antichain of $b$-labeled elements
$L_i$ contains a large antichain of $b$-labeled elements but contains no large antichain of $a$-labeled elements

Further, such a partition can be computed in PTIME.

I have posted our current proof online. It's very rough and essentially not proofread because we have no use for the result for now, but I still thought it was tidier to add an answer to this CStheory question with our current progress. Don't hesitate to get in touch with me if you're interested in the result but can't make sense of the proof.


What is the complexity of this graph problem? Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that

for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and
the size of $A$ is minimum.

That is, we are looking for a cluster, in which at  least half of the neighborhood of every internal vertex stays internal. The mere existence of such a cluster is obvious, since the whole vertex set $V(G)$ always has property 1.
But how hard is it to find the smallest (nonempty) such cluster?

Is there a standard name for this problem? What is known about its complexity?

This is a reduction from Clique to your problem .

We start with an instance of Clique: a graph $G$ and an integer $k$, let $V = \{ v_1, v_2,...,v_n\}$.

Clique remains NPC even under the constraint that $max(deg(v_i)) \leq 2(k-1)$ (proof sketch: if $max(deg(v_i) > 2(k-1)$ then add a $K_t$ where $t = 2(k-1) - max(deg(v_i))$ and connect it to all nodes of $G$ and ask for a clique of size $k' = k + t$ in the new graph).

So we assume that in $G$, $max(deg(v_i)) \leq 2(k-1)$. For each node $v_i$ for which $deg(v_i) < 2(k-1)$ we create an "external" clique $C_i$ of size $2(k+1)+1$ (every node of $C_i$ clique has at least $2(k+1)$ neighbours).

If $deg(v_i)$ is the degree of $v_i$, we connect $v_i$ to $2(k-1) - deg(v_i)$ nodes of $C_i$.

In the resulting $G'$, each $v_i$ has degree $2(k-1)$; so $|A| \geq k$ because at least one vertex must be selected.

It is clear that if one of the vertex of $C_i$ is included in $A$ then at least $2(k+1)/2 = k+1$ nodes must also be inserted in it. Note that if an original node has $deg(v_i) < k-1$ then at least one node of the linked $C_i$ must be included, leading to $|A| > k$.

So we can build a set $A$ of minimum size $|A| = k$ if and only if $G$ contains a clique of size $k$.

An example of the reduction in which we ask if the graph $G$ represented by the yellow nodes and bold edges contains a clique of size $k = 3$ (a triangle).

The blue nodes (grouped for better readability) are $K_9$, the red edges are the links between nodes of $G$ with $deg(v_i) < 2(k-1)$ .


Can we verify satisfiability of first order statements via saturation in sub-exponential time? In first order logic, we can prove satisfiability several ways: Finite model generation, truthful monadic abstractions, and also saturation. With finite model generation techniques, we can verify the model directly. With saturation we saturate the search space, running out of inferences, thus proving that a model exists.

How can we verify satisfiability demonstrated through saturation without rerunning the entire search, which might take quite a long time? Satisfiability demonstrated through saturation might be an infinite model, so model generation may not be sufficient.

I am assuming by saturation you mean saturation-based reasoning as used by a resolution theorem prover e.g. where we negate and attempt to find a contradiction by saturation if we saturate we can conclude there is no contradiction assuming certain properties were preserved during proof search.

Given this setting, it is the part in bold that kills any attempt to do what you are hoping for. To be able to conclude that a saturated set was produced using a complete proof search procedure means checking every inference not made during proof search to make sure this was allowed. In practice this means looking at selected literals of every given clause and all reductions or deletions.

As far as I'm aware, so far there has been no effort to make theorem provers record the necessary information to check these things. But such information could be exponentially larger than the saturated set.


Positive topological ordering, take 2 This is a followup to David Eppstein's recent question and is motivated by the same  problems.

Suppose I have a dag with real-number weights on its vertices.  Initially, all of the vertices are unmarked.  I can change the set of marked vertices by either (1) marking a vertex with no unmarked predecessors, or (2) unmarking a vertex with no marked successors.  (Thus, the set of marked vertices is always a prefix of the partial order.)  I want to find a sequence of marking/unmarking operations that ends with all vertices marked, such that the total weight of the marked vertices is always non-negative.

How hard is finding such a sequence of operations?  Unlike David's problem, it's not even clear that this problem is in NP; in principle (although I don't have any examples) every legal move sequence could have exponential length.  The best I can prove is that the problem is in PSPACE.
Is the unmarking operation actually unnecessary?  If there is a valid move sequence, must there be a valid move sequence that never unmarks a vertex?  An affirmative answer would make this problem identical to David's.  On the other hand, if unmarking is sometimes necessary, there should be a small (constant size) example that proves it.

On our regular 666 research seminar we came up with the following proof.

We start with some definitions. Let P be our poset. For simplicity, suppose that none of the weights sum up to zero.
Denote the weight of a vertex by w(x) and the sum of the weights of a set by w(X).
We say that a set X is Y-up (closed) if it is contained in Y and every element of Y that is bigger than an element of X is also in X.
Similarly, say that a set X is Y-down if it is contained in Y and every element of Y that is smaller than an element of X is also in X.
In this language the set of marked elements must be always P-down.

We prove by contradiction. Take the shortest mark/unmark sequence that marks every element. We call such sequences full. At any given point, consider the set of elements that were marked before but are now unmarked. Denote this set by U.

Claim: w(U)>0.

Proof: We prove that the weight of any U-up set, X, is positive. The proof is by induction on the size of X.
If there is an X-down set, Y, such that w(Y)>0, then since by induction we know that w(X\Y)>0 (since it is X-up), we also have w(X)>0.
If for every X-down set, Y, we have w(Y)<0, then by deleting up to this point all the markings and unmarkings of the elements of X from our sequence, we get a shorter full sequence. We are done with the proof of the claim.

Now suppose that we have a full sequence where w(U)>0 at any point for the set U of currently unmarked elements. Take the sequence that we obtain from this by taking the first marking of every element and never unmarking anything. It is clear that this will also be a full sequence satisfying that the set of marked elements is always P-down. Moreover, the sum of the weights will be always at least as much as in the original sequence since at any given time the difference is w(U). We are done.

With this method one can even prove that if instead of marking the whole of P, we only want to mark a subset of P, then it can be done with a sequence of markings followed by a sequence of unmarkings. The proof is the same except that at the end some elements, U, stay unmarked but these can be moved to the end of the sequence as the weight of any U-up set is positive.


On the status of learnability inside $\mathsf{TC}^0$ I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\mathsf{TC}^0$, since I'm not an expert in the area.

What I've discovered thus far is:

All of  $\mathsf{AC}^0$ can be learned in quasipolynomial time under the uniform distribution via Linial-Mansour-Nisan.
Their paper also points out that existence of a pseudorandom function generator prevents learning, and this, coupled with a later result of Naor-Reingold that $\mathsf{TC}^0$ admits PRFGs, suggests that $\mathsf{TC}^0$ represents the limits of learnability (at least in a PAC-sense)
There's a 2002 paper by Jackson/Klivans/Servedio that can learn a fragment of $\mathsf{TC}^0$ (with at most polylogarithmic majority gates).

I've done the usual google scholaring, but am hoping the collective wisdom of cstheory might have a quicker answer:

  Is what I described the state of the art for our understanding of the
  complexity of learning (in terms of which classes sandwich efficient
  learners) ? And is there a good survey/reference that maps out the current state of the landscape ?

The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov.  They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.


What is this matrix column-selection problem, and how hard is it to approximate? I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place it.

The input is a set $A^1,\ldots,A^m \in {\mathbb R}^{n \times n}$ of $n\times n$ real-valued matrices. A feasible solution is a set of columns $S \subseteq \{1,\ldots,n\}$.  The value of $S$ is the sum, over all matrices $A^k$, of the maximum sum of a row of $A^k$ when restricted to columns $S$. Formally,

$ val(S) = \sum_{k=1}^m \max_{i=1}^n A^k_i \cdot 1_S,$

where $A^k_i$ denotes the i'th row of matrix $A^k$, $\cdot$ denotes dot product, and $1_S$ denotes the $\{0,1\}$ vector with a 1 in columns corresponding to S. The objective is to find a set of columns $S$ maximizing $val(S)$.

Is this problem well known? What is known about the polynomial-time solvability or approximability of this problem?

Here is what I know. Observe that this problem is trivial when the matrices all have nonnegative entries --- here picking S to be all columns is optimal. The problem is also trivial when the input consists of a single matrix --- simply try all rows and select all positive entries in the row. Therefore, this problem is interesting only when the input consists of many matrices, and the matrices have both positive and negative entries. A (simple though nontrivial) reduction from max-cut shows that this problem is NP-hard, and UGC-hard to (multiplicatively) approximate better than the Goemans-Williamson constant. Beyond that, I don't know much else.

After more thought, I found a simple approximation-preserving reduction from independent set, showing that this problem is hard to approximate better than $n^{0.5}$. Here it is.

Consider a graph $G=(V,E)$ with n vertices. Construct the following matrices, with columns indexing the vertices.

For each vertex $v$, construct a matrix with the top row containing a 1 in column v, and a 0 elsewhere. All remaining rows are filled with $-\infty$.
For each edge $e=(u,v) \in E$, construct a matrix with the first row with $-\infty$ at $u$ and $0$ elsewhere, and the second row with $-\infty$ at $v$ and $0$ elsewhere. All remaining rows are filled with $-\infty$.

The matrices corresponding to edges penalize choosing two adjacent vertices in the graph by $-\infty$, essentially enforcing that the selected set of columns is an independent set of vertices. The matrices corresponding to vertices add one to the objective value for each column selected (i.e. for each vertex included in the independent set). Consequently, $val(S)$ is $-\infty$ for all non-independent sets S, and |S| for all independent sets S.

This shows that the maximum of val(S) is as hard to approximate as the maximum cardinality of an independent set, as needed.


Size of decision tree for f is polynomial in the DNF size of f and CNF size of f I've been having hard time with proving the following claim:
Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the number of leaves) decision tree for $f$. Also, let $size_{CNF}(f),size_{DNF}(f)$ denote the number of clauses, terms in the minimal $CNF,DNF$ formulas for $f$ respectively.

Prove that $size_{DT}(f)\in poly(n,size_{DNF}(f),size_{CNF}(f))$.

As pointed out by the OP (user13772), this is false.  Jukna et al. constructed explicit Boolean functions $f$ that require deterministic decision trees of size $2^{\Omega(\log^2 N)}$, where $N$ is the number of monomials in a minimal DNF for $f$ and $\lnot f$.  Note that every Boolean function on $n$ inputs can be expressed as a deterministic decision tree of size $2^{O(\log n \log^2 N)}$.

S. Jukna, A. Razborov, P. Savický, I. Wegener, On P versus NP$\cap$co-NP for decision trees and read-once branching programs, Computational Complexity 8 (1999), 357–370.  doi:10.1007/s000370050005  (preprint)


Covering only one of two types of objects in a cartesian space using minimum number of rectangles There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the problem to search for it. I hope someone can help. The precise definition can be found on http://imgur.com/goKKuSQ. Here I explain it in an informal language.

Problem definition:

There are two types of objects (say red and blue pieces) on a finite discrete 2-D space (the space is a closed subset of ZxZ). Number and locations of the pieces are arbitrary. Two pieces on the same coordinate are considered as one. It is not possible for a red piece and a blue piece to co-exist at the same coordinate.

In this space, we can define a rectangle by the coordinate of its upper-left and lower-right corners. The size and location of a rectangle can be anything but it is always parallel to X and Y axis.

I am looking for an algorithm to find the minimum number of rectangles that cover one type of the objects (say the blue pieces) only. Every and each blue piece should be inside or at the border of one or more rectangles, and no red piece can be on the border or inside any rectangle. The algorithm should return the coordinates of all such rectangles.

So, have you heard of this problem before? The first correct answer(s) will surely be acknowledged in my thesis.

Edit: I am searching for an algorithm of complexity smaller than exponential. The exhaustive search took forever to run and I had to stop the program. Also Evolutionary methods are not a good choice because of their long running time.

This sounds like the minimum rectangle cover problem.

  Given an orthogonal polygon with holes, find the minimum number of
  rectangles needed to cover the interior of the polygon without
  covering any of the holes.

In your case, the red points mark the holes, and the blue points mark the interior of the polygon(s). In general, two blue regions might be disconnected, but then the minimum equals the sum of the minimum covers for the two disconnected regions.

Your problem can be easily mapped to the rectangle cover problem, and conversely the rectangle cover problem can be mapped to your problem assuming that all vertices of the polygon are on a grid, which can be assumed w.lo.g.

The bad news is that the minimum rectangle cover is NP-hard. It's also fairly hard to approximate in general (the best current approximation ratio is $O(\sqrt{\log n})$. However, if you had more information about the red and blue points, it's possible you might fall into one of the many special cases of rectangle cover that are easier to solve.


NP-completeness of a problem using a "T-gadget" Working on a problem I came up with the following "T-gadget":

It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2);
it can be rotated (0, 90, 180, 270 degrees);
two gadgets X and Y, can be linked together (one connector of X is joined with one connector of Y);
the wires used to link the T-gadgets cannot overlap.

A signal is propagated on the wires; and it can use 1 or 2 connectors to traverse a T-gadget. Suppose that it enters through wire A1, then it can:

go back through wire A2, OR
choose among connector B or C - suppose that it chooses connector B; then it can exit the gadget through wire B1, re-enter through B2 and exit again through A2

When a signal enters a gadget and exits from the same connector, the gadget is "activated".

Possible traversals of a T-gadget:
(OUT) - A1 - A2 (OUT)
(OUT) - A1 - B1 - (OUT) - B2 - A2 - (OUT)
(OUT) - A1 - C1 - (OUT) - C2 - A2 - (OUT)
(OUT) - B1 - B2 (OUT)
(OUT) - B1 - A1 - (OUT) - A2 - B2 - (OUT)
(OUT) - B1 - C1 - (OUT) - C2 - B2 - (OUT)
(OUT) - C1 - C2 (OUT)
(OUT) - C1 - B1 - (OUT) - B2 - C2 - (OUT)
(OUT) - C1 - A1 - (OUT) - A2 - C2 - (OUT)

The signal starts on wire A1 of a gadget (with connector A unlinked) and must return to A2.

Question: is the problem: "Given a set of T-gadgets linked together, does exist a path that activates all of them?" $NP$-complete?

If we omit option 1 (go back through wire A2) I think that the problem is $NP$-complete (through reduction from Hamiltonian path problem on cubic planar graphs).

You're asking whether the underlying 3-regular graph has a Hamiltonian path, which is NP-complete.  Your activation signal must traverse every edge in this path exactly twice.

See also this question and this one.


The entropy of a convolution over the hypercube Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural to define the entropy of such a function as follows:
$$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x)^2 \log \left( f(x)^2 \right) .$$

Now, consider the convolution of $f$ with itself:
$$ [ f*f] (x) = \sum_{y \in \mathbb{Z}_2^n}f(y)f(x+y) .$$
(Note that since we are dealing with $\mathbb{Z}_2^n$, then $x+y=x-y$)

Is it possible to upper bound the entropy of $f*f$ (normalized in its $L_2$-norm, in order for it to be a distribution) by the entropy of $f$? Formally, is there any constant $C$ such that
$$ H \left( \frac{f*f}{\|f*f\|_2} \right) \le C \cdot H(f)$$

There is no such $C$. Define $g\colon\mathbb{Z}_2^n\to\mathbb{R}$ by
$$g(x_1,\dots,x_n)=\begin{cases}
2^{2n/3}&\text{ if $x_1=\dots=x_n=0$}\\
1&\text{ otherwise.}\end{cases}$$

Then $g*g$ satisfies
$$(g*g)(x_1,\dots,x_n)=\begin{cases}
2^{4n/3}+2^n-1&\text{ if $x_1=\dots=x_n=0$}\\
2^{2n/3}\cdot 2+2^n-2&\text{ otherwise.}\end{cases}$$

Let $f=g/\|g\|_2$. Then $H(f)=H(g/\|g\|_2)$ is $o(1)$ (in fact it's exponentially small in $n$), while $H(g*g/\|g*g\|_2)$ is about $n$.


Hamiltonian cycle vs co-NP I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:
Considering a graph G, is it true that it does not have an Hamiltonian cycle?

Is this correct?
If so, then how is this complementary version a different class of complexity than the original Hamiltonian cycle problem? The decision question is the same. To put it differently, what is the difference between NP and co-NP here?
Otherwise, if this complementary version is false, what would be the correct version (if any exists)?
Update

To put it simply, returning an opposite answer for one input does not cover for all possible inputs.

In the comments of dkaeae's answer below, I say "NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian." Fact is if a P-machine can decide whether a graph is Hamiltonian or not, it can also deliver an instance of such a cycle in P-time if any exist. This does not harm the formal definition of NP.

The complementary version given by Wikipedia is correct.

coNP consists of the complements of the problems in NP. In this case, the universe of discourse (i.e., the encoded instances) is the set of (properly encoded) graphs. The Hamiltonian cycle decision problem contains those graphs which are Hamiltonian; its complement is exactly the set of graphs which are not Hamiltonian.

You are correct; the two problems do look almost the same. This is a vital realization concerning coNP (or any co-class in fact). The key difference is that, for some problem classes, being able to efficiently check whether a solution is correct (NP) does not necessarily mean you can also efficiently verify all answers are incorrect (coNP) and vice-versa.


For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free? Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and $b$ with some modulo conditions, e.g., $R(a,b)$ if and only if ($a<2b+1$ and $a\equiv 2 \bmod 6$) OR ($a-b=2$ and $a\equiv 2 \bmod 6$) OR ($2a-3b>5$ and $2a+b\equiv 3 \bmod 6$).

Is there some similar characterization known when the language can contain only some fixed, bounded number of non-zero characters?

For example, for which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Related: I've discovered that this topic has been studied a lot for primitive words, see Kaszonyi-Katsura: Some new results on the context-freeness of languages.

What you're looking for is an old result of Ginsburg and Spanier actually related to one of the oldest open questions of the field.   See Ginsburg's book The Mathematical Theory of CFLs.

Defs. A linear set is a set of the form $\vec{v} + P^*$ where $\vec{v} \in \mathbb{N}^k$ and $P$ is a finite set of such vectors ($P^*$ denotes all linear combinations of the vectors in $P$).  A linear set is stratified if :

All the vectors in $P$ have at most two nonzero components;
For all $\vec{x}, \vec{y} \in P$, the nonzero positions of $\vec{x}$ and $\vec{y}$ are not interleaved (this is related to the fact that $a^ib^ic^jd^j$ is CFL but not $a^ib^jc^id^j$).

Theorem. Let $w_1, \ldots, w_k$ be some words.  Any CFL $L \subseteq w_1^*\cdots w_k^*$ can be written as $L = \{w_1^{i_1}\cdots w_k^{i_k} \mid (i_1, \ldots, i_k) \in R\}$ where $R$ is an union of stratified sets.  Somewhat conversely, any language of that form with $R$ a union of stratified sets  is a CFL.

Naturally, there are languages that are CFL that can be written in the previous way with $R$ being quite arbitrary—e.g., with $w_1=w_2=a$ and $R = \{(2^i, j)\}.$
 However, if for instance all $w_i$'s are different letters, then $R$ has to be a union of stratified sets for $L$ to be a CFL.

As for the open question I mentioned before, the following problem is not known to be decidable:

Given: A finite union of linear sets
Question: Is this set presentable as a finite union of stratified sets?


What are some interesting applications of homotopical algebra in theoretical computer science? I am an homotopy theorist, interested in computer science.

I would like to ask what are some interesting applications of homotopical algebra (model categories, infinity categories, simplicial categories, etc) in theoretical computer science?

Two big applications of homotopy theory in theoretical computer science are

Homotopy Type Theory revealed a completely unexpected connection between the theory of the typed lambda calculus and homotopy theory. As a quick intuition, think of it as either a (vast) generalization of the connection between intuitionistic logic and topological spaces, or a language for doing "synthetic homotopy theory".
The directed version of algebraic topology and homotopy theory (ie, where paths are not reversible) has been developed precisely with applications to computer science in mind. The intuition is that the possible evaluations of a concurrent program correspond to a space, program executions correspond to paths in that space, and synchronization primitives correspond to obstructions. By considering the geometric properties of these spaces/programs, it becomes possible to develop tools for reasoning about their behaviour.


Is the MapReduce framework a type of BSP? Is it accurate to call the mapReduce framework a type of bulk synchronous parallel programming framework with no local memory retention within processors between synchronizations? If not, what parallel programming model most accurately encapsulates the mapReduce framework?

In section 2 of http://arxiv.org/abs/1101.1902, the authors define a model of MapReduce that is intentionally structured like BSP. They prove simulation theorems as well. May be a good place to start.


Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$ Sean Anderson published bit twiddling hacks containing the Eric Cole's algorithm to find the $\lceil\log_2 v \rceil$ of an $N$-bit integer $v$ in $O(\lg(N))$ operations with multiply and lookup.

The algorithm relies on a "magic" number from De Bruijn sequence.
Can anybody explain fundamental math properties of the sequence used here?

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

First note that this algorithm only computes $\lceil \log_2 v \rceil$, and as the code is written, it works only for $v$ that fit in a $32$-bit word.

The sequence of shifts and or-s that appears first has the function of propagating the leading 1-bit of $v$ all the way down to the least significant bit. Numerically, this gives you $2^{\lceil \log_2 v \rceil} - 1$.

The interesting part is the de Bruijn trick, which comes from this paper of Leiserson, Prokop and Randall (apparently MIT professors spend time doing bit hacks :) ). What you need to know about de Bruijn sequences is that they represent all possible sequences of a given length in a way that's as compressed as possible. Precisely, a de Brujn sequence over the alphabet $\{0, 1\}$ is a binary string $s$ of length $2^k$ such that each length $k$ binary string appears exactly once as a contiguous substring (wrap around is allowed). The reason this is useful is that if you have a number $X$ whose bit representation is a de Bruijn sequence (padded with $k$ zeros), then the top $k$ bits of $2^iX$ uniquely identify $i$ (as long as $i <k$).


Known sparse integer programming problems I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ?

I would define sparse problems as problems that have their output mostly populated by zero values.

Thank you

Probably, this is not an intended answer.  The sparsity constraint can be naturally represented in integer programming.

(1) For the binary integer programming (the variables take only values 0 and 1), an extra constraint that "the sum of variables is at most $k$" leads to a solution with at most $k$ non-zeros.

(2) If your problem is not binary and each variable takes the value in $\{0,\ldots,M\}$, then for each variable $x_i$ we introduce another 0/1 variable $y_i$, and give an extra constraint as $y_i \leq x_i \leq M y_i$. This means that $y_i=0$ if and only if $x_i=0$, so the sparsity can be described by means of $y$. Namely, we introduce the sparsity constraint $\sum y_i \leq k$ as (1) above.

I'm imagining you're to look at an analogue of linear programming (or convex programming) with sparsity constraint to integer programming. However, linear programming with sparsity constraint is no longer linear programming, while integer programming with sparsity constraint is still integer programming (as described above). Their natures are totally different.

Or, if you need some "interesting" examples, I would say "any combinatorial optimization problem with cardinality constraint".  That's almost equivalent to a binary integer programming with the constraint that the sum of variables is at most a certain number.


Graph (Forest) representation that supports edge deletion and efficient traversal I am trying to write a data structure that given a general tree (or forest) will support the following operations:

Edge deletion
Connected(u,v) queries

This problem is addressed in section two of the following ACM journal article: "An On-Line Edge-Deletion Problem". The idea given claims to be able to carry out q edge deletions in O(q + |V|log|V|) time, while allowing constant time Connected(u,v) queries. The idea being: to maintain a table mapping each vertex to a connected component. Upon each deletion, each of the new trees is scanned in parallel. Which ever tree is finished being scanned first - becomes a new component. Now my question is, which graph representation can I use to implement their idea? On one hand I need to be able to delete an edge without having to scan an O(|V|) adjacency list, on the other hand, I need to be able to run a traversal (DFS) in O(|E|) = O(|V| (tree) time which can't happen using a matrix.

This problem is known as Decremental Connectivity. In general, decremental connectivity is where you need to support the operations:

Connected($u$,$v$) : Check whether vertex $u$ is connected to vertex $v$
Delete($e$): Remove an edge $e$

Given $n$ queries of the first kind and $m$ queries of the second, Even and Shiloach [1] gave an $O(n\log{n} + m)$ algorithm and later, Alstrup et al. gave an $O(n+m)$ algorithm in [2].

There is a simple way to do the former using a data-structure known as the Euler Tour Trees or the approach taken in [1] could also be used. If you wish to implement [1], the tree is stored as a set of connected components. It is then enough to determine which component each vertex belongs to answer the connected-ness query. There is a breadth-first seach used to answer the deletion process. But it is $O(\log{n})$ amortized. This would achieve $O(n\log{n} + m)$.

If the $\log{n}$ factor must be removed, then a leaf-trimming approach would work. You trim all subtrees with size $\geq\log{n}$. Then, you can use the Euler Tour Trees (or the approach in [1]) to perform queries in the untrimmed portion. Some cases could need to be seperately handled. This is the approach given in [2].

[1] S. Even and Y. Shiloah. An on-line edge-deletion problem. Journal of the Assoiation for
Computing Mahinery, 28:1-4, 1981.

[2] Stephen Alstrup and Jens Peter Secher and Maz Spork. Optimal On-line Decremental Connectivity in Trees, IPL, 65:64-8, 1997


bounded language complete for NSPACE(log n)? What are the consequences of a sparse language being complete for $\mathsf{NSPACE(\log n)}$ under deterministic $O(\log n)$-space many-one reductions? Is there an analog of Mahaney's Theorem for $\mathsf{NL}$ (if there is a sparse $\mathsf{NL}$-complete language then $\mathsf{L} = \mathsf{NL}$)?

Bounded here was meant to indicate that if the input alphabet is $\{a_1, ..., a_k\}$, the language is a subset of $a_1^* a_2^* ... a_k^*$. Any such language clearly has number of strings of length $n$ that is bounded by $n^k$ so bounded => sparse.

$\mathsf{L}=\mathsf{NL}$. Yes, there is an analog of Mahaney's Theorem for log-space. If there is a sparse set that is hard for $\mathsf{NL}$ under logspace reductions, then $\mathsf{L}=\mathsf{NL}$:

J.-Y. Cai and D. Sivakumar. Resolution of Hartmanis’ conjecture for NL-hard sparse sets. Theoret. Comp. Sci. 240(2):257–269, 2000.

van Melkebeek extends this to logspace bounded truth-table reductions, which is quite close to the state of the art for extensions of Mahaney's Theorem in the polytime world as well:

D. van Melkebeek. Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets. J. Comput. Syst. Sci. 57(2):213-232, 1998.

(I think the reversed dates are simply because these are the journal publications rather than the corresponding conference publications.)


When does BPP with a biased coin equal standard BPP? Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a machine in polynomial time. It is a standard exercise to prove that:

A) If $p$ is rational or even $BPP$-computable then $BPP_p=BPP$. (By $BPP$-computable I mean: there is a randomized polynomial algorithm that being fed $n$ in unary returns w.h.p. the binary rational with denominator $2^n$ that lies within $2^{-n-1}$ of $p$.)

B) For some uncomputable $p$ the class $BPP_p$ contains an undecidable language and hence is larger than $BPP$. Such values of $p$ form a dense set in $(0,1)$.

My question is the following: what happens in between? Is there a criterion for $BPP_p=BPP$? In particular:

1) Do uncomputable in $BPP$ probabilities $p$ exist such that $BPP_p=BPP$? (They may be computable in some higher classes).

2) Is $BPP_p$ wider than $BPP$ for all uncomputable $p$? (The parameters in question are those whose binary expansion contains very long sequences of zeros and/or ones. In this case computing bits by random sampling may take very long, even uncomputable time, and the problem cannot be rescaled to polynomial time. Sometimes the difficulty can be overcome by another base of expansion, but certain $p$ may fool all bases).

1) Yes, but only because of your definition. Take a unary language $L\in EXP\setminus BPP$ (yeah, I know this might be empty, in that case just take something even bigger than $EXP$), that is very sparse in the sense that $n\notin L$ if $n$ is not a tower of $2's$, i.e., of the form $2^{2^{2^\ldots}}$. Define $p=\sum_{n\in L} 1/n$. This $p$ is not $BPP$-computable, but $p$ can be approximated in $P$ up to a small enough additive error that allows the simulation of a $BPP_p$ machine.

Had you defined $BPP$-computable such that you want to approximate $p$ up to an additive error of $1/n$ (instead of $1/2^n$) in polynomial time, things would be different.

Update. The below answer is for the case when the additive error we allow is $2^{-n}$ instead of $2^{-n-1}$.

2) Yes, because here you can forget about the polynomial restriction on the classes and by sampling $2^n$ times you can get the $n$-th bit of $p$ in $BPP_p$.


Negative results on identical particles approach to Graph Isomorphism (GI) problem There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed promising, was proved to be incomplete for general graphs in this paper by Amir Rahnamai Barghi and Ilya Ponomarenko. Other similar approach was also refuted in this paper
by Jamie Smith. In both of these papers, they use the idea of coherent configuration (schemes) and alternative but equivalent formulation of cellular algebra (matrix subalgebra indexed by a finite set -here vertex set- closed under point-wise multiplication, complex conjugate transpose, and containing Identity matrix I and all-one matrix J) respectively to provide necessary counter arguments.

I find it very difficult to follow those arguments and even if I follow individual arguments vaguely I do not understand the core idea. I would like to know if the essence of the arguments can be explained in generic terms -may be at the cost of slight rigour- without using  the language of scheme theory or cellular algebra.

You can do much better than checking all n! permutations when brute forcing a solution, http://oeis.org/A186202  The grail is showing that you can't do much better than that, or exploiting the fact that most graphs have no symmetry in them and using this to speed calculation.


Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset? It has been claimed that if $P = NP$, then every problem in $P$ (equivalently $NP$) is NP-complete.

As a blanket statement, I find this wrong because, well, there's the trivial problem or constant time problems, but more interestingly, I expect that there are classes that are very small that are provably not NP-complete but aren't entirely trivial. This is in analogy to the fact that it is known that $P != EXP$, there must be a $C \subsetneq NP$, presumably $C= NTIME(\log(n))$. But I have never heard discussed such a small class.

The smallest well-known class I can think of is $AC^0$, but I don't know whether it is known that it is not $NPC$. And there's Ryan's recent result that $NEXP \not\subset ACC^0$, which leads me to believe that it would have to be a much smaller class than $AC^0$ that would be known to be disctinct from $NP$.

I think the first statement might be considered to be true if all one has are deterministic polytime reductions (which would imply that -all- problems in $P$ are $P$-complete), but that seems to be too simplistic. A particular proof might use a particular reduction, but the distinctness of complexity classes is not parameterized by those reductions (or is it?).

So, thoughts/suggestions? Should I just accept the first statement since $NPC$ is defined with respect to deterministic polytime reductions? And even so, is there a well-known non-trivial class that is provably a proper subset of $NP$?

[Answering the original motivating issue: "Should I just accept the first statement since NPC is defined with respect to deterministic polytime reductions?"]

First, if $P=NP$ but the Berman-Hartmanis Isomorphism Conjecture fails, then there are infinitely many distinct p-isomorphism classes of languages within $P$. So even though it is true that $P=NP$ implies all sets in $P$ are $NP$-complete with respect to polynomial-time reduction (technical caveat below), that does not mean that we lose all information about $P$. By looking at a finer type of reduction -- but still polynomial-time, namely polynomial-time computable-and-invertible length-increasing one-one reductions -- we can potentially tell a lot about what's going on inside $P$.

In fact, if $P=NP$ but the Isomorphism Conjecture fails, then the partially ordered set of p-isomorphism classes inside $P$ is quite rich: any countable partial order can be embedded in it (see P. Young. Some structural properties of polynomial reducibilities and sets in NP. STOC 1983.).

But more generally, in some cases it does feel wrong to lump all of $P$ together and in other cases it's exactly what you want. This is why, for example, we don't use poly-time reductions when discussing $L$ versus $P$, but we do when discussing $P$ versus $NP$. But there might be another class you want to contrast with $NP$ where it makes sense to use other reductions. The type of reduction you use should be the type you need for the problem at hand; there is no "single right reduction" to define, e.g., $NP$-completeness (though "$NP$-complete" without qualification usually means w.r.t. poly-time many-one reductions, but that is a matter of convention).

Distinctness of complexity classes is not parametrized by reductions; however, there are several potentially distinct classes that could legitimately be called "$NP$-complete," namely for any reducibility $r$, "$NP$-complete with respect to $r$-reductions".

(Caveat: If we use poly-time many-one reductions, then $\emptyset$ and $\Sigma^{*}$ do not become $NP$-complete if $P=NP$. If we use poly-time Turing reductions, or even poly-time 1-tt reductions, they do.)


Do Higher-Order Functions provide more power to Functional Programming? My original question was: Is Kappa calculus less powerful than Lambda calculus?

Does the lack of Higher-Order functions on a programming language excludes some programs that could only be written in functional programming (and therefore in a turing machine)?

By "powerful" I mean a Turing Complete programming language. For example, a language that can not contain infinite recursive expressions, ie infinite recursion or an infinite while loop, is not as powerful as Lambda-Calculus and Turiung Machines, since it would otherwise be a contradiction to the Halting Problem.

I can't find the reference right now, byt I remember something about an algorithm that on a non-lazy functional programming language has an $\Omega( n \log n )$ complexity, while the same algorithm in imperative programming is $\Omega( n )$

Even the full simply typed lambda calculus with products is not Turing-complete (cf. http://en.wikipedia.org/wiki/Simply_typed_lambda_calculus#General_observations), and since the kappa calculus is a fragment of it (if I understand the Wikipedia page correctly), it isn't either.


What methods exist for returning all points within an arbitrary closed shape? I have been reading about range search algorithms, but most that I read apply only to a simple range (such as a standard rectangle in 2d).

In a similar fashion, what options exist for range search algorithms across arbitrary closed shapes?  For example, if I had a binary image of a person, and random points across the image, how do I determine which points lie on the portion of the person?

There are no options.

For any set of $n$ points, if you want to answer range queries for arbitrary ranges, all $2^n$ subsets are possible answers.  (In fact, for any set of $n$ points in convex position, every subset is the intersection with some convex range.)  It follows immediately that any query algorithm (describable as a decision tree) requires $\Omega(n)$ time, no matter how much time and space you spend preprocessing the points.

Equivalently: The range space (points in the plane, convex regions in the plane) has unbounded VC-dimension, so there's no hope for an efficient range searching algorithm.


Stackelberg solution to $n$-player Hotelling's game on a segment Suppose that several agents need to place points (one per
agent) on the interval $[0,1]$. An agent's goal is to maximize the
volume of the Voronoi cell that contains his point. When $n$ agents must
place their points sequentially, is an optimal strategy known?

From what I was able to glean from the literature so far, it appears I am asking for the Stackelberg solution to an $n$-player Hotelling's game on a segment.

This game has been studied in

  Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, René van Oostrum:
  "Competitive facility location: the Voronoi game"
  Theoretical Computer Science 310, 2004, pp 457-467

There also are lots of follow-up works, as for instance

  Sayan Bandyapadhyay, Aritra Banik, Sandip Das, Hirak Sarkar:
  "Voronoi game on graphs"
  Theoretical Computer Science 562, 2015, pp 270-282


How to deal with concept classes with exponential value of VC dimension Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how computational learning community handle the learnability of $C$.

One thing I am thinking about is investigating the learnability of $C$ in active learning. Hoping that I will end up with less number of examples required.

However, I prefer to stick with the passive learning for now and wondered what else I can do for this poor $C$? As I am new to the field, I also wish to have some examples of concept classes with exponential VC dimension.

One approach would be to stratify your concept class by VC-complexity. For example, suppose that $C$ is the set of all functions $f:\{0,1\}^n\to\{0,1\}$; its VC-dim is $2^n$.
However, you can decompose $C$ in any number of ways. Say, $C_k$ is the collection of all functions whose (minimal) binary tree has depth $k$ or less. Or, $C_k$ is the set of all functions whose Fourier expansion puts no weight on XORs of more than $k$ bits.
Then $C_1\subset C_2 \subset \ldots \subset C_n$, and selecting the appropriate $C_k$ is the problem of model selection. Machine learning theory offers a principled way of doings this via Structural Risk Minimization; here is a good start:
http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=705570&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel4%2F18%2F15247%2F00705570.pdf%3Farnumber%3D705570


Finding a common factor in $\lambda$-terms that agree under certain substitutions Suppose that $\mathcal{L}$ is the language of a simply typed lambda calculus of two base types, $e$ and $t$, with infinitely many constants at each type.

A substitution $j$ is a mapping from constants of type $\sigma$ to arbitrary closed $\mathcal{L}$-terms of type $\sigma$. $j$ extends to a mapping on arbitrary closed terms of type $\sigma$ in the obvious way: $j\alpha$ is the result of substituting the constants in $\alpha$ with their $j$ counterparts.

Now suppose that for each constant $a:e$ there is a term $\phi^a: t$, and suppose moreover that:

For any substitution, $j$, if  $ja = jb$ then $j\phi^a =_{\eta\beta} j\phi^b$

Does it follow that there exists a closed term $\alpha:e\to t$ such that $\phi^a =_{\eta\beta} \alpha a$ for each constant $a$?

In case anyone is interested, I believe the following does it. I'm assuming, for simplicity, that $\phi^a$ is in $\eta\beta$ normal form.

Pick some constant $a$ arbitrarily, and let $b$ and $d$ be distinct constants that don't appear in $\phi^a$. Finally, let us write $x,y \mapsto z$ for the substitution that substitutes both $x$ and $y$ for $z$ and does nothing else.

Firstly we prove that for any constant $c\not= b$, $\phi^c$ does not contain $b$. Let $k=a,c\mapsto d$. Then $k\phi^a =_{\eta\beta} k\phi^c$ since $ka=kc = d$. Indeed $k\phi^a = k\phi^c$, since $\phi^a$ and $\phi^b$ are in normal form, and $k$ substitutes constants, so that $k\phi^a$ and $k\phi^c$ are in normal form too. $k\phi^a$ does not contain $b$, since $\phi^a$ does not contain $b$, and $k$ introduces only $d$. So $k\phi^c$ does not contain $b$, and thus $\phi^c$ does not contain $b$ since $k$ leaves $b$ alone.

Now $\phi^b$ can be decomposed into $\alpha b$ where $\alpha$ does not contain $b$ (let $\alpha = \lambda x \phi^b[x/b]$). Let $c$ be any constant, and let $i = b,c\mapsto c$. Since $ib=ic$, we know that $i\phi^c =_{\eta\beta} i\phi^b =_{\eta\beta} i(\alpha b) =_{\eta\beta} i(\alpha)ib = \alpha ib = \alpha c$. Secondly, $i\phi^c = \phi^c$ since, as we showed above, $b$ does not occur in $\phi^c$. Thus $\phi^c = \alpha c$ for arbitrary $c$.


Quantified Boolean Formulas with logarithmic alternations I'm studying a problem which is hard for the class of quantified boolean formulas with a logarithmic number of alternations of the quantifiers. A problem in this class would look like:

$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$

Where $a_{\log n} = n$, and $F$ is a boolean formula of the variables $x_1 \ldots x_n$.

This class clearly contains $PH$ and is contained in $AP = PSPACE$. Is there a name for this class? Is there anything more known about it?

(1) What we already know:

As you've already stated, QBF with $\log(n)$ alternations of quantifiers is hard for every level of the polynomial hierarchy.

(2) I think that we can also prove the following:

The problem is $NSPACE(log^2(n))$-hard.

(3) Here is my informal justification for the preceding assertion:

Given a $log^2(n)$ space bound NTM and an input string, we need to determine whether there exists an accepting computation on the given input string.

Each configuration in the computation can be represented by essentially $\log^2(n)$ bits.  In other words, we can represent a configuration by a group of $\log^2(n)$ variables.

The idea is that we have a start configuration and a final configuration and we need to guess the computation that happens in between.  We recursively guess the "middle" configurations using exist quantifiers and recurse verifying that the "left" configuration goes to the "middle" and the "middle" configuration goes to the "right" using for all quantifiers.

Now to make this work, instead of picking one "middle" configuration, we need to pick a group of equally spaced "intermediate" configurations between the "left" and "right" configurations.  In particular, we could guess $\sqrt{n}$ equally spaced "intermediate" configurations using exist quantifiers with $\sqrt{n} * log^2(n)$ variables and then recurse on every gap between configurations using for all quantifiers with roughly $\log(n)$ variables.

The recursion only needs to continue on to depth $2 * \log(n)$ to be able to cover a computation of length $\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$ where each configuration has at most $\log^2(n)$ many bits.

Since the recursion is of depth $O(\log(n))$, we only have $O(\log(n))$ groups of variables i.e. alternations.  Since each group of quantifiers only has $\sqrt{n} * log^2(n)$ variables, in total we have $O(\sqrt{n} * log^3(n))$ variables.

Feel free to offer any feedback or corrections.  Thank you very much and I hope this helps a little bit.

(4) A more general assertion as suggested by Ryan's answer:

You should be able to carry out the preceding construction in a more general way.  Consider the following:

At each step of the recursion, break up into $g(n)$ groups of "intermediate" configurations using $c(n)$ bits per configuration.  Then, do the recursion to depth $d(n)$.

As long as we don't have too many variables and too many alternations, this seems to work fine.  Roughly, we need the following to be satisfied:

$g(n) * c(n) * d(n) \leq n$
$d(n) \leq \log(n)$

Our generalized approach will be used to simulate non-deterministic Turing machines that run for $g(n)^{d(n)}$ steps using $c(n)$ bits of memory.

In particular, we pick the following:

$g(n) = \sqrt{n}$
$c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$
$d(n) = 2 * \log^2(n)$

The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly $2^{\log^2(n)}$ steps using $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, we have a better hardness result than before.  In particular, the problem is hard for $NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$.

(5) Further generalizations:

In the preceding generalization, we were simulating non-deterministic time and space bounded Turing machines.  However, we may be able to simulate alternating time and space bounded Turing machines as well.

Let me explain a little bit.  So we use roughly $\log(n)$ alternations to do the recursion to depth $\log(n)$.  However, we could use some of the alternations initially, let's say $\sqrt{\log(n)}$.  Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.

In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ with sublinear witness lengths.  Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.

Thank you for the comments and feel free to offer any further corrections or clarifications.  :)


Does having unique normal forms imply weak normalization and confluence? Consider a term rewriting system $\mathcal{R} = (\Sigma, R)$ over a signature $\Sigma$ with basic rewrite rules $R$. If $\mathcal{R}$ is weakly normalizing and confluent, then we know that each $\Sigma$-term has a unique normal form (with respect to $\mathcal{R}$). Is the converse also true? I.e. if each term has a unique normal form with respect to $\mathcal{R}$, then does it follow that $\mathcal{R}$ is weakly normalizing and confluent? Obviously if each term has a unique normal form, then the system is weakly normalizing, so it remains to ask whether it will be confluent.

In short, I am wondering whether the property of a term rewriting system to be weakly normalizing and confluent is strictly stronger than the property of each term having a unique normal form (with respect to the system).

It is a little bit sketchy, but here is my argument: Suppose that there are three terms t, u, v such that t reduces to u, t reduces to v and suppose that each term has a unique normal form. Since you are weakly normalizing as you said, there exists a normal form for v and u. But since the normal form is unique, then v and u are joinable. Hence, the system is confluent.


Complexity of a matrix problem The following problem recently appeared in my research. Being no expert on algorithmic questions I have Googled extensively in the search for suitable problems to reduce from. I don't see how 3SAT would work, and even though ZOE is similar in spirit a reduction is not obvious. Another possibility would be the existential theory of the reals. That doesn't seem to be quite the match either but I might be wrong about that.

Problem:
$A$ and $B$ are both $n\times n$-matrices over your favorite field. We assume that an arbitrary set of indices of $A$ are set to 0. Likewise, an arbitrary set of indices of $B$ are set to 0. Question: can we fill in the remaining indices of $A$ and $B$ such that $AB = I_n$?

Example: $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$, $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$. Not possible.

What is the computational complexity of this (in $n$)?

Any hints or ideas to where to look for similar results in the literature will be greatly appreciated.

EDIT (completely forgot about this post): In recent work which is available on the arXiv (if anyone is interested in the preprint let me know) we have shown that the problem is NP-hard over any finite field.

Well, here's a not-horrible upper bound over $\mathbb{C}$: $\mathsf{PSPACE}$, or assuming the Riemann Hypothesis, $\mathsf{AM}$. This is because for any given patterns of zeros for $A,B$, checking whether one can make $AB=I_n$ is checking whether a certain system of $n^2$ integer polynomial equations has a solution in $\mathbb{C}$, and this can be done in these upper bounds, by Koiran.

Another approach is to try to leverage the fact that this is in fact a system of bilinear equations. Solving bilinear equations is equivalent to finding "rank 1" solutions to linear equations. I've been trying to determine if there are better upper bounds for solving bilinear systems in general, but with no luck so far. It's also possible that one could leverage the particular structure of these bilinear equations to get something better than what's known in general...


Bayes-consistent cost-sensitive classification In cost-sensitive classification,
we have a confusion (or cost) matrix
$C$, where $C(i,j)$ is the cost incurred
for predicting label $i$ when nature
specifies $j$. The costs are non-negative,
but no other restriction (such as symmetry) need be imposed. In the classic setting
(PAC and its multiclass generalization),
$C(i,j)=1[i\neq j]$.
The notion of Bayes-consistency carries
over naturally to the cost-sensitive setting. For any joint distribution
$P$
over the instances
$\mathcal{X}$
and labels
$\mathcal{Y}$,
we define the risk of a predictor
$f:\mathcal{X}\to \mathcal{Y}$
as
$$
R(f)=
\mathbb{E}_{(X,Y)\sim P}
C(f(X),Y).
$$
Letting $f^*$ be a minimizer of
$R(\cdot)$ over all measurable $f$,
we define the Bayes-optimal risk as
$R^*:=R(f^*)$.
Question: What is known about Bayes-consistent classification in the cost-sensitive setting? For example,
when $\mathcal{X}$ is a metric space
and $C(i,j)=1[i\neq j]$, various nearest-neighbor methods are known to be strongly Bayes-consistent. Is anything known about other cost matrices?

I'm not sure if this is what you're looking for, but people have studied consistency of surrogate risk minimization. There, we define a surrogate loss function $L$ and a link $\psi$. We first minimize surrogate loss on our dataset, yielding some surrogate hypothesis $h$. Then we define $f(x) = \psi(h(x))$. This procedure is roughly consistent if, as data $\to \infty$, we have $f \to f^*$.
The question is, given e.g. $C$, what are some nice, consistent surrogate losses? Example: for binary $0-1$ loss, one can use hinge loss or logistic loss as a surrogate, and one can show this is consistent as long as the hypothesis class is rich enough.
Tewari and Bartlett (2007) study multiclass classification, but I think not cost-sensitive, and relate consistency to calibration. A more recent work is Agarwal and Agarwal (2015), which has some more references.
[1] Tewari, Bartlett. On the Consistency of Multiclass Classification Methods. JMLR 2007. https://www.jmlr.org/papers/volume8/tewari07a/tewari07a.pdf
[2] A. Agarwal, S. Agarwal. On consistent surrogate risk minimization and property elicitation. COLT 2015. http://proceedings.mlr.press/v40/Agarwal15.pdf


Optimal preprocessing for certain types of queries Suppose we have a semigroup $(S,\circ)$ with elements $S=\lbrace s_1,s_2,\dots,s_n\rbrace$. Our goal is to compute products $s_i\circ s_{i+1}\circ \cdots\circ s_j$.

In their paper "Optimal Preprocessing for answering on-line product queries" Alon and Schieber prove that we can answer each such query in at most $O(\alpha(n))$ steps (where $\alpha$ is the inverse Ackermann function) by using only linear amount of preprocessing.

If it is desired that each query $s_i\circ s_{i+1}\circ \cdots\circ s_j$ can be answered in $O(\log(j-i))$ steps, can one still do this with only linear preprocessing?

(This question is inspired by this recent question by Brendan McKay at Mathoverflow.)

Construct an ordered balanced binary tree with $s_1,\dots,s_n$ in the leaves (in order).  In each internal node $v$ store the product of the leaves of the subtree rooted at $v$.  This preprocessing obviously runs in O$(n)$ time and space.

Now, to compute a product $s_i\circ\ldots\circ s_j$ (where $i<j$) walk the tree up from $i$ to the least common ancestor (LCA) of $i$ and $j$.  Collect the products stored in each right child hanging off the path, excluding the right child of the LCA.  In other words, as you go up from $u$ to its parent $v$, if $u$ is a left child of $v$, then pick up the product stored in $v$'s right child.  Similarly, walk up from $j$ to the LCA and collect the products stored in left children hanging off that path.  Multiply all these products, along with $s_i$ and $s_j$ in order.


Quantum GCD circuit: On reversibility and clearing ancillae Originally posted on PHYS, however, obviously it has more to do with CS

I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my work, I partially proceed from the paper Quantum Circuits for GCD Computation with O(nlogn) Depth and O(n) Ancillae published by I. Markov and M. Saeedi in 2013, which may be found at arXiv http://arxiv.org/abs/1304.7516.

The paper introduces a binary GCD algorithm analogue and works out a design of the quantum circuit which is clarified in least details, however, in the same time it is somewhat confusing due to several statements that actually do not correspond with the rest of the work. First of all, let me enclose an image denoting design of the circuit.

(Credit goes to the paper)

As you may see, the circuit entirely corresponds to the classical binary GCD algorithm. It takes advantage of quantum circuits for comparison, bit shift, addition and multiplication. Nevertheless, in our case those functions are controlled by state of ancillary qubits and thus, they may not regarded reversible on their own. It means, we have to account for a separate register of auxiliary qubits which cannot be erased till the end of our computation as it would simply violate desired reversibility otherwise.

But in contrast to that, in the paper we may find at least three statements which do actually deny those simple facts. Let me cite: (About preceding works) The authors did not clear all zero-initialized ancillae which limits the applicability of their techniques. (About the circuit) The zero-initialized ancillae may be modified in-side a given circuit, but should be returned to zero at the end of computation to be reused.  (About implementation) To count ancillae, note that all computational ancillae are cleared inside each block. After the final multiplication block for R·B, one can copy (in log depth) the final GCD result to another n-qubit zero-initialized register and apply the whole circuit (except for copying the result) in reverse order to recover A,B, and zero-initialized ancillae. Given that all components use O(n) ancillae, the total number of ancillae remains linear.

I ask myself: How can be all ancillaes cleared at the end of each computational block while the binary GCD seems to be reversible only with regard to an auxiliary register of control qubits? It is apparent this question reduces to the problem of binary GCD reversibility which is actually something I am doubtful about. Maybe I lack of insight and the usage of other control bits is so obvious so as to omit it, however, in every case I would like to ask you about your view on the problem.

It looks like they just directly translated the algorithm into a circuit, so it's not too hard to reproduce.

Write out the binary gcd algorithm as a loop:

def gcd(a, b):
    let shift = 0
    while a != 0 or b != 0:
        let pa = a & 1
        let pb = b & 1
        let pc = a >= b

        if pa == 0 and pb == 0:
            a >>= 1
            b >>= 1
            shift++
        elif pa == 0:
            a >>= 1
        elif pb == 0:
            b >>= 1
        elif pc:
            a -= b
            a >>= 1
        else:
            b -= a
            b >>= 1

    return (a | b) << shift

Keep track of any intermediate values so you can uncompute them instead of leaking them. Also switch to a fixed number of iterations to avoid leaking the size of the inputs.

def gcd(a, b, len_a, len_b):
    let shift = 0
    # Note: >> and << are now bit rotations instead of bit shifts
    for i in range(len_a + len_b):
        let g = a > b
        let pa = (a & 1) == 0
        let pb = (b & 1) == 0

        if pa and pb and a != 0 and b != 0: shift++
        if pa: a >>= 1
        if pb: b >>= 1
        if not pa and not pb:
            if g:
                a -= b
                a >>= 1
            else:
                b -= a
                b >>= 1

        # We can't clear these yet, so just set them aside until later
        push g, pa, pb

    let result = (a | b) << shift

    # Uncompute intermediate values
    for i in range(n + m):
        pop pb, pa, g

        if not pa and not pb:
            if g:
                a <<= 1
                a += b
            else:
                b <<= 1
                b += a
        if pb: b <<= 1
        if pa: a <<= 1
        if pa and pb and a != 0 and b != 0: shift--

        unlet pb = (b & 1) == 0
        unlet pa = (a & 1) == 0
        unlet g = a > b

    unlet shift = 0
    return result

Convert to a circuit.

(Edit: oops, I forgot the shift part. You'll have to add that part in yourself.)

It takes $O(n)$ iterations to guarantee the inputs have been reduced all the way down, and each iteration requires $\Omega(\lg n)$ depth and $O(n)$ gates so the overall bound is $O(n^2)$ gates and $O(n \lg n)$ depth.

Now, all that being said, you need to be wary of the fact that the result is not totally coherent. Before doing interference-y stuff with it, I'd want to be a lot more careful about ensuring the stashed ancilla are independent of the computed gcd. Also you'd want to do any computation in the middle so that the result doesn't have to co-exist with the inputs.

But I hope this gives the general idea.


Does p-isomorphism preserve phase transition? Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other must also have phase transition, with respect to some (possibly different) order parameter?

Intuitively, I would expect that the answer is yes. The reason is that p-isomorphmism means that the two languages are "essentially the same," apart from a polynomial-time re-encoding. It would appear quite surprising if one of them has phase transition, while the other does not, despite their p-isomorphism. But how can the implication be proved formally?

Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L_1, L_2$, and $L_1$ exhibits a phase transition with respect to some parameter $m(x)$. Then so does $L_2$, with respect to the parameter $m_2(y) := m(\varphi^{-1}(y))$. (This relies on the fact that "phase transition" talks about the fraction of satisfiable instances jumping from 0 to 1, as a fraction of an exponential number of instances of a given size, and p-isomorphisms preserve densities up to a polynomial.)

I'm not sure this is such a meaningful statement, however, because the parameter $m_2$ above can be totally unnatural from the point of view of $L_2$. Most phase transitions of interest are with respect to some natural parameter (e.g. clause-to-variable ratio in k-SAT, density of a graph, etc.). But those natural parameters are defined in terms of some "internal" structure to the instances, not by just treating the problem instances as abstract strings in $\Sigma^*$ ($\Sigma$ your finite alphabet). But p-isomorphism does just treat inputs as abstract strings, and "knows nothing" about the internal structure that we like to impose on them. So, sure, you can say that all paddable languages have a phase transition since k-SAT does. But that doesn't tell you if, for example, solvability of quadratic Diophantine equations exhibits a phase transition in terms of any parameter that is natural from the point of view of Diophantine equations...


VC Dimension generalized to discrete, non-binary, unordered domains? VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ordered domains: i.e. $f:X\rightarrow \mathbb{R}$. Is there a standard generalization of VC-dimension suited to functions with discrete, unordered domains? i.e. $f:X\rightarrow K$ where $K$ is a finite set with no ordering on it.

Yes - I think you are looking for "multiclass VC dimension," and there are a couple different generalizations of VC dimension to multiclass classification.  A good paper on this is by Ben-David et al. ('95). In addition to proving learnability results, they give a nice history and references to previous extensions of VC dimension to the multiclass case.  Another perhaps relevant work by Haussler and Long ('95) generalizes Sauer's lemma to more general versions of VC dimension.


Complexity of Unique s-t-Connectivity I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace):

Given a directed graph $G$ with two distinguished vertices $s$ and $t$, is there a unique path from $s$ to $t$ in $G$?

I feel that it is likely to be in $\mathsf{NL}$ since we can decide both if there is a $s$-$t$-path and if there is no such path. Yet, counting the number of such paths is $\mathsf{\sharp P}$-hard (Valiant, 1979).

So my questions: Do you have references about this? Is it obvious that it is in $\mathsf{NL}$? Or that it is not in $\mathsf{NL}$?

It seems your problem is in $NL$. Here is an algorithm.
First, nondeterministically guess a path from $s$ to $t$. If you guess incorrectly, reject. Call this algorithm $A$.
Consider the following nondeterministic algorithm $B$, which determines if there are at least two paths. Given a graph and $s,t$, for all pairs of distinct edges $e,f$, guess a path from $s$ to $t$ that includes $e$ but not $f$, then guess a path from $s$ to $t$ that includes $f$ but not $e$. If the guesses are correct, accept. If no acceptance occurs for all choices of $e$ and $f$, reject. Note $B$ is implementable in nondeterministic logspace.
Now, the set $L(B)$ is the set of $s$-$t$ graphs with at least two paths from $s$ to $t$. Because $NL = coNL$, the complement of $B$ is also in $NL$, i.e., we can determine if $s$ and $t$ have less than two paths, in nondeterministic logspace.
The final algorithm is: "Run $A$. If $A$ accepts, then run the complement of $B$ and output its answer."
I don't know of a reference.
UPDATE: If you really want a reference, check out the first paragraph of Section 3 of this paper. But this is probably only one of many references that cite this consequence. It would be more reasonable to call the result "folklore" rather than citing a paper that happens to mention it.
UPDATE 2: Let's suppose you want to determine if there is a unique simple path. In that case, algorithm $A$ doesn't have to change: if there is a path at all then there is a simple path. I believe the following modification will work for algorithm $B$.
We want to rewrite algorithm $B$ so that it accepts iff there are at least two simple paths.
First consider the following polynomial-time algorithm for the problem. Find a shortest path $P$ from $s$ to $t$. For every edge $e$ in $P$, check if there is another $s$-$t$ path that does not go through $e$. If you find such a path then accept. If you never find another path then reject. Because $P$ is shortest, it does not have a cycle, and if there is another path that doesn't use some edge of $P$, then there is another path which is simple and doesn't use some edge of $P$. (This algorithm is used for the "second shortest paths" problem.)
We will implement this algorithm in $NL$. If we had an $NL$ algorithm for querying the edges $e$ in a fixed path $P$, we could implement the above in nondeterministic logspace: iterating through all edges $e$ in $P$, guess an $s$-$t$ path and check that for every edge visited along the way, none of them are equal to $e$.
So what we need is a "path oracle", an $NL$ algorithm with the property: given $i=1,\ldots,n$, in every computation path the algorithm either reports the $i$th edge on a particular fixed $s$-$t$ path, or reject. We can get a path oracle by using $NL=coNL$ to isolate the lexicographically first path.
Here is a sketch of the path oracle.

Find $k$, the length of the shortest path from $s$ to $t$, by trying all $k=1,\ldots,n$ and using $NL=coNL$.
Set variables $u:=s$, $x:=1$, $j:=k$.
For all neighbors $v$ of $u$ in lexicographical order,
Determine whether or not there is a path from $v$ to $t$ of length $j-1$ (using the result $NL=coNL$).
More precisely, run the nondeterministic algorithm for $s$-$t$ connectivity (of length $j-1$) and the algorithm for its complement, simultaneously. When one of them accepts, go with its answer (it must be correct; both cannot accept). If both reject then reject.
If there is no path, proceed to the next neighbor. If you've exhausted all neighbors then reject.
If there is a path, then if $x=i$, output $(u,v)$ as the $i$th edge on the path from $s$ to $t$. Otherwise increment $x$, decrement $j$, set $u := v$, and start the for-loop again if $v \neq t$.
If $x < i$ after reaching $t$ output bad $i$ (the given $i$ was too big).

Given $i$, this algorithm either outputs the $i$th edge on the lexicographically shortest path $P$ from $s$ to $t$, or rejects.


Deciding whether a unary context-sensitive language is regular It is a well-known result that the question

  Does a context-free grammar generate a regular language?

is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case, the classes of context-free and regular languages coincide.

My question is to know what happens for unary context-sensitive languages.

  Is it decidable to know whether a given context-sensitive grammar on a
  unary alphabet generates a regular language.

If the answer is positive, an estimation of the complexity would be welcome.

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate that there is a unary CSL $X$ which isn't regular (in contrast to the positive result for unary CFLs), and then reduces from the halting problem for Turing machines by, given a TM $M$, constructing a CSG $G$ which simulates $M$ on a length of tape shorter than the parse string $w$, recognising $X$ if $M$ halts without overstepping its bounds and failing to parse otherwise, so that $G$ successfully parses all $w \in X$ that are sufficiently long iff $M$ halts (so that $L(G)$ differs from $X$ on only finitely many strings and therefore cannot be regular), otherwise $G$ recognizes the empty language (which is clearly regular).

Key to this approach is the observation that CSGs are not merely concerned with grammatical matters such as phrase structure -- indeed, CSG derivation sequences can carry out arbitrary nondeterministic space-bounded computation (indeed there are $\mathbf{PSPACE}$-complete CSLs) before ever getting to the business of aligning with the parse string. This is most easily observed via standard conversions between CSGs and monotonic grammars (which continues to work when restricted to unary alphabets), and the use of simple monotonic productions to simulate Turing machine transitions on derivation strings which represent stages in a computation history. Throughout this answer I'm going to assume the reader can intuit most of the details when a CSG is required to simulate a given computation. (I assume the asker is comfortable with all of this, but I'm going over it for completeness. Nevertheless, feel free to request clarification in the comments.)

Firstly, we need our non-regular unary CSG. (EDIT: so, this was overkill -- non-regular unary CSLs can easily be exhibited e.g. via the pumping lemma on any language which exhibits the most basic of non-regularity. See the comments for examples. In hindsight, using a diagonal argument was like bringing a nuclear warhead to a knife fight. Peruse this construction if you're curious, otherwise skip to the reduction.)

Let $D_1, D_2, ... $ be an enumeration of DFAs over alphabet $\{1\}$, such that the number of states in $D_i$ increases in $i$. We describe a CSG $G_X$ in terms of its behaviour whilst parsing string $1^n \in \{1\}^*$:

Nondeterministically generate a string of $n$ "blank" non-terminals, which we think of as the "tape". One of the blank non-terminals should be a separate "blank + read-write head + start state" non-terminal. If the parse string isn't $1^n$ then this derivation will end up failing. We describe the rest of the process in terms of the deterministic computation simulated by the only possible derivation.
Print on the tape an encoding of $D_i$ followed by the number $i$ in binary, where $i = n - c$ and $c$ is chosen so that we always have enough space on our tape to do what we need to. (This is possible since the space required to encode both $D_i$ and $i$ grows logarithmically in $i$.)
Evaluate $D_i$ on input $1^i$. This doesn't require a representing $D_i$'s tape -- you can just store a single state, which you change according to the transitions of $D_i$ as you decrement $i$.
If $D_i$ rejects $1^i$, overwrite the entire tape with non-terminals which produce $1$. Otherwise fail.

We take $X = L(G_X)$. Clearly $X \ne L(D_i)$ for any $i$, since $1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$.

The next step is to design a reduction from the halting problem to the asker's problem. (If you skipped the above section, let $X$ be an arbitrary non-regular unary CSL generated by CSG $G_X$.)

Let $M$ be an arbitrary TM. We convert $M$ into a CSG $G$ which behaves as follows on parse string $1^n$:

Generate $n-2$ blank non-terminals, the leftmost one being the separate blank + read-write head non-terminal, and also generate a "boundary" non-terminal on each side. Again, if we generate the wrong number of non-terminals then we fail.
Simulate $M$ in the space between the boundary non-terminals. If $M$ ever shifts onto one of the boundary states, we terminate the simulation and assume that $M$ never halts.
If $M$ halts, behave like $G_X$. If we had to terminate the simulation, then fail.

Note that if $M$ manages to run forever within the boundaries then $G$ can never generate a parse string and so will fail. If $M$ halts, then there is some amount of space $n$ which suffices to contain $M$'s entire computation, hence $G$ parses $1^m$ whenever $m \ge n+2$ and $1^m \in X$, and hence $X$ is the union of $L(G)$ and a finite language, whence $L(G)$ is not regular. On the other hand, if $M$ never halts, then $L(G) = \varnothing$ is clearly regular.

An algorithm for deciding whether $L(G)$ is regular or not would determine whether or not $M$ halts on a blank tape, which is undecidable. It follows that the asker's problem is undecidable.