Curry-Howard and programs from non-constructive proofs

This an interesting question. Obviously one can't expect to have a program that decides for each $e$ whether $\forall k T(e, k)$ holds or not, as this would decide the Halting Problem. As mentioned already, there are several ways of interpreting proofs computationally: extensions of Curry-Howard, realizability, dialectica, and so on. But they would all computationally interpret the theorem you mentioned more or less in the following way.

For simplicity consider the equivalent classical theorem

(1) $\exists i \forall j (\neg T(e, j) \to \neg T(e, i))$

This is (constructively) equivalent to the one mentioned because given $i$ we can decide whether $\forall k T(e, k)$ holds or not by simply checking the value of $\neg T(e, i)$. If $\neg T(e, i)$ holds then $\exists i \neg T(e, i)$ and hence $\neg \forall i T(e, i)$. If on the other hand $\neg T(e, i)$ does not hold then by (1) we have $\forall j (\neg T(e, j) \to \bot)$ which implies $\forall j T(e, j)$.

Now, again we can't compute $i$ in (1) for each given $e$ because we would again solve the Halting Problem. What all interpretations mentioned above would do is to look at the equivalent theorem

(2) $\forall f \exists i' (\neg T(e, f(i')) \to \neg T(e, i'))$

The function $f$ is called the Herbrand function. It tries to compute a counter example $j$ for each given potential witness $i$. It is clear that (1) and (2) are equivalent. From left to right this is constructive, simply take $i' = i$ in (2), where $i$ is the assumed witness of (1). From right to left one has to reason classically. Assume (1) was not true. Then,

(3) $\forall i \exists j \neg (\neg T(e, j) \to \neg T(e, i))$

Let $f'$ be a function witnessing this, i.e.

(4) $\forall i \neg (\neg T(e, f'(i)) \to \neg T(e, i))$

Now, take $f = f'$ in (2) and we have $(\neg T(e, f'(i')) \to \neg T(e, i'))$, for some $i'$. But taking $i = i'$ in (4) we obtain the negation of that, contradiction. Hence (2) implies (1).

So, we have that (1) and (2) are classically equivalent. But the interesting thing is that (2) has now a very simple constructive witness. Simply take $i' = f(0)$ if $T(e, f(0))$ does not hold, because then the conclusion of (2) is true; or else take $i' = 0$ if $T(e, f(0))$ holds, because then $\neg T(e, f(0))$ does not hold and the premise of (2) is false, making it again true.

Hence, the way to computationally interpret a classical theorem like (1) is to look at a (classically) equivalent formulation which can be proven constructively, in our case (2).

The different interpretations mentioned above only diverge on the way the function $f$ pops up. In the case of realizability and the dialectica interpretation this is explicitly given by the interpretation, when combined with some form of negative translation (like Goedel-Gentzen's). In the case of Curry-Howard extensions with call-cc and continuation operators the function $f$ arises from the fact that the program is allowed to "know" how a certain value (in our case $i$) will be used, so $f$ is the continuation of the program around the point where $i$ is computed.

Another important point is that you want the passage from (1) to (2) to be "modular", i.e. if (1) is used to prove (1'), then its interpretation (2) should be used used in similar way to prove the interpretation of (1'), say (2'). All the interpretations mentioned above do that, including the Goedel-Gentzen negative translation.


Formal representation of algorithm using recursive algebraic data types

You should get acquainted with inductive definitions.

Instead of saying that $Data$ is recursively defined, say that it is a set constructed inductively by:

$(0,i) \in Data$ for every $i \in \mathbb{Z}$,
$(1,d) \in Data$ for every $d \in Data$,
$(2,d) \in Data$ for every $d \in Data$.

Another way to say the same thing is that $Data$ is the smallest set such that
$$Data = \lbrace (0,i) \mid i \in \mathbb{Z} \rbrace \cup
\lbrace (1,d) \mid d \in Data \rbrace \cup
\lbrace (2,d) \mid d \in Data \rbrace.$$
Then remark that you use abbreviations $\mathcal{A} = 0$, $\mathcal{B} = 1$, $\mathcal{C} = 2$. Mathematicians are not used to introduction of basic symbols or tags, unless they are considering polynomials in a "variable" $X$ (which they really should call "symbol").

But it may be better not to cater to old-fashioned traditions of mathematicians. We should push them into the 21st century and teach them some math which they think of as "computer science". What is wrong with assuming your reader knows what an inductive data type is?

One word of warning: Haskell does not have inductive datatypes, but rather coindcutive data types. If you define the type in Haskell you will also get infinite elements of the form B (B (C (B ....))). There is just no way to get this right in Haskell. ML has proper datatypes.


Problems in NP but not in Average-P/poly

This is a slightly improved version of my two comments on the question combined.

Let’s restrict our attention to distributional problems in DistNP (aka (NP, P-computable)) for simplicity.  Then you are looking for a problem in DistNP ∖ Average-P/poly.  Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly.  And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under average-case reductions.

(Considering a larger class SampNP (aka (NP, P-samplable)) instead of DistNP does not change the situation much because DistNP ⊆ Average-P/poly if and only if SampNP ⊆ Average-P/poly.  This equivalence is a direct corollary of the result by Impagliazzo and Levin [IL90] that every distributional problem in SampNP is average-case reducible to some distributional problem in DistNP.)

I do not know which natural assumption implies DistNP ⊈ Average-P/poly.  The assumption that the polynomial hierarchy does not collapse is not known to imply even a weaker consequence that DistNP ⊈ Average-P, according to Section 18.4 of Arora and Barak [AB09]: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”

References

[AB09] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

[IL90] Russell Impagliazzo and Leonid A. Levin.  No better ways to generate hard NP instances than picking uniformly at random.  In the 31st Annual Symposium on Foundations of Computer Science, 812–821, Oct. 1990.  http://dx.doi.org/10.1109/FSCS.1990.89604


Complexity of finding vectors with optimal projection?

The problem is NP-Hard and the reduction is from partition.

So, assume you are given an instance of partition $S=${$x_1,\ldots,x_n$}. Let $t = (\sum_{i=1}^n x_i) / 2$. The question is whether there is a subset of $S$ such that its sum is $t$.

To this end, let $v_0 = (0, 2t, t)$ be a special vector. For every number $x_i$, create the vector

$v_i = (x_i, -x_i, 0)$,

for $i=1,\ldots, n$. Now, the claim is that there is a subset of the vectors with sum $\geq (t, t, t)$ (in absolute value) if and only if there is a subset of $S$ that add up to $t$.

So, consider a subset $X \subseteq S$, with $\alpha = \sum_{x\in X}$. We have that the corresponding sum of vectors (together with the special vector $v_0$) is

$(\alpha, 2t -\alpha, t)$.

Clearly, this vector is maximized when $\alpha=t$, as required.

Note, that you must include the special vector $v_0$ - otherwise the third coordinate would be zero in the sum of vectors.

QED

Note, that the problem is solvable in polynomial time if the numbers are polynomially small, doing dynamic programming (like the one used for solving subset sum if the numbers are small).

2d

If you set the special vector to be $(8t, 10t)$ then the above reduction would work verbatim in two dimensions. (The constant $8$ here is somewhat arbitrary...)


Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

The oracle goes back to Stockmeyer in 1983. Heller gave the stronger result that : $BPP = EXP^{NP}$ in a relativized world in 1986. Karpiniski and Verbeek (mentioned in the comments) reprove Heller's result.


What information can a program give about the Kolmogorov Complexity of its accepting Language

Let's assume we use TMs to describe the Kolmogorov Complexity of words over $\{0,1\}$. Since we can encode any string over a finite alphabet as binary string we don't lose generality.

Using Gödel Numbering we can encode every TM $M$ as a string over $\{0,1\}$. If there is an input $x$ such that $M$ outputs $w$ on input $x$, in symbols $<M,x>=w$, then the length of this description of $w$ is the length of the concatenated binary string of $M$ and $x$, in symbols $|M \circ x|$.

Now, due to your request we have a TM $M$ that decides our language $L$. That implies that $M$ halts on every input(a semi-decision algorithm would be sufficient as well but the following algorithm would be slightly more cumbersome). With $M$ we can construct a TM $M'$ which enumerates $L$. That means $M'$ on some input $n$, which we will interpret as a natural number but 0, does the following:

counter := 0
for all x in {0,1}^*
    if x in L then counter++
    if counter = n then break
return x

To decide $x$ in $L$ we use $M$. Additionally, I'd consider it useful that the sequence of all binary strings should be traversed in ascending order w.r.t length(for assessing the quality of our upper boundary later on).

Now, let for all words $w \in L$ be $f(w)$ the natural number such that $<M',f(w)> = w$. Then we can state an upper bound for the KC of any word $w$ in $L$ as

$K(w) \leq |M' \circ bin(f(w))|$

with $bin(x)$ being the binary representation we also use to pass $f(w)$ as input to $M'$. Extra: the quality of our upper bound for the larger words in $L$ can be estimated by comparing the growth rate of $|w|$ to $log_2(f(w))$.


Complete problems and universal simulator machines

There is a universal simulator for $\mathsf{DSPACE}(o(\log \log n)) = \mathsf{DSPACE}(O(1))=\mathsf{REG}$. Namely, $U_{REG}(p,x)$ treats the first input $p$ as the description of a DFA, and then runs that DFA on input $x$. The universal simulator, however, is not itself in $\mathsf{DSPACE}(o(\log \log n))$---the $U_{REG}$ I just described uses space essentially $O(p)$---so I don't know about complete languages in this case.

More generally, complete problems and universal simulators are related, but not equivalent. For one, a universal simulator for a class $\mathcal{C}$ need not be (and in general won't be) in the class $\mathcal{C}$ itself, as in the above example. Your example of "polynomially-hampered universal TMs" for $\mathsf{P}$ exhibits this distinction even better: let $M_1, M_2, \dotsc$ be an enumeration of poly-time TMs, where $M_i$ is hampered to use time at most, say, $n^i + i$. Then let $U(i,x) = M_i(x)$. $U$ is a universal simulator for $\mathsf{P}$, but there is no single polynomial that bounds the runtime of $U$, so $U$ itself is not in $\mathsf{P}$ and hence not complete.

Furthermore, there cannot be a single polynomial that bounds the runtime of a universal simulator for $\mathsf{P}$: if the universal simulator ran in time $n^k$, it would never be able to decide a language which required more time, say, $n^{k+1}$. We know that such languages exist by the Time Hierarchy Theorem.

However, the other direction usually holds. That is, if a class has a complete language under essentially any of the natural types of reductions, then it has a universal simulator. As an example, consider $\mathsf{NP}$ and its standard complete language SAT. Then we construct a universal machine for $\mathsf{NP}$ as follows (we knew how to do this for $\mathsf{NP}$ already using polynomially-hampered nondeterministic machines, but you'll see how this construction generalizes to any class with a complete language). $U(i,x) = SAT(M_i(x))$ where $M_i$ is the $i$-th poly-time deterministic TM, as above. Here we are using the $M_i$ to list out the possible reductions to the complete language, rather than the deciders of languages themselves.


There does not seem to be a general algorithm.

Checking whether two Datalog programs are equivalent (in the sense of producing the same output database for every possible input database) is undecidable.  The containment problem, of checking whether one Datalog program always produces all the tuples of the other (plus possibly some others), is also undecidable.  So there is no general algorithm for verifying the output of your proposed minimization algorithm.  One can generate all syntactically valid Datalog programs up to the size of the input Datalog program, but there is no general way to check whether these are equivalent to or even implied by the original Datalog program.

Oded Shmueli, Equivalence of Datalog queries is undecidable, The Journal of Logic Programming 15(3) 231–241, 1987.  doi: 10.1016/0743-1066(93)90040-N

What you perhaps mean is minimization over all Datalog programs made up only of the terms that occur in the original program, such as the $A(x) \leftarrow D(x).$ example you provided above.  This is a restricted form of Datalog containment, since one only wants to check containment between syntactically closely related Datalog programs.  It is not obvious to me whether this restriction makes the problem decidable or not, although there may be some related work, perhaps in the rewriting systems or finite automata communities.

Restricting the problem somewhat, one can try to find an equivalent minimal non-recursive Datalog program.  Unfortunately checking for equivalence between a recursive and a non-recursive Datalog program requires time that is triply exponential in the size of the programs, and checking whether the recursive program is contained in the non-recursive one requires doubly exponential time.  Moreover, these algorithms require constructing exponential-sized tree automata, so are probably not feasible for actual implementation.

Surajit Chaudhuri and Moshe Vardi, On the Equivalence of Recursive and Nonrecursive Datalog Programs, JCSS 54(1), 61–78, 1997. doi: 10.1006/jcss.1997.1452 (preprint)

Finally, consider really simple Datalog programs, where there are only two unary predicates $T(x)$ and $F(x)$, such that $T(x) \equiv \lnot F(x)$.  In other words, each variable must take either the value "true" or "false".  Each such Datalog program then corresponds to a Horn formula, a universally quantified conjunction of Horn clauses.  The minimization problem for these highly restricted Datalog programs is still NP-hard, and also likely to be hard to approximate.

Amitava Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi, and György Turán, On Approximate Horn Formula Minimization, ICALP 2010, doi:10.1007/978-3-642-14165-2_38 (preprint)

The authors mention some prior work on efficient algorithms for restricted cases, such as quasi-acyclic Horn formulas and for approximation in terms of the number of different variables in the formula.

You might also be interested in the literature on finding shortest implicants.


Any fast algorithm for minimum cost feedback arc set problem?

Daniel Apon linked to the conference version of my paper. I suggest the draft journal version instead: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .
On tournament graphs some experimental work suggests that local search does quite well. See Anke van Zuylen and Frans Schalekampf's recent ALENEX paper: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .
If the weights satisfy either "probability constraints" or "triangle inequalities" there's a constant-factor approximation algorithm based on quicksort. See Ailon, Charikar and Newman's recent JACM paper.
Can you tell us a bit more about what sorts of instances you have in mind and whether you're looking for something that works well in practice or in theory?


Reduction from SAT to 0,1 integer linear program with zero or one solutions

OptP-complete. Krentel showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much by definition.

Note that you need n calls to an NP-oracle to solve ILP via binary search, O(log n) isn't sufficient.

There really isn't much of a connection to UP, though Mulmuley, Vazirani and Vazirani give an isolation lemma that gives an alternate proof of Valiant-Vazirani via a maximization problem.


Sure.  These are known as homomorphic hash functions.  There are many schemes: see e.g., https://crypto.stackexchange.com/q/6497/351 for one possible entry point into the literature.

One example construction is to let $\mathbb{G}$ be a group with group operation $*$ and let $h:\{0,1\} \to \mathbb{G}$ be an arbitrary function, then extend $h$ to a function $h:\{0,1\}^* \to \mathbb{G}$ by associativity, i.e.,

$$h(x_1 x_2 \dots x_n) = h(x_1) * \cdots * h(x_n).$$

Then you can choose any group $\mathbb{G}$ of your choice.  If you want $*$ to be non-commutative, choose a non-abelian group $\mathbb{G}$.  One plausible choice is $\mathbb{G} = SL_2(\mathbb{F})$ over some finite field $\mathbb{F}$; see https://crypto.stackexchange.com/q/17730/351.

Your reasons why it can't exist are not valid.  I don't know what "there would be a loss of entropy" means; any hash function always causes a loss  of entropy (if the domain is larger than the range), thanks to the pigeonhole principle, but that doesn't mean hash functions don't exist or can't be deterministic.  The existence of Merkle trees doesn't preclude the existence of other solutions.


It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values).

On the other hand, if we use  a tree based data structure, we may be able to improve the run-time from the $k \cdot Q(n)$ time to perform $k$ queries that each individually take $Q(n)$ time. For example, if the keys are clustered closely together, and we use a finger-search tree. (See e.g. Brodal's chapter on finger search trees).

If you are dealing with sequential files, then
Expressions for Batched Searching of Sequential and Hierarchical Files is a relevant reference.

If you are concerned with the I/O cost of accessing an external database, then perhaps the buffer tree is a more relevant reference.


I guess you know the classical result of Schaefer from STOC'78, but just in case.

10.1145/800133.804350

Schaefer proved that if SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions to linear equations in GF(2)), 0-valid (relations satisfied by the all-0 assignment) and 1-valid (relations satisfied by the all-1 assignment).


The problem of deciding whether a monotone CNF implies a monotone DNF

Assuming SETH, the problem is not solvable in time $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ for any $\epsilon>0$.

First, let me show that this is true for the more general problem where $\Phi$ and $\Psi$ may be arbitrary monotone formulas. In this case, there is a poly-time ctt reduction from TAUT to the problem that preserves the number of variables. Let $T^n_t(x_0,\dots,x_{n-1})$ denote the threshold function
$$T^n_t(x_0,\dots,x_{n-1})=1\iff\bigl|\{i<n:x_i=1\}\bigr|\ge t.$$
Using the Ajtai–Komlós–Szemerédi sorting network, $T^n_t$ can be written by a polynomial-size monotone formula, constructible in time $\mathrm{poly}(n)$.

Given a Boolean formula $\phi(x_0,\dots,x_{n-1})$, we may use De Morgan rules to write it in the form $$\phi'(x_0,\dots,x_{n-1},\neg x_0,\dots,\neg x_{n-1}),$$
where $\phi'$ is monotone. Then
$\phi(x_0,\dots,x_{n-1})$ is a tautology if and only if the monotone implications
$$T^n_t(x_0,\dots,x_{n-1})\to\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$$
are valid for every $t\le n$, where
$$N_i=T^{n-1}_t(x_0,\dots,x_{i-1},x_{i+1},\dots,x_{n-1}).$$

For the left-to-right implication, let $e$ be an assignment satisfying $T^n_t$, i.e., with at least $t$ ones. There exists $e'\le e$ with exactly $t$ ones. Then $e'\models N_i\leftrightarrow\neg x_i$, thus $e'\models\phi$ implies $e'\models\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$. Since this is a monotone formula, we also have $e\models\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$. The right-to-left implication is similar.

Now, let me return to the original problem. I will show the following: if the problem is solvable in time $2^{\delta n}\mathrm{poly}(l)$, then for any $k$, $k$-DNF-TAUT (or dually, $k$-SAT) is solvable in time $2^{\delta n+O(\sqrt{kn\log n})}\mathrm{poly}(l)$. This implies $\delta\ge1$ if SETH holds.

So, assume we are given a $k$-DNF
$$\phi=\bigvee_{i<l}\Bigl(\bigwedge_{j\in A_i}x_j\land\bigwedge_{j\in B_i}\neg x_j\Bigr),$$
where $|A_i|+|B_i|\le k$ for each $i$. We split the $n$ variables into $n'=n/b$ blocks of size $b\approx\sqrt{k^{-1}n\log n}$ each. By the same argument as above, $\phi$ is a tautology if and only if the implications
$$\tag{$*$}\bigwedge_{u<n'}T^b_{t_u}(x_{bu},\dots,x_{b(u+1)-1})\to
\bigvee_{i<l}\Bigl(\bigwedge_{j\in A_i}x_j\land\bigwedge_{j\in B_i}N_j\Bigr)$$
are valid for every $n'$-tuple $t_0,\dots,t_{n'-1}\in[0,b]$, where for any $j=bu+j'$, $0\le j'<b$, we define
$$N_j=T^{b-1}_{t_u}(x_{bu},\dots,x_{bu+j'-1},x_{bu+j'+1},\dots,x_{b(u+1)-1}).$$
We can write $T^b_{t}$ as a monotone CNF of size $O(2^b)$, hence the LHS of $(*)$ is a monotone CNF of size $O(n2^b)$. On the right-hand side, we may write $N_j$ as a monotone DNF of size $O(2^b)$. Thus, using distributivity, each disjunct of the RHS can be written as a monotone DNF of size $O(2^{kb})$, and the whole RHS is a DNF of size $O(l2^{kb})$. It follows that $(*)$ is an instance of our problem of size $O(l2^{O(kb)})$ in $n$ variables. By assumption, we may check its validity in time $O(2^{\delta n+O(kb)}l^{O(1)})$. We repeat this check for all $b^{n'}$ choices of $\vec t$, thus the total time is
$$O\bigl((b+1)^{n/b}2^{\delta n+O(kb)}l^{O(1)}\bigr)=O\bigl(2^{\delta n+O(\sqrt{kn\log n})}l^{O(1)}\bigr)$$
as claimed.

We get a tighter connection with the (S)ETH by considering the bounded-width version of the problem: for any $k\ge3$, let $k$-MonImp denote the restriction of the problem where $\Phi$ is a $k$-CNF, and $\Psi$ is a $k$-DNF. The (S)ETH concerns the constants
$$\begin{align*}
s_k&=\inf\{\delta:k\text-\mathrm{SAT}\in\mathrm{DTIME}(2^{\delta n})\},\\
s_\infty&=\sup\{s_k:k\ge3\}.
\end{align*}$$
Likewise, let us define
$$\begin{align*}
s'_k&=\inf\{\delta:k\text-\mathrm{MonImp}\in\mathrm{DTIME}(2^{\delta n})\},\\
s'_\infty&=\sup\{s'_k:k\ge3\}.
\end{align*}$$
Clearly,
$$s'_3\le s'_4\le\dots\le s'_\infty\le1$$
as in the SAT case. We also have
$$s'_k\le s_k,$$
and the double-variable reduction in the question shows
$$s_k\le2s'_k.$$
Now, if we apply the construction above with constant block-size $b$, we obtain
$$s_k\le s'_{bk}+\frac{\log(b+1)}b,$$
hence
$$s_\infty=s'_\infty.$$
In particular, SETH is equivalent to $s'_\infty=1$, and ETH is equivalent to $s'_k>0$ for all $k\ge3$.


For log-space machines, why do we care about PRGs?

You show that RL$\subseteq$P. Better derandomization could show that RL=L.


Consequences of faster parameterized integer programming

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally corresponds to a constraint $x_1 + x_3 + (1-x_4) + (1-x_6) \geq 1$, when all variables are forced to take values $0$ and $1$.

Hence if integer programming in $k$ variables can be solved in time $k^{O(k^\alpha)}$ for some $\alpha < 1$, then CNF-SAT with arbitrarily long clauses can be solved in $k^{O(k^\alpha)} = 2^{O(k^\alpha \cdot \log k)}$, which would contradict the Strong Exponential Time Hypothesis since $c \cdot k^\alpha \cdot \log k < k$ for any constant $c$, $\alpha < 1$, and sufficiently large $k$.


Bipartite maximum matching size from eigenvalues

As an expansion of the comment I made above, here it is in answer form.

I'll just talk about maximum matchings, since that will demonstrate the point.  Suppose that we consider both $K_{1,2n-1}$ and $K_{n,n}$. The first has a maximum matching of size 1, since it's a star graph, and the other has $n$ for obvious reasons.

It's easiest to reason about the normalized adjacency matrix $D^{-1}A$, but the same applies to the normalized Laplacian.  Both of these graphs have an eigenvalue of 1, because every connected graph does. The corresponding eigenvector is the vector of all ones (this is easy enough to see because $A\mathbf{1} = D\mathbf{1}$). Since they're bipartite, they both also have eigenvalues of -1, with eigenvectors corresponding to being negative on one side and positive on the other: e.g. the column vector with parts $\mathbf{1}_L$ and $-\mathbf{1}_R)$.

The trick is to see that the other eigenvalues are zero. But this should be obvious, because the adjacency matrix of a complete bipartite graph only has two independent rows/columns. Any others are just copies of these.


Surveys on Algorithmic Problems in Coding Theory

There are known worst-case hardness results about ML decoding (for general and specific families of codes such as Reed-Solomon), computing or approximating minimum distance of codes, and so on. However there is a great room for improvement in these directions and several seemingly intractable problems are not analyzed yet.

There are coding theoretic problems that are conjectured to be intractable, such as problems related to decoding random ensembles of codes. Such intractability assumptions are related to hardness of learning noisy parities and also form the basis of coding-theoretic public key cryptography (which is a big area of research by itself). For a good account of the latter, see Lorenz Minder's thesis.

Finally, there's a survey on tractable algorithmic problems in coding, including recent developments in list decoding: Algorithmic Results in List Decoding. This is a good resource to quickly learn about basics of coding theory. Also for learning the basics, Luca Trevisan's article "Some Applications of Coding Theory in Computational Complexity" may be useful.


Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?

It's not a hidden link but one that has been made explicit using the language of category theory and also a very natural question to ask and study. There is a fair bit of material on the subject.

CS Theory question asking the same thing
Andrej Bauer's blog post about fixed point theorems and Cantor's theorem.
A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points, Noson Yanofsky, 2003. Gives you a gentle introduction to Lawvere's paper, below.
Diagonal arguments and cartesian closed categories, F. William Lawvere, 2006 republication of a 1969 article making these connections precise.
Incompleteness in a General Setting, John Bell, 2007
From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference, Samson Abramsky and Jonathan Zvesper, 2010. Extension of the Lawvere arguments to game-theoretic impossibility results.


Is this language recognizable by a 3 symbols TM in O(n log n)?

Can't you use the same idea as what you have for the case of 4 symbols, with the following modifications:

Always process a pair of symbols simultaneously.
In your "div 2" sweeps, mark a two-symbol block as "processed" by mapping $(00, 01, 10, 11) \mapsto (\epsilon0, \epsilon1, 0\epsilon, 1\epsilon)$. You still have $\epsilon\epsilon$ available as a "separator" that you can use at both ends, and you can recover the original data easily.
Use a similar trick for "mod 2" steps.

In general, you can squeeze in arbitrarily large amount of bookkeeping information with the help of the third symbol by processing $O(1)$ symbols at a time.


What are the relationship and difference between ambiguous grammars and non-deterministic ones?

See this related Wikipedia link:

http://en.wikipedia.org/wiki/Unambiguous_grammar#Recognizing_ambiguous_grammars

  The efficiency of context-free grammar parsing is determined by the
  automaton that accepts it. Deterministic context-free grammars are
  accepted by deterministic pushdown automata and can be parsed in
  linear time, for example by the LR parser.[3] This is a subset of the
  context-free grammars which are accepted by the pushdown automaton and
  can be parsed in polynomial time, for example by the CYK algorithm.
  Unambiguous context-free grammars can be nondeterministic. For example, the language of even-length palindromes on the alphabet of 0
  and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An
  arbitrary string of this language cannot be parsed without reading all
  its letters first which means that a pushdown automaton has to try
  alternative state transitions to accommodate for the different
  possible lengths of a semi-parsed string.[4] Nevertheless, removing
  grammar ambiguity may produce a deterministic context-free grammar and
  thus allow for more efficient parsing. Compiler generators such as
  YACC include features for resolving some kinds of ambiguity, such as
  by using the precedence and associativity constraints.

An ambiguous grammar may be defined as a grammar for which there exists more than one parse tree for some string belonging to the language it generates.

A deterministic grammar may be defined as a grammar for which there exists a deterministic machine model which is capable of recognizing the language it generates.

Assume Grammar 1 generates the same language as Grammar 2.  Assume Grammar 1 is unambiguous and Grammar 2 is ambiguous.  If a deterministic machine model is capable of recognizing the language generated by Grammar 1, then it is also capable of recognizing the language generated by Grammar 2 (by the assumption that they both generate the same language).  Clearly, both are deterministic grammars and yet they differ on the question of ambiguity.

The definition of grammar ambiguity addresses the actual syntactical structure of the grammar and its relation to parsing, NOT whether an ambiguous grammar could be structured differently so as to generate the same language and yet remove ambiguity.

The definition of grammar determinism, however, is not related to the structure of a grammar but rather to the properties of the language it generates regarding recognition by an appropriate deterministic machine model.


FL with polynomial number of log-space "reductions" still in FL?

The answer is no unless L=P (and obviously yes if L=P).  To see this, fix a deterministic Turing machine (DTM) M which solves a P-complete problem in polynomial time, and consider a function f which maps a configuration of M to the configuration in the next time step.  Function f is just the simulation of one step in the DTM and can be computed in logarithmic space.  If you iterate this function t times, you can compute the configuration after t steps, and therefore you can decide whether DTM M accepts on a given input string within t steps.  If you can do this in logarithmic space, you have solved the P-complete problem in logarithmic space, and therefore L=P.


If you look at the original paper by Lenstra, Lenstra, and Lovasz, you will see the following applications:

factoring univariate polynomials over the rationals (the motivation for developing LLL basis reduction)
efficient version of Dirichlet's classical diophantine approximation theorem: for rationals $a_1, \ldots, a_n$ and $\epsilon$, find in polynomial time integers $p_1, \ldots, p_n$, and $q$ such that

$$
\forall 1 \leq i \leq n: |qa_i - p_i| < \epsilon,
$$

and $q< 2^{n(n+1)/4}\epsilon^{-n}.$ Dirichlet proved this without the $2^{n(n+1)/4}$ factor, but his proof is a pigeonhole argument (sometimes called Dirichlet's principle) and does not yield an efficient algorithm.

efficiently find integer relations between rationals: given rationals $a_1, \ldots, a_n$ find integers $m_1, \ldots, m_n$ such that $\sum{m_i a_i}$ is minimized and the $m_i$ are not too large.

You can also check out Oded Regev's lecture notes which reference more applications. This book chapter by Hanrot gives details about quite a few applications of LLL to constructive versions of results in diophantine approximation.


Problems with no known quantum advantage

This is not in NP, but comparison-based sorting. The $\Omega(n \log n)$ lower bound is information theoretic.


Do Higher-Order Functions provide more power to Functional Programming?

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


The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

The probability that $x \in C + e$ is equal to $2^n \langle T_\rho 1_{0}, 1_{C+e} \rangle$, where $T_\rho$ is the noise operator and $\rho = 1-2\epsilon>0$. Now
$$
2^n \langle T_\rho 1_0, 1_{C+e} \rangle = 2^n \langle T_\rho 1_e, 1_C \rangle = \frac{2^n}{|C|} \langle T_\rho 1_{C+e}, 1_C \rangle.
$$
In terms of the Fourier expansion, this quantity equals
$$
\frac{2^n}{|C|} \sum_S \rho^{|S|} \widehat{1_C}(S) \widehat{1_{C+e}}(S) = \frac{2^n}{|C|} \sum_S \rho^{|S|} \widehat{1_C}(S)^2 \chi_S(e).
$$
Since $\rho > 0$, this is maximized uniquely when $\chi_S(e) = 1$ whenever $\widehat{1_C}(S) \neq 0$. In other words, the quantity is maximized uniquely for $e$ satisfying $C + e = C$.

Note that even when $C$ isn't a code, we have shown that if you start at a random point in $C$, apply the noise, and measure the probability that you reach $C + e$, then this probability is maximized for $e$ satisfying $C + e = C$, and in particular for $e = 0$.


Is there a backup/replacement for the Complexity Zoo?

I cannot remark on whether the Zoo has a continuous existence on the web or elsewhere. However, there are still some proto-Zoo and Zoo-derived resources available on the web.

There seems to be a copy of at least an earlier incarnation of the Zoo on Greg Kuperburg's UC Davis website.
A Latex/PDF version of some state of the Zoo written by Chris Bourke seems still to be available on his webspace at the University of Nebraska–Lincoln.

Other sources on the net seem to be links to the first (or to the URL to the stanford.edu subsite), or pieces of the second.

It is worth noting that the entire qwiki.stanford.edu subsite seems to have disappeared, and that google searches for "qwiki", with or without specifying "stanford", either yields references to a multimedia product launched in January of last year, or produces the typical spoor of SEO companies trying to leach off of online resources.


I'm not an expert, but perhaps this recent survey can help you:

K. Santle Camilus, V. K. Govindan, A Review on Graph Based Segmentation;
I.J. Image, Graphics and Signal Processing, 2012, 5, 1-13

Abstract: ... The major
four categorizations we have employed for the purpose of
review are: graph cut based methods, interactive methods,
minimum spanning tree based methods and pyramid
based methods. This review not only reveals the pros in
each method and category but also explores its
limitations. ...


Applications of Ramsey theory to CS, Gasarch


Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

It depends what you mean by "learn[ing] the manifold", but here are a few papers that present some algorithms and a theoretical analysis:

Isomap (see tech report by Bernstein, de Silva, Langford and Tenenbaum)
Random linear projections (see paper by Ken Clarkson)
Nash-type embedding (see paper by Nakul Verma)
Maximum variance unfolding (see arXiv:1209.0016)

In terms of using/exploiting manifold structure to help learning or estimation, there are many such results. For example, many of the papers by Misha Belkin and Samory Kpotufe explore this direction.


Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

While parity games are known to be in both, it's been claimed that stochastic parity games are not known to be in UP intersect coUP.


Polynomial time construction of families of pairwise nonhomomorphic graphs

Take cycles $C_{p_1}, \ldots, C_{p_n}$ where $p_i$ is the $i$th prime number.

We can find the first $n$ prime number in time polynomial in $n$.


Splay trees can easily do this, with their nodes augmented to have two extra pieces of information: the total number of descendants of each node (so you can answer retrieve queries), and a reverse bit, such that the roles of the left and right pointers at node x are reversed if x and its ancestors have an odd number of reverse bits. The amortized time per operation would be O(log n).

Whenever the tree is rotated it is possible to update this extra information in constant time (and maintain consistency of the reverse bits so that each node has the same parity of ancestral reverse bits as it did before the rotation). To handle a retrieve, just do a binary search down through the tree using the number-of-descendants of the left subtree at each step to determine whether to go left or right (and then as with any splay tree operation, splay up the node found by the retrieve). To handle a reverse operation, split the splay tree at i and j to form three trees, flip the reverse bit of the root of the middle tree, and concatenate them back together again.

I'm not sure of a published reference but looking through the splay tree literature might work. The one I'd try first is Tarjan's Data Structures and Network Algorithms, but I don't have time right now to check it.


Minimum chordless odd-cycle graph completion: is it NP-hard?

We prove that the problem is NP-hard even in its decision form, i.e. ''Is the input graph $G$ already a chordless odd-cycle completion?'' by reduction from the following problem:

  Problem P: Given a graph $G$ and an edge $e\in E(G)$, is there an chordless odd cycle of length greater than 3 passing through $e$?

This problem is known to be NP-hard by reduction from ''detecting chordless even cycles passing through a given node'' in the reference given in one of your comments which is stated in the paragraph before section 3 by letting $p=0$ and $q=2$:

  As an aside, let $q>1$ and $p\ge 0$ be arbitrary fixed integers. The following problems are NP-complete: Does a graph $G$ contain an induced cycle through a prescribed vertex $u$, of length $p$ (mod $q$)? ...

(There may be a Karp reduction, but if we allow a Cook one, consider the following reduction: Replacing the given degree d node into a complete subgraph of size d with proper outgoing edges.  Then for each edges in the complete graph we can query the oracle that solves Problem P.  Note that a chordless even cycle passing through the given node corresponds to a chordless odd cycle of length greater than 3 passing through one of the edges in the complete graph.)

Now for the main reduction.  Given an instance of Problem P, first we detect if there are any triangles passing through $e$; if so, delete every node that forms a triangle with $e$.  Note that deleting nodes that forms a triangle with $e$ will not removing any chordless odd cycles passing through $e$ (by the chordless property).

Next, for each edge $f$ other than $e=(u,v)$ we add an auxiliary node $v_f$ and two edges $(v_f,u)$ and $(v_f,v)$.  Observe that the new graph $G'$ has the following property:

  $G$ has a chordless odd cycle of length greater than 3 passing through $e$ if and only if $G'$ is a chordless odd-cycle completion.

For the only if direction, it can be proved by considering different types of edges in $G'$.  Every edge other than $e$ (including those newly added edges) will be in at least one triangle (the one that contains the auxiliary node); and $e$ will be in a chordless odd cycle in $G′$ since there is a chordless odd cycle passing through $e$ in $G$, and the cycle is not removed during the node-deleting process.

For the if direction, since every edges other than $e$ must be in at least one triangle, we only have to worry about the edge $e$.  There is a chordless odd cycle passing through $e$ in $G'$ ($G'$ is a chordless odd cycle completion).  The cycle cannot have length 3 by construction of $G'$, and since the cycle cannot contain any auxiliary nodes (by chordless property), it will be in graph $G$ as well.  Therefore the proof is complete.


Since you've tagged machine learning, I'll address this setting. Indeed, for the usual $\ell_p$ norms on $\mathbb{R}^n$, we have $||x||_p\le ||x||_q$ for $p>q$. However, in machine learning applications, these are normalized norms (see, e.g., Mendelson, A few notes on Statistical Learning Theory
https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/readings/mendelson.ps
).
Let $D$ be a distribution on $\{1,\ldots,n\}$. Then the corresponding $\ell_p(D)$ norm is defined by
$$
||x||_{\ell_p(D)}^p = \sum_{i=1}^n D(i)|x_i|^p.
$$
You can verify that for these norms, the inequality goes the other way:
$||x||_{\ell_p(D)}\ge ||x||_{\ell_q(D)}$ for $p>q$. This explains the covering number inequality as well.


Existing implementation of Scott's reduction?

You might check the FO2 solver by Tomer Kotek: https://forsyte.at/alumni/kotek/fo2-solver/
This is the only existing FO2 solver (Tony Tan with his student are working on developing something too).
Answering the question, the authors implemented an improved version of Scott Normal Form, called therein "Skolemized Scott Normal Form". All the details are available here: https://arxiv.org/pdf/1610.02101.pdf


How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?

I think its easier to turn it around.

If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$
for some constant $c$, and any $T(n) > n$.
Since $\mathsf{DTIME} ((T(n)^c)$ does not contain
$\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$,
this means we cannot solve, say all problems in $\mathsf{DTIME}(2^n)$ in
$\mathsf{NTIME} (2^{\epsilon n})$ for some $\epsilon$.
So a non-deterministic time $2^{o(n)}$ algorithm for a problem complete for
$\mathsf{DTIME} (2^n)$ under quasi-linear reductions would be enough to prove $\mathsf{P} \neq \mathsf{NP}$.


How to generalize a map of type for many operators?

The way Haskell solves this problem is through Type Classes (see these papers for an overview). The idea is that it is not the $\_^{-1}$ operation that is special; it is the $\mathrm{\bf Array}$ type! To this end, you can define a (statically) overloaded method $map$ which works on each such type. In Haskell:

class Mappable m where
  map : (a -> b) -> (m a -> m b)

Then you can instantiate this for arrays (in pseudo-Haskell):

instance Mappable Array where
  map f v = [f(v[i]) | i in (index v)]

By the way, this class exists and is widely used in Haskell, it goes by the name Functor (and $map$ is $fmap$ for some reason).

This solves the problem for unary operators. For binary operators, or more generally, $n$-ary operators, things get a tiny bit trickier: in this case, you need to figure out what you mean. Do you want the sum of all pairs of numbers in each array, or just the "fusion" of the arrays by the operation sum? I suspect you mean the latter. The way to solve this problem is by another Type Class named $\mathrm{\bf Applicative}$. The definition is

class Applicative m where
  pure  :: a -> m a
  fusion :: m (a -> b) -> m a -> m b

and

instance Applicative Array where
  pure x = [x]
  fusion fs v = [fs[i](v[i]) | i in index v]

The idea is that you can use map to "build up" arrays of partially applied functions, and then use fusion to apply that array of functions to an array of arguments. In the case of $+$ you can just write

fusion (map + [1;2;3]) [4;5;6]

to get what you want. I agree that this is ugly, which is why Haskell has the notation

+ <$> [1;2;3] <*> [4;5;6]

The beauty is that you can iterate this as many times as you want if your function takes more arguments. For example $\mathrm{rem\_mod}$ that computes the remainder of a number $n$ divided by $m$ modulo $r$ of type

rem_mod : Int -> Int -> Int

can be lifted:

rem_mod <$> [1;2;3] <*> [4;5;6] <*> [7;8;9]

You can find more details here. Finally, I suspect you want to be able to infer the places in which to insert the $\mathrm{pure}$, $\mathrm{map}$ and $\mathrm{fusion}$ methods. It may be possible to adapt the type-class resolution mechanism to your purposes, but I don't guarantee you can do this without additional restrictions.


Recommendations for References on undecidability of First Order Logic

Let me clarify one subtle point: first order logic is only undecidable for certain given languages. In particular the language $\cal{L}$ that contains only monadic predicates, that is, predicates of the form $P(x)$ and no function symbols, is decidable.

If you allow function symbols or predicates with more than 1 argument, then $\cal{L}$ usually becomes undecidable. The proof involves encoding Turing machines and their computation sequences using the symbols of the logic. Then one adds a finite series of axioms $\phi_1,\ldots, \phi_n$, and build a formula $\psi(x,y)$ such that
$$ \phi_1,\ldots,\phi_n\vdash \psi(\overline{n},\overline{m})$$
is provable if and only if

  The Turing machine with index $n$ halts in at most $m$ steps on the empty input.

Undecidability of FOL follows, as proving

$$ \vdash \phi_1\wedge\ldots\wedge\phi_n\rightarrow \exists y,\psi(\overline{n},y)$$

is equivalent to determining wether the machine with index $n$ halts.

A detailed description of this proof is given in chapter 4 of Avigad's lecture notes on computability.


why are the constraints in the following paper tight?

Well, if any constraint is loose you can just decrease the corresponding $\xi_i$ until the constraint becomes tight, in which case you are only decreasing the objective value and get a better solution.


How is the iteration space of a nested for-loop containing two sequential nested loops represented?

This isn't really my area, but I think you want to Google for "the polytope model" or "the polyhedral model", and specifically for "affine-by-statement scheduling". The basic idea is that iterations in a loop nested $d$ deep are turned into a $d$-dimensional polytope, and that each iteration is a point within the polytope. You can then look at data dependencies between the iterations to figure out how to parallelize code (which turn out to correspond to affine transformations of the polytope).


Possible to do Complexity theory with only counting and Pigeonhole

If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which are not proof by contradiction, and therefore, in particular, are not instances of the pigeon-hole principle. There are also proofs by contradiction where the pigeon-hole principle is necessary but not sufficient.

My personal opinion: It is fruitful to take apart a proof and see why it works: what are the ingredients? When you understand the ingredients, a proof ceases to be a monolithic line of reasoning and "symbol-pushing", and it will become a modular object with identifiable moving parts, which you can then reuse between proofs, eventually making your own ones. As a corollary, you are right to become wary when all your results derive most of their power from one core lemma (such as PHP in this case), because it means that you are probably working within the narrow confines of that lemma, and you may benefit from learning and incorporating other theorems from other fields into your work (See also Terry Tao's advice, and more advice on this topic)

Hence it is useful to identify which proofs, and which parts of those proofs, are the PHP or versions and extensions thereof. At the same time, however, we must be careful to mark any and every type of counting argument as a PHP-argument, and even more careful to discard any proof that incorporates a pigeon-hole argument. Usually, the counting argument is only the closing argument to "plant the flag on the mountain", but the counting argument is used at a point that you can only get to when you've already done the bulk of the work, when "you've climbed the mountain", which is arguing why the one set is bigger than the other. The IP=PSPACE example is instructive here: It is true that there is a counting argument involved, but the more sophisticated part of the proof is arguing that Arthur's random choices usually lead to acceptance. This invokes the Fundamental Theorem of Algebra, which is typically proved using complex analysis via properties of holomorphic functions (Wikipedia lists four proofs, none of which can be said to boil down to PHP).

An extreme analogy: every line of every proof is an instance of modus ponens. But would be unfair to object that proofs simply boil down to modus ponens.

The most immediate concept that is not a proof by contradiction is algorithms.

For example, the algorithm of the Cook-Levin proof that SAT is NP-Complete transforms a (Turing Machine, input)-pair to a Boolean Circuit, or to a 3-CNF formula, according to taste. The proof then argues that this transformation preserves both soundness and completeness. This is not a pigeon-hole type argument, because it is constructive in the sense that they argue that something is possible, whereas the pigeon-hole principle argues that something is impossible.

More generally, all results which state that a language $L$ is complete for a complexity class $\mathcal{C}$ are constructive in this sense.

Is IP=PSPACE a pigeon-hole type argument?

The part of the proof of the sumcheck's protocol's soundness amounts, in the end, to saying "The polynomial does not have enough zeroes, relative to the size of the field, to fool Arthur with good probability." According to taste, this sentence may or may not be an instance of the pigeon-hole principle.

The protocol's soundness relies on, not just that the field is bigger than the number of the polynomial's zeroes, but it relies on the fact that the ratio of non-zeroes to zeros is large enough (sufficiently large for Arthur to guess a non-zero in each iteration of the protocol, with $1-\frac{1}{poly(n)}$ probability). This reasoning about ratios goes beyond the pigeon-hole principle: I would say this part of the proof is by counting, but not by pigeon-hole principle.

The proof argues that the protocol terminates in polynomial time. To this end, it requires polynomial-time randomized algorithms for guessing a large prime and computing $+,-,\times$ modulo large primes. The proof also argues that the arithmetization of a Boolean formula preserves its behaviour on the Boolean cube. These ingredients are non-trivial and necessary. Hence to this end, the pigeon-hole principle may be necessary, but is not sufficient.

Is the time hierarchy theorem a pigeon-hole type argument?

The proofs of the time- and space hierarchy theorems are not necessarily pigeon-hole type, even though they are proof by contradiction. However, they are identical in structure to (perhaps inspired by) Cantor's proof that some infinities are bigger than others, establishing a pigeon-hole principle for infinite sets (in particular, I have taught a class where I proved these two theorems at the same time, on two adjacent black boards, walking over from one to the other for every new line). Cantor's proof is diagonalization, and from diagonalization follows a type of pigeon hole principle for infinite sets. However, there are two things to be said against counting the time hierarchy theorem as a pigeon-hole type argument. First, the proof is by diagonalization, not by counting. Second, there are many more ingredients in the proof, without which, it would not go through; for instance, a simulation of one Turing Machine by another; for stronger versions, an efficient simulation, which in turn uses such ingredients as shifting the tape to achieve low amortized time complexity. The diagonalization is necessary but not sufficient.


$\ell_1$ norm of Fourier coefficients vector for the hypercube

The question is about the spectral norm of the symmetric function $h: \{0,1\}^n \to [-1,+1]$ defined as $h(x) = f(1-2|x|/d)$. (I have assumed range $[-1,+1]$ instead of $[0,1]$ which is wlog by appropriate rescaling.)

Ada, Fawzi and H. Hatami show that for any boolean $g: \{0,1\}^n \to \{-1, +1\}$, $$\log \|\hat{g}\|_1 = \Theta\left(r(g) \log\left(\frac{n}{r(g)}\right)\right)$$ where $r(g) = \max(r_0(g), r_1(g))$ and $r_0(g)$ and $r_1(g)$ are minimum integers such that $g$ is either constant or perfectly correlated with parity or anti-parity for $x$ with $|x| \in [r_0(g), n-r_1(g)]$.

Now, look at the proof of Lemma 3.1 in the paper. Note that this straightforward argument also holds for functions $h$ mapping to $[-1,+1]$ instead of $\{-1,+1\}$. So, the same upperbound also holds for your case. This upperbound is tight at least for the boolean functions, but I don't know if there's a similar general lowerbound for non-boolean $h$.


Efficient algorithm for finding directed cycle with smallest average weight

Karp has an algorithm that does exactly that. You can read about it in his paper "A characterization of the minimum cycle mean in a digraph."

There seem to be other algorithms proposed here which are perhaps easier to read.


what is the equivalence class of a given polytree representing a directed graphical model?

You can pick any other node as root and redirect nodes away from it to get Markov equivalent model. Markov equivalent means that two graphical models correspond to identical spaces of distributions.

Let "unshielded collider" be structure of the form A->B<-C

Theorem: Two directed acyclic graphs D1 and D2 are Markov equivalent if and only if D1 and D2 have the same vertex set, same adjacencies, and same unshielded colliders.

See Ch.4 of Meek's "Related Graphical Frameworks: Undirected, Directed Acyclic and Chain Graph Models"
http://repository.cmu.edu/cgi/viewcontent.cgi?article=1206&context=philosophy


Instance of FPT-reductions that is not a polynomial-time reduction

An early example is the W[2]-hardness proof for Tournament Dominating Set (Theorem 4.1 in [1]). The reduction is from Dominating Set and it constructs a tournament with $O(2^k n)$ vertices, where $n$ is the number of vertices of the dominating set instance and $k$ is the parameter.

[1]: Rodney G. Downey and Michael R. Fellows. Parameterized computational feasibility. In
P. Clote and J.B. Remmel, editors, Proceedings of Feasible Mathematics II,
pages 219-244. Birkhauser, 1995.


How do you call a subsequence of consecutive elements ?

In programming languages and libraries, it is usually called either a substring or a slice.

The former term is ubiquitous, and I would not mind using it even if your "characters" are a bit weird.

The latter term is neutral in the sense that it does not refer to strings. See array slicing in Wikipedia for more information and examples.


Encrypting or obfuscating transport stream identifiers in SSL-like connections

Use a variation on your shared secret-key encryption proposal: Every packet has an encrypted header for which the plaintext is the connection ID concatenated with the packet sequence number. After successfully receiving a (connection, n) packet, the next packet received on that connection will be (connection, n+1). Store the encryption of (connection, n+1) in a hash table and remove the expired entry for (connection, n). When receiving a packet, do a hash table lookup using the packet's encrypted header word to find out its associated connection. Obviously for this to work, sender and receiver must use synchronized ciphers (e.g. a stream cipher initialized with a negotiated IV and the shared secret key).

You can easily extend this algorithm to deal with longer sliding windows by adding hash table entries for sequence numbers n through n+k. The space cost is O(mk) where m is the number of open connections and k is the length of the sliding window.


One non-answer to your question is that SQUARE-FREE (is a number square free) is itself not known to be in P, and computing the Möbius function would solve this problem (since a square free number has $\mu(n) \neq 0$).


How far has computer science moved past Knuth's TAoCP, if at all?

Matrix multiplication exponent has been improved and integer multiplication has recently reached speculated optimal complexity.

Perhaps Han`s sorting applies if correct (on which there was a post here).

Note Knuth`s book is his view.

Modern view is richer. For example I doubt Knuth has spent much time on $NC$ algorithms for perfect matching or derandomization of primality or linear programming or counting algorithms.

So perhaps the algorithms he studies probably on whole not much more progress. However the analogy to mathematics that mathematics problems open in classical view does not mean mathematics has not moved forward holds in algorithms.


3-Clique Partition for graphs of fixed diameter

The problem seems to be in $P$.

Take two vertices $u$, $v$ with distance exactly 3 (such a pair must exist when $p\ge 3$). They must have different colors (I will use R, G, B to denote 3 colors and the vertices in the same clique are colored the same color). Wlog assume $u$ is colored Red and $v$ is colored Green.

Now the rest of the vertices are partitioned into 3 sets: $\Gamma(u)$ (neighbors of $u$), $\Gamma(v)$ and $V-\Gamma(u)-\Gamma(v)$. The third set must be colored Blue because they are  adjacent to neither $u$ nor $v$. Neighbors of $u$ must be colored either Red or Blue because they are not adjacent to $v$, similarly neighbors of $v$ must be colored either Green or Blue. Each vertex now has at most two choices, therefore the problem becomes a 2-SAT instance that we can solve in polynomial time.


This should be EXPSPACE-complete. I'll sketch how to achieve an exponential number of alternations, without reducing any EXPSPACE-complete problem to this one, but from here it should be simple to finish.

Denote the words in the oracle after $t$ rounds by $A_t$, so initially $A_0=\emptyset$.
Denote the words queried by $M^{A_t}$ by $Q_t$.
The main observation is that whoever is losing with $A_t$, can be assumed to add something from $Q_t$ to $A$.
This is because in this game every move costs money, we want to move as little as possible; there's no point making a move until we're winning.
But this also implies that if we're losing, there's no point adding anything from outside $Q_t$.

Assume for simplicity that $M$ runs for exactly $2n$ steps and at steps $2i$ and $2i+1$ it queries a word of length exactly $i$.
The cost function $f$ will simply be $2^{-i}$ on words of length $i$.
The game will be such that Alice always needs to add odd length words and Bob always needs to add even length words to $A$.
Suppose that $n$ is odd and initially Alice is losing.

The budgets $m_A$ and $m_B$ will be set so that she can choose exactly one of the length $n$ words queried by $M^{A_0}$ to be added to $A$.
The game will be such that this makes her the winner, so Bob will have to move.
Again due to budget constraints, he will have to choose exactly one of the length $n-1$ words queried by $M^{A_1}$ to be added to $A$.
After any of these are added, $M^{A_2}$ will query two new length $n$ words (the same ones, regardless of what word Bob added to $A$), and Bob will win.
Alice will be forced to add exactly one of these new length $n$ words to $A$ to make her win.

The game goes on in this manner, which can be imagined as following the branches of a complete binary tree of depth $n$, though at each branching node one of the players (determined which by the parity of the depth of the node) needs to make a choice about which word to add to $A$.
After they go through the tree, they will run out of their budget.
If at any stage of the game one of them decides to add some word that is shorter (e.g., Alice a length $k<n$ word from $Q_0$ in the first step), then if the other player (in our example Bob) just plays always the longest word he can in the binary tree, he will have some money left at the end and we make the game so that he can use this to win.
(Note that Alice might also have some money left, but Bob will have more, so we design the end-game that if one of them has more money, then that player can win.)

This way Alice decides for exponentially many pairs of odd-length words, and Bob about exponentially many even-length words which one of each pair goes to $A$, and they make these choices in an alternating manner.


Does Hadwiger conjecture imply that NP = coNP?

I think the problem here is that you are stating the converse of Hadwiger's conjecture. The conjecture (according to Wikipedia) states that "if a graph needs at least k colors for a proper coloring, then it contains a $K_k$ minor (i.e. there exist subgraphs $G_1,\ldots,G_k$ as you state)". You are talking about the assertion that "If a graph has a $K_k$ minor, then it needs at least k colors for a proper coloring".

These two are not equivalent. Indeed, the latter statement is false. Consider for example a $K_{n,n}$. This graph contains a $K_n$ minor (take a perfect matching, this gives a collection of $n$ connected components all of which have edges to each other). However, its chromatic number is 2.


What is the tradeoff between population size and the number of generations in genetic algorithms

There are some works on this issue. Since you don't specify for what problems you want guidelines I will list some major and some last papers of general interest. They are:

C. Witt (2008) Population Size versus Runtime of a Simple Evolutionary Algorithm // Theoretical Computer Science, 403(1), pp. 104-120.
T. Chen, K. Tang, G. Chen and X. Yao A large population size can be unhelpful in evolutionary algorithms // Theoretical Computer Science. Article in Press
O. Giel, P.K. Lehre (2010) On the effect of populations in evolutionary multi-objective optimisation // Evolutionary Computation 18 (3), pp. 335-356.
P.S. Oliveto, J. He, X. Yao (2008) Analysis of Population-based Evolutionary Algorithms for the Vertex Cover Problem. In Proceedings of the IEEE World Congress on Computational Intelligence.
P.S. Oliveto, J. He, X. Yao (2007) Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results // International Journal of Automation and Computing. See here 4.1 section for results on population-based EAs.


Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

The short answer is that the state we wrote down is only an approximation in the large $n$ limit (which is all that is required to prove the upper bound). The state isn't normalized for finite $n$, but becomes normalized as $n \rightarrow \infty$. It looks like we either used a different approximation than what I will describe below, or made a typo - thanks for pointing this out! - but these details don't affect our proof.

The details:

After $t$ Grover iterations, the exact state of the system is
$\sin((2t+1)\theta) | x \rangle + \cos((2t+1)\theta) \Sigma_{y\neq x} \frac{1}{\sqrt{2^n-1}} | y\rangle$
Where $\theta$ is such that $\sin(\theta) = 2^{-n/2}$ (this exact solution is given in Nielsen & Chuang Section 6.1.3).

Working with the exact expression isn't very informative about how this state behaves asymptotically. So most of the time, to analyze asymptotics, people use the approximation that for small $\theta$, we have that $\sin\theta \approx \theta$ and $\cos\theta\approx 1-\theta^2/2$. Using this approximation, you can show that if you set $t=2^{n/3 -1}$, then your resulting state is $\approx \frac{2^{n/3}+1}{2^{n/2}} |x\rangle +\left(1-\frac{1}{2}\left(\frac{2^{n/3}+1}{2^{n/2}}\right)^2\right) \Sigma_{y\neq x} \frac{1}{\sqrt{2^n-1}} | y\rangle$. Note we've lost the normalization because of our approximation - so if you plug in any $n\in\mathbb{N}$ as you did, you'll get a non-normalized state. However as $n\rightarrow\infty$ the state becomes normalized, because the approximation $\sin\theta\approx \theta$ becomes increasingly accurate.

From this, you can easily see that if you measure this state, you see $x$ with probability $\Theta(2^{-n/3})$. Hence if you could perform $\tilde{O}(2^{n/3})$ non-collapsing measurements, you'd see the marked item once with constant probability. This is all we're using about the state to prove our upper bound.


Status of Raghavendra's algorithm for solving linear systems in finite fields

This is a paper that seems to improve upon the result. https://arxiv.org/pdf/1209.3995.pdf


Are there protein-based computational models?

Membrane Computing is a model that is based on the possibility or not of movement of molecules through membranes; also on possible reactions of these molecules inside a membrane compartment. While this is not specifically talking about proteins, in reality some of these molecules and the channels through which they pass would be proteins.

Here is an overview written by the creator of this model.

Another model possibly involving proteins is Computing by Observing which models the way that a person conducting an experiment extracts information from what she/he sees. The observed process may very well model protein interactions.


Does the Law of Excluded Middle imply the Axiom K in Martin-Löf's Intensional Type Theory?

Yes, LEM implies K. See HoTT book Theorem 7.2.5, known as Hedberg's theorem, which shows that any type with decidable equality satisfies axiom $K$. If we assume excluded middle, all types have decidable equality.

Your second principle is known as UIP or Uniqueness of Identity Proofs. It is equivalent to Axiom K, see Theorem 7.2.1 in the HoTT book (just scroll up from 7.2.5 by one page). Neither of these can be derived in Martin-Löf intensional type theory, by a famous result of Thomas Streicher and Martin Hofmann.


Testing low degree bivariate polynomials

If you only care about the first variable, then I believe the following simple test should work: pick a random value $\beta \in \rm{GF}(q)$ and check that $f(\cdot, \beta)$ is a univariate polynomial of degree at most $d$ - say, by choosing few collections of $d+2$ points of the form $(\cdot,\beta)$ and interpolating them.

The analysis of this test should be trivial: If the function is far from being of degree $d$ in the first variable, it must be far from a univariate polynomial of degree $\le d$ for many values of $\beta$.

If you wish to test that $f$ is of degree $\le d$ in both variables, you can use the (highly non-trivial) result of Polischuk and Spielman from 1994, which is proved in Sections 2-5 in the following paper (see Theorem 9):
http://cs-www.cs.yale.edu/homes/spielman/Research/holographic.html


Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

"So, applying MIS on $g$"

To apply the Majority is Stablest theorem, you need to apply it to a non-negative parameter $\rho'\in[0,1)$ (read the statement of the theorem). Since in Proposition 7.3 the parameter $\rho\in(-1,0]$ is non-positive, this means you here apply it to $\rho' \stackrel{\rm def}{=} -\rho\in[0,1)$, giving $$\mathbb{S}_{-\rho}(g) \leq 1-\frac{2}{\pi}\arccos(-\rho)+\epsilon =  -1+\frac{2}{\pi}\arccos(\rho)+\epsilon$$
using that $\arccos x+\arccos(-x) = \pi$ for all $x$ (This may very well be the part you are missing. $\arccos$ is not an odd function).
Then
$$\mathbb{S}_{\rho}(f) \geq -\mathbb{S}_{-\rho}(g)  \geq -\left(-1+\frac{2}{\pi}\arccos(\rho)+\epsilon\right) = 1-\frac{2}{\pi}\arccos(\rho)-\epsilon$$
as stated.


Planarity of planar finite automata intersection

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: for two languages $L_1$ and $L_2$, let $L_1 Ш L_2$ denote their shuffle (aka interleaving). Let $L_d = (a_1b_1)^* Ш \ldots Ш  (a_db_d)^*$. This language can be expressed as the intersection of the $d$ languages $L_i = (\Sigma\setminus\{a_i,b_i\})^*(a_ib_i)^*(\Sigma\setminus\{a_i,b_i\})^*$. The minimum DFA for $L_d$ is isomorphic to the $d$-dimensional hypercube and has $n=2^d$ states. On the one hand, in (Gruber/Holzer, DLT '09) a lower bound of $2^{\Omega(n/\sqrt{\log\log n})}$ on required regular expression size for $L_d$ is shown. On the other hand, it is proved in (Ellul/Krawetz/Shallit/Wang, JALC '05) that an $s$-state planar  NFA can be converted into an equivalent regular expression of size at most $2^{O(\sqrt s)}$. This shows that $s$ must be in$\Omega(\frac{n^2}{\log\log n})$, as desired.
References:

Keith Ellul, Bryan Krawetz, Jeffrey O. Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. J. Autom. Lang. Comb. 10(4): 407-437 (2005)
Hermann Gruber, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287


Is the problem of finding the "all-terminal connectivity polynomial" polynomially bounded?

I'll convert my comment to an answer.

The problem of computing the Rel(G) is #P-Complete (see this paper by Karger), and there's also an FPRAS for 1-Rel(G) (also in the Karger paper). Note that if you could verify whether Rel(G) was less than any fixed number $k$, then you could binary search for an approximate solution for Rel(G) that would run in P-time, which seems a little unlikely.


Complexity of a variant of the Mandelbrot set decision problem?

Let's look at $M$ for fixed $k$ first.

Given a fixed $k$ in unary, the problem essentially reduces to figuring out the algebraic set $|P_c^{(k)}(0)| = 2$.  Since the level sets 'at infinity' are properly nested, the question becomes a membership test in an algebraic set.  The issue is that the minimal polynomial is of degree $2^k$.  However, one can represent it as a straight-line problem of size $k$.

So then the question becomes: what is your arithmetic model?  You'll need arbitrary precision arithmetic to do this 'right', and then counting bit operations or counting "real number" operations will give radically different answers [NP-hardness is rather fragile that way, unlike 'computability'].

For arbitrary $k$, things get messier still.  It really depends on whether one would have a uniform modulus of continuity; if that were the case, then the Mandelbrot set would be locally connected, which would indeed be a breakthrough.  So I rather think that that problem is open.

Looking up the Yampolsky and Braverman book is a good idea in any case.


This isn't a full answer, but a partial one since there's a lot of literature out there.

To answer the question, we need some model of how information spreads in a social network. You seem to maybe be assuming that everyone we talk to tells their friends, but their friends don't tell anyone (so we just want to pick the set that maximizes the number of neighbors). But many other dynamics are possible. Usually, one thinks of the problem as finding an initial set of nodes to "infect", and assuming that all nodes have some rule for when they get infected as a function of the number of infected neighbors. For example, you could have a threshold which says that I get infected as soon as I have 3 or more infected neighbors; or that $i$ has a probability $p_{ij}$ of getting infected from $j$ in the timestep after $j$ is first infected.

The original/classic paper for this problem is Maximizing the Spread of Influence Through a Social Network by Kempe, J. Kleinberg, and Tardos in 2003.1 If you search it on Google Scholar you'll see something like 1500 citations, so there is a lot of work in this area. You can see some on Jon Kleinberg's homepage under "Information Flow and Cascading Behavior in Networks"; he gave a survey talk on the area at this year's EC, but I don't know if the slides are available anywhere.

In 1, the authors show that, under several models of influence like those mentioned above, the "influence" of a set of vertices is a submodular function ; this allows greedy algorithms to find a set of initial nodes that gives a $1-1/e$ approximation to the best total influence. (However, solving the problem exactly is NP-hard.)

1 http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf


Complexity of counting poset automorphisms

Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.


First, Kaveh is correct that the verification for IPS is randomized, so all it would show is $\mathsf{NP} \subseteq \mathsf{coAM}$ (not $\mathsf{NP} = \mathsf{coNP}$). However, this alone would still be enough to collapse the polynomial hierarchy.

Second, I think the actual thing you are missing here is that the IPS proofs they give have size polynomial in the size of $|A| = |\{\sum_i \alpha_i x_i : \vec{x} \in \{0,1\}^n\}|$, which can be exponential in $n$, in general.


Reference for Dyck languages being $\mathsf{TC}_0$-complete

Here is an $AC_0$ reduction from $\rm Majority$ to $Dyck(1)$.
(This implies that $\rm Majority$ is $AC_0$ reducible to $Dyck(k)$ for all $k \geq 1$.)
In order to do it, we construct a poly-size
constant depth circuit whose gates are $AND$, $OR$, $NOT$ and $Dyck(1)$.

Given an instance $x \in \{0,1\}^n$ of $\rm Majority$ do
Compute $y \in \{0,1\}^{2n}$ by replacing each $0$ with $(($ and each $1$ with $()$.
Now for each $i = 1,\dots, n/2$ let $z_i$ be the string obtained by concatenating $y$ with $2i$-many closing parentheses, i.e. $z_i = y \circ )^{2i}$.
If $z_i \in Dyck(1)$ for some $i = 1,\dots, n/2$ then ACCEPT.
Otherwise, REJECT.

This can be clearly done with a constant depth circuit. (Computing $z_i$ can be done in depth 1, and computing the last step is done using an $OR$ gate.)

It is also easy to see that this circuit indeed computes $\rm Majority$ because $z_i \in Dyck(1)$ if and only if ${\rm weight}(x) = n - i$.


Some missing topics from my collection of graph algorithms articles:

Dynamic graph algorithms
K shortest paths
Spanners and approximate shortest path data structures

Also, not so much missing topics, but a lot of the articles on topics covered by undergraduate algorithms classes kind of look like they were written by students in those classes. There's a deeper level of understanding missing, and they take a dogmatic point of view that reflects a single textbook rather than a synthesis of multiple sources. More expert help there could be useful.


Membership testing in transformation monoids

The nondeterministic polynomial-space algorithm for this problem works as follows:

Initialize h: A→A to the identity mapping.
Is h=g?  If so, we found out that g is in the monoid generated by S; accept and halt.
Guess one element f∈S.
Update h to f∘h.
Go to step 2.

As you correctly pointed out, the sequence can be exponentially long in the input size, so this algorithm may take exponential time before accepting.

Note that the algorithm does not guess a whole sequence at once and store this sequence in the work space—doing so would require exponential space.


Are there knot theoretic formulations of NP complete problems?

You can take a look to:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, and Aleksandar Chakarov. 2009. Tricolorable torus knots are NP-complete. In Proceedings of the 47th Annual Southeast Regional Conference (ACM-SE 47). ACM, New York, NY, USA, , Article 42 , 6 pages.

Abstract: This work presents a method for associating a class of constraint satisfaction problems to a three-dimensional knot. Given a knot, one can build a knot quandle, which is generally an infinite free algebra. The desired collection of problems is derived from the set of invariant relations over the knot quandle, applying theory that relates finite algebras to constraint satisfaction problems. This allows us to develop notions of tractable and NP-complete quandles and knots. In particular, we show that all tricolorable torus knots and all but at most 2 non-trivial knots with 10 or fewer crossings are NP-complete.

and also to its seminal report:

P. Golbus, R. W. McGrail, M. Merling, K. Ober, M. Sharac, and J. Wood. The class of constraint satisfaction problems over a knot. Technical Report number
BARD-CMSC-2008-01, Bard College, 2008.


Expanding my comment:

Computing the permanent of a matrix is #P-hard (Valiant 1979) even if the matrix entries are all either 0 or 1.

We can interpret a matrix $M \in \{0,1\}^{n \times n}$ as a bipartite graph $G$ with left vertices $[n]$ and right vertices $[n]$, where the edge $(i,j)$ is present if and only if $M_{i,j}=1$. A perfect matching is a subset of the edges of $G$ such that every left and right vertex is incident to exactly one vertex in this subset. Now the permanent of the matrix $M$ is simply the number of perfect matchings in $G$.

To see why this is the case, note that each perfect matching in $G$ can be uniquely specified by a permutation $\sigma : [n] \to [n]$. So that the matching is the set of edges $\{(i,\sigma(i)) : i \in [n]\}$. That is each left vertex $i$ is matched to right vertex $\sigma(i)$. A permutation $\sigma$ is a valid matching if and only if all the edges $(i,\sigma(i))$ are present in $G$. By the definition of $G$, a permutation $\sigma$ gives a valid matching if and only if $\prod_{i=1}^n M_{i,\sigma(i)}=1$. Thus the number of valid matchings in $G$ is exactly $$\sum_{\sigma \in S_n} \mathbb{I}[\sigma \text{ specifies a valid matching}] = \sum_{\sigma \in S_n} \prod_{i=1}^n M_{i,\sigma(i)} = \mathrm{Permanent}(M).$$

As a consequence $\mathrm{Permanent}(M) \ne 0$ if and only if $G$ has a perfect matching. There are simple polynomial-time algorithms to find a perfect matching in a bipartite graph. Thus there is a polynomial-time algorithm to determine whether the permanent of a matrix is nonzero.

This works for all matrices with non-negative entries: Simply replace each nonzero entry with 1. This will distort the permanent but will not change whether or not it is nonzero.

The simplest algorithm for finding a perfect matching is augmenting paths and runs in $O(n^4)$ time.

We can actually do better and approximate the permanent for matrices with non-negative entries.


Problems with efficient solution except for a small fraction of inputs

I'm not sure whether this is what you're looking, but the phase transition in random SAT is an example. Let $\rho$ be the ratio of number of clauses to number of variables. Then a random SAT instance with parameter $\rho$ is very likely to be satisfiable if $\rho$ is less than a fixed constant (near 4.2) and is very likely to be unsatisfiable if $\rho$ is a little bit more than this constant. The "black hole" is the phase transition.


$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.


I have 3 answers, all giving somewhat different hardness results.

Let $f: \{0,1\}^n \rightarrow \{0,1\}$ be some function.

Answer 1

Given a decision tree $T$ computing $f$ and a number, it is NP-hard to tell if there exists a decision tree $T'$ computing $f$ of size at most that number. (Zantema and Bodlaender '00)

Answer 2

Given a decision tree $T$ computing $f$, it is NP hard to approximate the smallest decision tree computing $f$ to any constant factor. (Sieling '08)

Answer 3

Let $s$ be the size of the smallest decision tree computing $f$.
Given a decision tree $T$ computing $f$, assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, one cannot find an equivalent decision tree $T'$ of size $s^k$ for any $k \ge 0$.

I think that this stronger answer (relying on a weaker assumption) can be made from known results in the learning theory of Occam algorithms for decision trees, via the following argument:

Is it possible to find a decision tree on $n$ variables in time
$n^{\log s}$, where $s$ is the smallest decision tree consistent with examples coming from a distribution (PAC model). (Blum '92)
Assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, we cannot PAC learn size $s$ decision trees by size $s^k$ decision trees for any $k \ge 0$. (Alekhnovich et al. '07)

These two results seem to imply a hardness result for your problem. On the one hand (1), we can find a large decision tree; on the other hand (2), we shouldn't be able to minimize it to get an equivalent "small" one, of size $s^k$, even when one exists of size $s$.


The short answer is 'no'. No such implication is known. There are two main obstacles: Going from arithmetic circuit complexity to boolean complexity (VP≠VNP implies P/poly≠NP/poly) and then going from boolean circuit complexity (P/poly≠NP/poly) to uniform complexity (P≠NP). Neither of these steps is known. I believe that P/poly≠NP/poly implies VP≠VNP, however.


You can do it with the isolation lemma. Here are the important details (admittedly hastily written):

We'll imagine picking a hash function from $H$ as follows: first, pick $w_1^0,\ldots,w_n^0,w_1^1,\ldots,w_n^1$ uniformly and independently from  integer weights in $[1,4n]$. Then pick a threshold $T$ in $[1,4n^2]$ also uniformly and independently at random. Let $w(x) = \sum_i x_iw_i^1 + (1-x_i)w_i^0$. Now define $h(x)$ to be one if $w(x) \le T$ and zero otherwise.

We can then lower-bound the probability you're interested in by
$$\begin{align*}
P_{h\gets H}[ h(x_2) = \cdots = h(x_{n^k}) = 0, h(x_1) = 1 ] \\
&\ge P_{h \gets H}[ \forall i > 1 : w(x_1) < w(x_i), T = w(x_1) ] \\
&= P_{h \gets H}[ \forall i > 1 : w(x_1) < w(x_i) ] \cdot P_{h\gets H}[ w(x_1) = T \mid \forall i > 1 : w(x_1) < w(x_i) ]
\end{align*}$$
which is to say that $x_1$ is the unique minimum-weight element, and $T$ equals $w(x_1)$. We can easily compute the right factor
using the uniformity and independence of $T$:
$$P_{h\gets H}[ w(x_1) = T \mid \forall i > 1: w(x_1) < w(x_i) ] = \frac{1}{4n^2}$$
Bounding the other factor will involve the isolation lemma. The lemma tells us that
$$P_{h \gets H}[\exists j \forall i\ne j : w(x_j) < w(x_i)] \ge 1-\frac{2n}{4n} = \frac{1}{2}$$
By a union bound, the left hand side is at most
$$\sum_{j=1}^{n^k} P_{h \gets H}[\forall i\ne j: w(x_j) < w(x_i)]$$
From here, observe that the distribution of $w(x)$ doesn't depend on $x$. Hence, the terms in the above sum are all identical (they don't depend on $j$). Combining with the previous inequality and rearranging, we thus have
$$P_{h \gets H}[\forall i > 1 : w(x_1) < w(x_i)] \ge \frac{1}{2n^k}$$
Plugging this into our earlier work, we conclude
$$P_{h\gets H}[ h(x_2) = \cdots = h(x_{n^k}) = 0, h(x_1) = 1 ] \ge \frac{1}{8n^{k+2}}$$
Lastly, each $h$ can be computed very easily: a fixed $h$ needs $O(n\log(n))$ bits to store the $w_i^b$ and $T$, and then some circuitry to sum the appropriate weights and compare against $T$.


We can modify Dijkstra's algorithm to solve this problem too. For each vertex, in Dijkstra's algorithm, we store the shortest path to that vertex obtained so far. Here, we store $r+1$ different shortest paths per vertex (where the required colour sequence is $c_1,c_2,\ldots ,c_r$). In each vertex, the first path corresponds to shortest path so far, containing only whites. And for $i=1,2,\ldots ,r$, $(i+1)^{th}$ path is the shortest path so far, that contains vertices of colours $c_1,c_2,\ldots ,c_i$ (in that order) mixed with white vertices.

While modifying shortest paths for the new node, we will modify all $r+1$ paths if it is white and if it is of a different colour $c$, only those $(i+1)^{th}$ paths are modified which have $c_{i+1}=c$. And when the algorithm ends, the $(r+1)^{th}$ path in each vertex gives the required shortest path to that vertex.

Complexity will be $r$ times the complexity of Dijkstra's. Note that we have not assumed the colours in the sequence to be distinct (so we can get shortest paths with required sequence as red-black-red-blue too). Also, we can easily modify this to allow multiple vertices of same colour to occur together (i.e., red-red-black-blue can be considered same as red-black-blue).


Are Alice and Bob allowed to copy qubits in quantum communication complexity model?

Let me add to Artem’s nice explanation a pedantic point about your wording “something a quantum algorithm cannot do.”

In the usual setting of communication complexity, each party is allowed to perform any local operations, regardless of whether it is computable or not.  This is true in both classical and quantum cases.  In this sense, each party is indeed allowed to do something a quantum algorithm cannot do.  However, Alice and Bob are still constrained by the law of physics, and cloning is disallowed because of this.  In short, cloning is disallowed not because there is no quantum algorithm for it, but because it is ruled out by the law of physics.


Are there problems for which divide-and-conquer / recursion is provably useless?

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

Yes.  Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P.  There is a tally language in E∖P by a standard diagonalization argument.

  Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime $o(f(n))$?

It may depend on the computational model, but I doubt this is known, given that the time hierarchy theorem for two-tape Turing machines is not powerful enough to distinguish, say, O(n2) time and o(n2) time even without giving the latter the constant-time access to the answers on smaller instances.

Random comments on your questions in this post:

I do not think that these questions are related to the usefulness of recursive programs, despite what the title of the post and your choice of terminology suggest.  As BVMR wrote in an answer, recursions and iterations are equivalent in a certain sense.  Instead, I think that the questions have a connection to the usefulness of the divide-and-conquer approach.
In complexity theory, a related notion to your notion of “recursive algorithms” with their “recursive runtime” is called “length-decreasing self-reductions” with their time complexity.
Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.


It seems it would depend on your particular model, in particular what information you have access to.

From what I infer, you are thinking of the following model:

you have a memory $m$, for instance of size $O(\log n)$.
at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$
you then have to say whether the word under you new sliding window shifted by $1$ is in $L$, based solely on $m$.

In particular, you don't have access to the letter leaving the sliding window. If you had this information, the problem would be more symmetrical, and for instance languages Parity and Majority would be computable with constant and logarithmic memory respectively.

Memory constraint

In the setting above without this information, here is for instance a proof that a linear memory is needed for Parity, so  basically you need
 to remember the whole word.
Indeed, if you use sublinear memory, there are two different words $u$ and $v$ of length $n$ that give rise to the same memory state $m$.
Then, let $d$ be the first position where $u$ and $v$ differ, and consider that your stream continues with $0^d$. After having read this suffix, you will have the same memory $m'$, so you must answer the same thing in both cases. But since the bit that got out of the window is not the same for $u$ and $v$, your answer is wrong for one of the two.

Time constraint

It is possible to recognize any regular language $L$ with quasi-constant amortized time. The time complexity is the one from a union-find-delete (UFD) data structure.
For instance this paper shows that operations union, makeset and delete can be done in constant time, and the find operation in reverse Ackermann (so at most $5$ for any input value making sense in the physical word, see wikipedia on union-find).

Let $A$ be a DFA recognizing $L$, with states $Q$, transition function $\delta:Q\times\Sigma\to Q$, and initial state $q_0.$
Let $k=|Q|$, since $L$ is fixed $k$ is a constant.

Let $a_0a_2\dots a_{n-1}\in\Sigma^n$ be the word currently under the window.
The idea is to maintain a memory structure $m$, giving for each word $u_i=a_i\dots a_{n-1}$ the state $q_i$ reached by $A$ after reading $u_i$.
We will also maintain an index $\gamma\in[0,n-1]$, giving the identifier associated with $u_0$. The identifier for $u_j$ is $\gamma+j \mod n$.

The UFD structure will store identifiers of all words $u_0\dots u_{n-1}$, and two words $u_i,u_j$ will be in the same partition if and only if $q_i=q_j$. The common state $q$ labels the partition.

So in order to know whether the current word is in $L$, it suffices to identify the label $q$ of partition of the identifier $\gamma$ (corresponding to the word $u_0$), and check whether $q$ is accepting.

When a new letter $a$ is read, we update the memory as follows:

the identifier $\gamma$ is deleted from the UFD structure
a new identifier $\gamma$ is added, and joins the partition labeled $q_0$. A new partition is created if none exists. For this we can use the help of an auxiliary memory of constant size, storing which states are currently labelling partitions, and giving a witness identifier for each one.
the current index $\gamma$ is updated to $\gamma'=\gamma+1\mod n$.
all labels of partitions are updated to their $a$-successors: $q'=\delta(q,a)$ for each label $q$. Partitions that get the same label are merged.

All these operations are either constant time or in quasi-constant amortized time.


No, Ref T is not a subtype of T. In typical sub-typing rules, a term of type Ref T is not substitutable for a term of type T. A Ref T has the value of a pointer to a location in memory of an T, whereas T has the value of an T. More concretely, in ML-based languages, in order to pass the value from a Ref T to a function that takes the enclosed type T, you need to dereference the argument first. Typically that will involve using a unary operator like !.

So, while it is possible that a coercion could make the Ref T appear to be a subtype, I think it's better to think of Ref as a container type, rather than a more specific kind of T.

An example from OCaml:

# let t = ref 2 ;;
val t : int ref = {contents = 2}
# let q : int = t ;;
Error: This expression has type int ref
       but an expression was expected of type int
# let r : int = !t ;;
val r : int = 2

A possible workaround for this would be to look into some form of implicit coercions, which are available in certain languages. See more on coercion here.


Is every busy beaver strictly monotonic asymptotically?

Take an $n$-state Turing machine $M$ which outputs $k$ one symbols. Define the new Turing machine $M'$ with $n+1$ states as follows. Every transition in $M$ to the ACCEPT state instead goes into a new state $q'$. The state $q'$ has the following behavior. If the head currently contains a ZERO, we overwrite with a ONE and ACCEPT. If the head currently contains a ONE, we shift to the right and remain in state $q'$.

As machine $M$ halts, so does machine $M'$. Furthermore, machine $M'$ always puts one $k+1$ ONES onto the tape.

So $BB(n+1) \geq k+1 > k = BB(n)$


Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?

Your proposed optimization is a special case of the "forward reasoning" nontermination detection that Marxen and Buntrock describe in part 5 of their paper:

  If there is a set S of states such that all transitions from elements of S are defined and their target state is also in S, (and the machine is in one of those states) it will never again leave S and thus not halt (closed state/transition cluster).

If you've implemented this nontermination detection then your optimization is redundant.  You could include it for a possible slight efficiency win.  Your optimization applies whenever we are defining the 2k-th transition and there are currently only k states.  That will not be the case as often as you might think, since Marxen and Buntrock's enumeration algorithm does not assign transitions in order by state index.  Instead, it simulates each Turing machine during enumeration and assigns each transition only as it is reached.

The "forward reasoning" nontermination detection will catch cases that your optimization would not, e.g. in this partially defined 3-state machine:

    0    1
A: 1LB, -?-
B: 1LC, 1LC
C: 1RB, 1RB


Why do TCS papers have author names in alphabetical order of their surnames?

The American Mathematical Society has released a statement (pdf link) about the commonly accepted practice of listing authors in alphabetical order in mathematics. Their reasoning applies, in my opinion, to TCS as well.

This kind of theoretical research is often done in small groups of 2-5 people. In close collaboration it can be difficult to determine who came up with which idea and/or whose ideas are more important for the main results. Using the alphabetical order lets us circumvent arguments about it and default to "everyone contributed equally", which is often (but not always) more or less the case anyway. It's also easy to explain to non-mathematicians by e.g. showing the above statement. When you apply to math/TCS positions, the hiring committee will be aware of this convention and won't hold your last name against you. My impression is that researchers in fields close to math/TCS tend to know about it as well.

In biology and other fields where research is based on experiments, papers are written by large groups whose members have distinct roles. A professor has an idea and obtains funding, one researcher designs the experiments, some lab assistant runs them, someone else analyzes the results, others write the paper. In this context it makes more sense to differentiate the authors by their contribution.


As pointed in the comments, You cannot do this in general,
However, if you're willing to restrict the class and add some some structure you can achive this. For example, you can use the self-reducibility of SAT to remove the advice, i.e if
$NP\in P/log$ then $NP=P$.

In general, the same is true for complexity classes with self-reducible complete problem, and similar arguments for complexity classes with instance checkers $(EXP,PSPACE,P^{\#P})$ will allow you to remove even larger advices (polynomial) with the difference that now you need to use  probabilistic machines.


Historical reasons for adoption of Turing Machine as primary model of computation.

This seems to be true in the context of (some areas of) computer science but not generally.
One reasons has to do with the Church's Thesis. The main reason is that some experts like Godel didn't think that the arguments that previous/other models of computation capture exactly the intuitive concept of computation were convincing. There are various arguments, Church had some, but they did not convince Godel. On the other hand Turing's analysis was convincing for Godel so it was accepted as the model for effective computation. The equivalences between different models is proven later (I think by Kleene).
The second reason is technical and a later development related to the study of complexity theory. Defining the complexity measures like time, space, and nondeterminism seems to be easier using Turing machines than other models like $\lambda$-calculus and $\mu$-recursive functions.
On the other hand, $\mu$-recursive functions were and are still used as the main way of defining computability in logic and computability theory books. They are easier to work with when one only cares about effectiveness and not about complexity. Kleene's book "Metamathematics" was very influential for this development. Also $\lambda$-calculus seems to be more common in CMU/European style computer science like programming languages and type theory. Some authors prefer the RAM and Register Machine models.
(It seems to me that for some reason Americans adopted Turing's semantic model and Europeans adopted Church's syntactic model, Chruch was American and Turing was British. This a personal opinion/observation and others have a different view. Also see these papers by Viggo Stoltenberg-Hansen and John V. Tucker I,II.)
Some resources for further reading:
Robert I. Soare has a number of articles on the history of these developments, I personally like the one in the Handbook of Computability Theory. you can find more by checking the references in that paper.
Another good resource is Neil Immerman's computability article on SEP, see also Church-Turing Thesis article by B. Jack Copeland.
Godel's collected works contains lots of information on his views. Specially introductions to his articles are extremely well-written.
Kleene's "Metamathematics" is a very nice book.
Finally, if you are not still satisfied check the archives of the FOM mailing list, and if you cannot find an answer in the archive post a an email to the mailing list.


If you don't need deletions, I think the first part of Lemma 4.1 on page 349 of the following paper:

Jeffery Westbrook: Fast Incremental Planarity Testing. ICALP 1992: 342-353
  http://dx.doi.org/10.1007/3-540-55719-9_86

gives you a linear time algorithm for any sequence of operations consisting of constructing and marking the tree, as well as conducting nearest marked ancestor queries (i.e. the query time is amortized constant).


The first problem you face is that a password cannot be used as an encryption key. For instance, let the password be $%^gHk23. How do you interpret this as an AES-256 key?

The second problem is that the client has to send the password in clear, and then the server tries to make a key from it, and decrypt saved values.

Thirdly, the scheme is fixed. No salting whatsoever is incorporated in it, and thus it is vulnerable to a variety of attack, most notably the dictionary attack.

The hashing scheme you described at the beginning of your post is very old. Today, an extremely secure password-based identification scheme, named SRP, is gaining momentum. (See also the demo.)


You'll need to modernize the notation, but McCarthy and Painter's Correctness of a Compiler for Arithmetic Expressions is simple and good, and also of historical interest (since to the best of my knowledge it's the first paper on the subject).