It is possible to restrict the QMA verifier to single-qubit measurements and classical pre- and postprocessing (with randomness) while keeping QMA-completeness.

To see why, take any class of $k$-local QMA-complete Hamiltonians on qubits. By adding a constant of order $\mathrm{poly}(n)$ and rescaling with a $1/\mathrm{poly}(n)$ factor, the Hamiltonian can be brought into the form
$$
H=\sum_i w_i h_i\ ,
$$
where $w_i>0$, $\sum_i w_i=1$, and $h_i = \tfrac12(\mathrm{Id}\pm P_i)$, where $P_i$ is a product of Paulis. Estimating the smallest eigenvalue of $H$ up to accuracy $1/\mathrm{poly}(n)$ is still QMA-hard.

We can now build a circuit which only uses single-qubit measurements which, given a state $|\psi\rangle$, accepts with probability $1-\langle\psi|H|\psi\rangle$ (which by construction is between $0$ and $1$).  To this end, first randomly pick one of the $i$'s according to the distribution $w_i$. Then, measure each of the Paulis in $P_i$, and take the parity $\pi$ of the outcomes, which is now related to $\langle\psi|h_i|\psi\rangle$ via
$$
\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .
$$
The circuit now outputs $1-\langle\psi|h_i|\psi\rangle$, and the output is therefore distributed according to $\langle\psi|H|\psi\rangle$.

This is, if we picked a yes-instance of the (QMA-complete) local Hamiltonian problem, there is a state $|\psi\rangle$ such that this verifier will accept with some probability $\ge a$, while otherwise any state will be rejected with probability $\le b$, with $a-b>1/\mathrm{poly}(n)$.  The variant of QMA where the verifier is restricted to one-qubit measurements is therefore QMA-complete for some $1/\mathrm{poly}(n)$ gap.  Finally, this version of QMA can be amplified using just the conventional amplification techniques for QMA, which finally proves it is QMA-complete independent of the gap (within the same range as QMA).


Are types propositions? (What are types exactly?)

The key role of types is to partition the objects of interest into different universes, rather than considering everything existing in one universe. Originally, types were devised to avoid paradoxes, but as you know, they have many other applications. Types give a way of classifying or stratifying objects (see blog entry).

Some work with the slogan that propositions are types, so your intuition certainly serves you well, though there is work such as Propositions as [Types] by Steve Awodey and Andrej Bauer that argues otherwise, namely that each type has an associated proposition. The distinction is made because types have computational content, whereas propositions don't.

An object can have more than one type due to subtyping and via type coercions.

Types are generally organised in a hierarchy, where kinds play the role of the type of types, but I wouldn't go as far as saying that types are meta-mathematical. Everything is going on at the same level – this is especially the case when dealing with dependent types.

There is a very strong link between types and category theory. Indeed, Bob Harper (quoting Lambek) says that Logics, Languages (where types reside), and Categories form a holy trinity. Quoting:

  These three aspects give rise to three sects of worship: Logic, which gives primacy to proofs and propositions; Languages, which gives primacy to programs and types; Categories, which gives primacy to mappings and structures.

You should look at the Curry-Howard Correspondence to see the link between Logic and Programming Languages (types are propositions), and Cartesian Closed Categories, to see the between the relationship with Category Theory.


What is the value of this "game" (counters rebalancing)?

Here is an upper bound for question 2.

Theorem: After $TM$ steps, you can have at most $T \log M$ positive counters.

Notation: we assign each step a number, ending with the $0$th step, and starting with the $(-TM+1)$th step.

Observation: in the optimal strategy, if you increment a counter, you do not let it return to $0$.

Proof: Let us assign a value of $1$ to each time you increment a counter in the last $T$ steps; $\frac{1}{2}$ to each time you increment a counter in the previous $T$ steps; $\frac{1}{3}$ to each time you increment a counter in the $T$ steps before that, etc. That is, if you increment a counter between step $-kT+1$ and $-(k-1)T$, it gets a value of $\frac{1}{k}$.
We need a lemma that we will prove later.

Lemma: for a counter to be positive, it must have had a total value of at least $1$ assigned to it.

With the lemma, the proof is easy:  the total value we have to assign is $T \sum_{i=1}^M \frac{1}{i} \approx T \log M$, and each positive counter requires us to have assigned total value of at least $1$ to it.

Proof of Lemma: Look at the first time you made that counter positive. If that was between $-kT$ and $-(k-1)T$, then it has been decremented at least $k-1$ times, and so you need to have incremented it $k$ times to have it end up positive. But each of these increments assigns it a value of at least $\frac{1}{k}$.

And here is an upper bound for question 1. Let's use the same overall proof strategy as before.  Again, we assign a value of $\frac{1}{k}$ when we increment a counter on a step between $-kT+1$ and $-(k-1)T$. We also assign a value of $\frac{1}{M}$ when we increment a counter on a step between $-2MT$ and $-MT$, and a value of $0$ if we increment a counter before that. By the same reasoning as before, any counter that was $0$ at step $-2MT$ must be assigned a value of at least $1$. But now, if a counter was positive at step $-2MT$, it still must have been assigned a total value of at least $1$, since it must have been incremented $M$ times to end up positive. Now, the total value we have to assign is $T\log M + T$, so we can have at most $T (\log M + 1)$ positive counters.


What is the minimum size of a circuit that computes PARITY?

This gate-elimination lower bound does not match Marzio’s upper bound, but it’s a start.

  Proposition: Every unbounded fan-in AND/OR/NOT circuit computing parity on $n\ge2$ variables contains at least $2n-1$ AND and OR gates.

For convenience, I will use a model where the only gates are AND-gates, but we allow negation wires. It is easy to see that $3$ gates are necessary for $n=2$, hence it is enough to show that if $C$ is a minimal-size circuit computing parity on $n>2$ variables, we can find a restriction of one variable which kills at least two gates.

If some variable $x_i$ has at least two positive parents (i.e., it is connected by unnegated wires to two different gates), setting this variable to $0$ will kill the parents and we are done; likewise if it has two negative parents. We may thus assume that each variable has at most one positive and at most one negative parent.

Let $a$ be a bottom-level gate in the circuit. Without loss of generality, $a=x_1\land x_2\land\cdots$. Set $x_1=0$, which forces $a=0$ and kills it. The restricted circuit $C'$ still computes parity, in particular it depends on $x_2$, hence $x_2$ has a negative parent $b=\neg x_2\land c_1\land\dots\land c_r$. Notice that in $C'$, no $c_j$ depends on $x_2$. If there were an assignment to $x_3,\dots,x_n$ which (on top of $x_1=0$) makes some $c_j$ false, the circuit restricted by this assignment would be constant, contradicting the fact that it computes $x_2$ or $\neg x_2$. Thus, in $C'$, all the $c_j$ compute constant $1$, and $b$ computes $\neg x_2$, hence we can eliminate it along with $a$.

EDIT: As I learned from Yuri Kombarov’s paper, this $2n-1$ lower bound, as well as the $\lfloor\frac52n\rfloor-2$ upper bound implied by Marzio De Biasi’s answer, were originally proved in

[1] Ingo Wegener, The complexity of the parity function in unbounded fan-in, unbounded depth circuits, Theoretical Computer Science 85 (1991), no. 1, pp. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4


Approximation algorithms for problems in P

As Jukka points out, computational geometry is a rich source of problems that can be solved in polynomial time, but we wish to get fast approximations. The classic "ideal" result is an "LTAS" (linear time approximation scheme) whose running time would be of the form $O(n + \text{poly}(1/\epsilon))$ - usually these are obtained by extracting a constant (poly($1/\epsilon$)) sized kernel from the data, and running an expensive algorithm on that kernel, with a guarantee that an exact solution on the kernel is an approximate solution on the entire input.

There are a number of tricks, reductions and principles, and Sariel Har-Peled's new book is full of these. I don't think there's a rich complexity theory as such.


#P-complete problem whose decision version is in P

If you insist on parsimonious reductions (where the number of solutions is preserved) you cannot have such a reduction unless P = NP because the decision algorithm for non-emptyness of solutions for B will give you a decision algorithm for non-emptyness of solutions for A. On the other hand, if you allow other kind of reductions you can have such a case. For example, Valiant showed that #SAT reduces to the problem of counting perfect matchings in a bipartite graph: the reduction starts with a CNF-formula $F$ and builds a bipartite graph $G$ whose number of perfect matchings mod $2^{8m}+1$ is $4^m$ times the number of satisfying assignments of $F$, where $m$ is the number of literal occurrences in $F$. Note how this is not a parsimonious reduction, but a reduction nonetheless since you can recover the number of satisfying assignments of $F$ from the number of perfect matchings of $G$.

See Chapter 18 in Papadimitriou's "Computational Complexity" book for a clear exposition of this.


Note: this reduction is written in the wrong direction, and when fixed it only works for multigraphs. See explanations in the edit to the original question.

I think the problem is #P-hard already on 3-regular graphs using the results of Cai, Lu and Xia, Holographic Reduction, Interpolation and Hardness, 2012. I will do this by showing the #P-hardness of counting the non-satisfying valuations of $G$, i.e., the valuations $\nu$ where for every edge $e$ at least one of the endpoints of $e$ is not mapped to $e$ by $\nu$. Indeed, counting this reduces in PTIME to counting the satisfying valuations of $G$ as you ask: this uses the fact that the total number of valuations (both satisfying and non-satisfying) can be computed in PTIME, using the closed-form formula in your question.

To show the hardness of counting non-satisfying valuations on 3-regular graphs, consider a 3-regular graph $G = (V, E)$, and construct the bipartite graph $G' = (V \cup E, W)$ between $V$ and $E$: it is a 2-3-regular graph in the sense that vertices in $V$ all have degree $3$ and vertices in $E$ all have degree $2$. Now, a non-satisfying valuation of $G$ in your sense amounts to picking one edge of $W$ incident to each vertex of $V$ in $G'$, so that we never pick the two edges of $W$ incident to a vertex of $E$. In other words, I'm claiming that counting the non-satisfying valuations of $G$ is exactly to counting the subsets $W'$ of $W$ such that each vertex of $V$ has exactly one incident edge in $W'$ (= we pick one edge for each vertex of $V$), and each vertex of $E$ has 0 or 1 incident edges in $W'$ (= no edge of $E$ has both its endpoints selected).

If I'm not mistaken, this is precisely the problem #[1,1,0][0,1,0,0] in the notation of Valiant used in the paper I quote: note that there's a hopefully legible explanation in Appendix D of this paper (which, incidentally, we co-authored ;-P). Now looking at the table on page 23 of Cai, Lu and Xia, we see that #[1,1,0][0,1,0,0] is #P-hard.

As for the problem having an established name more palatable than #[1,1,0][0,1,0,0], I don't know, but maybe this can be one direction in which to look.


Are non-deterministic tree-walking automata stronger than deterministic ones?

For tree automata, you have the following results:

Deterministic bottom-up tree automata have the same expressive power as non-deterministic bottom-up tree automata.
Deterministic top-down tree automata are weaker than non-deterministic top-down tree automata.

More details can be found in the Tree Automata book.

It seems that you are interested in top-down tree automata, so the answer to your question is no. You will of course have to check whether top-down tree automata are in fact what you are interested in.


Why don't we use larger classes to study determinism vs non-determinism?

The issue may be a bit cleaner with $E=Dtime(2^{O(n)})$ and $NE=Ntime(2^{O(n)})$.
The easiest way to think about these classes is that they are the same as $P$ and $NP$ but restricted to unary languages. That is, all inputs are of the form $1^k$.

That is, the language $L$ is in $E$ if and only if the language $U_L = \{ 1^x : x\in L \}$ is in $P$ (identifying strings with numbers using binary representation), and similarly $NE$ is isomorphic to unary $NP$.

So, trying to separate $NE$ from $E$ is just like trying not just to separate $P$ from $NP$, but actually do it using a unary language. No reason it should make your life even conceptually easier.


Max network flow with arbitrary source / sink

Finding max flow from arbitrary source/sink can be reduced to finding max flow under insertion/deletion of edges.

We modify the graph by adding two vertices $s^*$ and $t^*$ not connected to any vertex. We maintain the data structure to compute max flow from $s^*$ to $t^*$ under insertion/deletion of edges. Now, whenever we want to calculate max flow from any source $s'$ to any sink $t'$, we simply add edges $(s^*,s')$ and $(t',t^*)$ with infinite capacity. The max flow from $s^*$ to $t^*$ would then essentially be the max flow from $s'$ to $t'$.

In case you want to change the source and sink to $s''$ and $t''$ respectively, simply delete $(s^*,s')$ and $(t',t^*)$ and add $(s^*,s'')$ and $(t'',t^*)$. The max flow from $s^*$ to $t^*$ would now represent the max flow from $s''$ to $t''$.

This technique was earlier used to show the equivalence of All Pair Shortest Path and Single Source Shortest Path in the dynamic environment.
Similarly, it can also show equivalence of All Pair Reachability and Single Source Reachability in the dynamic environment.


Simple example of halting-unprovable Turing machine

Take the "current mathematical system" $S$ and an undecidable sentence $P$ for $S$. Consider the Turing machine $T$ which enumerates all theorems of $S$ and halts if it ever enumerates either $P$ or $\lnot P$. System $S$ cannot decide whether $T$ halts.

Note that such a $T$ does not halt.


What will go wrong if a recursive record type has a negative eta rule?

Having a recursive record type with eta-equality wouldn't destroy consistency of the theory, but it would destroy decidability of typechecking.

For example, let's define your out type as a record type in Agda:

record Out : Set where
  inductive
  constructor cons
  field
    in : Out

Agda doesn't use eta-equality for this type. Suppose it did, then Agda's typechecker would loop whenever it tries to solve an equation of the form x = y : Out (where x and y are two variables or neutral terms): x = y iff in x = in y iff in (in x) = in (in y) iff in (in (in x)) = in (in (in y)) ...


Are equally weighted MSTs closely related?

Yes. More generally, any spanning tree can be reached from any arbitrarily-chosen MST by a sequence of single-edge replacement operations that never decrease the weight. When such a sequence is used to reach another MST, it can also never increase the weight, because then it would have to decrease it at some other step. See e.g.

H.N. Gabow, Two Algorithms for Generating Weighted Spanning Trees in Order, SIAM J. Comput. 6, 1977, 139–150. http://epubs.siam.org/doi/pdf/10.1137/0206011


Graph decompositions for combining "local" functions of vertex labelings

What I want to say is too long for (but really should be) a comment.

If I am reading the question correctly, you want a FPRAS (fully polynomial randomised approximation scheme) for either of the above quantities, each of which includes various #P-complete problems as special cases.  In particular, you want a general FPRAS in the case of planar graphs, by the use of cluster expansion.

I doubt that this is possible due to the fact that NP-completeness of the existence problem (e.g. proper colouring) implies that the corresponding counting problem (e.g. number of proper colourings) is complete in #P with respect to AP-reducibility (approximation-preserving).  See Dyer, Goldberg, Greenhill and Jerrum, Algorithmica (2004) 38: 471-500.

But perhaps I've misread the question.

(Actually, would you be able to explain to the uninitiated the meaning of high-temperature expansions?)


Where can I find examples of error correcting codes of the following types?

If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many explicit constructions of such codes, and you can find the basic ones in lecture notes of courses about coding theory. For example, you can find a description of a classic construction in Lecture 7 here. Another example of a construction is expander codes, which are described in Lecture 14 there.

If you are looking specifically for codes where the distance between any two codewords is close to $\frac{m}{2}$, and in particular is upper bounded by $(1+\delta)\cdot \frac{m}{2}$, then things are a bit more complicated. Such codes are tightly related to objects called "$\epsilon$-biased sets", which have been studied for quite a while in TCS. You can find a very recent construction of such codes here. The earliest constructions can be found here and here (although they only give you $m = \rm{poly}(n)$).


How to properly define a zero-knowledge proof system with oracle access

Regarding your reference request, I remember the following paper off the top of my head:

Willaim Aiello and Johan Hastad. 1991. Relativized perfect zero knowledge is not BPP. Inf. Comput. 93, 2 (August 1991), 223-240. http://dx.doi.org/10.1016/0890-5401(91)90024-V.

Now, to answer your question: Consider any NP-complete language $L$, let $G$ be a generator for a public-key encryption scheme, and define $O$ as a decryption oracle for this encryption system. Finally, let $(P,V)$ be a protocol for proving membership in $L$.

Based on $(P,V)$, define the following modified protocol $(P',V')$: In the beginning of the protocol, $P$ uses $G$ and generates a public key pair $(pk,sk)$, and sends $pk$ to $V'$. Moreover, any message exchanged in $(P,V)$ in encrypted using $pk$ in $(P',V')$.

The prover can find the decrypted messages using $sk$, and the honest verifier $V'$ can use the oracle $O$ to find the decrpted messages. However, no other verifier $V^*$ can follow the protocol if we disallow their access to $O$. Therefore, the protocol is ZK for any cheating verifier!

In general, I think the definition should allow any verifier to access $O$, to prevent "twisted" protocols such as the one described above. The same holds for the distinguisher and simulator. However, I believe the prover need not necessarily have access to $O$.


SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms

There are many ways.  See Encoding 1-out-of-n constraint for SAT solvers for a compendium of several ways and for a useful reference with more information.

From a practical perspective, the different schemes have different tradeoffs.  If you are trying to encode a $k$-out-of-$N$ constraint in something you are feeding to a SAT solver, you can try each of the different candidate encodings to see which makes the SAT solver run faster; they can have a significant impact on the efficiency of the SAT solver.


Is the maximum independent set in cubic planar graphs NP-complete?

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.

  Bojan Mohar:
  "Face Covers and the Genus Problem for Apex Graphs"
  Journal of Combinatorial Theory, Series B 82, 102-117 (2001)


Deciding whether an NC${}^0_3$ circuit computes a permutation or not

This problem with $k=3$ is coNP-hard (and therefore coNP-complete).

To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a non-bijective function).

First a preliminary definition that will be helpful:

We define a labeled graph to be a directed graph, some of whose edges are labeled with literals, with the property that every vertex has either one unlabeled incoming edge, one labeled incoming edge, or two unlabeled incoming edges.

The reduction

Suppose we have a 3-SAT formula $\phi$ consisting of $m$ clauses, each containing three literals. The first step is to construct a labeled graph $G$ from $\phi$. This labeled graph contains one copy of the following gadget (sorry for the terrible diagram) for each clause in $\phi$. The three edges labeled L1, L2, and L3 are instead labeled with the literals in the clause.

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

The gadgets (one for each clause) are all arrange in one big cycle with the bottom of one gadget linking to the top of the next.

Note that this arrangement of gadgets does in fact form a labeled graph (every vertex has indegree 1 or 2 with only edges leading to vertices of indegree 1 being labeled).

From the formula $\phi$ and the labeled graph $G$ (which was constructed from $\phi$) we next construct an $NC_3^0$ circuit (this will conclude the reduction). The number of inputs and outputs for this circuit is $n+v$ where $n$ is the number of variables in $\phi$ and $v$ is the number of vertices in $G$. One input and one output is assigned to each variable in $\phi$ and to each vertex in $G$. If $x$ is some variable in $\phi$ then we will refer to the input and output bits associated with $x$ as $x_{in}$ and $x_{out}$. Furthermore, if $l$ is a literal with $l = x$ then we define $l_{in} = x_{in}$ and if $l$ is a literal with $l = \neg x$ then we define $l_{in} = \neg x_{in}$. Finally, if $v$ is some vertex in $G$ then we will refer to the input and output bits associated with $v$ as $v_{in}$ and $v_{out}$.

There are four types of output bits:

1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Note that this output depends on only one input bit.

2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Note that this output depends on only two input bits.

3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l_{in})$. Note that this output depends on only three input bits since $l_{in}$ depends only on $x_{in}$ for whatever variable $x$ is used in the literal $l$.

4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. Note that this output depends on only three input bits.

Since in all cases the output depends on only three inputs, the circuit we build is in $NC_3^0$ as desired.

Correctness proof case 1: $\phi$ is satisfiable

Suppose there exists a satisfying assignment for $\phi$. Then construct the following two sets of values for the inputs.

1) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. All of the inputs associated with vertices of $G$ are given the value 0.

2) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. Consider the vertices in one clause gadget in $G$. If the value of a label is 0 (under the satisfying assignment), the input associated with the vertex at the target endpoint of the edge labeled with that label is given a value of 0. If both L1 and L2 have value 0 then the second-top vertex in the gadget (as shown above) is also given a value of 0. All other vertices are given a value of 1.

We wish to show that these two sets of inputs yield identical outputs and therefore that the $NC_3^0$ circuit does not encode a permutation.

Consider the four types of output bits:

1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Since $x_{in}$ is the same for both sets of inputs, outputs of this form will always be the same across the two sets of inputs.

2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Examining the gadget whose copies make up $G$, we see that all such edges consist only of pairs of vertices whose input values are always 1s under the second set of inputs. Thus $v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$ under the first set of inputs and $v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$ under the second set of inputs. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l)$. If $l$ is false under the assignment then $v_{in}$ is 0 under both sets of inputs; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$ under both sets of inputs. If $l$ is true under the assignment, $v_{in}$ is 0 under the first set of inputs and 1 under the second; also note that in the gadget, the only labeled edges $(u, v)$ have vertices $u$ which always have $u_{in} = 1$ under the second set of inputs. As a result we see that under both sets of inputs, $u_{in} = v_{in}$ whenever $l$ is true; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. There are two such vertices in each gadget. The top vertex and the second-from top vertex. We consider those two cases separately.

4a) When $v$ is the second-top vertex in a gadget, $u$ and $w$ are the two target endpoints of the edges labeled L1 and L2. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff L1 has value 0 under the satisfying assignment (aka $u_{in} = L1$); similarly, $w_{in}$ is 0 iff L2 has value 0 under the satisfying assignment (aka $w_{in} = L2$); and finally, $v_{in}$ is defined to be 0 iff both L1 and L2 have value 0  (aka $v_{in} = L1 \lor L2$). Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

4b) When $v$ is the top vertex in a gadget, $u$ is the second-top vertex and $w$ is the target endpoint of the edge labeled L3. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff both L1 and L2 have value 0 (aka $u_{in} = L1 \lor L2$); $w_{in}$ is 0 iff L3 has value 0 (aka $w_{in} = L3$); and finally $v_{in} = 1$. Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$ where the equality $(L1 \lor L2 \lor L3) = 1$ holds by definition in a satisfying assignment for every clause. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

Clearly, we see that the outputs are the same for two different sets of inputs and therefore that the $NC_3^0$ circuit enacts a non-bijective function.

Correctness proof case 2: $\phi$ is unsatisfiable

Suppose now that there exists no satisfying assignment for $\phi$. Then assume for the sake of contradiction that some two different sets of inputs lead to the $NC_3^0$ circuit having the same output.

Clearly, the two inputs must have the same values for $x_{in}$ for every variable $x$ in $\phi$. Thus we may now unambiguously refer to the value of $x$.

Define $S$ to be the set of vertices $v$ in $G$ such that $v_{in}$ is different in the two sets of input values.

We will prove the following lemmas below:

Lemma 1: If in some gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertices above those three in the gadget are in $S$.

Lemma 2: If in some gadget the top vertex is not in $S$ then in the next gadget up no vertex is in $S$.

Since the gadgets form a loop, this implies that if in any gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertex in $G$ is in $S$ (in other words $S$ is empty).

However, consider a gadget associated with a clause $(L1 \lor L2 \lor L3)$ that is not satisfied. In this gadget all three labels have value 0. We know that edge $(u, v)$ labeled $L$ must satisfy $v_{out} = v_{in} \oplus (u_{in} \land L)$, but $L = 0$, so $v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$. Thus since the output is the same for both inputs, the values of $v_{in}$ must also be the same across the two sets of inputs. In other words, we have shown that $v$ is not in $S$. Thus we see that in this particular gadget, the three vertices at the target endpoints of the labeled edges are not in $S$.

As a result, we conclude that $S$ is empty. This however, implies that between the two sets of inputs, there were no differences, which contradicts the assumption that these input sets are different. As a result, we see that the function enacted by the $NC_3^0$ circuit is injective and therefore a bijection.

All that's left is to prove the lemmas.

To do this, we note that for every type of vertex in $G$ (indegree 1 with label, indegree 1 without label, and indegree 2), if all incoming edges come from vertices not in $S$ then the vertex in question is also not in $S$. This is because in all three cases $v_{out} = v_{in} \oplus X$ where $X$ is some function of the inputs associated with variables and/or vertices with edges to $v$. Since all such vertices are not in $S$ by assumption, the value of $X$ must be the same under both sets of inputs. Therefore $v_{in} = v_{out} \oplus X$ is also the same under both sets of inputs. In other words $v$ is not in $S$.

Now that we have the rule that a vertex is not in $S$ whenever all of its predecessors are not in $S$, the lemmas follow simply by applying the rule repeatedly to the gadget diagram above.


Intersection graphs of squares and rectangles

See "Squarability of rectangle arrangements", Konečný, Kučera, Opler, Sosnovec, Šimsa, and Töpfer, CCCG 2016. In particular their Theorem 6 proves for all $d$ the existence of graphs with boxicity 2 and cubicity $d$.


Relationship between shift-reduce parsing and delimited continuations?

I believe that the following paper explores some of this connection, mostly by using continuations to backtrack when things happen in parsers.  But there's definitely more to do here.

  Modular rollback through control logging: A pair of twin functional pearls

  Olin Shivers, Aaron Turon, ICFP 2011.


Is Kolmogorov complexity a surjective function?

Just an extended comment with no deep insights: perhaps you can cheat on the encoding of a Turing machine, and build an artificial encoding that leads to a surjective Kolmogorov complexity:

$0$ represents the Turing machine that outputs $0$ (1 state TM);
$0p$ represents the Turing machine that outputs $p+1$ (the number represented by the binary string $p$ plus one); it is simply an implicit "zipped" version of a decidable TM that outputs $p+1$;
$1p$ represents the $p+1$-th Turing machine in a standard enumeration (the enumeration can skip the TMs already included with $0$ and $0p$).

The corresponding universal TM on input $bx$ checks what is the value of $b$, if it is $0$ then it simply outputs $x+1$, otherwise it  simulates TM $M_{x+1}$ ($M_0$ when $x$ is the empty string); note that $M_{x+1}$ embeds the inputs.

For all strings $x$, $1 \leq K(x) \leq |x|+1$; and for all $n \geq 1$ there are $2^{n}$ strings of length $n$ but there are only $2^{n-1}-1$ programs of length $< n$ that can be represented using the $1p$ encoding; and only $2^{n}-1$ programs of length $n$ that can be represented using the $1p$ encoding; so at least a string $x'$  of length $n$ cannot be represented with a program $1p$ of length $\leq n$; but it can surely be represented with the program $0x'$ of length $n+1$ (we don't worry if there is also a program $1p$ of the same length $n+1$ that generates it).

We can conclude that for all $n > 1$, there exists a string $x', |x'|=n$ such that $K(x') = n+1$ (so this particular K is surjective).


Gentle introduction to the algorithmic aspects of tree-depth

My favorite resource for this subject is the book Sparsity by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic aspects. And for a more brief and quick introduction, there's always the Wikipedia article.


Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet

I'm still not sure why you want it in strict quadruple form, with a set of structure-less states. That's a model that mainly intended for doing the abstract mathematics surrounding state-transition systems, but famously ill-suited to actual computation unless you are looking for the extreme speed offered by "pre-compiling" into deterministic form, at the expense of storage space.

User834 is correct that this is a fairly simple sub-problem of regular expression matching, with the added feature of counting matches, so you may take my solution in that vein.  I'm not a RE maven, but I think there is a way to get match counting out of REs in most implementations. So that's an approach you might consider for practical implementation without all the trouble of constructing your own FSAs.

I also agree that this probably belongs in the CS area rather than theoretical CS.

If I read your problem correctly, it amounts to taking a set of strings $V$ and looking for every occurrence of a string in $V$ as a maximal substring (prefix, suffix or interior) of $x$, the input to the DFSA we'll call $D$. That count is the "penalty" for $x$. Here's one way to do it, though following your prescription not to worry about performance, takes no advantage of any structure or redundancy in $V$.

In your example, $V=\{abd, abe, acd, ace, add, ade, b...\}$. Pre-multiply all the sets $V_i$ into strings of $V$ in tree form, with elements of $V_i$ all on level $i$, each descended directly from each element of $V_{i-1}$. Level $0$ is an abstract root, say $\epsilon$. For your example, descended from $\epsilon$ are $a$ and $b$, the elements of $V_1$. On level 2, descended from each of $a$ and $b$ are the members of $V_2$: $b$, $c$ and $d$. So there are 6 nodes on level 2 altogether, the 3 members of $V_2$ repeated twice. And so on to the leaves.  Each path from $\epsilon$ to a leaf of the tree represents one "penalty string" in V. You did not make clear what happens if a string appears more than once in $V$. If you don't want it to count for multiple penalties, then you should prune duplicate strings out of the tree by some suitable algorithm.

Construct the a non-deterministic FSA $D'$ as follows.  States of $Q$ are pointers to nodes of the tree. Each state thus represents a complete string in $V$ or a prefix of such a string, to be represented here by $[x]$ (though that $x$ isn't unique to a node -- I assume there is a pointer to the actual node of the tree).  The transition function $\delta$ contains three kinds of edges:

$\langle[x],a,0,[xa])\rangle$ where $a$ is a direct descendant of $[x]$, and $[xa]$ is that descendant node. Note that we output 0 at this point because we aren't sure we've reached the maximal match.

$\langle[x],a,1,[])\rangle$ where $a$ is not a direct descendant of $[x]$ in the tree, and $[]$ is a dead state. We output $1$ here because $[x]$ is matched but it is maximal, since $[xa]$ is not matched.

If we were dealing with prefixes only and not interior and suffix matches, we'd be done and this would be a deterministic automaton. To account for non-prefixes, we need to non-deterministically circle back to $[\epsilon]$, the start state, at every stage with an edge like this for every state $[x]$ except $[\epsilon]$ and $[]$:

$\langle[x], \epsilon, 0, [\epsilon]\rangle$

Convert that NFSA to a DFSA and you are done.


Is it possible to convert any tree to a B-tree or an R-tree?

An N-ary tree is the general term describing a tree data structure containing/organizing a list of numbers.

A B-tree is an N-ary tree opimized for block/disk access. Each leaves contain ranges of elements.

An R-tree is an N-ary tree but the order imposed on the list of elements is no longer the "greater than" order on a list of numbers but a"close to" metric on points in 2D and more. The "close to" metric is approximated by bounding boxes. An R-tree can be implemented over a B-tree, technically speaking.

Furthermore, any data set in n-dimensions has representations in 1D. Therefore, given some metric, all these tree topologies are isomorphic...


Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

The $L_1$ problem with $d_v=1$ for all $v$ is a variant of the classical NP-hard minimum linear arrangement problem.   Charikar et al [SODA 2006] and independently Feige and Lee [IPL 2007] described polynomial-time $O(\sqrt{\log n} \log \log n)$-approximation algorithms via semidefinite programming.  Devanur et al [STOC 2006] proved an $\Omega(\log\log n)$ integrality gap for the semidefinite relaxation.


What would a very simple quantum program look like?

Caveat Emptor: the following is heavily biased on my own research and view on the field of QC.  This does not constitute the general consensus of the field and might even contain some self-promotion.

The problem of showing a 'hello world' of quantum computing is that we're basically still as far from quantum computers as Leibnitz or Babbage were from your current computer.  While we know how they should operate theoretically, there is no standard way of actually building a physical quantum computer. A side-effect of that is that there is no single programming model of quantum computing.  Textbooks such as Nielsen et al. will show you a 'quantum circuit' diagram, but those are far from formal programming languages: they get a little 'hand-waving' on the details such as classical control or dealing with input/output/measurement results.

What has suited me best in my research as a programming language computer scientist, and to get the jist of QC across to other computer scientist, is to use the simplest QC model I've come across that does everything.

The simplest quantum computing program I have seen that contains all essential elements is a small three-instruction program in the simplest quantum programming model I've come across.  I use it as you would a 'hello world' to get the basics across.

Allow me to give quick simplified summary of the The Measurement Calculus by Danos et al.1  that is based on is based on the one-way quantum computer2: a qubit is destroyed when measured, but measuring it affects all other qubits that were entangled with it.  It has some theoretical and practical benefits over the 'circuit-based' quantum computers as realized by the photonic chip, but that is a different discussion.

Consider a quantum computer that has only five instructions: N, E, M, X and Z.  Its "assembly language" is similar to your regular computer, after executing one instruction it goes to the next instruction in the sequence. Each instruction takes a target qubit identifier, we use just a number here, and other arguments.

N 2          # create a new quantum bit and identify it as '2'
E 1 2        # entangle qubits '1' and '2', qubit 1 already exists and is considered input
M 1 0        # measure qubit '1' with an angle of zero  (angle can be anything in [0,2pi]
             # qubit '1' is destroyed and the result is either True or False
             # operations beyond this point can be dependent on the signal of '1'
X 2 1        # if the signal of qubit '1' is True, execute the Pauli-X operation on qubit '2'

The above program thus creates an ancilla, entangles it with the input qubit, measures the input and depending on the measurement outcome performs an operation on the ancilla. The result is that qubit 2 now contains the state of qubit 1 after Hadamard operation.

The above is naturally at such low level that you wouldn't want to hand-code it. The benefit of the measurement calculus is that it introduces 'patterns', some sort of composable macros that allow you to compose larger algorithms as you would with subroutines.  You start off with 1-instruction patterns and grow larger patterns from there.

Instead of an assembler-like instruction sequence, it is also common to write the program down as a graph:

 input                .........
    \--> ( E ) ---> (M:0)     v
(N) ---> (   ) ------------> (X) ---> output

where full arrows are qubit dependencies and the dotted arrow is a 'signal' dependency.

The following is the same Hadamard example expressed in a little programming tool as I would imagine a 'quantum programmer' would use.

edit: (adding relation with 'classical' computers)  Classical computers are still really efficient in what they do best, and so the vision is that quantum computers will be used to off-load certain algorithms, analogous to how current computer offloads graphics to a GPU. As you have seen above, the CPU would control the quantum computer by sending it an instruction stream and read back the measurement results from the boolean 'signals'.  This way you have a strict separation of classical control by the CPU and quantum state and effects on the quantum computer.

For example, I'm going to use my quantum co-processor to calculate a random boolean or cointoss.  Classical computers are deterministic, so its bad at returning a good random number.  Quantum computers are inherently probabilistic though, all I have to do to get a random 0 or 1 is to measure out a equally-balanced qubit.  The communication between the CPU and 'QPU' would look something like this:

 qrand()       N 1; M 1 0;
 ==>  | CPU | ------------> | QPU |  ==> { q1 } ,  []
                 start()
      |     | ------------> |     |  ==> { } , [q1: 0]
                 read(q1)
      |     | ------------> |     |
                  q1: 0
 0    |     | <-----------  |     |
 <==

Where { ... } is the QPU's quantum memory containing qubits and [...] is its classical (signal) memory containing booleans.

Danos et al. The Measurement Calculus. arXiv (2007) vol.
quant-ph
Raussendorf and Briegel. A one-way quantum computer.
Physical Review Letters (2001) vol. 86 (22) pp. 5188-5191


This is a special case of what is called an $f$-c.e. set. A set $A$ is $f$-c.e. iff there is computable function $g$ such that

$\chi_A(x) = \lim_i g(x,i)$, and
$\forall x \ |\{s \mid g(x,i) \neq g(x,i+1) \}| \leq f(x)$.

If we consider $f(x)=n$ then we get the definition of $n$-c.e sets.

They don't need to be c.e. because c.e. is not closed under complement. Take two c.e. sets and take their difference. It is a $2$-c.e. set but it does not need to be a c.e. set.

Barry Cooper and colleges have been interested in these sets and the notion of computability in limit. You may want to check his "Definability in the Real Universe" article from "Computability In Context: Computation and Logic in the Real World".


Defining binary natural numbers without quotient types

Use an auxiliary type of positive natural numbers.
data positive : Set where
  one : positive
  s0  : positive → positive -- multiply by 2
  s1  : positive → positive -- multiply by 2 and add 1

data N : Set where
  zero : N
  pos : positive → N

Supplemental: Another option, which I found on my whiteboard today (probably put there by Egbert Rijke months ago) is this:
-- Dyadic natural numbers without redundancy
data N : Set where
  zero : N      -- 0
  suc0 : N → N  -- suc1 n = 2 * n + 2
  suc1 : N → N  -- suc1 n = 2 * n + 1

I think you'll probably prefer this one.


Can typed lambda calculi express *all* algorithms below a given complexity?

I will give a partial answer, I hope others will fill in the blanks.

In typed $\lambda$-calculi, one may give a type to usual representations of data ($\mathsf{Nat}$ for Church (unary) integers, $\mathsf{Str}$ for binary strings, $\mathsf{Bool}$ for Booleans) and wonder what is the complexity of the functions/problems representable/decidable by typed terms.  I know a precise asnwer only in some cases, and in the simply typed case it depends on the convention used when defining "representable/decidable".  Anyhow, I don't know of any case in which there is a doubly exponential upper bound.

First, a brief recap on the Lambda Cube.  Its 8 calculi are obtained by enabling or disabling the following 3 kinds of dependencies on top of the simply typed $\lambda$-calculus (STLC):

polymorphism: terms may depend on types;
dependent types: types may depend on terms;
higher order: types may depend on types.

(The dependency of terms on terms is always there).

Adding polymorphism yields System F.  Here, you can type the Church integers with $\mathsf{Nat}:=\forall X.(X\rightarrow X)\rightarrow X\rightarrow X$, and similarly for binary strings and Booleans. Girard proved that System F terms of type $\mathsf{Nat}\rightarrow\mathsf{Nat}$ represent exactly the numerical functions whose totality is provable in second order Peano arithmetic. That's pretty much everyday mathematics (albeit without any form of choice), so the class is huge, the Ackermann function is a sort of tiny microbe in it, let alone the function $2^{2^n}$. I don't know of any "natural" numerical function which cannot be represented in System F. Examples usually are built by diagonalization, or encoding the consistency of second order PA, or other self-referential tricks (like deciding $\beta$-equality within System F itself).  Of course in System F you can convert between unary integers $\mathsf{Nat}$ and their binary representation $\mathsf{Str}$, and then test for instance whether the first bit is 1, so the class of decidable problems (by terms of type $\mathsf{Str}\rightarrow\mathsf{Bool}$) is equally huge.

The other 3 calculi of the Lambda Cube which include polymorphism are therefore at least as expressive as System F.  These include System F$_\omega$ (polymorphism + higher order), which can express exactly the provably total functions in higher order PA, and the Calculus of Constructions (CoC), which is the most expressive calculus of the Cube (all dependencies are enabled).  I don't know a characterization of the expressiveness of the CoC in terms of arithmetical theories or set theories, but it must be pretty frightening :-)

I am much more ignorant regarding the calculi obtained by just enabling dependent types (essentially Martin-Löf type theory without equality and natural numbers), higher order types or both. In these calculi, types are powerful but terms can't access this power, so I don't know what you get.  Computationally, I don't think you get much more expressiveness than with simple types, but I may be mistaken.

So we are left with the STLC. As far as I know, this is the only calculus of the Cube with interesting (i.e., not monstrously big) complexity upper bounds. There is an unanswered question about this on TCS.SE, and in fact the situation is a bit subtle.

First, if you fix an atom $X$ and define $\mathsf{Nat}:=(X\rightarrow X)\rightarrow X\rightarrow X$, there is Schwichtenberg's result (I know there's an english translation of that paper somewhere on the web but I can't find it now) which tells you that the functions of type $\mathsf{Nat}\rightarrow\mathsf{Nat}$ are exactly the extended polynomials (with if-then-else). If you allow some "slack", i.e. you allow the parameter $X$ to be instantiated at will and consider terms of type $\mathsf{Nat}[A]\rightarrow\mathsf{Nat}$ with $A$ arbitrary, much more can be represented. For example, any tower of exponentials (so you may go well beyond doubly exponential) as well as the predecessor function, but still no subtraction (if you consider binary functions and try to type them with $\mathsf{Nat}[A]\rightarrow\mathsf{Nat}[A']\rightarrow\mathsf{Nat}$). So the class of numerical functions representable in the STLC is a bit weird, it is a strict subset of the elementary functions but does not correspond to anything well known.

In apparent contradiction with the above, there's this paper by Mairson which shows how to encode the transition function of an arbitrary Turing machine $M$, from which you obtain a term of type $\mathsf{Nat}[A]\rightarrow\mathsf{Bool}$ (for some type $A$ depending on $M$) which, given a Church integer $n$ as input, simulates the execution of $M$ starting from a fixed initial configuration for a number of steps of the form
$$2^{2^{\vdots^{2^n}}},$$
with the height of the tower fixed. This does not show that every elementary problem is decidable by the STLC, because in the STLC there is no way of converting a binary string (of type $\mathsf{Str}$) representing the input of $M$ to the type used for representing the configurations of $M$ in Mairson's encoding. So the encoding is somehow "non-uniform": you can simulate elementarily-long executions from a fixed input, using a distinct term for each input, but there is no term that handles arbitrary inputs.

In fact, the STLC is extremely weak in what it can decide "uniformly".  Let us call $\mathcal C_{ST}$ the class of languages decidable by simply typed terms of type $\mathsf{Str}[A]\rightarrow\mathsf{Bool}$ for some $A$ (like above, you allow arbitrary "slack" in the typing). As far as I know, a precise characterization of $\mathcal C_{ST}$ is missing. However, we do know that $\mathcal C_{ST}\subsetneq\mathrm{LINTIME}$ (deterministic linear time). Both the containment and the fact that it is strict may be shown by very neat semantic arguments (using the standard denotational semantics of the STLC in the category of finite sets). The former was shown recently by Terui. The latter is essentially a reformulation of old results of Statman. An example of problem in $\mathrm{LINTIME}\setminus\mathcal C_{ST}$ is MAJORITY (given a binary string, tell whether it contains strictly more 1s than 0s).

(Much) Later add-on: I just found out that the class I call $\mathcal C_{ST}$ above actually does have a precise characterization, which is moreover extremely simple.  In this beautiful 1996 paper, Hillebrand and Kanellakis prove, among other things, that

  Theorem. $\mathcal C_{ST}=\mathsf{REG}$ (the regular languages on $\{0,1\}$).

(This is Theorem 3.4 in their paper).

I find this doubly surprising: I am surprised by the result itself (it never occurred to me that $\mathcal C_{ST}$ could correspond to something so "neat") and by how little known it is. It is also amusing that Terui's proof of the $\mathrm{LINTIME}$ upper bound uses the same methods employed by Hillebrand and Kanellakis (interpreting the simply-typed $\lambda$-calculus in the category of finite sets). In other words, Terui (and myself) could have easily re-discovered this result were it not for the fact that we were somehow happy with $\mathcal C_{ST}$ being a "weird" class :-)

(Incidentally, I shared my surprise in this answer to a MO question about "unknown theorems").


Techniques for showing that problem is in hardness "limbo"

Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo."  But besides that, there are several others:

Show that your problem is in NP ∩ coNP.  (Example: Factoring.)
Show that your problem is solvable in quasipolynomial time.  (Examples: VC dimension, approximating free games.)
Show that your problem is no harder than inverting one-way functions or solving NP on average.  (Examples: Lots of problems in cryptography.)
Show that your problem reduces to (e.g.) Unique Games or Small-Set Expansion.
Show that your problem is in BQP.  (Example: Factoring, though of course that's also in NP ∩ coNP.)
Rule out large classes of NP-completeness reductions.  (Example: The Circuit Minimization Problem, studied by Kabanets and Cai.)

I'm sure there are others that I'm forgetting.


Separation of classes with different amounts of advice?

Let $s(n) \ge n$ be some function. It can be proven that:

$\mathbf{DSIZE}(s) \subseteq \mathbf{DTIME}(s^2) / F(O(s\log s))$

Here, $\mathbf{DSIZE}(s)$ denotes the set of languages decidable by deterministic circuits of size $s$. The notation $\mathbf{K/F}$ denotes the complexity class $\mathbf{K}$ with advice function from the set $\mathbf{F}$, defined as:

$F(f) = \left\{h \colon \{0,1\}^* \to \{0,1\}^* \mid |h(x)| \le f(|x|) \text{ for all } x\right\}$.

In addition, let $d(n) \ge \log n$ be another function. Then:

$\mathbf{DDEPTH}(d) \subseteq \mathbf{DSPACE}(d) / F(2^{O(d)})$

where $\mathbf{DDEPTH}(d)$ denotes the set of languages decidable by deterministic circuits of depth $d$.

Edit: two more inclusions:

For $t(n) \ge n$ we have $\mathbf{DTIME}(t) \subseteq \mathbf{DSIZE}(t \log t)$,
and for $l(n) \ge \log n$ we have $\mathbf{NSPACE}(l) \subseteq \mathbf{DDEPTH}(l^2)$.

  For proofs, see section 2-3 of Heribert Vollmer's book.

Using these inclusions, and time/space hierarchies, one can build hierarchies for non-uniform complexity classes.

Edit 2:

You may combine the above results with the following results on hierarchies for classes with advice:

Time Hierarchies for Computations with a Bit of Advice.
Unconditional Lower Bounds Against Advice.


What is known about matrix multiplication, and matrix circuits?

While I don't know about the complexity of matrix polynomials in general, the state of the art in the complexity of matrix multiplication is nicely summarized in a recent ToC Graduate Survey by Markus Bläser.

Computing entries mod $p$ is basically the same as the question of the complexity of performing the computation over the field $\mathbb{F}_p$, which is fairly well-studied (though perhaps not as well-studied as characteristic zero).

Most matrix multiplication research works in the nonuniform setting anyways, so it should almost all be relevant to the question of circuit size.


Is there an algorithm to generate proof in Coq?

I guess the resource you are looking for is Adam Chlipala's Certified Programming with Dependent Types in which he builds up powerful tactics.


hardness of constant approximation of largest matching set

Check out

  Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai:
  "Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses"
  Link:  https://arxiv.org/abs/1308.2617


What are the known pseudo-polynomial PSPACE-complete problems?

Consider Subset Sum. A standard reduction from 3-SAT produces an instance with values $x_0,\ldots,x_{2n+1}$, where if there is a subset with the target sum, that set contains exactly one of $x_{2i},x_{2i+1}$ for each $i$. Furthermore, choosing $x_{2i}$ corresponds to setting the $i$th variable in the 3-SAT instance to true, and choosing $x_{2i+1}$ corresponds to setting it false. You can use this same reduction to reduce from quantified 3-SAT to result in a PSPACE-complete quantified version of subset sum, $\exists y_0 \forall y_1 \cdots \sum_{i}y_i = k$, where $y_i$ is equal to either $x_{2i}$ or $x_{2i+1}$.

You can use the same pseudo-polynomial time algorithm for subset sum on this quantified version with some minor modifications. We simply fill in a table of all sums $k$ such that $Q_iy_iQ_{i+1}y_{i+1}\cdots Q_ny_n\sum_{j=i}^{n}y_j = k$ (where each $Q_j$ is either $\exists$ or $\forall$). This table has only polynomial size if all the values are polynomially bounded, and it's not hard to see how to fill it in for $i-1$ given the values for $i$ - simply add $x_{2(i-1)}$ and $x_{2i-1}$ to all the values for $i$, and take either the union or intersection of these sets (for $\exists$ and $\forall$ quantifiers, respectively).


State of research on SHA-1 Collision Attacks

SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1.

It is an identical-prefix collision attack that enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-collision block pairs for any suffix $s$ that collides.

$$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$$ for any suffix $s$, where $(m_0, m_1) \neq (m'_0, m'_1)$

The computational requirement is estimated to $2^{63.1}$

  The first first-block near collision was found after spending about 3583 core years that had produced 180 711 partial solutions up to step 61. A second near collision block was then later computed; it required an additional 2987 core years and 148 975 partial solutions.1


Upper bounds on higher order eigenvalues of regular graphs

I wanted to add this as a comment but it was too long. I am not sure if this completely answers the question.

For bipartite graphs for instance we can possibly get a simple first cut bound from a simple trace method. Lets look at the adjacency matrix. In your case we want to show that $\lambda_k$ is not close to 0. So consider $Trace(A^2)$. For a d-regular graph this is always $\geq dn$. Therefore $$\sum \lambda_i^2 \geq dn$$ which implies that $$2d^2k + n\lambda_k^2 \geq dn$$ Now for $k << n$ and $d$ a constant one can essentially get a $\Omega(\sqrt{d})$ bound for $\lambda_k$. So indeed they cant be very close to 1 in the normalized laplacian. I am not sure whether the parameters work out in the way you want them to.


Minimum weight matching in general graphs with additional input specifying the number of matched edges

Add $n-2k$ extra vertices, each connected to all the original vertices with zero-weight edges, and add a large enough number $W$ to each of the original edges to make their weights all positive. Then look for the minimum weight perfect matching.


Finding an answer key given tests and scores

Solving this problem is NP-hard. In particular, even deciding whether there exists an answer key consistent with the given answer choices and scores is NP-complete. We can prove this by reduction from 1-in-3 SAT.

Given a 1-in-3 SAT formula with $c$ clauses and $n$ variables, we construct an instance of your problem with $n$ questions, each with 3 choices, and $c+1$ sample answer/grade pairs.

For each variable $x$, one of the questions is "what is the value of boolean variable $x$?" and the three possible answers are "True", "False", and "17".

One student answers every question with the answer $17$ and gets a score of zero. The remaining students are each assigned a clause. For every positive literal $x$ occurring in the clause, the student answers the question about $x$ with the answer "True". For every negative literal $\neg x$ occurring in the clause, the student answers the question about $x$ with the answer "False". For every other question, the student answers $17$. Every such student gets a score of one.

An answer key must correspond with an assignment of binary values to the variables (since no question has $17$ as the correct answer as shown by the fact that the student who always answered $17$ got zero points). Furthermore, there must be exactly one true literal in each clause under this assignment in order for the answer key to match the scores given to the students. In other words, the satisfying assignments to the input 1-in-3 SAT formula are in a bijection with the answer keys consistent with the student scores.

Clearly then, deciding whether an answer key consistent with the student scores exists is NP-hard. Similar arguments can be made to show that for example counting answer keys is #P-complete.


This is not quite an answer, but it's close. The following is a proof that the problem is NP-hard under randomized reductions.

There's an obvious relation to subset sum which is: suppose you know the factors of $N$: $p_1$, $p_2$, $\ldots$, $p_k$. Now, you want to find a subset $S$ of $p_1$ $\ldots$ $p_k$ such that

$$\displaystyle \log L \leq \sum_{p_i \in S} \log p_i \leq \log U.$$

The problem with trying to use this idea to show the problem is NP-hard is that if you have a subset-sum problem with numbers $t_1$, $t_2$, $\ldots$, $t_k$,
you can't necessarily find primes in polynomial time such that $\log p_i \propto t_i$ (where by $\propto$, I mean approximately proportional to). This is a real problem because, since subset-sum is not strongly NP-complete, you need to find these $\log p_i$ for large integers $t_i$.

Now, suppose we require that all the integers $t_1$ $\ldots$ $t_k$ in a subset sum problem are between $x$ and $x(1+1/k)$, and that the sum is approximately $\frac{1}{2}\sum_i t_i$. The subset sum problem will still be NP-complete, and any solution will be the sum of $k/2$ integers. We can change the problem from integers to reals if we let $t'_i$ be between $t_i$ and $t_i+\frac{1}{10k}$, and instead of requiring the sum to be exactly $s$, we require it to be between $s$ and $s + \frac{1}{10}$. We only need to specify our numbers to around $4 \log k$ more bits of precision to do this. Thus, if we start with numbers with $B$ bits, and we can specify real numbers $\log p_i$ to approximately $B + 4 \log k$ bits of precision, we can carry out our reduction.

Now, from wikipedia (via Hsien-Chih's comment below), the number of primes between $T$ and $T+ T^{5/8}$ is $\theta(T^{5/8}/\log T)$, so if you just choose numbers randomly in that range, and test them for primality, with high probability get a prime in polynomial time.

Now, let's try the reduction. Let's say our $t_i$ are all $B$ bits long. If we take $T_i$ of length $3B$ bits, then we can find a prime $p_i$ near $T_i$ with $9/8B$ bits of precision. Thus, we can choose $T_i$ so that $\log T_i \propto t_i$ with precision $9/8\, B$ bits. This lets us find $p_i \approx T_i$ so that $\log p_i \propto t_i$ with precision $9/8\,B$ bits. If a subset of these primes multiplies to something close to the target value, a solution exists to the original subset sum problems. So we let $N=\Pi_i p_i$, choose $L$ and $U$ appropriately, and we have a randomized reduction from subset sum.


A generalization of the geometric closest pair problem to balls

As Suresh says in his comment, you can extract the closest pair from the additively-weighted Voronoi diagram of the centers of the balls.  The closest pair of balls (in your case, diamonds) will have adjacent Voronoi regions.

The additively weighted Voronoi diagram of $n$ points in the plane can be constructed in $O(n\log n)$ time with high probability using a standard randomized incremental algorithm.  The same algorithms work, with only minor modifications, for diagrams in the Euclidean metric ($L_2$), the Manhattan metric ($L_1$), the supremum metric ($L_\infty$), or the $L_p$ metric for any other fixed $p\ge 1$.


SAGE supports interactive graph drawing. You can easily create customized software for your own use.

Graph editor


Deciding whether a context-free language is regular

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.

Regarding DCFL, I have two references (from Hopcroft+Ullman 79):

A regularity test for pushdown machines,  R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. Valiant, JACM 1975

Regarding a procedure to get a regular version when possible, I have no suggestion.


You need  to understand that $\mathsf{CSP}$  problems have a structure that generic $\mathbf{SAT}$ problems do not have. I will  give  you  a  simple example. Let $\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$.   This language is  such that  you can only  express equality  and inequality between   two  variables.  Clearly any such set of constraints is solvable in polynomial time.

I  will  give  you  two  arguments  to  clarify  the  relation  between
$\mathsf{CSP}$ and clauses. Notice that all that follows assumes $\mathbf{P}\not=\mathbf{NP}$.

First: constraints have a fixed number  of variables,  while  the encoding  of intermediate problems may need  large clauses. This is not  necessarily an issue when such large constraints can  be expressed as a conjunction  of small ones  using auxiliary  variables.  Unfortunately this is not always the case for general $\Gamma$.

Assume $\Gamma$ to just contain the $\mathsf{OR}$ of five variables.  Clearly you  can express the $\mathsf{OR}$ of less variables   by  repeating   inputs.  You   cannot  express   a  larger $\mathsf{OR}$  because the  way  to do  it  using extension  variables requires  disjunctions  of positive  and  negative literals.  $\Gamma$ represents relations  on variables,  not on literals.  Indeed when you think  about 3-$\mathbf{SAT}$ as  a $\mathsf{CSP}$ you  need $\Gamma$ to contain four relations of disjunction with some negated inputs (from zero to three).

Second: each relation in $\Gamma$ can be expressed as a batch of clauses with (say) three literals.  Each constraint must be a whole batch of such   clauses.  In   the  example   with equality/inequality   constraints    you   cannot   have    a   binary $\mathsf{AND}$ (i.e. relation ${(1,1)}$) without enforcing a binary negated  $\mathsf{OR}$   (i.e.  relation  ${(0,0)}$)   on  the  same
variables.

I hope this illustrates to you that $\mathbf{SAT}$ instances obtained from $\mathsf{CSP}$s have a very peculiar structure, which is enforced by the nature of $\Gamma$.  If the structure is too tight then you cannot express hard problems.

A corollary of Schaefer Theorem is that whenever $\Gamma$ enforces a structure loose enough to express $\mathbf{NP\backslash P}$ decision problems, then the same $\Gamma$ allows enough freedom to express general 3-$\mathsf{SAT}$ instances.


Is the longest trail problem easier than the longest path problem?

From the comments above: the Hamiltonian cycle problem remains NP-complete even in grid graphs with max degree 3 [1], but in these graphs every traversal of a node requires two edges and at most one edge remains unused, so a node cannot be traversed twice by an Eulerian path.

So apparently there is an immediate reduction from the Hamiltonian cycle problem to your problem:
given a grid graph with max degree 3 $G = (V,E)$, just ask for a trail of length $|V|$.

But all three edges of the node at the end of the trail can be used; to avoid this situation you can pick the top-left node $u$ of the grid graph (which has degree two) and add two nodes: $V' = V \cup \{u',u''\}$ and a new edges $E = E \cup  \{(u,u'), (u,u'')\}$ and ask for a trail of length $|V'| = |V|+2$: informally the added edge forces $u',u''$ to be the endpoints of the trail.

[1] Christos H Papadimitriou, Umesh V Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231-246, ISSN 0196-6774


Is embedding a solution feasible for SAT?

You can take any formula $\varphi$ and change it to the formula $\varphi \vee \psi_x$ where $\psi_x$ is a "hard" SAT instance whose only solution is $x$. One way to construct such a formula is using cryptography:  if $f:\{0,1\}^n\rightarrow \{0,1\}^n$ is a one-way permutation and we choose $x$ at random and set $y=f(x)$, then one can convert $y$ into a SAT formula such that $x$ is its only solution and thus finding $x$ corresponds to inverting $f$. (We need for this $x$ to be random, but this something similar is anyway assumed if we think finding $x$ should be hard.)


Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings?

tl;dr:

(1) While (a) there is a kind of Rice's Theorem for your example construction, (b) it seems to me unlikely that one holds for realizable numberings in general.

(2) Your particular construction of a code $\psi$ with a fixed encoding for some $f$ has lots of (provable) deficiences, and I think other numberings can only get worse from there, so I don't think it's a very good programming environment, though I suppose that's a matter of what you're willing to trade off in order to have that fixed encoding.

Elaboration:

(1a) Rice-type theorem for your example construction. Let $\psi$ be the encoding from the comments, namely $\psi_0$ is the all-zeros function, and $\psi_n = \varphi_b + \delta_a$ where $n = (a,b)$ under some fixed computable bijection $\mathbb{N} - \{0\} \to \mathbb{N}^2$, $\varphi$ is a standard (acceptable) numbering, and $\delta_a$ is the Kronecker delta function, which is $\delta_a(a) = 1$ and $\delta_a(a') = 0$ for all $a' \neq a$. Let $P^{(1)}_1$ denote the subset of $P^{(1)}$ consisting of functions that have at least one nonzero output value (note that these are precisely the functions $\psi_{(a,b)}$ such that $\varphi_b(a)$ halts). Then for any subset $\emptyset \neq S \subsetneq P^{(1)}_1$, the function
$$s(a,b)=1 \text{ iff } \psi_{(a,b)} \in S$$
is not computable. We mimic the proof of Rice's Theorem; suppose $s$ were computable. Let $(a_0,b_0)$ be such that $\psi_{(a_0,b_0)} \notin S$ and let $(a_1,b_1)$ be such that $\psi_{(a_1,b_1)} \in S$. Let $D(p)$ be the total computable function which proceeds as follows:

$D(0)=0$
$D(p)(n)$ = if $s(p)=1$ then $\psi_{(a_0,b_0)}(n)$, otherwise $\psi_{(a_1,b_1)}(n)$

Now, if $s$ is computable, then so is $D$, and furthermore, $D$ is in $P^{(2)}_1$, so there is some index $(a_d,b_d)$ for $D$. Then consider $D((a_d,b_d))$: if $s((a_d,b_d))=1$ then $D((a_d,b_d)) = \psi_{(a_0,b_0)} \notin S$, and if $s((a_d,b_d))=0$ then $D((a_d,b_d)) = \psi_{(a_1,b_1)} \in S$, so either way $s$ gets it wrong.

(1b) The above relied on the fact that although we don't have a total computable compiler from $\varphi$ to $\psi$, we at least had a partial one which covered a nontrivial set of functions. I wouldn't be surprised if you can cook up a realizable numbering where there's essentially no such partial compiler.

(2) Since a $\psi$-Rice's Theorem fails for $\{f\}$, $\psi$ also must not satisfy the S-m-n Theorem (currying). In particular, there is some $n$ such that $\psi_n(x,y) = \varphi_x(y)$ (i.e., a universal TM). But then there is no computable program transformation $t$ such that $\psi_{t(m,x)}(y) = \psi_m(x,y)$ for all $m,x,y$, for if there were, $t(n,x)$ would enable you to decide whether $\varphi_x = f$, which is undecidable by the usual Rice's Theorem. Currying is a pretty basic feature for a programming environment to lack. I think one can prove a similar thing not just for currying, but for infinitely many program transformations, probably whenever the transformation is not finitely different from the identity map and has $f$ in its image.


Which areas of TCS are better for a math bachelor?

It had been argued that Theoretical Computer Science is a branch of mathematics, so it seems to me that any answer to this question would necessarily be primarily opinion-based. That said, in your place (and this is an uninformed opinion) I would steer clear of subfields in which a tremendous volume of technical work has been done, and in which coding plays a greater role. The barrier to entry in such subfields will be quite high for a math major. So for example, I would be cautious of anything related to computer vision and speech recognition. I would also be cautious of subfields in which the objective is perhaps a bit fuzzy, such as AI and machine learning. More controversially, I think that perhaps you should steer clear of quantum computation for this reason.

Conversely, subfields in which the objective is well-defined and in which coding plays a lesser role have a lower entry barrier for a math major. For example, complexity theory, graph algorithms, information theory (perhaps especially for you!), concurrency, cryptography, and maybe even things like clustering and compressed sensing.


Functions that are Not Efficiently Computable but Learnable

I will formalize a variant of this question where "efficiency" is replaced by "computability".

Let $C_n$ be the concept class of all languages $L\subseteq\Sigma^*$
recognizable by Turing machines on $n$ states or fewer.
In general, for $x\in\Sigma^*$ and $f\in C_n$, the problem of evaluating
$f(x)$ is undecidable.

However, suppose we have access to a (proper, realizable)
PAC-learning oracle $A$
for $C_n$. That is, for any $\epsilon,\delta>0$,
the oracle requests
a labeled sample of size
$m_0(n,\epsilon,\delta)$
such that, assuming such a sample was drawn iid from
an unknown distribution $D$,
the oracle $A$ outputs a hypothesis $\hat f\in C_n$
which, with probability at least $1-\delta$, has $D$-generalization error
not more than $\epsilon$.
We will show that this oracle is not Turing-computable.

Actually, we will show that a simpler problem is undecidable:
One of determining,
given a labeled sample $S$,
whether there exists an $f\in C_n$ consistent with $S$.
Suppose (to get a contradiction) that $K$ is a Turing machine
that decides the consistency problem.

We make the following notational conventions.
Identify $\Sigma^*$ with $\mathbb{N}=\{0,1,2,\ldots\}$ via the usual
lexicographic ordering.
For $x\in\{0,1\}^*$, we say that a TM $M$ "S-prints"
$x$ if it accepts all of the strings in $\Sigma^*$
corresponding to the indices $i$ s.t. $x_i=1$
and does not accept (possibly by not halting)
any of the strings
corresponding to the indices $x_i=0$.
Since (by assumption) $K$ is
decidable,
it follows that the function $\tilde K:x\mapsto k$,
defined to be the smallest $k$ such that some TM in $C_k$
S-prints $x$, is Turing-computable.
It further follows that
the function
$g:k\mapsto x$, which maps a $k\in\mathbb{N}$
to the least (lexicographically) string $x\in\{0,1\}^*$
such that $\tilde K(x)>k$, is also computable.

Now define the TM $M$ as follows: $M$ S-prints $g(|\langle M\rangle|)$,
where
$\langle M\rangle$ is the encoding of $M$,
$|x|$ denotes string length, and the recursion theorem
is being invoked to assert the existence of such an $M$.
Then $M$ has some encoding length, $\ell=|\langle M\rangle|$,
and it S-prints some string, $x_M\in\{0,1\}^*$.
By construction, $\tilde K(x_M)>\ell$, and so $x_M$ cannot be S-printed
by any TM with description length $\ell$ or shorter. And yet it is defined
as the S-print output of a TM with description length $\ell$ --- a contradiction.


What is the fastest algorithm for Weighted Planar Max Cut

Shih, Wu, and Kuo's "unifying" paper reduces the planar maximum cut problem to two related problems in planar graphs: (1) maximum-weight bipartite matching and (2) minimum cycle (aka weighed girth).  Both problems are solved in $O(n^{3/2}\log n)$ time using divide-and-conquer algorithms that rely on Lipton and Tarjan's planar separator theorem.

After a long series of improvements, the minimum-weight cycle in a weighted planar graph can now be computed in $O(n \log\log n)$ time using a recent algorithm of Łącki and Sankowski (2011).

However, I am unaware of any improvement on the time to find maximum-weight matchings, which means Shih, Wu, and Kuo's $O(n^{3/2}\log n)$ time algorithm is still the fastest algorithm known (at least to me) for weighted planar max-cut.


Type theory for memory safe data structures

There has been a lot of work around the idea of statically checking the memory safety properties of programs.

Francois Pottier give an excellent overview of various approaches in this presentation. The main technique you probably would be interested in is region typing.

The Wikipedia article is quite complete, but the basic idea is to keep explicit regions which references are required to explicitly be assigned to a given region, which can be managed by the programmer or left to be inferred by the compiler. This is somewhat reminiscent of the RAII approach to memory management used mainly in C++ (the wiki article is terrible however).

In practice, region inference hasn't gained widespread use in compilers, mainly because of the complexity of the analyses involved.

Again related, there has been a flurry in work on separation logic over the last decade, which is an extension of Hoare Logic which allows reasoning over separate regions of the heap, in order to analyze whether objects can share memory locations or not. This method of reasoning is quite difficult to apply to a language like C with "real" pointers, because of the possibility of pointer aliasing.


Commutativity of addition in polymorphic lambda calculus

The fact that $\mathsf{Add}\ u\ v = \mathsf{Add}\ v\ u$ is not provable for arbitrary $u$ and $v$ does indeed follow from the Church-Rosser property.

Write $u =_\beta v$ if $u \mathrel{({}_\beta\!\!\leftarrow\cup\rightarrow_\beta)^\ast} v$, where $\rightarrow_\beta$ is $\beta$-reduction in System F and $(\cdot)^\ast$ is the reflexive-transitive closure operator (this is a possible definition of $\beta$-equality, which Breazu-Tannen and Coquand denote simply by $=$. Here I will use the $\beta$ subscript and keep the $=$ symbol for strict equality, i.e., $\alpha$-equivalence if you like).  It follows immediately from the definition that if two terms have a common reduct, i.e., $u\rightarrow_\beta^\ast w$ and $v\rightarrow_\beta^\ast w$, then $u=_\beta v$. The Church-Rosser theorem states that the converse also holds:
$$u=_\beta v \quad \textrm{implies}\quad \exists w.\ u\rightarrow^\ast w\textrm{ and }v\rightarrow^\ast w.$$
It follows that $\beta$-equivalent normal forms are necessarily identical:
$$u,v\textrm{ normal and }u=_\beta v\textrm{ implies }u=v.$$

Read contrapositively, the above says that different normal forms can never be $\beta$-equivalent. Now, suppose $\mathsf{Add}\ u\ v=_\beta\mathsf{Add}\ v\ u$ for arbitrary $u$, $v$. In particular, this holds when $u=x$ and $v=y$ are distinct variables of type $polyint$. But it is easy to show (just apply a couple of steps of $\rightarrow_\beta$) that $\mathsf{Add}\ x\ y=_\beta u'$ and $\mathsf{Add}\ y\ x=_\beta v'$ with $u'$ and $v'$ distinct normal forms. Contradiction.


Many-one reductions vs. Turing reductions to define NPC

Two reasons:

(1) just a matter of minimality: being NPC under many-one reductions is a formally stronger statement and if you get the stronger statement (as Karp did and as you almost always do) then why not say so?

(2) Talking about many-one reductions gives rise to a richer, more delicate, hierarchy.  For example the distinction NP vs co-NP disappears under Turing reductions.

This is similar in spirit to why often one uses Logspace-reductions rather than polytime ones.


A data structure for minimum dot product queries

Consider the special case where you just want to determine if your query vector is orthogonal to some vector in your preprocessed collection. (That is, you want to determine if $\min_i \langle x, v_i \rangle = 0$, where the vectors under discussion have non-negative coefficients.) This case is already very interesting.

Suppose you can answer queries in $n^{O(1)} m^{1-\delta}$ time for some $\delta > 0$, with $m^{O(1)} n^{O(1)}$ preprocessing (the polynomial's degrees should not depend on $m$ or $n$ or $\delta$).

In the paper "A new algorithm for optimal 2-constraint satisfaction and its implications", I observed that such a data structure would actually allow you to solve CNF-SAT in $2^{\alpha v}$ time for some $\alpha < 1$, where $v$ is the number of variables. This would refute the "Strong Exponential Time Hypothesis" that k-SAT requires essentially $2^n$ time for unbounded $k$.

To see why, suppose the preprocessing time is bounded by $(nm)^c$. Consider a CNF formula $F$ with $v$ variables and $n$ clauses. We split the set of variables into two parts $P_1$ and $P_2$ of size $v(1-1/(2c))$ and $v/(2c)$, respectively. List all possible assignments to the variables in the parts (getting $2^{v(1-1/(2c))}$ and $2^{v/(2c)}$ assignments, respectively). Associate each of these partial assignments $A_i$ with an $n$-bit vector $w_i$ where $w_i[j]=1$ iff the $j$th clause of $F$ is not satisfied by $A_i$. So we have two lists of exponentially many bit vectors.

Notice that $F$ is satisfiable iff there is a vector $w_1$ from an assignment on $P_1$ and a vector $w_2$ from an assignment on $P_2$ such that $\langle w_1, w_2 \rangle = 0$.

Now let $m=2^{v/(2c)}$, and preprocess the assumed data structure with all vectors from part $P_2$. This takes $n2^{v/2}$ time, by assumption. Run the query algorithm on all vectors from assignments on part $P_1$. By assumption this takes $2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$. Let $\alpha = 1 - \delta/(2c)$.

Perhaps it is possible to get efficient preprocessing and $n^{O(1)} m^{1-1/(\log \log m)}$ query time with existing techniques. The best known CNF-SAT algorithms don't rule it out. (They get something like $2^{n-n/\log n}$.) But to compute $\min_i \langle x, v_i\rangle$ is slightly stronger -- in this setup, it would be like solving MAX CNF-SAT.


Are there decidable problems for which for no algorithm we can give time bounds?

For every algorithm $A$ that terminates on a class of inputs $\mathsf{In}$, we can define the function of its running times:
$$
f(n)=\max_{i\in \mathsf{In(n)}}~~ \mathsf{time}(A(i)),
$$
where $\mathsf{In}(n)$ is the class of inputs of length $n$ and $\mathsf{time}(A(i))$ is the time algorithm $A$ requires to terminate on $i$. Of course, this definition is unsatisfying as it relates to the algorithm, but it shows the existence of such a function.
The question that remains is whether there exists a concise representation (and I believe that this was what you were asking for).

If we use simple algebraic terms (without recursion of any sort) as definition of concise, then I think the answer is no: There are problems which can be decided but whose complexity is nonelementary. That is, there does not exist a stack of the form $2^{2^{2^{2^{\dots^n}}}}$ that bounds the execution time of an algorithm for a problem of size n.

I hope I understood your question in the right way.


Minimum weight subforest of given cardinality

Similar to the solution for a binary tree, you can solve it in polynomial time on a tree without degree restriction:
First, generalize the problem such that every node also has a "count" $c_i\in\{0,1\}$, and the problem is to find a subforest $S$ of count $k=\sum_{i\in S} c_i$.
Generalize the dynamic programming approach to this version (it still works with a table, given a fixed count $C$, what is the minimal weight subforest in the subtree having count precisely $C$)

Keep the original tree with nodes of count 1.  Every node $v$ with degree greater than 2 is split into a binary tree with deg$(v)$ leaves (the shape does not matter).  The new nodes have count and weight 0. Solve the problem on the new tree. When reading out the solution ignore any new node; this will still be a subforest of the same weight.  Because any original subforest translates into a new subforest of the same weight, the found subforest is optimal.


It seems this is false in general. Take the tree with a central node $x$, connected to a bunch of nodes $y_1,\dots,y_n$. Each node $y_i$ is additionally connected to a node $z_i$.

The total number of nodes is $N=2n+1$.

Any caterpillar in this tree can contain at most two $z$ nodes, and therefore, $n/2$ caterpillars are needed to cover it. So it is impossible to cover it with $O(log N)$ caterpillars.


What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

Although not exactly what you're looking for, this paper seems to be the most current (2019) efforts towards tight $AC^0[2]$ bounds as of yet, and provides a good summary of the difference between $AC^0$ and $AC^0[2]$ bounds.


Let $\alpha$ be the probability of clicking through a link and let $1-\alpha$ be the probability of going to a random website. I think you're asking whether PageRank will work with $\alpha=1$. The answer is yes if and only if the network is strongly connected and the induced random walk is aperiodic. I'm not sure what "entirely closed" means.

Setting $\alpha = 1 $ gives intuition for how PageRank works, but there are very good reasons for setting $\alpha < 1$. Namely, we want PageRank (1) to converge in every graph, (2) to converge to the same thing regardless of the initial rank distribution, (3) to converge as quickly as possible. PageRank is just a fancy name for how to set up a particular Markov Chain. For any $\alpha \in [0,1] $ you'll get some Markov Chain, you just need to make sure that it has properties 1-3.

This is the best PageRank survey that I've seen (better than Wikipedia or the original paper) and explains this: http://www.ams.org/samplings/feature-column/fcarc-pagerank

Edit: As per MCH's answer we also want the 4th condition that every vertex has positive rank, which is also ensured by the random surfer model.


What exactly is Lawler's modification to Yen's algorithm and how does it work?

Yen's original paper 1, from 1971, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1).
Lawler's original paper 2, from 1972, improves the time complexity upper bound to $O(Kn^3)$.
Wikipedia's analysis of Yen's algorithm, leading to the $O(Kn(m+n\log n))=O(Kn^3)$ upper bound, is based on the Fibonacci heap implementation of Dijkstra's algorithm, from 1984. [3] But even the $O(n^2)$ upper bound for Dijkstra's algorithm would be fine; the issue, as far as I can tell, is that Wikipedia is not considering the same problem.

Namely, Yen's paper, as well as Lawler's, consider graphs where negative weights are allowed. The Wikipedia seems to restrict itself to non-negative weights, so... one can use Dijkstra there.

See for instance this quote from Yen's paper (Section 5):

and this one for Lawler's paper (Section 5):

1 Finding the K Shortest Loopless Paths in a Network, Jin Y. Yen (1971).
Management Science 197117:11 , 712-716

2 A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem,
Eugene L. Lawler (1972). Management Science 197218:7 , 401-405

[3]  Fibonacci heaps and their uses in improved network optimization algorithms. Fredman, Michael Lawrence; Tarjan, Robert E. (1984). 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934.


It is not hard to see that without additional stability assumptions one won't be able to get high probability bounds. For example consider predicting unbiased coin using majority label in the sample. With probability $~1/\sqrt{n}$ we get that majority of leave-one-out is exactly the opposite of the excluded point so LOO will give error of 1. Note that the true error is always 1/2.

If one assumes stability then the bounds will depend on the notion of stability being used. Uniform stability will give high probability bounds for both empirical mean and LOO estimator (e.g. https://arxiv.org/abs/1902.10710).
Weaker notions will give you weaker bounds. I guess the latest on variance of the estimator is this paper http://www.satyenkale.com/papers/crossvalidation.pdf


I am not completely sure what you are looking for, but the following might
be interesting to you:

The idea that restricting numerical predicates in FO-formula corresponds to uniformity conditions is explicitly investigated, for example, in the paper
"FO(<)-uniformity" by Behle and Lange.
The survey "Arithmetic, first-order logic, and counting quantifiers"
by Schweikardt provides i.a. an overview of known results about
the expressive power of different arithmetical predicates


For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

For undirected graph problem admits a FPT algorithm for any fixed $k$. Robertson and Seymour, Graph Minor XIII. Their algorithm runs in time $2^{2^{2^{2^{O(k)}}}} P(n)$ which means for $k = O(\log\log\log\log n)$ is polynomial. But it's not known whether there is better bound for $k$ or not. In special cases like undirected planar case and recently bounded genus case, running time improved.

For directed graph it's NP-Complete even case of 2-disjoint path problem. But in planar graphs is FPT by result of Marx et al., in graphs of bounded genus is at least in XP (not known whether is FPT or not), in directed acyclic graphs is $W[1]$-hard by result of Slivkins, for tournaments is NP-complete (not known if is FPT or even XP, edge disjoint version admits XP algorithm by result of Seymour et al).


Improved lower bound on monotone circuit complexity of perfect matching?

Eva Tardos proved that the gap is truly exponential by showing that there is a monotone boolean function that has poly size circuits but requires exponential size monotone circuits. Nothing better than super-polynomial is known for matching.

Raz has a result that monotone circuits for matching have linear depth. (Thanks Klauck, for pointing the typo.)

AFAIK, we know nothing better.

Ref: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf

(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps


Does focused proof search ever have to backtrack across the choice of focus formula?

Yes, backtracking in focused proof search may be necessary due to a wrong choice of focus formula.  Consider the provable sequent
$$\vdash p\otimes q, (p^\bot\mathrel{\wp} q^\bot)\otimes r, r^\bot.$$
Choosing to focus on $p\otimes q$ leads to a dead end, because however you "split" the context you end up with an atom ($p$ or $q$) without matching dual.  So $(p^\bot\mathrel{\wp} q^\bot)\otimes r$ must be decomposed first.

A side remark, not directly related to the question but which gives some  further context: the formula $p\otimes q$ above is known to proof net connoisseurs as a "non-splitting tensor".  When showing that proof nets (in the sense of suitably labelled graphs satisfying certain connectivity and acyclicity conditions) correspond to sequent calculus proofs (the sequentialization theorem) one must at some point prove the non-trivial "splitting lemma": if the conclusions of a proof net come only from axiom or tensor nodes, then there is one such tensor node which is "splitting", in the sense that removing it decomposes the proof net into two connected components which are themselves proof nets (this allows sequentialization to be proved inductively).  One of course may wonder whether all tensors are always splitting, and the above is the minimal counterexample.
In terms of proof nets, focusing strengthens the splitting lemma by adding that there always exists a "hereditarily splitting tensor", in the sense that there is a tensor node such that all tensor nodes directly above it have the splitting property.


Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

The article by Thomas Colcombet on Green's Relations and Their Use in Automata Theory might be interesting for you. These relations are very common in the algebra of semigroups.

See also Section 2.8 in Chapter 10 of the Handbook of Formal Languages.


Early references for discrete optimization

Usually, Schrijver provides a good source for history. You can look at the following books and an article.

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003.
Alexander Schrijver. Theory of Linear and Integer Programming. Wiley 1998.
Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming 91(3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
Alexander Schrijver. On the history of combinatorial optimization (till 1960).  Handbook of Discrete Optimization, Elsevier, 2005.  http://homepages.cwi.nl/~lex/files/histco.pdf


What does it mean for a language to have "order"?

My angle on a related distinction: http://chrisamaphone.livejournal.com/751991.html

The "order" of nth-order (including higher-order) logic refers to the level of things that can be quantified over. In first-order logic, the things quantified over are terms of some unrelated domain: "All men are mortal." In second order logic, you can quantify over first-order predicates: "All properties of men also hold of dragons." Higher-order logic is the generalization of this to all higher predicates, which I think is better understood in terms of system F-omega (equivalent to HOL), wherein you can form type operators (constructors of kind type -> type) which can be quantified over as well as types.

The relation to "order" in polynomials is better understood as an analogy pertaining to recursion (nth order polynomials include a term multiplied by itself n times) than anything more rigorous.


Solve a simple system of linear inequalities in natural numbers

Construct a graph with one vertex per variable, and one extra vertex $s$. Make an edge from $s$ to all other vertices, of length zero. For each inequality $a_i + c \ge a_j$, make an edge of length $c$ from $a_i$ to $a_j$. Then if your graph has a negative-length cycle, your inequalities have no solution, and if it does not have a negative-length cycle then the distance from $s$ to each vertex gives a solution. You can use Floyd or Bellman–Ford or any other shortest path algorithm that can allow negative weights.


What is the correct definition of $k$-tree?

I basically agree with you, with just a tiny modification:

  A graph $G$ is a $k$-tree if and only if either $G$ is a complete graph with $k+1$ vertices, or $G$ has a vertex $v$ such that the (open) neighborhood of $v$ forms a $k$-clique, and $G - v$ is a $k$-tree.

In other words, $v$ should have degree $k$, instead $k-1$ in your definition.

I personally prefer the bottom-up definition, but this is just a matter of taste:

  The complete graph on $k+1$ vertices is a $k$-tree.
  A $k$-tree $G$ with $n+1$ vertices ($n\ge k+1$) can be constructed from a $k$-tree $H$ with $n$ vertices by adding a vertex adjacent to exactly $k$ vertices that form a $k$-clique in $H$.
  No other graphs are $k$-trees.

This definition is a slightly modified version of the definition from Pinar Heggernes' lecture notes.


Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

Here are the lower bounds I can show. I conjecture that for a fixed $\epsilon$, the right lower bound is $\Omega( \log n)$, but naturally I might be wrong.

I am going to use a decreasing sequence (just for convenience). The basic mechanism is breaking the sequence into $L$ blocks. In the $i$th block there are going to be $n_i$ elements (i.e., $\sum_i n_i = n$).

In the following, we want the algorithm to succeeds with probability $\geq 1-\delta$, for some parameter $\delta >0$.

First lower bound: $\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$.

The $i$th block has $n_i = 2^{i-1}$ elements, so $L = \lg n$. We set the value of all the elements in the $i$th block to be $(1+X_i)/(2n_iL)$, where $X_i$ is a variable that is either $0$ or $1$. Clearly, the total sum of this sequence is
$$
\alpha = \sum_{i=1}^L \frac{1+X_i}{2n_i L} = \frac{1}{2} + \frac{1}{2L}\left(\sum_{i=1}^L X_i \right).
$$
Imagine picking each $X_i$ with probability $\beta$ to be $1$ and $0$ otherwise.  To estimate $\alpha$, we need a reliable estimate of $\beta$. In particulate, we want to be able to distinguish the base $\beta = 1-4\epsilon$ and, say, $\beta=1$.

Now, imagine sampling $m$ of these random variables, and let $Z_1, \ldots, Z_m$ be the sampled variables.  Settings $Y = \sum_{i=1}^m (1-X_i)$ (note, that we are taking the sum of the complement variables), we have $\mu = E[Y] = (1-\beta) m$, and Chernoff inequality tells us that if $\beta =1-4\epsilon$, then $\mu = 4\epsilon m$, and the probability of failure is
$$
 P\left[ Y \leq 2\epsilon m \right] =  P\left[ Y \leq (1-1/2) \mu \right] \leq \exp \left( -\mu (1/2)^2 / 2 \right) = \exp \left( -\epsilon m / 2 \right).
$$
To make this quantity smaller than $\delta$, we need $\displaystyle m \geq \frac{2}{\epsilon} \ln \frac{1}{\delta}$.

The key observation is that the Chernoff inequality is tight (one has to be careful, because it is not correct for all parameters, but it is correct in this case), so you can not do better than that (up to constants).

Second lower bound: $\Omega( \log n / \log \log n)$.

Set the $i$th block size to be $n_i = L^i$, where $L = \Theta( \log n / \log \log n)$ is the number of blocks. An element in the $i$th block has value $\alpha_i = \Bigl(1/L\Bigr)/n_i$. So the total sum of the values in the sequence is $1$.

Now, we might decide to pick an arbitrary block, say the $j$th one, and set all values in its block to be $\alpha_{j-1} = L \alpha_j$ (instead of $\alpha_j$). This increases the contribution of the $j$th block from $1/L$ to $1$, and increase the total mass of the sequence to (almost) $2$.

Now, informally, any randomized algorithm must check the value in each one of the blocks. As such, it must read at least $L$ values of the sequence.

To make the above argument more formal, with probability $p=1/2$, give the original sequence of mass $1$ as the input (we refer to this as original input). Otherwise, randomly select the block that has the increased values (modified input). Clearly, if the randomized algorithm reads less than, say, $L/8$ entries, it has probability (roughly) $1/8$ to detect a modified input.  As such, the probability this algorithm fails, if it reads less than $L/8$ entries is at least
$$
 (1-p)(7/8) > 7/16 > 1/3.
$$

P.S.  I think by being more careful about the parameters, the first lower bound can be improved to $\Omega(1/\epsilon^2)$.