Is there any good and free Introduction to topological graph theory

My lecture notes on computational topology include some basic material on topological graph theory.  They don't come anywhere close to the completeness of Archeacon's survey (or Giblin's book, Mohar and Thomassen's book, or Gross and Tucker's book), but you may still find them useful.  (Start with "Curves on Surfaces".)

If you're a student, you may also find your local university library useful.  Most mathematics libraries have copies of all the books I mentioned, and they will actually let you borrow them for free, possibly for several months at a stretch.  Sadly, these books may only be available in a legacy format that is difficult to search and copy from, but hey, you get what you pay for.


Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

For the sake of completeness, I'll note that my version of the proof appears in

NdB. A linearized stabilizer formalism for systems of finite dimension. Quantum Information & Computation 13 (pp. 73–115), 2013. [arXiv:1102.3354v4]

appearing as Lemma B.3 (page 38) in the published version, and Lemma 12 (page 23) in the arXiv preprint; in both cases occuring in Appendix B.

If anyone can point to an reference to a proof which is older than this question, I'll accept and reward the earliest such reference which is provided.


Space complexity to compute the optimal string alignment for the Levenshtein edit distance

There is no need for the tradeoff that Yuval suggests.  The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg.  (A linear space algorithm for computing maximal common subsequences.  Commun. ACM 18(6):341–343, 1975.)

Intuitively, Hirschberg's idea is to compute a single editing operation halfway through the optimal edit sequence, and then recursively compute the two halves of the sequence.  If we think of the optimal edit sequence as a path from one corner of the memoization table to the other, we need a modified recurrence to record where this path crosses the middle row of the table.  One recurrence that works is the following:

$$
Half(i,j) = \begin{cases}
   \infty & \text{if $i<m/2$}\\
   j & \text{if $i=m/2$}\\
   Half(i-1,j) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\
   Half(i,j-1) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\
   Half(i-1,j-1) & \text{otherwise}
\end{cases}
$$

The values of $Half(i,j)$ can be computed at the same time as the edit distance table $Edit(i,j)$, using $O(mn)$ time.  Since each row of the memoization table depends only on the row above it, computing both $Edit(m,n)$ and $Half(m,n)$ requires only $O(m+n)$ space.

Finally, the optimal editing sequence transforming the input strings $A[1..m]$ into $B[1..n]$ consists of the optimal sequences transforming $A[1 .. m/2]$ into $B[1 .. Half(m, n)]$ followed by the optimal sequence transforming $A[m/2 + 1 .. m]$ into $B[Half(m, n) + 1 .. n]$.  If we compute those two subsequences recursively, the overall running time obeys the following recurrence:
$$
T(m,n) = \begin{cases}
  O(n) & \text{if $m\le 1$}\\
  O(m) & \text{if $n\le 1$}\\
  O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right)  & \text{otherwise}
\end{cases}
$$
It's not hard to prove that $T(m,n) = O(mn)$.  Similarly, since we only require space for one dynamic-programming pass at a time, the total space bound is still $O(m+n)$.  (The space for the recursion stack is negligible.)


Goldberg&Tarjan: How to find a blocking flow in a graph

They gave the wrong reference, for whatever reason, as have you have found out by yourself.

The blocking flow method you are supposed to use is the one given in

http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf,
Section 8.3.


What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

Almost all graphs have trivial automorphism group. So all you need to do is generate a graph uniformly at random (see e.g. http://en.wikipedia.org/wiki/Random_graph), then compute its automorphism group (or just determine its order). Repeat until you find a graph with trivial automorphism group (also called a rigid graph).


Is the complement of { www | … } context-free?

Still CFL I believe, with an adaptation of the classical proof.  Here's a sketch.

Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the words of length not $0$ mod $3$ removed.

Let $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$.  Clearly, $L'$ is CFL, since you can guess a position $p$ and consider that $u$ ends $p/2$ after that.  We show that $L = L'$.

$L \subseteq L'$: Let $w = xyz \in L$.  Assume there's a $p$ such that $x_p \neq y_p$.  Then write $u$ for the $3p/2$ first characters of $w$, and $v$ for the rest.  Naturally, $u_{2|u|/3} = x_p$.  Now what is $v_{|v|/3}$?  First:

$$|v|/3 = (|w| - 3p/2)/3 = |w|/3 - p/2.$$

Hence, in $w$, this is position:
$$|u|+|v|/3 = 3p/2 + |w|/3 - p/2 = |w|/3 + p,$$
or, in other words, position $p$ in $y$.  This shows that  $u_{2|u|/3} = x_p \neq y_p = v_{|v|/3}$.

If $y_p \neq z_p$, then let $u$ be the first ${3\over2}(|w|/3 + p)$ characters of $w$, so that $u_{2|u|/3}$ is $y_p$; $v$ is the rest of $w$. Then:
$$|u| + |v|/3 = 2|w|/3 + p$$
hence similarly, $v_{|v|/3} = z_p$.

$L' \subseteq L$: We reverse the previous process.  Let $w = uv \in L'$. Write $p = 2|u|/3$. Then:
$$p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$$
Thus $w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$, and $w \in L$ (since if $w$ is of the form $xxx$, it must hold that $w_p = w_{p+|w|/3}$ for all $p$).


What is the time complexity of computing a Fibonacci number of at least n?

It is known that
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.
$$
Using this, compute $F_1,F_2,F_4,\ldots,F_{2^m}$ until $F_{2^m} \geq n$. Then use binary search to recover the minimal Fibonacci number exceeding $n$.

Since $F_r$ grows exponentially in $r$, we have $2^m = \Theta(\log n)$ and so $m = \Theta(\log \log n)$. The algorithm thus runs in $O(\log\log n)$ steps. Each one involves calculation with numbers of size $O(\log n)$, so the overall complexity is $\tilde{O}(\log n)$.


For a given binary-search tree obtain an isomorphic splay tree

It can be done with a linear number of operations.

Suppose you start with an arbitrary given tree $T_0$ over keys $[n]$ and want to reach an arbitrary given $T$ over keys $[n]$ using splay operations. (In case we have to start with the empty tree, just insert $[n]$ in any order.)

A result of Cleary [*1] (see also Lucas [*2]) shows that you can get from $T_0$ to $T$ using $O(n)$ normal rotations, even if you restrict yourself to rotations at the root and at the right child of the root.

Let's try to simulate these restricted rotations with splay operations. Rotation at the root is easy, just splay the corresponding child.

What about rotations at the right child? There are two cases (see figure).

The first case (left to right) is easy: splay y, then splay x.

The second case (right to left) is more tricky:

Suppose z has a right child t. Then we can:

splay t, then splay z, then splay x, obtaining the required rotation.

We had to assume that t exists. We can make sure of this, by inserting an $\infty$ key element in the beginning and making sure that it will always remain a leaf. We can make sure it is a leaf in the beginning, for instance by splaying $\infty$, and then 1,2,3,...,n. Afterwards, t $=\infty$ is never splayed, except if the above situation arises where it is the right child of z, and then we can see that it stays a leaf after the transformation.

In the end, we just need to clip away this leaf and get the target tree $T$. This last step is a bit of cheating, since a proper splay deletion would clip away the leaf, then splay its parent.

We can get around this cheating by deleting $\infty$ earlier, i.e. the last time when the above right-to-left transformation involving $\infty$ happens. Then, after the splay z and before the splay x steps, we can do a proper splay-delete t (t $= \infty$) operation, and since t is the child of the root at that time, no unintended side-effect happens.

A (perhaps simpler) alternative formulation is that, if in the above right-to-left transformation z has no right child, then we do the sequence:
insert(n+1), splay(z), delete(n+1), splay(x). (assuming that insert works by inserting as a leaf and then splaying an element).

[*1] S. Cleary, Restricted rotation distance between binary trees,
Inform. Process. Lett. 84 (2002) 333–338

[*2] J. Lucas, A direct algorithm for restricted rotation distance,
Inform. Process. Lett. 90 (2004) 129–134


How hard is deciding the existence of Red-Blue perfect matching?

As Mikhail noted, the problem was called Perfect Matching Cut in literatures. It was proved to be NP-complete in the following paper (see Theorem 1 on page 5), with a reduction from monotone 1-in-3-SAT:

Pinar Heggernes, Jan Arne Telle. Partitioning Graphs Into Generalized Dominating Sets.


Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make the algorithm look bad (chosen before the hash function's random seed is known, for a specific 2-independent hash function that is also chosen to make the rest of the algorithm look bad). So it shouldn't be surprising that with two different input models you get two different results.


The figure appears to come from the paper "Games, Logic, and Computers" by Hao Wang, which appeared in Scientific American, Volume 213, Number 5, November 1965, pages 98-106.  There is a copy online here:

http://www.cs.virginia.edu/cs200/readings/wang.pdf

In case you're wondering how I found it, I googled 'Turing machine "memory dial"'.  None of my Turing machines have a memory dial, so I was hoping to learn where to buy one.


Effective algorithm of searching the "nearest" doubly stochastic matrix

This is a special case of the following problem: given a polytope $P$ specified by linear constraints and a point $x$ find $y \in P$ that minimizes $\|x - y\|_2^2$.

If you are ok with a small additive approximation to $\|x - y\|_2^2$, you can try using the Frank-Wolfe algorithm. This is a sort of gradient descent algorithm. You start from a point $y_0 \in P$ (in your case this could be say the $n \times n$ matrix with $1/n$ in every coordinate) and in each steps you compute $y_{i+1}$ from $y_i$ as follows:

Let $w = x - y_i$.
Let $v$ be the vertex of $P$ that maximizes $w^Tz$ for $z \in P$ (can be found by LP).
Find the point on the line through $y_i$ and $v$ that is closest to $x$ (this is quadratic optimization in a single variable). This point is $y_{i+1}$.

Ken Clarkson has analyzed this simple algorithm. In $t$ steps, the additive approximation is bounded by $d(P)^2/t$, where $d(P)$ is the diameter of $P$. In your case, I believe $d(P) \leq \sqrt{n}$, as the vertices of $P$ are permutation matrices and they all have Frobenius norm $\sqrt{n}$. So in $O(n/\epsilon)$ iterations of the above algorithm you can get $Q$ such that  $\|D - Q\|_F^2 \leq \|D - Q^*\|_F^2 + \epsilon$, where $Q^*$ is the optimal solution.


Was counting complexity first introduced by Valiant in 1979?

Yes, the complexity class $\mathsf{\#P}$ is first introduced in Valiant's seminal paper "The complexity of computing the permanent." TCS, (1979).  This is very clear. As for the terminology, strictly speaking, Valiant does not use the term "counting complexity" in this paper. Instead, he speaks of "counting problems" in several places. In any case, it is probably hard to tell who coined these terms first, but this is probably also not very important.

What remains important is the fact that the complexity class $\mathsf{PP}$ (which, intuitively, is the decision-theoretic variant of $\mathsf{\#P}$) had already been introduced in 1974, by Gill's seminal paper "Computational complexity of probabilistic Turing machines". In this sense, Valiant was very much influenced by Gill's work. In fact, Valiant cites Gill's paper and loosely tells that #P is essentially equivalent to $\mathsf{PP}$ (which is not meant in the strict, formal sense).


Halting time of non deterministic machine

Claim: $S\subseteq NEXP$.

To prove it, take $L\in S$. It follows that there exists a machine $K$ s.t. $L=S(K)$. I imagine $K$ to be a Turing machine because I am more familiar with them. Now $n\in L$ iff there exists some computation of $K$ on empty input of length $n$. So we can verify whether $n\in L$ by non-deterministically guessing first $n$ steps of $K$ on empty input and verifying whether $K$ halts after this $n$ steps. $\square$

Considering that the problem of verifying whether a non-deterministic TM makes at most $n$ steps on empty inpuit on some computation is NEXP-complete (NEXP-complete problems), I would guess that $S$ contains arbitrary hard NEXP problems.


Uniform way of quantifying "branching" in nondeterministic, probabilistic, and quantum computation?

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs can be. While I don't know of papers that studied this question, this could give you a direction of where to look for them.
One paper that studied a related question in the context of interactive proofs is "On Interactive Proofs with Laconic prover", by Goldreich, Vadhan, and Wigderson:
http://www.wisdom.weizmann.ac.il/~oded/p_laconic.html

Regarding probabilistic computation: The amount of "branching" used in the computation is exactly the number of random bits/coin tosses that the algorithm uses. Quantifying this number and minimizing it is studied extensively in the area of "Derandomization". You can read about it in Chapters 20 and 21 of the Arora-Barak book (http://www.cs.princeton.edu/theory/index.php/Compbook/Draft) or in Chapter 8 of Goldreich's book (http://www.wisdom.weizmann.ac.il/~oded/cc-book.html).
It should also be mentioned that the common belief in this area is that $P=BPP$. If this is true, then the number of random bits a computation uses does not affect its power, as long as this number is polynomial.


Euclidean TSP in NP and square root complexity

Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, rather, how close the sum of square roots of integers can get to an integer, without actually being integral.

Q2. The $n=1$ case is of course easy. It's the same as $q \le A^2$, which is in polynomial time, because squaring a rational number is in polynomial time.

Q3. According to this page, the best that's known is that there are integers $a_1, \ldots, a_k, b_1, \ldots, b_k$, all between $1$ and $n$, such that $| \sum_{i = 1}^k \sqrt{a_i} - \sum_{i = 1}^k \sqrt{b_i}| = O(n^{-2k + 3/2})$. This is a lower bound of $\Omega(2k\log n)$ on the number of bits needed to be computed for the potentially harder problem which allows negative coefficients. The best upper bound on the number of bits is exponential in $k$.

Q4. I think the decimal representation could be quite inefficient. The length of the period is the multiplicative order of 10 modulo the denominator, which can be exponential in the number of bits of the denominator.


I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states.
An exponential lower bound on $f$ can be given as follows.
Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that reading a 1 we go ahead by one until we reach the end, i.e., $\delta_1(v_i)=v_{i+1}$ for $i<k$, while $\delta_1(v_k)=v_k$, but if we read a 0 before the end we have to start all over again, i.e., $\delta_0(v_i)=v_1$ for $i<k$, while $\delta_0(v_k)=v_k$.
If the initial states are $v_1$ and $v_k$, then the question is how fast we reach the terminal state in this simple Markov-chain; in expectation this is about $k2^k$.


Minimum number of real multiplications to multiply two quaternions

de Groote showed that one could compute both $uv$ and $vu$ using only a total of 10 non-scalar multiplications.

Howell and Lafon, in a tech report (that I could not find a refereed version of and have not checked myself, but is probably correct) showed that one can do quaternion product with only 8 multiplications.

7 is certainly a lower bound, as noted in both of the above papers.

(While this was an interesting question and fun to look up, I found the answer in about 5 minutes of Googling. Google is your friend.)


Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

VC-dimension has multiple multiclass extensions:
pseudo dimension, Natarajan dimension, graph dimension.
See here for example:
http://math.huji.ac.il/~amitd/multiclass.pdf
http://jmlr.org/papers/volume8/guermeur07a/guermeur07a.pdf

There are also extensions to continuous-valued functions (fat-shattering dimension):
http://users.cecs.anu.edu.au/~williams/papers/P53.pdf


How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2.
The crucial reference is

  Theodore Motzkin and Ernst Strauss  (1965)
  "Maxima for graphs and a new proof of a theorem of Turan"
  Canadian Journal of Mathematics 17, pp 533-540

Motzkin and Strauss consider an undirected graph $G=(V,E)$
with vertex set $V=\{1,2,\ldots,n\}$.
They show that the optimal objective value of the following optimization problem equals $1-1/\omega$, where $\omega$ is the clique number of $G$:

\begin{eqnarray*}
\max &&\sum_{ij\in E} x_ix_j \\[2ex]
s.t. &&\sum_{i\in V} x_i=1 \\[1ex]
&& 0\le x_i\le 1~~~ \text{ for all $i\in V$}
\end{eqnarray*}

Since computing the clique number is NP-hard, this implies the NP-hardness of maximizing a multivariate polynomial function subject to linear constraints.


Meaning of P=NP? depends on space-time geometry ?

P=NP is a well-defined mathematical question which does not depend on space-time geometry. The question "which problems can be solved by computations that are tractable in this universe?" may depend on physics, and the answer does indeed appear to change in hyperbolic space or with quantum mechanics (e.g. quantum computing). However, this doesn't affect the P=NP question.

In fact, one of the first reactions of a theoretical computer scientist would have to your reference is: "What complexity class can be computed by a cellular automaton in hyperbolic space?" If you redefine complexity classes when you change to hyperbolic space, it becomes much harder to talk about this question.

And if you look later in the book, the author defines P$_h$ as problems solvable in polynomial time on a hyperbolic cellular automaton, and proves P$_h$=PSPACE (and NP$_h$=P$_h$=PSPACE), so even the author isn't really taking complexity classes to change in hyperbolic space.


Efficiently computable by a "simple" algorithm?

Elaborating on my comment as suggested by OP:

Let us start by giving definitions to the two definitions for program complexity as suggested by the other commenters and me.

Definition (Kolmogorov complexity of $L$): Let $L$ be some language. We define the Kolmogorov complexity $K(L)$ of $L$ to be the (description) length of the smallest program which decides $L$ (using some fixed programming language) or $\infty$ if no such program exists.

Definition (State complexity of $L$): Let $L$ be some language. We define the state complexity $S(L)$ of $L$ to be the minimal number of states a TM which decides $L$ needs to have or $\infty$ if no such TM exists.

The first observation we make is that there are only finitely many programs of length $n$ (and the same holds for Turing machines if we fix the alphabets and state names). It follows that any infinite class $\mathcal C$ of languages and any $m \in \mathbb N$, there is some language in $\mathcal C$ which has a Kolmorogov complexity which is at least $m$ (and the same holds for state complexity).

Indeed, this means that even problems which can be decided in constant time can have an arbitrarily large program complexity, which makes me pessimistic about the existence of results that imply that a large program complexity incurs a large runtime complexity. What about the converse statement?

The same argument from above yields directly that if we have two (infinite) decidable complexity classes $\mathcal{C}_1$ and $\mathcal{C}_2$, then for any $L_1 \in \mathcal{C}_1$ there must exist some $L_2 \in \mathcal{C}_2$ with $K(L_2) > K(L_1)$ (and the same result holds for state complexity) as $K(L_1)$ is finite (by decidability) and he program complexity for any infinite complexity class is unbounded. Even stronger, it follows that there exist infinitely many such $L_2$ and the difference in program complexity can be arbitrarily large (again by the first observation). In particular, one can deduce that for any decidable language, there exist infinitely many languages with (arbitrarily) larger program complexity but constant time complexity.


What techniques are used for proving algorithms optimal?

Intuitively, proving that a problem in P requires, say, time $\Omega(n\log n)$ is not any easier than proving the same lower bound for SAT. In fact, proving this lower bound for SAT should be easier, because we think SAT is harder than any problem in P. Concrete examples are matrix multiplication or fourier transform over GF(2). These are polynomial time problems but we don't have superlinear lower bounds.

One notable exception are time hierarchy results which give you (artificial) problems that are solvable by a Turing machine in time $O(t(n))$ but not solvable in time $O(t(n)/\log(n)).$ These results are proved via diagonalization.


Genetic Algorithm convergence test functions

One-max is really only suitable for testing for obvious bugs in your implementation.

There are a few widely used sets of benchmark functions, but they're of rather dubious value in general as well. You don't mention what sort of domain you're planning to work on -- there are binary problems like Knapsack problems, real-valued problems (which may or may not be represented with binary encodings in a given GA), permutation problems like TSP, QAP, and some scheduling problems, etc.

Some of the more popular benchmarks have always been real-valued function optimization problems. Griewangk's function, Rastrigin's function, Ackley's function, Rosenbrock's function, and the De Jong F1-F5 functions have all been used pretty heavily in the literature (as well as others). There are also shifted and rotated versions of several of those problems that attempt to work around some of the more obvious biases and deficiencies such as the optimum of most of them being at the origin.

There have been a few attempts at producing good sets of benchmarks. There was a 2005 CEC workshop that proposed 25 or so real-valued problems. I think there was another workshop in 2010 that might have included a different set of problems, but I'm hazy on the details now.

I haven't been able to provide you with much in the way of concrete information about particular test functions, but hopefully there's enough here to get you started with Google.


Complexity of maximising weighted sum of and functions on a set of binary variables

(1) has a polynomial solution. Consider a graph with source $s$, sink $t$, vertices $U$ corresponding to the variables and vertices $V$ corresponding to the functions. If $f_j = x_1 \land \ldots \land x_k$ then add edges $f_j \to x_i$ for each $i \in \{1,\ldots,k\}$ with capacities equal to $C$ for $C > \sum p_j$. Add edges $x_i \to t$ with capacities $c_i$ and edges $s \to f_j$ with capacities $p_j$. Consider minimum cut between $s$ and $t$ in this graph (it could be easily found with almost any maximal-flow algrorithm). Let $U_s \subseteq U$ and $V_s \subseteq V$ be the sets of vertices in the component of $s$. Then the value of the minimum cut is $$\sum\limits_{i \in U_s} c_i + \sum\limits_{j \not\in V_s} f_j = \underbrace{\sum\limits_{j\in V} f_j}_{\text{constant}} - \underbrace{\left(-\sum\limits_{i \in U_s} c_i + \sum\limits_{j \in V_s} f_j\right)}_{\text{objective function}}$$
Thus if this value is minimised, the objective function is maximised. On the other hand $U_s$ and $V_s$ for minimum cut have the property that if $x_1 \land \ldots \land  x_k = f_j \in V_s$ then $x_1, \ldots, x_k \in U_s$ since otherwise the value of the cut is $\ge C$ which is not optimal. Thus setting $x=1$ for $x \in U_s$ and $x=0$ for $x \not\in U_s$ gives an optimal solution for (1).

The case with arbitrary $p_j$ is $\mathbf{NP}\text{-}\mathrm{complete}$ even with polynomially-bounded $|p_j|$.

If you allow $p_j$ to be negative, you can reduce $\mathrm{max}\text{-}\mathrm{SAT}$ to this problem. For each variable $x_i$ of $\mathrm{max}\text{-}\mathrm{SAT}$ add two variables $x_i$ and $\lnot x_i$ to your input. For each of these pair add the condition $x_i \land \lnot x_i$ with the cost $-C$ for a large enough constant $C$. For all clauses of $\mathrm{max}\text{-}\mathrm{SAT}$ input add the corresponding conjunction with all literals reversed: $x \lor \lnot y \lor z$ becomes $\lnot x \land y \land \lnot z$ (here $\lnot x$ and $\lnot z$ are variables in the new problem). $\lnot x \land y \land \lnot z \iff \lnot (x \lor \lnot y \lor z)$ therefore each unsatisfied conjunctions correspond to satisfied clauses. Thus you can set the cost $p$ for each conjunction as $-1$. For $c_i = 0$ for all $i \in \{1,\ldots, n\}$, $m -\max \left\{\sum\limits_j f_j p_j - \sum\limits_i a_i c_i\right\}$ (where $m$ is the number of clauses in the $\mathrm{max}\text{-}\mathrm{SAT}$ instance) is the maximum number of clauses that could be satisfied in the instance of $\mathrm{max}\text{-}\mathrm{SAT}$ or a value greater than or equal to $C - n$ if the instance is unsatisfiable. Thus $C = 3n$ is "big enough". I.e. for negative $p_j$ there is no polynomial solution even with bounded $|p_j|$ and $|c_j|$ unless $\mathbf{P} = \mathbf{NP}$.


Estimating a percentile among distributed nodes without revealing values

You seem to ask two related questions:

“which indices in the list correspond to the top”
“Estimating a percentile”, “a number X for which … K% are larger”

These may need very different numbers of pairwise comparisons.

An other aspect that may have significant impact is what information is shared. Everybody knows the number he received, knows the sum, and the yes/no results of comparisons they have taken part in. However, you also say that “parties wish to output of which indices in the list correspond to the top” thus you suggest that some information about the indices will be shared. Depending on what exactly is shared you may get very different solutions again.


Cases of Linear programming known to be in $NC$?

Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential algorithm). The more recent paper by Blelloch et al. shows that the randomized-incremental approach for constant-dimensional LP can actually be parallelized efficiently.

Alon and Meggido (1994): Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Blelloch et al. (2016): Parallelism in Randomized Incremental Algorithms


The Goemans-Williamson algorithm in the $SOS$ framework

Looking at the Goemans–Williamson algorithm in the SOS framework yields no technical advantages: it is exactly the same algorithm and the same ideas are used in the analysis.
The only advantages in doing so are:

Arguably the algorithm seems less "magical" in that viewpoint, though of course that's a matter of taste.
It's a good basic case to get intuition for the SOS framework, and so understanding this algorithm will help in understanding more complicated uses of it.

As Sasho Nikolov points out, a degree 2 pseudo-distribution is simply a positive semidefinite (PSD) matrix, and so finding such a matrix satisfying any particular linear constraints can be done via semidefinite programming. In particular, for any pseudo-distribution $\{ u_i \}_i$ of degree at least 2, the matrix $X_{i,j} = \tilde{\mathbb{E}} u_i u_j$ is PSD.

Given an $n\times n$ PSD matrix $X$, one can find a Gaussian distribution $y\in\mathbb{R}^n$ such that $\mathbb{E} y_iy_j = X_{i,j}$ for all $i,j$ and hence the distribution $\{ y_i \}_i$ matches the second moments of the pseudo-distribution represented by $X$. (One can obtain $y$ by sampling a standard Gaussian vector $z$ and letting $y=X^{1/2}z$.)

The rounding algorithm is to obtain a distribution $w$ over $\{\pm 1\}^n$ by letting $w_i = \textrm{sign}(y_i)$. This is exactly equivalent to the standard description of "hyperplane rounding" whereas one takes vectors $v_1,\ldots,v_n$ such that $X_{i,j} = \langle v_i,v_j \rangle$ and lets $w_i = \textrm{sign}(\langle v_i , z\rangle)$ where $z$ is a random Gaussian vector.

Now we want to compare the value of the pseudo-distribution, which (up to scaling) is the same as the sum of $-X_{i,j}$ over all edges $(i,j)$, with the expected value of our rounded solution $w$, which will be the sum of $- w_iw_j$. So now we want to calculate the probability that the edge will be cut by $w$ as a function of $X_{i,j}$. It all boils down to figuring out the following calculation: if $w_i$ and $w_j$ are two Gaussian random variables with $\mathbb{E} w_i^2 = \mathbb{E} w_j^2 = 1$ and  $\mathbb{E} w_i w_j = \rho$, what would be the probability that their signs agree? I personally think that the most interesting regime for Max-Cut is when the objective value is close to $1$. One nice thing in that regime is that you can get some qualitative insight by showing that if $\rho = -1 +\epsilon$ then their signs agree with probability at most $O(\sqrt{\epsilon})$. However, if you are interested in figuring out the approximation ratio (or more generally figure out the precise trigonometric function behind this $O(\cdot)$ term) then Goemans–Williamson's analysis exactly resolves this calculation.


Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation

Hardness

Following your comment on the question, we will call a circuit where each output bit depends on at most k input bits a “NC0k circuit.”  Using this term, your problem is coNP-complete in case of NC05 circuits.  That is, the following problem is coNP-complete.

Instance: A Boolean circuit C with n input bits and n output bits where each output bit depends on at most five input bits.
Question: Is the mapping from {0,1}n to itself computed by C bijective?

As Kaveh commented, it is clearly in coNP, even without the bound on the number of input bits on which each output bit depends.  To prove the coNP-hardness, we will reduce 3SAT to the complement of the current problem.  The key idea of the reduction is the same as the one used in the paper [Dur94] by Durand, which I mentioned in a comment on the question, but the whole reduction is much simpler in our case.

Given a 3CNF formula φ with n variables and m clauses, we construct a Boolean circuit C with (n+m) input bits and (n+m) output bits as follows.  We label the input bits as x1, …, xn, y1, …, ym, and the output bits as x′1, …, x′n, z1, …, zm.  We consider that the input bits x1, …, xn specify a truth assignment to the n variables in φ.

x′i = xi for 1≤i≤n.  That is, the first n bits of input are always copied to the first n bits of output.
For 1≤i≤m, if the ith clause of φ is satisfied, then zi = yi ⊕ yi+1, where the subscript is interpreted modulo m.  Otherwise, zi = yi.

Note that each output bit depends on at most five input bits.  I omit the proof of the correctness of the reduction, but the key idea (which I borrowed from [Dur94]) is that if φ is satisfiable and input bits x1, …, xn are set to a satisfying assignment of φ, then the m output bits z1, …, zm are constrained to have the even parity, and therefore the circuit cannot be a permutation.  On the other hand, if input bits x1, …, xn are set to a non-satisfying assignment of φ, then output bits z1, …, zm can be set to anything; because of this, if φ is unsatisfiable, then the circuit is a permutation.

Tractability

On the tractable side, your problem is in P in case of NC02 circuits.  This is shown as follows.  In general, each output bit in a Boolean circuit for a permutation is balanced; i.e., exactly half of the input strings set the output bit to 1.  However, every balanced Boolean function from {0,1}2 to {0,1} is affine; i.e., a copy of a single input bit, the XOR of the two input bits, or the negation of them.  Therefore, we can first check that each output bit is balanced, and then check the bijectivity by the Gaussian elimination.

I do not know the complexity in case of NC03 circuits or in case of NC04 circuits.

References

[Dur94] Bruno Durand.  Inversion of 2D cellular automata: some complexity results.  Theoretical Computer Science, 134(2):387–401, Nov. 1994.  DOI: 10.1016/0304-3975(94)90244-5.


[Edit: this answer does not work, see comments.]

This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless.

I will suppose that your bounds should depend on how much $u$ and $v$ differ; if they don't, it seems clear to me that the worst case are strings differing only by their first character (strings differing at a set $X$ of positions have more chances of being told apart than strings differing at a set $Y \subset X$ of positions, I'd say, and putting the difference as early as possible gives you opportunity to resynchronize).

I will also look at the probability that the words are distinguished, namely, they reach different states. I guess you would then need to adapt for being accepted or rejected based on how your random DFAs allocate final states. If each state has a probability 1/2 of being final, then when the strings end up at the same state they are not distinguished, and when they end up at different states they have probability 1/2 of being distinguished.

Now I will consider the word $w$ obtained from $u$ and $v$ as follows: $w_i = 1$ if $u_i = v_i$, and $w_i = 0$ otherwise. I think it is clear that $w$ is the only interesting thing to consider about $u$ and $v$.

Now, define $p(i)$ the probability that we are at the same state after reading prefixes of length $i$ of $u$ and $v$, and $q(i) = 1 - p(i)$ the probability that we aren't.

I think we have $p(i+1) = p(i) + q(i)/n$ when $w_{i+1}$ is $1$. Intuitively, we are at the same state after reading $i+1$ letters either when we were at the same state after reading $i$, or when we were at two different (random) states, we drew two transitions to random states, and they happened to be the same one. Likewise, we have $p(i+1) = 1/n$ when $w_{i+1}$ is $0$: you are drawing two random states, no matter where you started from.

From this I think you could compute the probability of being at the same state after reading $u$ and $v$.


Caution: As Jukka Suomela commented on the question, the page linked from the question is about a problem different from the problem stated in the question in that the problem on the page has a restriction that the lengths of given sticks are greater than or equal to n.  This answer is about the problem without this restriction.  Since Emil’s comment on the question refers to the problem with the restriction, there is no contradiction between his comment and the following answer.

The problem is NP-complete, even if the numbers are given in unary.

The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an in unary, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.
Question: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

The 3-partition problem is NP-complete even if a1, …, an are all distinct [HWW08] (thank you to Serge Gaspers for telling me about this).  It is possible to reduce this restricted version of the 3-partition problem to the problem in question as follows.

Suppose that we are given an instance of the 3-partition problem consisting of distinct positive integers a1, …, an.  Let m=n/3 and B=(a1+…+an)/m, and let N be the maximum among ai.  Consider the following instance of the stick problem: the instance consists of one stick of length k for each k∈{1, …, N}∖{a1, …, an} and m sticks of length B.  By using the fact that each ai satisfies ai > B/4 ≥ N/2, it is easy to prove that this stick problem has a solution if and only if the instance of the 3-partition problem has a solution.

References

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger.  Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.  Operations Research Letters, 36(5):594–596, Sept. 2008.  http://dx.doi.org/10.1016/j.orl.2008.05.004


XOR-SAT is in $\mathsf{L}^{\oplus\mathsf{L}} = \oplus\mathsf{L}$ (because it can be viewed as the feasibility of a system of linear equations mod 2 hence by Allender-Beals-Ogihara). Thus using a division free determinant algorithm (e.g. by Mahajan-Vinay) we can reduce it to the problem of iterated matrix product over $F_2$ by a finegrained reduction (certainly Log-space will work but something finer like Dlogtime projection should also). Now design an $\mathsf{NC}^2$ circuit to multiply together several matrices over $F_2$ using $\{\vee,\wedge,\neg\}$-gates. Thus composing the above reductions with the reduction from CVP to HornSAT gives the final reduction.


Optimal sort algorithm in number of swaps

There exists a stable in-place sorting algorithm with $O(n \log n)$ comparisons and $O(n)$ moves.

See:
Gianni Franceschini: Sorting Stably, in Place, with $O(n \log n)$ Comparisons and $O(n)$ Moves. Theory Comput. Syst. 40(4): 327-353 (2007)
http://www.springerlink.com/content/d7348168624070v7/


Complexity of distributively verifying that the diameter is small

There is an $O(k)$ rounds algorithm for distinguishing between graphs of diameter at most $k$ and those with a diameter larger than $2k$.

This works in two stages:

First, each vertex broadcasts the smallest ID it has learned about for $k/2$ rounds.
For a vertex $v$, let $L_v$ be the smallest ID that $v$ has observed by the end of this stage.

Next, the algorithm makes $k+1$, such that in each iteration every vertex broadcasts the largest $L_v$ and smallest $L_u$ it has learned about. If the graph is indeed of diameter $k$, then we would have these equal in all vertices.

Assume that the graph has a diameter larger than $2k$, then any vertex $v$ has a path of length at least $k+1$ starting from it. This means that there exists a vertex $u$ such that $d(u,v)=k+1> 2(k/2)$ which implies $L_u\neq L_v$. Thus, both $u,v$ would learn that not all vertices agreed on the node with the minimal identifier.


It's GI-complete which means it's probably not NP-complete.

Reduction from undirected graph isomorphism to DAG isomorphism: given an undirected graph $(V,E)$, make a DAG whose vertices are $V\cup E$, with an edge from $x$ to $y$ whenever $x\in V$, $y\in E$, and $x$ is an endpoint of $y$. (i.e. replace every undirected edge with a node and two ingoing edges)

Reduction from DAG isomorphism to undirected graph isomorphism: replace each arc $x\rightarrow y$ in the DAG with a four-edge subgraph consisting of a triangle having $x$ as one endpoint, and a dangling edge on the triangle connected to $y$. The reduction is only ambiguous in the case of a component that's a directed cycle, and that's not a DAG.


How do top researchers keep track new results in datastructures

You can subscribe to the RSS of ArXiv, and you can keep track of which papers are getting accepted to the relevant conferences.


In-approximability results in severely restricted graph classes

The labelled perfect matching problem, which consists in finding a perfect matching in an edge-coloured graph that uses the minimum number of colours, is not in APX for subcubic bipartite graphs (but it is $2$-approximable if the maximum degree is $2$ instead of $3$). See Monnot for details.


KRW Conjecture: separation of NC^1 and P

There are a few points to consider here:

If we wish to show that $CC(f) = \omega(\log n)$, we should show that it is not possible to cover the domain of $f$ using $\mathrm{poly}(n)$ monochromatic rectangles (rather than $n$ rectangles). Showing it for $n$ rectangles would only establish that $CC(f) > \log n$.

If we wish to prove a lower bound on $D(EQ)$, then we should prove a lower bound on $CC(\mathit{KW}_{EQ})$ rather than on $CC(EQ)$. Therefore, the lower bound on $CC(EQ)$ does not imply a lower bound on $D(EQ)$.

In particular, in order to use the Karchmer-Wigderson approach to prove lower bounds on depth complexity, we need to prove lower bounds on the communication complexity of relations rather than functions. This is considerably trickier. For example, in the context of relations, one needs to change the definition of a monochromatic rectangle. Now, it no longer makes sense to require that "the function is constant over $f$" since a relation may allow multiple valid solutions for every input, so it is not clear what being "constant" means. Instead, one should use the following more complicated definition: a rectangle $R \subseteq X \times Y$is said to be monochromatic with respect to a relation $S \subseteq X \times Y \times Z$ if there exists an output $z\in Z$ that is a valid solution for every input in $R$ (i.e., $(x,y,z) \in S$ for every $(x,y) \in R$).

Alas, it is not possible to use rectangle covers to prove meaningful lower bounds on KW relations. The reason is that every KW relations can be covered by $2n$ rectangles. Those rectangles are constructed as follows: for every index $i \in [n]$ and bit $b \in \{0,1\}$ we have the rectangle $$R_{i,b} = \{ x\in f^{-1}(0) \mid x_i = b \} \times \{ y\in f^{-1}(1) \mid y_i = \neg b \}. $$ It is not hard to see that those rectangles are indeed monochromatic rectangles for any KW relation $\mathit{KW}_f$, and that they cover the whole domain of the KW relation.


Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you're given a circuit for the function.

The paper:

https://eccc.weizmann.ac.il/report/2017/109/

shows that certain counterexamples to BBH would refute a non-uniform version of ETH (Circuit SAT has $2^{o(n)}$ size circuits). They conjecture something like that "non-uniform ETH for Circuit SAT <=> BBH is true".

Note in the other direction, if SETH is false for circuits, this would refute some version of BBH: we cannot possibly solve SAT for black boxes in $o(2^n)$ time.


The Examiner's Problem (uniform generation of SAT decision instances/answers)

The question you are asking is equivalent to unary NP = unary P, which in turn is equivalent to NE = E, by padding.

From the title, perhaps you meant to ask if it is possible to generate input/output pairs such that the distribution on the inputs is "hard."  The possibility of doing this lies somewhere between P $\ne$ NP and one-way functions exist.

In restricted computational models, it is known that this is possible.  E.g. one can generate input/output pairs for the parity or majority functions in AC$^0$ or below.  See The complexity of distributions.


Triangular Mesh Reordering - Huddling Triangles

There appears to be a solution used by game programmers that both optimizes graphics hardware cache utilization and facilitates mesh connectivity compression. It is Tom Forsyth's Linear-Speed Vertex Cache Optimisation described here: https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html

The algorithm uses a heuristic based on modeling the GPU vertex cache to produce a sequence of triangles with high locality and vertex reuse. The pattern produced is reportedly not unlike the Hilbert curve. The algorithm has linear time complexity.

The master thesis "Efficient Triangle Reordering for Improved Vertex Cache Utilisation in Realtime Rendering" (http://www.martin.st/thesis/) contains a C++ implementation and also seems to describe an improved algorithm.


Why is the consensus problem so important in distributed computing?

The paper you mention is important for 2 reasons:

It shows that there is no asynchronous deterministic consensus algorithm that tolerates even a single crash fault. Note that in the synchronous setting,there is a deterministic algorithm that terminates in $f+1$ rounds when $\le f$ processes crash.
It introduces bivalence and univalence of configurations (*), which are used in many lower bounds and impossibility proofs later on.

Applications

One important application of the consensus problem is the election of a coordinator or leader in a fault-tolerant environment for initiating some global action. A consensus algorithm allows you to do this on-the-fly, without fixing a "supernode" in advance (which would introduce a single point of failure).

Another application is maintaining consistency in a distributed network: Suppose that you have different sensor nodes monitoring the same environment. In the case where some of these sensor nodes crash (or even start sending corrupted data due to a hardware fault), a consensus protocol ensures robustness against such faults.

(*) A run of a distributed algorithm is a sequence of configurations. A configuration is a vector of the local states of the processes. Each process executes a deterministic state machine. Any correct consensus algorithm must eventually reach a configuration where every process has decided (irrevocably) on the same input value. A configuration $C$ is $1$-valent if, no matter what the adversary does, all possible extensions of $C$ lead to a decision value of $1$. Analogously, we can define $0$-valency. A configuration $C$ is bivalent if both decisions are reachable from $C$ (which one of the two is reached depends on the adversary). Clearly, no process can have decided in a bivalent configuration $C$, as otherwise we get a contradiction to agreement! So if we can construct an infinite sequence of such bivalent configurations, we have shown that there is no consensus algorithm in this setting.


Constrained version of vertex cover in a bipartite graph

The following is a list of results I'm going to prove:

if $k$ and $l$ are parts of the input and $d = 1$ is a fixed constant then the problem is polynomial time solvable
if $k$ and $l$ are parts of the input and $d \ge 2$ is a fixed constant then the problem is NP-complete
if $k$ is a fixed constant then the problem is polynomial time solvable
if $l$ is a fixed constant then the problem is polynomial time solvable

The first two bullet points address question number 1 and the last two address question number 2.

lemma: if we know $A \subseteq V_1$ with $|A| \le l$ (or $B \subseteq V_2$ with $|B| \le k$), we can decide in polynomial time whether there exists $B \subseteq V_2$ with $|B| \le k$ (resp $A \subseteq V_1$ with $|A| \le l$) such that $A \cup B$ is a vertex cover

For the proof of this lemma, we do not use the constraint that vertices in $V_1$ have degree at most $d$. Therefore, the situation is symmetric in the two parts of the bipartite graph, and we can restrict our attention to just one part of this lemma: we wish to show that if $A \subseteq V_1$ with $|A| \le l$ then we can decide in polynomial time whether there exists $B \subseteq V_2$ with $|B| \le k$ such that $A \cup B$ is a vertex cover.

Let $B' = \{v \in V_2 | \exists x \in V_1 \backslash A \text{ s.t. } (x, v) \in E\}$.

Suppose that for some $b \in B'$, it is the case that $b$ is not in $B$. By definition of $B'$, there exists an $x \in V_1 \backslash A$ such that $(x,b) \in E$. Then that edge has $x \in V_1$ with $x \not\in A$ and $b \in V_2$ with $b \not\in B$, so $A \cup B$ is not a vertex cover.

Thus in order for $A \cup B$ to be a vertex cover, it must be that $B' \subseteq B$.

Next suppose $B' \subseteq B$. Then consider any $(x, v) \in E$. If $x \in A$ then this edge is covered. If $x \not \in A$ then $v \in B'\subseteq B$ by definition of $B'$, so again the edge is covered. Thus $A \cup B$ is a vertex cover.

So $A \cup B$ is a vertex cover if and only if $B' \subseteq B$. Then there exists a $B$ with $|B| \le k$ such that $A \cup B$ is a vertex cover if and only if $|B'| \le k$.

So in order to decide whether there exists a $B$ with $|B| \le k$ such that $A \cup B$ is a vertex cover, all we have to do is compute $|B'|$ and compare with $k$. This can be done in polynomial time.

If $k$ and $l$ are parts of the input and $d = 1$ is a fixed constant then the problem is polynomial time solvable

Begin by removing all vertices of degree zero since the presence or absence of those vertices in a set does not affect whether that set is a vertex cover.

Since $d = 1$, we see that in the remaining graph, every element of $V_1$ has exactly one neighbor. We can conclude that $G$ has $|V_2|$ connected components, each of which consists of one element of $V_2$ together with all of its neighbors in $V_1$.

We wish to know whether it is possible to construct a vertex cover $A \cup B$ with $A \subseteq V_1$ and $B \subseteq V_2$ where $|A| \le l$ and $|B| \le k$.

Each connected component of the graph provides a choice: either $B$ must contain the element of $V_2$ in that component or $A$ must contain each element of $V_1$ from that component.

Then in order to minimize the size of $A$ while maintaining $|B| \le k$, it is clearly optimal to choose $B$ such that it contains the elements of $V_2$ with largest degree.

Since we know the optimal value of $B$ (in polynomial time), we can apply the lemma to solve the problem in polynomial time.

If $k$ and $l$ are parts of the input and $d \ge 2$ is a fixed constant then the problem is NP-complete

First note that the problem is clearly in NP since the set $A \cup B$ forms a certificate. Thus we must simply prove the problem NP-hard in order to show NP-completeness.

We do this by reduction from the clique problem.

Suppose we are given a clique instance in the form of a graph $G' = (V', E')$ and a value $k'$. This instance is a yes instance if and only if there exists a clique in $G'$ of size $k'$.

Then we construct an instance of our problem consisting of $G = (V_1, V_2, E)$, $k$, and $l$ as follows:

$V_1 = E'$
$V_2 = V'$
$E = \{(e, v) \in E' \times V'| v \text{ is an endpoint of } e\}$
$l = |E'| - \frac{k'(k' - 1)}{2}$
$k = k'$

Note that each element of $V_1$ has exactly two neighbors (which is ok since $d \ge 2$).

This reduction is clearly polynomial time, since each part of the output instance can be computed from the input instance very quickly.

Suppose the input instance in a yes instance. Then let $B$ be a clique in $G'$ of size $k'$ (which exists since the input instance is a yes instance). Let $A \subseteq E'$ contain those edges of $G'$ which are not in the clique $B$. There are $\frac{k'(k' - 1)}{2}$ edges in the clique, so $|A| = |E'| - \frac{k'(k' - 1)}{2}$.

Thus we have found $A \subseteq V_1$ and $B \subseteq V_2$ with $|A| \le l = |E'| - \frac{k'(k' - 1)}{2}$ and $|B| \le k = k'$. The only thing left to do in order to show that the output instance is a yes instance is to show that $A \cup B$ is a vertex cover.

So consider any edge $(e, v) \in E$ (where $e \in V_1 = E'$ and $v \in V_2 = V'$). If $e \in A$ then the edge is covered. If $e \not\in A$ then $e$ must by one of the edges in the clique $B$ (in graph $G'$). By the definition of $E$, $v$ is an endpoint of $e$ (which is an edge in the clique $B$). Thus $v \in B$ and again the edge $(e, v)$ is covered. We see that $A \cup B$ is a vertex cover.

We showed above that if the input instance is a yes instance, so is the output instance.

Now suppose that the input instance is not a yes instance. Suppose we have $A \subseteq V_1$ with $|A| \le l = |E'| - \frac{k'(k' - 1)}{2}$ and $B \subseteq V_2$ with $|B| \le k = k'$. Since the input is not a yes instance, there is no clique in $G'$ of size $k'$; therefore fewer than $\frac{k'(k' - 1)}{2}$ edges in $G'$ have both endpoints in $B$. Then since $V_1 \backslash A = E' \backslash A$ contains at least $\frac{k'(k' - 1)}{2}$ elements, each of which is an edge of $G'$, we conclude that at least one edge in $E' \backslash A$ has an endpoint not in $B$.

Let $e = (w, v)$ be an edge in $E'$ with $e \not\in A$ and $v \not\in B$. Then the edge $(e, v)$ (which is in $E$ by the definition of $E$) is not covered, and so $A \cup B$ is not a vertex cover.

We see then that in the case that the input instance is a no instance, the answer to the output instance is no as well.

We showed above that the reduction is polynomial time and answer preserving. Since the input problem (clique) is NP-hard, the output problem is NP-hard as well.

If $k$ is a fixed constant then the problem is polynomial time solvable

The number of sets $A$ with $|A| \le k$ is $|A| \choose kl$, which is polynomial in the size of the input since $k$ is a fixed constant.

Furthermore, these sets are easily enumerable.

For each candidate value of $A$, we simply apply the lemma to determine whether there exists a corresponding value of $B$ such that $A \cup B$ solves the problem.

If a solution is found, the answer to the overall problem is yes, and if no solution is found, the answer to the overall problem must be no.

If $l$ is a fixed constant then the problem is polynomial time solvable

The number of sets $B$ with $|B| \le l$ is $|B| \choose l$, which is polynomial in the size of the input since $l$ is a fixed constant.

Furthermore, these sets are easily enumerable.

For each candidate value of $B$, we simply apply the lemma to determine whether there exists a corresponding value of $A$ such that $A \cup B$ solves the problem.

If a solution is found, the answer to the overall problem is yes, and if no solution is found, the answer to the overall problem must be no.


State of the art algorithms for community detection in graphs

There's a recent paper [1] on dense subgraph (i.e. community) detection in the context of distributed computing.
In [1], each node of the graph represents an operating entity (i.e. runs an instance of a distributed algorithm) and each node can communicate with its neighboring nodes by sending messages. The graph itself can change (slowly) over time. Note that the connections in social networks evolve over time, so considering a dynamic graph seems like the right model.
By running a distributed algorithm, each node can locally determine whether it's part of a dense subgraph. You might want to consult the related work section of [1] to get pointers to other references.

[1] Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Amitabh Trehan: Dense Subgraphs on Dynamic Networks. DISC 2012: 151-165. Full paper available at http://arxiv.org/abs/1208.1454


Does this graph problem have a formal name?

The TSP problem, given a graph and an edge-weight function, asks to find a tour visiting each vertex exactly once having minimum length.

I think your problem is equivalent to the Metric TSP problem, that is the TSP problem on the complete graph where the weight of each edge $uv$ is the length of a path between $u$ and $v$ with minimum weight in your original graph.

Indeed, a minimum walk on your original graph corresponds to a minimum tour in the newly defined clique, and vice-versa.

For the first side, consider a minimum walk in the original graph. If some node is repeated (say $v$ is repeated: $\ldots, v, \ldots, u, v, w, \ldots$) one can get rid of the repetition by replacing the portion $u,v,w$ by $u,w$ in the shortest path graph. Doing this for each repetition one gets a tour in the shortest path graph having the same length as the original walk. Since the walk was optimal the tour is optimal too.

For the other side, given an optimal tour of the new graph, replace each edge $uv$ of the tour by a shortest weighted path from $u$ to $v$ is the original graph. This walk may contain some repetitions, but has now the same length as the tour, and it is optimal.


Was Babbage's Analytical Engine really turing-complete?

Your question states:

  However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card.

However, the link you supply as a reference for that says

  The number starting in column 4 indicates how many cards are to be advanced past or backed up past the reader.

This would seem to render your question moot.


Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

Just a note: the $n^{\log n}$ factor can be replaced by a polynomial, without much trouble. Here's one way to do it, not at all optimized...

Imagine there is a global graph $G$ with vertex set $[n]$, and a current induced subgraph $G' = (V',E')$ of $G$, with $n'=|V'|$. Instead of guessing the middle vertex along with each of the ${n' \choose \lfloor n'/2\rfloor}$ subset choices for $S \subseteq V'$, one can recurse only on the choice of $S$. Assume the recursive calls return $n \times n$ matrices $A_S$ and $A_{V'-S}$ such that:

 $A_S[i,j]$ equals the minimum cost of a Hamiltonian tour that starts with some vertex $i \in V$ (not necessarily in $S$), traverses only through vertices in $S$, then ends with some vertex $j \in V$ (not necessarily in $S$).  $A_{V'-S}[i,j]$ is defined similarly.

The algorithm should then return the $n\times n$ matrix $A_{G'}$, where for all $i,j=1,\ldots,n$, $A_{G'}[i,j] = \min_{S \subseteq V'} \min_{k\in V'} (A_S[i,k]+ A_{V'-S}[k,j])$.  Note that we do not have to store all these matrices; we could for example maintain $O(1)$ matrices per recursion layer (and the recursion depth is $O(n)$). After we compute the matrix product $A'[i,j] = \min_k (A_S[i,k]+ A_{V'-S}[k,j])$, we can simply take the MIN of $A'[i,j]$ with the current $A_{G'}[i,j]$ over all $i,j$, then erase $A_S$ and $A_{V'-S}$ before going to the next subset $S$. Thus the space usage is $poly(n)$.

Now the time recurrence is $T(n',n) = {n' \choose \lfloor n'/2\rfloor} \cdot (T(\lfloor n'/2\rfloor,n) + T(\lceil n'/2\rceil,n) + poly(n))$ for all $n' \leq n$ and $T(1,n) = poly(n)$, which yields $T(n',n) \leq 4^{n'} \cdot n^k$ for some $k \geq 1$. To verify this, note that the RHS of the recurrence is upper bounded by

$2^{n'+1} T(n'/2,n) + 2^{n'} \cdot poly(n) \leq 2^{n'+1} \cdot (4^{n'/2} (n/2)^k) + 2^{n'} n^k$
$= 2 \cdot 4^{n'} (n/2)^k + 2^{n'} n^k
\leq 4^{n'} n^k/2^{k-1} + 2^{n'} n^k$,

which is $\leq 4^{n'} n^k$ for $k \geq 3$ (for example).


When is Ising partition function easy to compute?

Well, you seem to be missing cases with high symmetry. Basically, any case where there is only a polynomial number of energy eigenvalues and it is easy to compute the degeneracy of these levels and easy to find an eigenstate with each eigenvalue should make the partition function efficiently computable.

An example of this would be a maximally connected graph for arbitrary J and h.

Update

Since Yaroslav asked in a comment, here is the reasoning:

The partition function for the Ising model is (taking $\beta=1$) $Z_G=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$.

Notice that the first sum is over all configurations. We can separate this into two separate sums as follows:

$Z_G=\sum_{y=0}^n \sum_{x \in H_y} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$
where $H_y$ is the set of strings of Hamming weight $y$.

Next, note that every $x \in H_y$ has the same energy, due to the permutation invariance of the maximally connected graph. So we can define
$E_y = -\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right) = -J\left( \binom{y}{2}+\binom{n-y}{2} - y(n-y)\right)-h(n-2y)$.

This gives $Z_G=\sum_{y=0}^n |H_y| ~ e^{-E_y} = \sum_{y=0}^n \binom{n}{y} ~ e^{-E_y}$.

As the sum has only $n$ terms, and each term is efficiently computable, the entire partition function can be efficiently computed to a chosen precision for the maximally connected graph of $n$ vertices.

The approach outlined above makes use of the fact that there is only a polynomial number of distinct eigenvalues and that both the value and degeneracy of each level is known. This works in general, whenever these conditions are satisfied, since we can then express the partition function as $Z=\sum_{y=0}^{poly(n)} D_y ~ e^{-E_y}$, where $D_y$ is the degeneracy of level $E_y$. If both $E_y$ and $D_y$ are efficiently computable, then we can compute this sum directly in polynomial time. This is true of all Hamiltonians, not simply the Ising model.


Under the right derandomization assumptions (see Klivans-van Melkebeek) you get the following: There is a polytime computable $f(\phi)=(\psi_1,\ldots,\psi_k)$ s.t. for all $\phi$,

If $\phi$ is satisfiable then at least one of the $\psi_i$ has exactly one satisfying assignment.
If $\phi$ is not satisfiable then all of the $\psi_i$ are unsatisfiable.

You need k polynomial in then length of $\phi$. Probably can't be done for $k=1$.


What are the best current lower bounds on 3SAT?

As far as I know, the best known "model-independent" time lower bound for SAT is the following. Let $T$ and $S$ be the running time and space bound of any SAT algorithm. Then we must have $T \cdot S \geq n^{2 \cos(\pi/7) - o(1)}$ infinitely often. Note $2 \cos(\pi/7) \approx 1.801$. (The result that Suresh cites is a little obsolete.) This result appeared in STACS 2010, but that is an extended abstract of a much longer paper, which you can get here: http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Of course, the above work builds on a lot of prior work which is mentioned in Lipton's blog (see Suresh's answer). Also, as the space bound S gets close to n, the time lower bound T gets close to n as well. You can prove a better "time-space tradeoff" in this regime; see Dieter van Melkebeek's survey of SAT time-space lower bounds from 2008.

If you restrict yourself to multitape Turing machines, you can prove $T \cdot S \geq n^{2-o(1)}$ infinitely often. That was proved by Rahul Santhanam, and follows from a similar lower bound that's known for PALINDROMES in this model. We believe you should be able to prove a quadratic lower bound that is "model-independent" but that has been elusive for some time.

For non-uniform circuits with bounded fan-in, I know of no depth lower bound better than $\log n$.


Is there higher-dimensional generative grammar?

Yes, there are n-dimensional grammars and in some cases specifically applied to music, see for example Grammar-based music composition by Jon McCormack, which talks about parametric extensions to L-grammars, or more generally, Regulated Array Grammars of Finite Index, Part I: Theoretical Investigations by Henning FERNAU, Rudolf FREUND and Markus HOLZER which talk about n-dimensional array grammars.


Escaping references in Eff and resources

The problem "Does a reference escape its scope?" is undecidable. An effect system can only overapproximate the answer to the question, so there will necessarily by tricky situations in which the compiler will claim that a reference might be escaping its scope, but it really won't. However, this is unlikely to be a real problem. After all, if a sophisticated compiler can't tell whether a reference is escaping its scope, how can we expect humans to do it?

Note that there are uses of references where we want them to escape scope. Here are some such cases:

A function memo which takes another function f and returns its memoized form. Typically memo creates a local reference in which it stores the cache.
A self-optimizing data structure such as a self-balancing tree uses local references in the background, so that it can modify itself. Such structures are often referentially transparent, i.e., the optimizaiton has no observable effect other than better efficiency.
It is unrealistic to expect that nobody will ever implement any stateful data structures. These need to use state, and they must be allowed to escape the scope in which they were created, or else the structure of the entire program becomes a hostage to correct scoping of handlers.

A similar issue arises regarding instances of effects. A realistic programming language must allow dynamic creation of new effect instances. Some situations which require this are:

opening any number of files or communication channels: each is an instance of an effect, and we cannot tell at compile-time how many we need,
creating a list of references, where do not know ahead of time how many will be created.

Multicore OCaml simulates instances with first-class modules. To my mind that is a hack, as they're using the genericity of modules to simulate generation of fresh names, and as far as I can tell, it's difficult to write a handler that captures all instances of a given effect.

Let me also say that resources are not a hack. They are inspired by comodels by Plotkin and Powers. I find it a pity that the people who're doing effects largely ignore resources. They think it's possible to write programs without local references. That's just denial for the sake of theoretical simplicity.


A curious asymmetry in good characterizations

(This is to answer Sasho Nikolov's comment, but it is way too long for the comment field, so I post it as an answer.)

The two examples in the original question are special cases of LP duality. There are many similar examples, but one can argue that they all inherit the asymmetry from LP duality. Weak LP duality is easy to prove (it provides the "trivial obstacle"), while strong duality is deeper, proving that the trivial obstacle is the only obstacle. In this sense, the examples that are "children of LP" may be viewed that they are only different incarnations of the same core example.

Here are, however, some other cases that (to my knowledge) are not related to LP. The examples below are all from graph theory, but other fields probably also contain similar patterns.

Let $k, l, d$ be positive integers. Then there is a simple graph with vertex-connectivity $k$, edge-connectivity $l$, and minimum degree $d$, if and only if $k\leq l \leq d$. Since it is (almost) trivial to prove that these parameters always satisfy the inequalities, the violation of at least one inequality is a trivial obstacle for such a graph to exist. The other direction, that such a graph always exists is nontrivial.
(See the book of Bollobas "Extremal Graph Theory," Theorem 1.5. Note: the way it is presented there is somewhat more complicated, using more inequalities, because it also uses another parameter, the number of vertices. But this simpler version can be extracted from it, to show the essential nature that here again the trivial obstacle is the only obstacle.)
Given an undirected simple graph, does it have two vertex-disjoint circuits?
This is answered by the following theorem of Lovasz and Dirac: If a simple graph with minimum degree $\geq 3$  does not have two vertex-disjoint circuits, then the graph can only be one of the following three types: (1) $K_5$, (2) a wheel graph, (3) $K_{3,n-3}$, with possibly any edges added to the the 3-vertex class. Here the trivial obstacle is that the graph falls into one of these types, since these types are easily seen not to contain 2 vertex-disjoint circuits. If the trivial obstacle is absent, the graph always has the property (but it is quite nontrivial to prove).
Given a sequence $d_1\geq\ldots\geq d_n$ of integers, and an integer $k\geq 2$, does there exist a $k$-edge connected simple graph that has $d_1\geq\ldots\geq d_n$ as its degree sequence? A 1964 result of Edmonds answers the question: such a graph exists if and only if two conditions hold: (a) the sequence is graphical (i.e., there is a graph at all that implements it as a degree sequence, which is trivially necessary, and can be checked  by the Erdos-Gallai Theorem), and (b) $d_n\geq k$, which is also trivially necessary, since the edge connectivity is bounded from above by the minimum degree. Once these essentially  trivial necessary conditions are satisfied, the desired graph always exists.
Given a complete graph $G$, and a fixed graph $H$, can the edges of $G$ be partitioned into disjoint copies of $H$? A 1976 theorem of Wilson proves that if $G$ is sufficiently large, then the only obstacle for such a partition to exist is the violation of one the following trivially necessary divisibility conditions: (a) $|E(H)|$ is a divisor of $|E(G)|$, (b) if $g$ is the greatest common divisor of the degrees of $H$, then $g$ is a divisor of $|V(G)|-1$.


Relating PAC learning results and abstaining classifiers

There is work on this, and abstaining can sometimes help. You might be looking for this paper: Trading Off Mistakes with Don't Know Predictions by Sayedi et al. from the last NIPS.


Network / Social network analysis visualization tools?

FLARE produces rather beautiful graphs and visualisations, and in fact I have used it for just this purpose with a small private social network. In particular you may want to look at "layouts" in the demo as it gives an excellent demonstration of transforming between different ways of drawing the graph.


How can an inherited attribute be simulated using a synthesized attribute?

How can inherited attributes be simulated with synthesized ones: an example.

The way of doing it is to postpone the evaluation of any attribute
that uses directly or indirectly an inherited attribute, by
abstracting it into a function that takes the inherited attribute as
argument. There may be several such arguments.

Here is a fragment of a simple example, on the grammar rule $T\rightarrow T\; v$
 for a term in an expression, which is to be type-checked.

Right hand side symbols are subscripted to identify occurrences, so we actually write $T\rightarrow T_1\; v_1$
We use the following attributes:

for $T$ the inherited attribute $symtab$ and the synthesized
attribute $type$;
for $v$, which is a terminal, the synthesized attribute $name$ which is actually produced by the lexer.

The semantic rule  for type checking is:  $type(T)\gets
 if\; type(T_1)=symtab[name(v_1).type]\; then\; type(T_1)\; else\; typefail$

meaning that the type of the subterm $T_1$ and the type associated with the symtab entry of the $name$ of the variable $v_1$
must be the same, and that the name of this common type or $typefail$ is the value for the
synthesized attribute $type$ for $T$.

You replace that semantic rule by the following one:
$type(T)\gets \lambda\; symtab.\;      if\; type(T_1)(symtab)=symtab[name(v_1).type]\;$ $\qquad\qquad\qquad\qquad\;\;\;\;\;\;then \;type(T_1)\; else\; typefail$

The synthesized attribute $type$ is now a function rather than a type
name.  When called, it takes a symtab as argument and checks whether
the expression $T$ is well typed with respect to this symtab, calling
recusively other such functional values of the attribute to actually
do the type checking for subexpressions.

You no longer need to know the symbtab where you do the type checking, so you do not need the inherited attribute $symtab$.
When higher up in the tree you get a synthesized attribute that is the
actual symtab, you simply apply the type attribute with that symtab as
argument to get the type checking done.  Well, it is a bit more
complicated with scope rules.

This can be completely formalized, but I do not have the right papers
handy, and I have no courage or time to redo the complete formal presentation. But I am sure there are books and papers on this

It is a kind of continuation passing style for processing the inherited attributes.

A proof that inherited attributes are not necessary

Hypotheses:

attributes can carry values of any type, though functional types
are not really a requirement (see the proof) despite the example
above.
any type of computation on the attributes is permitted.

We assume a CF grammar $G$ with an attribute system, such that
evaluation of attributes on a parse tree $T$ will produce a result
$E(T)$ for a distinguished attribute $\rho$ of the initial symbol
$S$ labeling the root: $\rho(root_T)=E(T)$. Our purpose is to exhibit an attribute system that produces the
same result using only synthesized attributes. Without loss of
generality, we assume that the initial symbol S of the grammar is
never used used in a right-hand side of a rule.

Intuition: we make a copy of the tree as a purely synthesized attribute of the root node.

In the formalization below $A_i$ denotes an occurence of a symbol in a rule, and
we note $\sigma A_i$ the actual symbol in that occurence.

We have a single synthesized attribute $\theta$ for all terminals and
non-terminals. For terminals, this attribute is initialized to a tree
degenerated to its root node labeled by the terminal. In addition,
there is the attribute $\rho$ for the initial symbol
$S$.

To each grammar rule  $\qquad \sigma A_0 \to \sigma A_1 \dots \sigma A_n$

we associate the following attribute calculation

$\theta(A_0) \leftarrow tree(\sigma A_0, [\theta(A_1), \dots \theta(A_1)])$

where $\theta(s,tt)$ is a function that takes two arguments, a
non-terminal $s$ and a list of trees $tt$, and returns a new tree with
a root labeled with $s$ and all the trees in $tt$ as daughters of the
root, in the same order.

It is easily shown by structural induction that attribute evaluation
of a tree $T$ will thus assign to the attribute $\theta(S)$ a value
that is precisely equal to $T$ (i.e., a copy of $T$ if that is more
intuitive). Since we know from the initial attribute system that there
is an effective procedure to compute the result $E(T)$, we only have
to add one extra attribute rule to be associated with the initial
symbol $S$:
$\rho(S)\leftarrow E(\theta(S))$

Thus, our new attribute system has only synthesized attributes and
computes exactly the same result as the initial system.

Some readers may find the proof a bit unsettling, but it is not a
circular (tautological) proof. We do not have to use the initial
attribute system to actually compute $E(\theta(S))$. The only thing
that matters is that it is computable.

Actually it is very close to the technique used in the example above,
using functional attributes, but it delays computation by passing
syntactic information bottom up, rather than doing it more
semantically by passing a continuation. One could use that functional attribute technique to do the proof, but I suspect it would be technically much more complex.

It shows that what matters to make sure than an evaluation policy can
be used is to check that this evaluation policy is able to duplicate
all the data, in this case the parse tree.

From that perspective, it is easily seen that using only inherited
attributes will not in general be adequate, because the tree cannot be
duplicated with only inherited attributes.

The reason is quite simple: when you are going top-down exclusively
you cannot pass information sideways in the tree. Take the rule
$  A \to B C$. If you are on the $B$ node of an instance of that
rule in the tree and want to compute the inherited attributes, all you see is $A$ above. There is no way you can relate to the $C$ side of the tree. And $A$ cannot look at it since information goes top down only, and $C$ is below $A$. The information on the current node depends only on the path from the root to that node, not on the whole tree.


Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was answered negatively by Turing in his famous 1936 paper "On Computable Numbers, with an application to the Entscheidungsproblem". The word literally means decision problem. I assume that the word is no longer used since it refers to a problem that has been solved. In English it may still be more common due to its prominent use in the title of Turing's paper.

Gödels Unvollständigkeitssatz is his incompleteness theorem, stating that no consistent arithmetic theory is complete, in particular it can not prove its own consistency. This answered negatively a different question of Hilbert, viz. the second of his 23 famous problems, which was to prove the consistency of the axioms of arithmetic.


On complexity of permanent ${}\bmod 2^t$?

One can compute it in $\sum_{i=0}^{t-1} \binom{n}{i}n^3$ expected time. Consider a $(n+1)\times(n+1)$ matrix

$M^+ = \left[\begin{array}{ll} M & v \\ 0 & 1 \end{array}\right],$

where $v$ is a random vector with elements chosen from $\{0,1\}$, uniformly and independently. Note that $\operatorname{per}(M^+)=\operatorname{per}(M)$. Now consider Ryser's formula

$\operatorname{per}(M^+)=\sum_{(n+1)\in X\subseteq [n+1]} (-1)^{n+1-|X|}T(X)$, where $ T(X)=\prod_{i=1}^{n+1} \sum_{j\in X} M^+_{ij}.$

Note that for many $X$, the term T(X) will be zero modulo $2^t$, namely at least for all $X$'s that make $t$ or more row sums $\sum_{j\in X} M^+_{ij}=0 ( \operatorname{ mod} 2)$. We can list only those terms $X$ that stand a chance of contributing a non-zero term by solving $\sum_{i=0}^{t-1} \binom{n}{i}$ linear equation systems over GF($2$), where we guess what rows will be zero modulo $2$. In expectation there will be one solution for each guess, so by the linearity of expectation the runtime follows.

[This is proven in a paper by B., Husfeldt, and Lyckberg currently under submission.]


Diameter of Cayley graphs of subgroups of $S_n$ without inverses

The answer is yes, we can improve the upper bound to $\mathrm{e}^{(1 + o(1))\sqrt{n\ln n}}$. It was proved in a more recent paper of Babai (Corollary 2.9).


Here's one possible approach.

For a fixed value $b$, it's easy to build a Bloom filter that stores a set $S$ of values and lets us answer queries of the form "is there any $s \in S$ such that $s \in [x,x+2^b-1]$?", where $x$ is a parameter of the query and is constrained be a multiple of $2^b$ (in other words, the ranges are $2^b$-aligned and are of length $2^b$).  (How do you do that?  Store $\{\lfloor s/2^b \rfloor : s \in S\}$ in a regular Bloom filter.)

Now, for a value $x$, you can decompose the range $[x-k,x+k]$ into a union of $O(\lg k)$ ranges of the above form.

So, our succinct data structure will be composed of multiple Bloom filters: one Bloom filter for each non-negative integer $b$.  We store a copy of $S$ in each of those Bloom filters.  To answer the query "is there any $s \in S$ such that $s \in [x-k,x+k]$?", we decompose $[x-k,x+k]$ into $O(\lg k)$ ranges that are $2^b$-aligned, and then we make the appropriate queries to the component Bloom filters.  Since we increase the number of queries by a factor of $O(\lg k)$, the false positive rate doesn't increase too much.  In fact, I think you can show that you will only need to make at most 2 queries to each component Bloom filter (i.e., the constant hidden by the big-O notation is at most 2), so I expect this should work pretty well in practice.

Note that this data structure actually allows you to generalize even further: $k$ does not need to be fixed in advance; it can instead be specified as part of the query.

I would expect this data structure to be a little bit more compact than a binary search tree, but not a lot.

A binary search tree uses $\Theta(|S| \lg \max(u,|S|))$ space, where $u$ is an upper bound on the largest value that can be stored in $S$.
In contrast, for a fixed $k$, my data structure uses $O(|S| \lg k)$ space.  This is a little bit smaller, if $k \ll u$ or $k \ll |S|$.
Also, if $u \approx |S|$, then my data structure is more compact still: it uses $O(|S|)$ space (due to collisions, the Bloom filter for $b$ only needs to able to hold up to $u/2^b$ items and thus can be stored in $O(u/2^b)$ space; note that $u + u/2 + u/4 + \dots \le 2u$).

At this point the constants are likely to matter, so you might need to try out some implementations to see if my approach is truly better than a binary search tree in practice.  You might also want to compare to storing the elements of $S$ in sorted order and answering queries using binary search over that list.


The complexity of recognizing optimal set systems for the V-C dimension

This doesn't answer the question, but it might be helpful.  Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented:

On the Complexity of Approximating the VC Dimension
http://users.cms.caltech.edu/~umans/papers/MU01-final.ps


Algorithm for finding smallest set and instanciation for a given constraint system

Your problem is at least as hard as SAT: given a CNF formula $\varphi$ on variables $x_1,\dots,x_n$, add variables $x_{\bot},x_{\top}$ and the clause $x_{\bot} \ne x_{\top}$, and translate each occurrence of the literal $x_i$ in $\varphi$  to $x_i \ne x_\bot$ and each occurrence of the literal $\overline{x_i}$ to $x_i \ne x_\top$.  In this way each clause of $\varphi$ can be translated into a constraint of your form.  Then $\varphi$ is satisfiable iff the resulting set of constraints can be satisfied by a set $A$ of size 2 (i.e., $|A|=2$).  Therefore, if we could solve your problem, we could solve SAT.  So your problem is at least as hard as SAT.

Consequently, solving your problem by bit-blasting to SAT is a reasonable way to solve your problem.  I don't think you should expect a much better algorithm.

This does leave some room for cleverness in how you encode your problem as a SAT instance.  You could encode each $x_i$ either with a one-hot encoding (using $nk$ bits), or in binary (with $n\lceil \lg k \rceil$ bits), or by encoding which pairs of $x$'s are equal (with ${n \choose 2}$ bits, i.e., a boolean variable for each $i,j$ encoding whether $x_i = x_j$, with transitivity constraints enforced).  Which you choose is likely to affect the running time in practice.  I suggest experimenting a bit with different possible ways of encoding your problem as SAT to see what seems to work best for the types of problems you are dealing with.  (I don't particularly expect a SMT solver to do any better than a SAT solver here, but you could try it.)


I'm not sure this is research level, but here's a sketch. Suppose this algorithm outputs a 1-tree and the actual cheapest 1-tree is some other 1T. Now, since you built your tree with Kruskal's algorithm, you know that the tree directly proceeding adding your last edge(the cycle-inducing edge) was minimal, and as such costs less than any subtree of the "true" cheapest 1-tree.

So, consider the subtree of the "true" 1-tree that is comprised of all edges save one edge in the cycle that your tree doesn't contain(it is easy to show that, unless their cycles are equal, this edge must exist)*. This tree is more expensive than yours. Moreover, since your tree is a tree, adding that edge from the "true" 1T would have made yours a 1-tree. So your final edge must be cheaper than that edge, or you would have chosen that edge. Thus, your 1-tree must be cheapest.

*If the cycles are the same, but the remaining subtrees are different, you are also done since yours was built using Kruskal's algorithm.


Neighborly properties in a bipartite graph

There is a polynomial time algorithm for this problem.
First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between $A$ and $B$.
In particular, if there is no perfect matching then there is a subset $S$ with $|S| > |N(S)|$, and we can remove vertices from $S$ without affecting $N(S)$ until we get an answer.
Now that we have a perfect matching we also have that $|S| \le |N(S)|$ for any set $S$, so we are looking for a set $S$ with $|S| \ge |N(S)|$.
Consider a version of this problem where we have a special vertex $a_0 \in A$ and we are looking for a set $\emptyset \subsetneq S \subseteq A \setminus \{a_0\}$ with $|S| \ge |N(S)|$. The original problem can be reduced to $|A|$ instances of this problem in polynomial time.
We create a linear program that can be seen as a relaxation of this problem, and prove that this linear program has a feasible solution if and only if the problem has a solution.
The linear program has a variable $X_a \ge 0$ for each vertex $a \in A$ and a variable $X_b \ge 0$ for each vertex $b \in B$.
We require that $\sum_{a \in A} X_a = 1$ and $\sum_{b \in B} X_b = 1$. For each edge $(a, b)$ we require that $X_b \ge X_a$. We also set $X_{a_0} = 0$ for the special vertex $a_0$. This linear program has a feasible solution if we have a solution $S$: for each $a \in S$ set $X_a = 1/|S|$ and for each $b \in N(S)$ set $X_b = 1/|N(S)|$.
Let's prove that if there is a feasible solution to the linear program then we have a solution to the problem.
Take $S$ as the set of vertices $a \in A$ with $X_a > 0$. If $|N(S)| \le |S|$ we are done.
Suppose $|N(S)| > |S|$.
There is a matching from $S$ to a subset $N' \subsetneq N(S)$ because the graph has a perfect matching.
Note that $1 = \sum_{a \in S} X_a \le \sum_{b \in N'} X_b$ because the matching matches each vertex $a \in S$ to a vertex $b \in N'$ with $X_b \ge X_a$.
There is a vertex $b \in (N(S) \setminus N')$ with $X_b > 0$, and therefore $\sum_{b \in N(S)} X_b$ must be greater than $1$, which is a contradiction.


Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

Trivially there will be space-bounded classes $P\ne Space(n)\subsetneq Space(n^2)\subsetneq PSPACE$, and $NSpace(n)\subsetneq NSpace(n^2)\subsetneq PSPACE$, which do not collapse due to the space hierarchy theorem.
More interestingly, the Complexity Zoo lists two other classes that is in PSPACE but not in CH, namely

$QSZK$ (Quantum Statistical Zero Knowledge)
$RG[\#1]$ (single-round referreed games).

Perhaps $QSZK$ satisfies your condition. The best published upper bound (that I can find) is that $QSZK\subseteq PSPACE$ by Watrous[1]. Perhaps it does not satisfy your condition; because it has a complete problem that asks to determine the trace distance between the quantum states produced by two quantum circuits given as input, and this is typically doable in $P^{\#P}$, which you have assumed is equal to $P^{\#P}=P$. I don't know, and invite people to think about whether $QSZK\subseteq CH$ or not. Since you asked specifically for a hierarchy, you can think about the hierarchy $QSZK^{{QSZK}^{\cdots}}$. It is unknown whether this class is self-low, i.e. whether $QSZK=QSZK^{QSZK}$ and the hierarchy collapses.
Update
Known results:
$$QMA=QIP[1]\subseteq A_0PP\subseteq PP$$
$$QMA[2]=QMA[k]$$
$$QSZK\subseteq QIP[2]\subseteq QIP[3]=QIP=PSPACE.$$
Perhaps $RG[\#1]$ satisfies your condition. No upper bound is known except that $RG[\#1]\subseteq RG[\#2]=PSPACE\subseteq RG=EXP$.
[1] J. Watrous. Limits on the power of quantum statistical zero-knowledge, to appear in Proceedings of IEEE FOCS'2002


Arithmetic coding, the termination symbol, and the empty string

Why shouldn't you be able to send the empty string? Shouldn't it be considered a valid message?

But if you don't allow the empty string as a message, then your modified protocol will work fine, and will save you on average a small fraction of a bit per message.

Is this tweak worth putting into your implementation so as to improve the performance? Let's work out how much it saves you. Suppose you're using a binary alphabet, and your average message is around 100 bits in length. You then want the termination symbol to have probability 1/100. By not allowing the possibility of the termination symbol being the first bit, you save on the order of 1/100 bits* per message. If you assume a compression ratio of 2, the total improvement in performance is 0.02%. Since 100 bits is a smaller average message length than I expect you would see anywhere, the actual performance improvement would probably be even smaller. I thus suspect that this variant would not actually be used in practice.

* 1/100 nats, or 0.014 bits, to be more precise.


Approximate graph colouring  with a promised upper bound on maximum independent set

Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound of (1 - 2c)n colors and an approximation ratio of 1/(1-2c). Solving the equation 64(1-c) = 1/(1-2c) leads to an approximation ratio slightly larger than 32; see Sasho Nikolov's comment for the precise value.


Quantum algorithms for determining whether two sets intersect

It's not completely obvious to me that this problem can be reduced to element distinctness (ED). What if the two sets are disjoint, but the sets contain repeated elements? If you just solve ED on the union of the two sets, ED will return YES, but the sets are disjoint.

But this problem (let's call it Set Disjointness or SD) has query complexity $\Theta(n^{2/3})$ when the two sets are of size $n$.

To show a lower bound of $\Omega(n^{2/3})$, we can reduce ED to SD. Here's a simple probabilistic reduction: Take any ED instance. Randomly partition it into two parts and solve SD on this instance. If it was a NO instance of ED, it will be a NO instance of SD. If it was a YES instance, then with probability >= 1/2, it will be a YES instance of SD.

For an upper bound of $O(n^{2/3})$, I can't, off the top of my head, think of a reduction to a known problem. The easiest way I can think of is to use Ambainis' algorithm for ED, but modify it to work for this problem. It is known that Ambinis' algorithm actually works for any two-place relation R(.,.), not just the relation EQUALITY(x,y), which is 1 iff x and y are the same. So we can use the relation R(x,y) = 1 iff x = y and x and y are from different sets.


The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of space, then what you need from your PRNG is that its output cannot be distinguished from a stream of random bits by a small space algorithm. Such a PRNG was constructed by Nisan, and the proof of pseudorandomness is unconditional.

A seminal paper in streaming algorithms that used Nisan's generator is Indyk's work on sketches of $L_1$. Since the sketch uses Cauchy random variables for which the mean and the variance do not exist, the usual moment calculations do not work, so it is hard to imagine how to use $k$-wise independence. That's why the heavy hammer of Nisan's generator comes handy.

A problem with these heavy hammers is that they come at a cost in space. The seed needs to be stored in memory, and for Nisan's generator the seed length is roughly $S\log R$ where $R$ is the number of random bits and $S$ is the space complexity of the algorithm. So you end up multiplying the space complexity by roughly the logarithm of the stream length $n$. If you can use $k$-wise independence you usually add a term like $O(k\log n)$ to the space complexity.


Amortized time and worst case (non-amortized) separation

Heapify is one example:
https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/
Another simpler example (Min / Max queue):
https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/  . This is also discussed here (see Szymon's answer): https://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-from-a-queue
And there are many more...


Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ (Buhrman&Fortnow, pdf), so the only way the hierarchy didn’t collapse to (at most) the second level and didn’t exhaust $\mathrm{BPP}$ would be for the  unlikely reason that $\mathrm{RP}$ oracles were significantly weaker than $\mathrm{promiseRP}$ oracles.


Combinators for the Primitive Recursive Functions

Yes, but you have to consider typed combinators. That is, you need to give $S$ and $K$
the following type schemas:
$$
\begin{array}{lcl}
K & : & A \to B \to A \\
S & : & (A \to B \to C) \to (A \to B) \to (A \to C)
\end{array}
$$
where $A, B$, and $C$ are meta-variables which can be instantiated to any concrete type at each use.

Then, you want to add the type $\mathbb{N}$ of natural numbers to the language of types, and add the following combinators:
$$
\begin{array}{lcl}
z & : & \mathbb{N} \\
succ & : & \mathbb{N} \to \mathbb{N} \\
iter & : & \mathbb{N} \to (\mathbb{N} \to \mathbb{N}) \to \mathbb{N} \to \mathbb{N}
\end{array}
$$

The equality rules for the additions are:
$$
\begin{array}{lcl}
iter\;i\;f\;z & = & i \\
iter\;i\;f\;(succ\;e) & = & f(iter\;i\;f\;e)
\end{array}
$$

It's much easier to read the programs you write, if you just write programs in the simply-typed lambda calculus, augmented with the numerals and iteration. The system I've described is a restriction of Goedel's T, the language of higher-type arithmetic. In Goedel's T, the typing for iteration is less limited:
$$
\begin{array}{lcl}
iter & : & A \to (A \to A) \to \mathbb{N} \to A
\end{array}
$$
In T, you can instantiate $iter$ at any type, not just the type of natural numbers. This takes you past primitive recursion, and lets you define things like Ackerman's function.

EDIT: Xoff asked how to encode the predecessor function. It follows via a standard trick. To explain, I'll use lambda-notation for this (which can be eliminated with bracket-abstraction), since that's far more readable. First, assume that we have pairs and the more general type for $\mathit{iter}$. Then, we can define:

$$
\begin{array}{lcl}
pred' & = & \lambda k.\;iter \;(z, z) \; (\lambda (n, n').\; (succ\;n, n))\;k\\
pred  & = & \lambda k.\;snd(pred'\;k)
\end{array}
$$

If you just have the nat-type iterator, then you need to exploit the isomorphism that $\mathbb{N} \simeq \mathbb{N} \times \mathbb{N}$, which is annoying but poses no fundamental obstacle.


Bob's Sale (reordering of pairs with constraints to minimize sum of products)

This is a follow-up on Gero's answer.  The idea is to modify his construction to show strong NP-hardness.

Instead of choosing $t_i=(2b+1)^i$, chose $t_i=i$.  Now, you have to modify the argument that a solution with prize $P=2b\sum_{1\leq i \leq k} t_i$ implies that there exists a 3-partition.

Take an arbitrary shelf order.  Do the accounting in the following way: distribute $w_i-1$ units of quantity of the root-product to its leaf-products.  Then every product has quantity 2.  By definition of the constraints, this does not shift to a higher price.
After this shifting, the price will be exactly $P$.
If the shifting moved some quantity to a lower prize, the original prize was strictly larger than $P$.

Hence, it is only possible to achieve the claimed prize, if all leaf-products have the same prize as their root-product, which means that there exists a 3-partition.

Citing the result from a SWAT 2010 paper this argument shows that even with unary encoding of the numbers and $k$ different price tags, a running time of $f(k)\cdot n^{O(1)}$ would violate "standard complexity assumptions".
This makes the hinted at dynamic programming with a running time of $n^{O(k)}$ look not so bad.

Also cross-posted to the original stack-overflow question.


Complexity of the Schönhage–Strassen algorithm

What you are actually asking is for the performance of the Schönhage–Strassen algorithm in the unit cost RAM (rather than its bit complexity). This is covered in Fürer's paper How Fast Can We Multiply Large Integers on an Actual Computer?, likely written with similar motivation to yours.


Because the input size (a description of the group and its generators) can be so much smaller than the graph itself, even standard polynomial-time graph optimization problems can become hard on Cayley graphs. For instance, shortest paths on circulant graphs (a special case of Cayley graphs) are NP-complete; see "On Routing in Circulant Graphs", Cai et al, COCOON 1999, doi:10.1007/3-540-48686-0_36

Of course that doesn't apply to the exact statement of the problem you give (where the group is given as a multiplication table, itself an object of size comparable to the Cayley graph) but it does indicate a need for some care.


Classification of Typed/Untyped Lambda Calculi

Your table is a bit confused; here's a better one.

Untyped lambda calculus -- no logical interpretation, as Andrej notes
Simply typed lambda calculus -- intuitionistic propositional logic
Polymorphic lambda calculus -- pure second-order logic (ie, without first-order quantifiers)
Dependent types -- generalization of first-order logic
Calculus of constructions -- generalization of higher-order logic

Type dependency is more general than first-order quantification, since it turns proofs into objects you can quantify over. Lambda calculi corresponding to ordinary intuitionistic FOL exist, but are not widely used enough to have a special name -- people tend to go straight to dependent types.

You can also relate the syntactic form of a calculus to logical systems, as well.

Combinator calculi (eg, SKI combinators) -- Hilbert-style systems
A-normal form -- sequent calculus
Ordinary typed lambda calculus -- natural deduction