What is the complexity of the equivalence problem for read-once decision trees?

I found a partial solution. The problem is in L.

The negation of $A \leftrightarrow B$ is equivalent to $(\bar A \land B) \lor (A \land \bar{B})$ which is equivalent to $False$ iff both $(\bar A \land B)$ and $(A \land \bar{B})$ are.

The read-once decision tree for $\bar{A}$ can be obtained from the read-once decision tree for $A$ by switching $True$ and $False$ in $A$.
This can be done in log space.

To check if $\bar A \land B$ is equivlent to $False$
(and similarly for ${A} \land \bar{B}$)
we run through all the pairs of $True$ leaves, one from each tree,
and check if they are compatible (that is there is no $x$ on one of the paths and $\bar x$ on the other). It is equivalent to $False$ iff we find no compatible pair.
This can be done in log space.

So the problem is at least in L.

EDIT: I have some ideas to prove this to be L-complete, under $AC_0$ reduction probably. But I'd need to check the details and it won't fit in here. I'll post a link to the article I am writing if it all works out!

EDIT2: there it is, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

So the problem is indeed Logspace-complete.


Different definitions of grammar complexity

I think that among the most obvious measures are variable and production complexity. These are structural measures, in the sense there is for each k an infinitude of languages having measure k. And they are independent from each other, unless you consider the numbers for grammars in Chomsky normal form.
Another obvious measure is the total size of the grammar. Here you can compare required size in various normal forms, for example. It's also the thing to look at for grammar  based compression. This measure is less a structural measure, but more a descriptional complexity measure. The textbook by M. Harrison on formal language theory (1978) has some coverage in chapter 4 of the early works on this by J. Gruska and others.
Here are a few pointers to the recent literature. I'm not aware of recent surveys, but maybe look at the cited references.
Jürgen Dassow, Ronny Harbich:
Production Complexity of Some Operations on Context-Free Languages. DCFS 2012: 141-154
Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid: On the Complexity of Grammar-Based Compression over Fixed Alphabets. ICALP 2016: 122:1-122:14
Stefan Hetzl, Simon Wolfsteiner:
On the cover complexity of finite languages. Theor. Comput. Sci. 798: 109-125 (2019)
EDIT (05/04/2021): An observation regarding the relation between number of variables and productions in context-free grammars: the left-hand side of every production from $P$ is a variable from $V$, so $|P|\ge |V|$, provided we assume (w.l.o.g.) that every variable is used in at least one production. Every finite language can be generated by a context-free grammar with just one variable (the start symbol), and with one production for each word – of which there are finitely many. On the other hand, there are finite languages for which the minimum number of productions required by any context-free grammar equals the number of words in the language (by work of Bucher, Maurer, Culik, Wotschke). This shows that the "production hierarchy" is more fine-grained than the "variable hierarchy".


For the case of Schaefer's dichotomy theorem, informally, the universal expressive power of Boolean CNF formulas built from non-Schaefer logical relations is behind the dichotomy. Every logical relation is definable by such formula using existential quantifier. This is stated formally in Schaefer's expressibility theorem (Theorem 2.5).


Deterministic dynamic dictionary on a small universe

If randomness is allowed, you can get space $B + o(B)$ and time $O(1)$ (worst-case, with high probability), where $B$ is $\lg {U \choose n}$, which is the lower bound on how much space you need using any representation: Arbitman et al., " Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation".

For deterministic dictionaries, the best known bounds are discussed in Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"


Are there any heuristics that works solely on graphs?

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known example in recent research is called ALT (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/

There has since been much further research on expanding and improving upon the heuristics used by the ALT technique. A simple search on this topic should turn up plenty of more-recent and relevant results (I tried posting links to some of them here, but the system has unfortunately limited the number of links I can provide in my response).

Aside from ALT, there has also been subsequent research on alternative techniques for constructing other similar heuristics purely from the graph representation (which is directly compared to ALT as well): http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5372/5180


Linear diophantine equation in non-negative integers

I am not an expert on this at all, but I would like to get a constructive discussion started. Here is an attempt, based on the math.stackexchange.com question Count the number of positive solutions for a linear diophantine equation. The stuff is related to Erhart polynomials, which I know nothing about, and I think also to @SashoNikolov's comments above.

Define $N(a_1, a_2, \ldots, a_n; b)$ to be the number of non-negative solutions of the Diophantine equation
$$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$$
where coefficients $a_i$ are positive and $b$ is non-negative. If I am getting my recursions right, then we have
$$N(a_1; b) = \begin{cases}
1 & \text{if $a_1 \mid b$} \\\\
0 & \text{otherwise}
\end{cases}$$
and
$$N(a_1, \ldots, a_{n+1}; b) =
\sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k)
$$
Now, the sum is a bit long (measured in terms of the length of the input), but we might hope to find a better way of computing it than to actually run through all the $k$'s. We know it's going to be a polynomial in $b$, but I do not see how to compute the polynomial fast enough.


Here is a well argued article by David Donoho and Jonathan Buckheit that I read in grad school which touches on exactly this topic from the point of view of wavelet researchers:

"WaveLab and Reproducible Research"

Their idea was even more ambitious, to provide code for reproducing all the figures in their papers in a convenient Matlab package.

I really like their idea but I think the issues are obvious.

(1) It is extra work (cleaning up the code, making at least a rudimentary user interface, writing some documentation, providing some support when people inevitably run into problems)

(2) It is not really required/expected by most conferences/reviewers

But I can't help but feel that the CS research community would benefit if there was an expectation of making the code and data used in any publication publicly available in a usable format. I admit that I haven't done so myself even when the amount of work involved would have been manageable. I think it is just hard to make yourself put in the extra effort when there is no external push.


Is it NP-hard to play international draughts correctly?

OK, here's the reduction. Turns out you don't need planarity after all. Also, for "find a legal move", I take the decision question as "is move X legal?".

First, let's work instead with a game where pieces move orthogonally instead of diagonally. This game is equivalent (just look at the draughts board rotated 45 degrees) except for edge properties, which we will not use. We use two gadgets: merge / split and crossover. See http://www.hearn.to/draughts.pdf. We assume there is a single White king on the board to move. (No other piece will be able to capture any significant number of pieces.) It will move through the indicated corridors, capturing black pieces along the way.

First, merge: if the king enters on any of the N paths A (via capturing a black piece, not shown), it can exit at B. Likewise, if we reverse the gadget and it enters at B, capturing the shown piece, it can exit along any path A (again, capturing an external black piece). This is a single-use gadget (because the exit black piece can be captured only once).

Second, crossover. If the king enters via A (C), it can exit at B (D). It can't stop in the middle and change routes, because that would be a non-capturing move segment.

Now, given a directed graph, construct a corresponding game configuration as follows. For each vertex, construct a merge which feeds into a split. Route the split outputs to the merge inputs of the vertex gadgets (merge + split) corresponding to the vertices the exiting edges connect to, using crossovers as necessary. Start the king on an extra input to any vertex (with a black piece to capture to let it enter the vertex).

Finally, equalize all of the "edge lengths" by adding extra black pieces along the output / input pathways as needed. If there are V vertices, and k black pieces along each edge, then the king can capture 2V + kV + 1 pieces if and only if there  is a Hamiltonian circuit of the corresponding graph. If the king has an alternative move available, capturing a simple chain of 2V + kV pieces, then determining whether that alternative move is legal is NP-complete.


What is necessary and/or sufficient requirement for a subring of a field to be computable?

The question of how to find computable substructures of algebraic structures was studied by Jens Blanck and myself in the paper "Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions". There we give general conditions on what it means for a substructure of an algebraic structure to be computable. Let me give a summary, but I recommend reading the paper for thorough understanding.

We work with respect to an arbitrary model of computation, such as Turing machines, Type II Turing machines, topological models, $\lambda$-calculus, a programming language, etc. The formalism which encompasses all of these is realizability theory.

There is an embedding $\nabla : \mathsf{Set} \to \mathsf{Asm}$ from the category of sets to the category of assemblies (over some partial combinatory algebra, see our paper). The category of assemblies can be thought of as a category of sets equipped with a computability structure. The embedding $\nabla$ maps sets to sets equipped with trivial computability structure, namely, if $S$ is a set then $\nabla S$ is the set $S$ in which every $x \in S$ is realized by every realizer (if you've never heard of realizability before, think of Gödel encodings of objects). Intuitively this says that when we look at a realizer we have absolutely no idea which element it represents.

Assume a fixed signature $\Sigma$ for an algebraic structure (such as one of a ring) and let $\mathcal{A}$ be a $\Sigma$-algebra in the category of sets, i.e., what people normally think of when they say $\Sigma$-algebra. Because $\nabla$ preserves products, it maps $\mathcal{A}$ to a $\Sigma$-algebra $\nabla \mathcal{A}$ in $\mathsf{Asm}$. Now, a computable $\Sigma$-subalgebra of $\mathcal{A}$ is just a subalgebra of $\nabla \mathcal{A}$ in the category $\mathsf{Asm}$.

When we unravel what this means in terms of realizers we see that it is the expected thing: for $\mathcal{B}$ to be a computable subalgebra of $\mathcal{A}$ it has to be a subalgebra in the usual sense (of course), you have to give a realizability relation for the carrier of $\mathcal{B}$ which explains how the elements of carrier are realized, and all the operations on $\mathcal{B}$ must be realized (computable) with respect to the chosen realizability relation on the carrier.

It occurs to me that maybe you are asking the following question: given a subalgebra $\mathcal{B}$ of an algebra $\mathcal{A}$ is there some computable structure on $\mathcal{B}$, i.e., is there some way of making all the operations on $\mathcal{B}$ computable? First note that $\mathcal{A}$ does not play a role here. Second, if the only requirement is that the operations on $\mathcal{B}$ be computable, then the answer is always "yes, just use the trivial computability structure $\nabla \mathcal{B}$". That is, represent every element of $\mathcal{B}$ with any realizer you want, say 42, and then all operations are implemented by functions that always return 42. In order to avoid such a silly answer you have to impose further conditions -- and that's what our paper is about.


One-way randomized communication complexity of approximate Hamming distance

Here is a simple protocol for Hamming distance that uses $O(\varepsilon^{-2} \log n)$ bits. The protocol is essentially the Alon, Matias, Szegedy second moment sketch. Or you can think of it as a version of the Johnson-Lindenstrauss lemma.

I am assuming that Alice has a vector $x \in \{0,1\}^n$ and Bob has a vector $y \in \{0,1\}^n$, and they share randomness. Notice that the Hamming distance between $x$ and $y$ is equal to $\|x-y\|_2^2$. Using the shared randomness Alice and Bob sample a $\varepsilon^{-2} \times n$ matrix $\Sigma$ of IID unbiased $\pm 1$ random variables. The Alice sends $\Sigma x$ and Bob outputs $\varepsilon^{-2}\|\Sigma (x - y)\|_2^2$.

For the analysis notice that $\mathbb{E}[\varepsilon^{-2}\|\Sigma (x - y)\|_2^2] = \|x-y\|_2^2$, so the output is an unbiased estimator of $\|x-y\|_2^2$. Because the rows of $\Sigma$ are IID,

$$
\mathrm{Var}[\varepsilon^{-2}\|\Sigma(x-y)\|_2^2] = \varepsilon^{-2} \mathrm{Var}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right],
$$

where $\sigma_1, \ldots, \sigma_n$ are IID unbiased $\pm 1$ random variables. Then, by Khintchine's inequality, for a constant C

$$
\begin{align*}
\mathrm{Var}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right] &\leq \mathbb{E}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^4\right] \\
&\leq C \mathbb{E}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right]^2 \\
&= C\|x-y\|_2^4.
\end{align*}
$$

So, by Chebyshev, with constant probability the output of the protocol is a $1+O(\varepsilon)$ approximation to $\|x-y\|_2^2$, which is equal to the Hamming distance.


Reconstruction Conjecture and Partial 2-trees

I believe that it has not been shown that bidegreed graphs are reconstructible. Bidegreed graphs are edge-reconstructible. Kocay did some work on reconstruction of bidegreed graphs, but did not reach a comprehensive result that I have been able to find. The notion that it has been proven that bidegreed graphs are reconstructible seems to be a bit of misinformation circulating on the web.


If there is an optimal pps (pps = propositional proof system, an optimal pps is a pps that can p-simulate any other proof system) then the pps EF (Extended Frege) strengthened with propositional axioms stating the soundness of the optimal propositional proof system will be optimal. More generally EF + Soundness of pps P can p-simulate P for any P. So EF has a kind of generality that you don't need to change the logic or the underlying pps structure, but just add propositional axioms to it to get any arbitrary strong pps.

In particular, if there is a super pps (a pps which has polynomial size proofs for all tautologies) then EF + Soundness of that pps will be a super pps. Note that $NP = coNP$ is equivalent to the existence of a super pps.

Soundness of a pps P is a (sequence of) propositional formulas stating that if $\pi$ is a proof in P for $\varphi$, then $\varphi$ is true.

In summery, there is no need to go outside propositional logic.

ps: Note that all pps are effective by definition, a pps has a polynomial time verifier, and therefore its theorems are computably enumerable. $NP=coNP$ means that there is a super pps for the propositional formulas. Being propositional is important here. We know that there is no such thing for stronger logics but their nonexistence does not seem to have any effect on $NP$ vs $coNP$.


What hierarchies and/or hierarchy theorems do you know?

The Fourier Hierarchy as defined in "Yaoyun Shi, Quantum and classical tradeoffs."

From the complexity zoo:

  $\mathsf{FH}_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with $k$ levels of Hadamard gates and all other gates preserving the computational basis.

  $\mathsf{FH}_0 = \mathsf{P}$
  $\mathsf{FH}_1 = \mathsf{BPP}$
  $\mathsf{FH}_2$ contains factoring because of Kitaev's phase estimation algorithm.

  It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, $\mathsf{FH}_k$ is strictly contained in $\mathsf{FH}_{k+1}$).


Language/type system closest to Haskell without general recursion

The language closest to Haskell without general recursion is Haskell without general recursion, with suitable fold operations taken as primitive.

Haskell's datatypes have non-wellfounded values thanks to Haskell's lazy evaluation strategy. Once we remove general recursion from Haskell, the difference between lazy and eager evaluation does not matter anymore, and the datatypes become inductive in the sense that only well-founded values may be expressed (because every program is terminating, and folding over an non-wellfounded value woudl give a non-terminating program). So, you can just keep Haskell without general recursion, it's got parametric polymorphism, and the inductive types will work as expected.


The use of crossovers in Genetic Algorithm

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions.  If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then crossover will increase performance of GAs. For example, if there is a function f(x,y)=g(x)+h(y), and x and y are encoded consequently in the genome, and e.g. g(x) has larger influence, then the part of genome that stands for x will be optimized in the first place, and it will become nearly the same for the whole population thanks to crossover. After this, h(y) term will be optimized. That is, crossover helps to loosely decompose the task into subtasks without prior knowledge (but dependent on the encoding scheme), if it is possible (otherwise it will yield no benefit, or even will make search less efficient). This is actually the main additional metaheuristic of GAs in comparison with other metaheuristic optimization methods.

Double-point crossover (or other more “clutter” types of crossover) can be more beneficial, if the most crucial parts of solutions are encoded in the middle of the genome or if they are placed in separate locations. The simplest example is the function f(x,y,z)=h(x,z)+r(y)+g(z), where h(x,z) has the highest influence, and genes encode the string xyz. Single-point crossover will prefer to take x from one parent, and z from another parent. However, (x,z) determine the solution quality together. If one individual will occasionally have optimal components (x*,z*), they will not appear simultaneously in its children after single-point crossover, so it will be more difficult for these parts of the genome to stabilize.


NP-hardness proof: looking for some good restricted np-hard problems

I don't know if there is a machinery way to do this, but my little personal experience works as follows.

I try to provide a polynomial time algorithm for a problem. In those tries usually I can see there are some restricted versions of problem which are polynomial time solvable. I also will understand what part of my algorithm was handwaving for original problem. I can compare this two cases (difference between restricted versions and the general one also the part of an algorithm which was hard to improve). By comparing those two cases usually it's possible to guess how does the problem bottleneck looks like. So we can find a related hard problem. Usually providing an algorithm for a problem is hard job, and needs good knowledge about a problem. After we get this knowledge about the problem we can have many different ideas to tackle problem in different scenarios (not just hardness results).

P.S: If your proof relays on a particular problem, I think it's because that problem is very close to your work, so don't blame yourself.


Finding optimal parallelization from general weighted undirected graph

This is very similar to overlaps of gene sequence in genome assembly. Chapter 4 of Ananth's thesis.

In parallel you search for promising pairs and maintain a distributed union find data structure. See Tarjan and Vishkin for their hook and shortcut algorithm to collapse the connected components.

Also, you can try recent DeBrujin graph methods on 64 bit row chunks of pixels. I think this will give you the best results. To help with quantization problems I would first reduce dimension of the pixels to 16 or 8 bit black/white. You then apply a parallel sort the 64 bit chunks, and then use them to infer edges between images.


Complexity of testing for a value versus computing a function

Makowski's "Algorithmic uses of the Feferman–Vaught Theorem" is possibly relevant. He defines polynomials by summing over MSOL-definable structures on graphs and shows that they are tractable to evaluate when graphs are tree-width bounded.

This doesn't say much about difference in complexity of testing/evaluation beyond being FPT. Testing for a value means asking if there exists a setting of variables such that given MSO2 formula on given graph evaluates to true, whereas evaluating involves enumerating over satisfying assignments of MSO2 formula. This seems to be related to the question of how complexity of counting SAT relates to complexity of SAT.

Edit 10/29
Another useful concept might be to look into Uniform Difficult Point Property. Apparently polynomials with this property are either easy to evaluate in all points, or hard to evaluate almost at every point. Makowski gives some references on slides 46-52 -- http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf


reset and shift only one level deep (delimited continuations)?

I think you might be misreading those rewrite rules.

A call to shift will find to the nearest enclosing call to reset, regardless of how deeply nested it is. Other examples in the tutorial you linked to should confirm that.

The Racket Reference has a slightly different set of rewrite rules for reset/shift, that might make things a little clearer.

(reset val) => val

(reset E[(shift k expr)]) =>
  (reset ((lambda (k) expr)
          (lambda (v) (reset E[v]))))

Using your example:

(reset (+ 1 (* 2 (shift k (k 42)))))
=>
(reset ((lambda (k) (k 42))
          (lambda (v) (reset (+ 1 (* 2 v))))))
=>
(reset (reset (+ 1 (* 2 42))))
=> 85

I don't speak Mathematica, but it might be possible to transcribe the rewrite rules from the Racket Reference to get what you want.


Lower bounds on simple hash table operations?

The best known lower bounds are discussed in Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems", and none preclude deterministic amortized constant-time operations.


Bigger picture behind the choice of matrices in the Strassen algorithm

De Groote (On Varieties of Optimal Algorithms for the Computation of Bilinear Mappings. II. Optimal Algorithms for 2x2-Matrix Multiplication. Theor. Comput. Sci. 7: 127-148, 1978) proves that there is only one algorithm to multiply $2 \times 2$-matrices with 7 multiplications up to equivalence. This might be a unique feature of $2 \times 2$-matrix multiplication. (Note: You will find different variants of Strassen's algorithm in the literature. They are all equivalent with the right notion of equivalence.)

If you now start to prove a lower bound for $2 \times 2$-matrix multiplication - see the book by Bürgisser, Clausen, and Shokrollahi how to do that - then Strassen's algorithm or some variant shows up quite naturally. You will find out a lot of identities that determine how the products look like. Then you can finish by some guessing.
(De Groote's proof shows that even guessing is not necessary.)

Schönhage once told me that Strassen once told him that he found his algorithm in this way, by trying to prove a lower bound.


Problems with complexity between P and NP that have  NP-complete generalizations

Most famously: Graph Isomorphism, and Dominating Set on Tournaments.

Generalizations are natural.


Counting occurences of 'a' in a book faster than O(n)?

You could try sampling. The assumption that the proportion of a's on any given page is roughly the same as on any other one (and that all pages have roughly the same amount of text) seems reasonable. If $n$ is the total number of pages, you could pick, say $k=n^{4/5}$ random pages, count their average number of characters and the proportion of a's, and scale up to $n$. Your runtime would be $O(n^{4/5})$, and with high probability, your estimate for the number of a's would deviate from the true count by $\tilde O(n^{3/5})$.

You can play with the exponents to get other accuracy-runtime tradeoffs (e.g., in $O(n)$ time you can achieve whp a deviation of $\tilde O(\sqrt n)$).

As pointed out in the comments, an exact count requires $\Omega(n)$ runtime. If the interviewer absolutely insisted on a sublinear runtime, I would suggest sampling.


I don't know what the density of common P-complete problems is, but here is a padding argument that shows how to lower any density below $1/n$:

Take your favorite P-complete language $L_n \subseteq \{0,1\}^n$. This language has some density $d(n) \in \omega(1/n)$. Now define $L'_{n + m} = \{x0^m | x \in L_n\}$. In general, $m$ will be some function of $n$, so this might not define $L'$ for all sizes, since we are worried only about the upper density, just make $L'_k = \emptyset$ if $k \neq n + m$. What is the upper density of $L'$? Well, we have

\[
d'(n + m) = \frac{|L'_{n + m}|}{2^{n + m}} = \frac{|L_n|}{2^{n + m}} \leq \frac{d(n)}{2^m}
\]

Now lets use LOG-reductions to build a machine $M$ for $L$ using a machine $M'$ for $L'$. Well, if you are given an input $x$ then simply copy it one bit at a time to the query tape (also use a counter to count what $n$ is), then use a second counter to count upto $m(n)$, adding one every time you add a zero to the query tape (to have log space, we need $m(n) \in poly(n)$ and easily computable). Then query and return the output as your answer.

If we want to be sure we are smaller than $1/n$ then just pick $m(n) = n$, and then we will have $d'(2n) \leq d(n)/2^n \in O(1/n)$.


I haven't thought it carefully, but I think You can use dynamic programming. If we have n cards in first deck and m cards in second deck, then there is n*m possible states of stack.

Best_Move(i,j)
    return Max(Stack1[i]-Best_Move(i-1,j),Stack2[j]-Best_Move(i,j-1))

You just have to remember all partial results, so they won't be calculated twice. This should give You the bes strategy in O(n*m).


Separation result for proper learning under the uniform vs. adversarial distributions?

Here is an example that may not be exactly what you want, but is still emblematic of a general class of problems. In this instance, the hardness is only for agnostic learning, and only for "proper" learning in the sense that the representation class is restricted, and the easyness over the uniform distribution is for trivial reasons.

Width-k conjunctions are NP hard to learn using halfspaces (and in particular using conjunctions) over arbitrary distributions, even for $k > \log(n)$: http://www.cs.cmu.edu/~yiwu/paper/mono.pdf

On the other hand, for $k \gg \log n$, width $k$ conjunctions are trivial to learn over the uniform distribution over examples using conjunctions, since every width-k conjunction will label a $1-1/2^k$ fraction of examples "0", so every width-k conjunction is a good hypothesis.

I would guess that there are similar examples that hold more broadly. Notice that easyness of learning over the uniform distribution holds for any "unbalanced" function, for the same trivial reason. Take a class of functions that is hard to learn even non-agnostically (poly-sized circuits, say). I would think that you could modify the lower-bound proof to hold even if you modify the circuits to be unbalanced: to evaluate to $1$ only on an $\epsilon$ fraction of random inputs. Meanwhile the hard distribution could still be one in which $\Pr[A(x) = 1] = 1/2$.


Question about non-private databases and $1^n$

As Huck Bennett pointed out, $1^n$ is the "security parameter", which is a cryptographer's way of expressing that the input has length n.  They express the input this way to make it easier to prove theorems about time complexity, resource requirements, etc, that are all supposed to be expressed in terms of the size of the input, instead of its value.


Are there any 'graphical' algebras that can describe the 'shape' of graphs?

Many people have tried to find an algebraic language to describe the shape of a graph.  This question is essentially the one that motivates structural graph theory.

At the heart of this area of discrete mathematics is the study of graph decompositions.  Some of the people working in this area are Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, and their collaborators, although this list is biased by my own research interests.

Particular kinds of graph decompositions have led to some of the most general results in graph theory.  For instance, one of the main technical tools developed for the graph minors project, which led to the Robertson-Seymour theorem, is the graph structure theorem.  This shows that classes of graphs that exclude some minor can be built up from simpler graphs.

In the proof of the Strong Perfect Graph theorem a somewhat different decomposition was used.  The key result is: For every Berge graph $G$, either $G$ is basic, or one of $G, \overline{G}$ admits a proper 2-join, or $G$ admits a balanced skew partition.

The decompositions studied to date are in some sense non-algebraic.  My personal intuition is that there are indications that there is no "nice" system such as the one you seek.  Making this glib statement precise would likely require a nontrivial enterprise in finite model theory, but I suspect it could also lead to interesting new results in graph theory (whether successful or not).


Rademacher complexity and lowerbounds in learning theory

First, let's distinguish between empirical end expected Rademacher complexities. The former is defined for a function class $F$ and sequence of points $X_1,\ldots, X_n$, by
$$ \hat R_n(F;X_1,\ldots,X_n) = E_\sigma \sup_{f\in F}\frac1n\sum_{i=1}^n
\sigma_i f(X_i).$$
The latter is defined for a function class $F$ and distribution $D$, by
$$ R_n(F;D) = E_{(X_1,\ldots,X_n)\sim D^n}[\hat R_n(F;X_1,\ldots,X_n)].
$$

It's known that for any function class with VC-dimension $d$, we have
$\hat R_n(F;X)=O(\sqrt{d/n})$ (for any sequence $X$) -- and hence the bound carries over to $R_n(F;D)$ for all distributions $D$.

It's also known that the Rademacher complexity upper bounds the generalization error for agnostic PAC (plus a confidence term decaying as $\sqrt{\log(1/\delta)/n}$). On the other hand there exist adversarial distributions that force any learner to have a generalization error of $\Omega(\sqrt{d/n})$;
see, e.g., my course notes
https://www.cs.bgu.ac.il/~asml162/Class_Material
.

From these considerations alone, we can conclude that for any function class with VC-dimension $d$, there is a distribution for which $R_n(F;D)=\Omega(\sqrt{d/n})$.

Edit: I also like to give the following exercise. Let $F$ be the set of all $\{\pm1\}$-valued functions on the integers. Prove that there exists a sequence of distributions $D_n$ such that $\lim_{n\to\infty}R_n(F;D_n)=1$.


Implementation of Wilf-Zeilberger and related methods

It is implemented in Maxima (http://maxima.sourceforge.net/docs/manual/de/maxima_77.html#SEC400), to which Sage has interface. A few dozens of examples (ranging from very easy to very difficult) I tested today work in the exact same way as in Maple.


Simple Constructions of Special Graph Families

This is a family of expander graphs: let $p$ be a prime, let the vertex set be $\{ 0,\ldots,p-1\}$, connect vertex $x$ to $x+ 1 \bmod p$, to $x-1 \bmod p$ and to $x^{-1} \bmod p$. Each such graph is a cycle, plus a matching over $p-3$ vertices. (The multiplicative inverse is undefined for $0$, and is the element itself for $p-1$ and $1$.)

This is a picture of what it looks like for $p=59$

There is no known elementary proof that this a family of expanders, but the construction is very simple.


Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT

The conjunction of the first two clauses, $(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ is equisatisfiable to the original clause, as can be easily checked (any valuation satisfying one of the $\sigma_i$ also satisfies one of the two new clauses, and can be extended to $u_1$ as needed to satisfy the other; any valuation satisfying both new clauses has to satisfy some $\sigma_i$, since it cannot satisfy both $u_1$ and $\bar{u}_1$.)

The additional clauses ensure that $u_1$ is in fact equivalent to $\sigma_3\cup\ldots\cup\sigma_m$, but as far as I can see, Karp does not actually use this. He credits Cook's 1971 paper for this particular reduction, but the version found there (actually for DNF tautologies rather than CNF satisfiability) does not feature these extra constraints.


Complexity class separations without hierarchy theorems

I'd love to be shown wrong, but I don't think there are currently any uniform lower bounds that aren't ultimately based on one of the hierarchy theorems. Our current understanding of how to take advantage of uniformity is really quite limited in that sense.

On the other hand, there are many uniform lower bounds that don't follow directly from hierarchy theorems, but use a hierarchy theorem in combination with other clever tricks, techniques, and results, for example:

$\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ [Hopcroft-Paul-Valiant]. They prove that $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ (the non-diagonalization part of their proof), and then use the fact that $\mathsf{CSL} = \mathsf{NSPACE}(n)$ in combination with the space hierarchy. Their result + the space hierarchy also implies $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$.
Time-space trade-offs for Satisfiability (see, e.g. the introductions of Buss-Williams and references therein)
$\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [Paul-Pippinger-Szemeredi-Trotter]. Uses a nontrivial simulation of any deterministic super-linear-time machine by a faster four-alternation machine, in combination with the deterministic time hierarchy.
Uniform lower bounds on the permanant [Allender, Allender-Gore, Koiran-Perifel]
$\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$ [Williams] (although technically this is a nonuniform lower bound, it uses a bunch of clever ideas in combination with the nondeterministic time hierarchy)


For efficient algorithm on "minimization" knapsack problem

There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search.

I think you can use the same rounding approach as the one for knapsack in order to get a PTAS for this problem. These notes notes should help you do it.


Parametricity and projective eliminations for dependent records

I just talked to Dan Doel and he explained that his reference was in fact one Neel Krishnaswami. He saw a comment on n-cafe by you that one could do strong induction using parametricity, so he went ahead and did it as an exercise, not realizing that doing it for sigma was apparently a novel result.

The precise quote: "My reference was him. I thought he said it was possible, so I did it."


Hardness of computing circles with max number of lattice points

It's probablyly much easier than factoring $n$, because you're looking for smooth numbers smaller than $n$ rather than for difficult factorizations; a smooth number is one that has many small factors, and these are the distances which will give you the most points on the lattice. If the center has to be at $(0,0)$, then you calculate how many lattice points are at distance $5^{a/2}13^{b/2}17^{c/2}29^{d/2}37^{e/2} \ldots$ using the formula for the number of ways of expressing a number as the sum of two squares. You can do the same thing for the circle centered at $(0,\frac{1}{2})$ or $(\frac{1}{2},\frac{1}{2})$. You can then do an optimization to find the largest value where this distance is less than $n/2$. I expect that this will be possible in polynomial time using dynamic programming.

I cannot imagine that the largest value would not correspond to the center having coordinates other than $0$ or $\frac{1}{2}$, but this should be proved.


Why is the circuit class AC0 unavoidable?

The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ if and only if it is definable in first-order logic in the language of word structures.
See e.g. Immerman's book for more details.

$\mathbf{AC}^0$ also arises naturally when studying theories of bounded arithmetic. The simplest of these theories $\mathbf{V}_0$ corresponds precisely to $\mathbf{AC}^0$ in that the functions and relations definable in the theory are exactly those in uniform $\mathbf{AC}^0$. See the book of Cook and Nguyen for more details.


Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

No. It is possible that L=P and that P != NP which implies that NL != NP since NL is contained in P.


What is the importance of linear languages?

The first obvious reason why linear languages were introduced is that mathematicians can hardly resist, facing a lateralized notion, to consider the symmetrical version as well. For instance, in algebra, you deal with left or right inverses, but also with inverses. In ring theory, you consider left or right ideals, but also ideals, etc.

Since left linear and right linear grammars define regular languages, studying linear grammars just came as a natural question to study in the early days of formal language theory. Furthermore, as you mentioned in your question, linear languages appeared to be a natural intermediate class between regular and context-free languages.

A nice characterization of linear languages was given by Arnold L. Rosenberg: A machine realization of the linear context-free languages, Information and Control 10 (1967) 175–188. The formulation below is Proposition V.6.5 in J. Berstel's book, Transduction and Context-free Languages, Teubner 1979.

A language $L$ of $A^*$ is linear if and only if there exists a rational subset $R$ of $A^* \times A^*$ such that
$$
L = \{ u\tilde v \mid (u, v) \in R \}
$$
where $\tilde v$ denotes the reversal of $v$. This result shows that, in a very loose sense, linear languages are a generalization of the language of palindromes.


Using Pearson Correlation Coefficient in computing user/item similarity

Pearson's correlation is undefined when the variance of one of the random variables is 0, I would look for a more credible source to read from.


No, this is not new; range searching with multilevel B-trees is completely standard.  See, for example, the following surveys:

Lars Arge.
External memory data structures.  Handbook of Massive Data Sets (James Abello, Panos M. Pardalos, and Mauricio G. C. Resende, eds.), 313-357.  Kluwer Academic Publishers, 2002.  See especially sections 5 and 6.
Jeffrey Scott Vitter.  Algorithms and data structures for external memory.
Foundations and Trends in Theoretical Computer Science 2(4): 305–474, 2008.
See especially section 12.


A monotone 1-in-2 clause demands that the two variables have different values. Thus, you can model the problem as a graph problem, with one vertex per variable which is to be colored black or white, and an edge for a clause indicating the colors need to be different. Thus, the question is to make the graph bipartite by deleting a minimum number of edges. This is the MaxCut or Edge Bipartization problem. It is NP-hard.

For Edge Bipartization, there is an algorithm that runs fast when few edges need to be deleted. I wrote an implementation for a slightly more general problem described here (source code).


Is there a rule-based implementation of weighted abduction other than the PTTP?

I'm not aware of any alternatives but some first-order abductive problems can be recast as evaluation of stable models.


Hardness of quantum circuit equivalence?

The problem isn't clearly in coQMA. If $U_1$ and $U_2$ are different, and you're given a state on which they act differently, it is not necessary that a polynomial-time quantum computer can check that the output states are different.

In fact, it is easy to show that if these two quantum states are different, but exponentially close in trace norm, then no polynomial-time quantum algorithm can distinguish the two. This is analogous to how no polynomial-time classical algorithm can distinguish two probability distributions that are exponentially close.

On the other hand, if we're promised that $U_1$ and $U_2$ are not too close when they are not equal, then the problem is in coQMA.

The complexity of either variant is known. In the exact case, this problem is complete for coNQP, which is the same as the class $C_=P$.

  Yu Tanaka, EXACT NON-IDENTITY CHECK IS NQP-COMPLETE. International Journal of Quantum Information 08:05, 807-819 http://arxiv.org/abs/0903.0675.

In the other case where we're promised that they're not too close when unequal, the problem is indeed coQMA-complete.

  D. Janzing, P. Wocjan, and T. Beth, Non-identity check is QMA-complete, International Journal
  of Quantum Information, 3(3), pp. 463–473, 2005; http://www.worldscientific.com/doi/abs/10.1142/S0219749905001067

(Note that the problem is equivalent to checking if $U_1U^\dagger_2$ is the identity matrix, which is called the identity check problem.)


research papers for undergraduate students

It's not true that all science papers have to be very complicated and rough for undergraduates. When I was still really fresh in CS I found a lot of science papers that helped me understand many problems. Try to look for something interesting for you on http://paperity.org/. I found many interesting journals and papers. I think this is currently the most useful aggregator on web


Addition and subtraction of binary numbers are in $\mathsf{AC^0}$.

For any constant number $c$,
$x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$):
$$x \bmod c = x -
(\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$

It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$
which is not a power of $2$.
Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$
which is not a power of $2$.

As noted by Emil in the comments there is an easy reduction for odd prime $c$
from $\mathit{MOD}_c$ (that is, $\sum_ix_i\bmod c$ with $x_i\in\{0,1\}$) to
$x\bmod c$ with binary input:
we use only input bits which are multiples of $p-1$ and use FLT ($2^{(p-1)i} \bmod p = 1$).


Parameterized complexity from P to NP-hard and back again

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

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

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


This question is tricky as the answer (as far as I know) is still "don't know".

To add some weight to this, Flum & Grohe [1] give as open problems (p. 164):

  Is the $\mathrm{W}$-hierarchy strict under the assumption $\mathrm{FPT} \neq \mathrm{W[P]}$?
  For $t \geq 1$, does the equality $\mathrm{W}[t] = \mathrm{W}[t + 1]$ imply $\mathrm{W}[t] = \mathrm{W}[t + 2]$?

Moreover, in Downey and Fellow's recent monograph [2] the strongest (outright) statement they make is (p. 521):

  A more subtle hypothesis is that the $\mathrm{W}$-hierarchy is proper, and, in particular, $\mathrm{W}[1] \neq \mathrm{W}[2]$.

There is no following (or later) statement along the lines "otherwise the $\mathrm{W}$-hierarchy would collapse", or similar.

This is also preceded by:

  A weaker hypothesis might be that for some $t$,
  $$\mathrm{FPT} \neq \mathrm{W}[t]$$

Implying that it is possible that $\mathrm{FPT} = \mathrm{W}[t-1]$ with no other effects on the hierarchy.

References:

J. Flum and M. Grohe, "Parameterized Complexity Theory", Springer, 2006.
R. Downey and M. Fellows, "Fundamentals of Parameterized Complexity Theory", Springer, 2014.


What are multiple rounds of SOS/Lasserre hierarchy?

Yes, that's exactly what it is: optimizing over higher degree pseudoexpectations. The results I think you refer to prove that the hypercontractive inequality holds when $f$ is replaced by a degree $4$ pseudo distribution over $\mathbb{R}^{\{-1,1\}^n}$, which is stronger than the classical theorem (see Lemma 2.10 in Boaz's notes). Specifically, the stronger Lasserre version of the inequality is that for any degree 4 pseudo expectation operator $\tilde{\mathbb{E}}$ over $f:\{-1,1\}^n\to \mathbb{R}$ we have

$$
\tilde{\mathbb{E}} [\|\Pi_d f\|_4^4] \leq 9^d \tilde{\mathbb{E}}[\|\Pi_d f\|_2^4],
$$
where $\Pi_d$ is the linear projection operator onto the span of degree $d$ polynomials on $\{-1, 1\}^n$, and for $g:\{-1, 1\}^n\to \mathbb{R}$, the $L^p$ norm is defined as
$$
\|g\|_p = (\mathbb{E}_{x} g(x)^p)^{1/p} = \left(\frac{1}{2^n}\sum_{x \in \{-1, 1\}^n} g(x)^p\right)^{1/p}.
$$

Equivalently, this means that the inequality can be proved in a weak proof system, the degree $4$ sum of squares proof system, which is the statement given in Lemma 2.10 in Boaz's notes. See the discussion after the statement of the lemma.

(Something that may be confusing is that there are two different classes of polynomials going on here. One is the degree $d$ polynomials on $\{-1, 1\}^n$: you should treat these as just a subspace of $\mathbb{R}^{\{-1,1\}^n}$. The other class of polynomials are the polynomials that arise in the sum of squares proof of the hypercontractive inequality. These are polynomials over the values of $f$.)

The reason this is interesting is that it gives a low degree sum of squares proof that the hypercube graph is a small set expander. Roughly speaking, the fact that the cube is a small set expander is one of the main ingredients of proving that certain instances of the unique games problem are "hard" for some weaker SDPs, for example for constant number of rounds of the Sherali Adams + SDP hierarchy (SA+SDP). I.e. on these instances SA+SDP overestimates how many constraints can be satisfied, and in some sense the reason is that it "does not know" that the hypercube is  a small set expander. (This is only a rough intuition, the hard instances for Sherali Adams are much more complicated than the hypercube.)

By contrast, because there is a low degree sum of squares proof that the hypergraph is a small set expander (again, I am oversimplifying a lot here, and there are many more ingredients you need), these same instances are not hard even for 8 rounds of Lasserre, i.e. the Lasserre SDP does not overestimate how many constraints can be satisfied in these instances. The precise statement of this result is Theorem 6.1. in the paper Hypercontractivity, Sum-of-Squares Proofs, and their Applications. This is interesting, because these were our best candidates for hard instances of unique games. Essentially, we do not know any distribution on unique games instances (or instances of the small set expansion problem) which are not solved with high probability by constant round Lasserre. You may take this as some evidence that unique games may not be hard after all.


Are any of the state of the art Maximum Flow algorithms practical?

I am one of the authors of the paper linked above.

Just want to mention that we used ``state-of-the-art'' to mean algorithms (with publicly available implementations) that perform well on max-flow instances arising in computer vision.

I would also like to add that within that narrow (yet practical) context, often the algorithms that perform well are the ones with poor theoretical guarantees. For instance, ref [5] from our paper (Boykov-Kolmogorov algorithm) is widely used in the computer vision community, but does not have a strongly polytime runtime bound.

Finally, in case anyone is interested, the data from our experiments is available here:
http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

The code will also soon be available too.


What kind of theoretical object corresponds to a C++ concept?

From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to bounded polymorphism or constrained genericity. Concepts themselves correspond to the constraints or bounds placed on a type.

A template is type-level function, parameterised by type that are constrained by a concept to implement a particular interface. When the template is applied to a type satisfying that concept, a new type results.

Templates+concepts are analogous to generics in Java, Scala or Eiffel. They differ from templates in earlier C++ because they allow constraints on the type parameters to be specified and checked, whereas C++ templates did not allow that. The benefit is better static checking that the program after applying the template will be well typed.

A good reference is Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press, Chapter 26: Bounded quantification.


Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover

A lower bound of approximately $\log_2 n$ still follows for arbitrary 3-regular graphs, based simply on the fact that there are at most $3\times 2^i$ different paths of length $i$ from any  given starting vertex and one needs the diameter to be large enough to give a different path to each of the $n$ vertices. The random graph example that you mention (or the example of a complete binary tree with some extra edges thrown in to make it 3-regular) shows that this is tight to within a constant factor, and I'm pretty sure the actual lower bound is really $(1+o(1))\log_2 n$.

As for an upper bound: there exist 3-regular graphs with diameter $\Omega(n)$, for instance the Möbius ladders.

If you want to know the diameters of graphs coming from specific hardness constructions, you'd have to look at the details of those constructions, but my guess is that in most such cases it would be straightforward to tack on either a large binary tree or a large ladder in order to make the diameter as small or as large as you want without much changing the hardness of the instance.


Complexity of solving systems of linear equations with hash preimages

It depends what you mean by "arbitrary cryptographic hash function".  If you care about practical cryptography, I think the most natural interpretation is to model $H$ as a random oracle (i.e., the random oracle model for hash functions).

In this setting, the problem is hard.  As a lower bound, it requires exponential running time.

To prove this, let $u=(1,2,4,\dots,2^{n-1})$ and let $A$ be a $n\times n$ matrix of rank $n-1$ such that $\operatorname{Ker} A$ is spanned by $u$.  (Such a matrix exists.)  Let $c=0$.  Then the problem amounts to: find a constant $\alpha \in \mathbb{Z}$ such that $x=\alpha u$ and $H(x_i)=z_i$ for $i=1,\dots,n$.  Treating $H$ as a random oracle, any candidate value of $\alpha$ has a $1/d^n$ chance of meeting all the $H(x_i)=z_i$ requirements, where $d$ is the size of the range of $H$; so you'll need to try about $d^n$ different values of $\alpha$ before finding the first that is satisfactory [*].  The size of all integers is at most $n \log d = \Theta(n)$ bits, so the time to try each is polynomial.  Thus, the total running time is $2^{\Omega(n)}$ for this case.

I don't know what the complexity is.  I suspect that for a random matrix $A$ you might be able to solve this by enumerating solutions to $Ax=c$.  You can enumerate solutions using Hermite normal form.  This equation has either 0 solutions, 1 solution, or infinitely many solutions.  If it has no solutions, you can immediately conclude that your problem has no solutions.  If it has 1 solution, you can find it with Hermite normal form and then test whether it meets your $H(x_i)=z_i$ requirement.  If it has infinitely many solutions, you can use Hermite normal form to sample from the space of all solutions and check for each whether it satisfies all of the constraints.  There are degenerate cases where this approach might be very inefficient or may never terminate. I suspect for a random matrix $A$ it will typically take at most exponential time, but I have no proof of this.

Alternatively, suppose you intended for "arbitrary cryptographic hash function" to mean that $H$ is an arbitrary function from the integers to a finite domain.  I'll assume $H$ is represented as an oracle.

In this case, the problem is undecidable: there is no algorithm that is guaranteed to always terminate and always output the correct answer.

To show this, it suffices to consider the one-dimensional case, $n=1$, where $A=0$, $c=0$, $z=1$.  Then the problem amounts to: find $x \in \mathbb{Z}$ such that $H(x)=1$.  Consider running the algorithm with the hash function $H_0$ defined by $H_0(x)=0$ for all $x$.  Let $m$ be the largest number that is queried to the oracle (i.e., the largest number that we use as input to $H_0$) when the algorithm is run with $H_0$.  Define $H_1$ by $H_0(x) = 0$ if $x\le m$, or $1$ otherwise.  Then the algorithm's behavior on $H_0$ and $H_1$ is identical, so the algorithm is wrong on at least one of those two.

If neither of those capture what you intended by "arbitrary  cryptographic hash function", then you'll need to define your setting more precisely (what are the inputs? how is $H$ modelled?  how is it represented and provided as input to the algorithm? etc.).

Footnote [*]: I over-simplified a little bit: technically, the attacker could potentially gain up to a $2n$ improvement in success probability by using the fact that $H(\alpha u)$ tells you something about $H(2 \alpha u)$.  But this can be accounted for in the proof by treating each query $w$ to $H$ as providing $2n$ guesses at a good $\alpha$, for free (namely, $w/2^{n-1},\dots,w/2,w,2w,\dots,2^{n-1}w$).  In this way, one can adapt the proof to show that you'll need at least about $d^n/(2n)$ queries to $H$ to have a good chance of finding a valid solution, and that is still $2^{\Omega(n)}$.


Collapses under the assumption that $NEXP\subseteq P/Poly$

A whole lot of fun things happen. Most of the ones I know of start with the IKW paper. There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of complexity classes that we know of. There are other sorts of "collapses" though that I think should be pointed out.
Most importantly, I think, is the "universal succinct witness" property (also from the IKW paper). For one, it gives you a tool from which many of the other collapses are straightforward consequences; for another, the recent circuit lower bounds (eg here and here) for $\textsf{NEXP}$ exploit this connection. Briefly, the property says that, for every $\textsf{NEXP}$ language $L$, and any $\textsf{NEXP}$-machine $M$ deciding $L$, every $x \in L$ has a succinctly describable witness according to $M$. Formally, there is a polynomial $p$ depending on $M$ so that for every $x \in L$, there is a circuit $C_x$ of size $p(|x|)$ so that the truth table of $C_x$ is a sequence of nondeterministic choices for $M$ that lead to acceptance on input $x$.
The succinctness of the witnesses comes in handy, because you can straightforwardly rederive a lot of the other collapses from it. For instance, it follows trivially that $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$. For example, suppose $L$ is in $\textsf{NEXP}$ via a $\textsf{NEXP}$-machine $M$. The succinct-witness property says there's a polynomial $p$ so that $M$ has succinct witnesses of size $p$. We can then decide $L$ in $\textsf{EXP}$ by, on input $x$, brute-forcing all the circuits of size at most $p(|x|)$, and checking whether they encode a sequence of choices that lead to $M$ accepting on input $x$. You can combine this with the (previously known via interactive proofs) result that $\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ to conclude $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$.
It's worth emphasizing that we get to pick $M$ and hence the form of the witnesses. For example, you can actually conclude from "$\textsf{NEXP}$ has universal succinct witnesses" that $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$. Here $\textsf{OMA}$ is "oblivious-MA", meaning that there is an honest Merlin which depends only on the input length.
It's easy to see that $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$, so basically this is just giving a normal form for how $\textsf{NEXP}$ languages are computed in $\textsf{P}/\textrm{poly}$ under the assumption that $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$ in the first place.
Here's one way to see the collapse to $\textsf{OMA}$:

For a language $L \in \mathsf{NEXP}$ decided by a machine $M$, construct a $\mathsf{NEXP}$ machine $M'$ as follows. View the $n$-bit input as a number $N$ between $1$ and $2^n$. For every $x$ of length $n$, guess a witness $w_x$ and run $M(x,w_x)$ to verify it. $M'(N)$ accepts if and only if $M$ accepts for at least $N$ values of $x$. The guesses are arranged such that a succinct description of a witness for $M'$ is a circuit $C$ which computes the map $(x,i) \mapsto$ the $i$-th bit of $w_x$. Now suppose that $N$ is precisely the number of strings in $L$ at length $n$. Then succinct witnesses for $M'$ on input $N$ are circuits that simultaneously encode all of $M$'s witnesses for length-$n$ inputs. In particular, if $M'$ has succinct witnesses, then all of $M$'s witnesses can be simultaneously described by the same circuit.
To complete the claim, we'll recall that $\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$. Letting $M$ be the machine which guesses the PCP and then deterministically simulates the verifier, the above paragraph tells us the existence of simultaneously succinctly describable PCPs for every language in $\textsf{NEXP}$. So now to get $\textsf{NEXP} = \textsf{OMA}$, we have Merlin send the succinct description of the PCPs for all inputs of the current input length, which Arthur can check by just plugging in his input and then running the PCP verifier.

[Thanks to Cody Murray for pointing out the trick of using the input to count the number of strings in $L$. Previously I had $M'$ use that if $\mathsf{NEXP}\subseteq\mathsf{P/poly}$ then $\mathsf{NEXP}=\mathsf{EXP}$ to write down the truth table of $L$, but Cody's strategy is more elegant.]
As a final note, while technically implied by $\textsf{NEXP}=\textsf{MA}$, the collapse $\textsf{NEXP}=\textsf{PSPACE}$ has another interesting implication. It's known that $\textsf{PSPACE}$ has a complete language which is both downward self-reducible as well as random self-reducible. Ordinarily, all such languages sit inside $\textsf{PSPACE}$ and so we shouldn't hope to say (unconditionally) that $\textsf{NEXP}$ has such a complete language as long as we hope that $\textsf{NEXP} \ne \textsf{PSPACE}$. However, if $\textsf{NEXP} = \textsf{PSPACE}$, then $\textsf{NEXP}$ does have such complete languages. A similar statement (replacing $\textsf{NEXP}$ by $\textsf{EXP}$) was used by Impagliazzo and Wigderson to conclude a sort of "derandomization dichotomy" for $\textsf{BPP}$ in relation to $\textsf{EXP}$, so it may be useful in discovering other consequences of $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$.


How do models of hypercomputation overcome the Halting Problem?

In the paper On the power of multiplication in random access machines
 it has been proven by Hartmanis and Simon that, if we add unit cost multiplication instruction in a RAM (called MRAM) then for this model P = NP. In addition the languages decided in polynomial time in the MRAM model are exactly the languages in PSPACE.

As stated in the paper, this results shows that multiplication have the same complexity as addition iff P = PSPACE.

A more related result I have heard of, is that if we add a division instruction with infinite precision in a RAM then we can solve undecidable problems. However I could not find the paper that proves this result. If anyone is familiar with it please comment and I will update the answer.


Computational hardness of "real" computer programs

You certainly can write programs which catch bugs -- there is a large and active community of people who write programs to do exactly that. However, what Rice's theorem prevents you from doing is to write bug-catchers which are both sound and complete (i.e., catch all bugs of a certain class with no false positives).

That said, naive restrictions on the model of computation don't actually help you very much in improving the practicality of program analysis. The reason is that you can get programs which do "almost the same thing" by turning while loops

while P do
   C

into for-loops with a big iteration constant:

for i = 0 to BIGNUM do
  if P then
    C
  else
    break

Now this program does not even need the full strength of primitive recursive (since the for-loop can be macro-expanded into a huge nested if-then-else statement), but in most practical cases it will behave just the same as before. Note that it does help decidability in theory -- the program is total, so you can answer questions by running the program and seeing what happens. This is not  what we actually want, which is to get answers faster than running the program -- the artificial termination introduced doesn't actually help program analysis in practice, since bugs occur because of errors in the real program logic, and we haven't touched that at all.

Furthermore, adding abstraction facilities to a programming language can radically worsen the complexity of the analysis problem, while making it easier to verify programs in practice. For example, proving termination of the simply-typed lambda calculus with natural numbers requires induction up to $\epsilon_0$, but by adding type polymorphism you get System F, whose termination proof as strong as the consistency of second-order arithmetic. Yet, in practice programs written in F are much easier to verify, because the modularity properties of second-order quantification make writing structured programs and correctness proofs much easier.


Bit complexity of integer factorization?

Not a full answer, but hopefully a useful partial answer.

First of all, there is an obvious barrier. How do you specify $d$? If we simply wish to find this for any factor $d$ then there are several legitimate values for some of the bits. This means that really from a single bit you can't always tell where you have a trivial factor (say 1 or N) or a non-trivial factor. This means that in general the problem is likely to be as hard as factoring. If for example you there was a factor of hamming weight 2 with the last bit as 1, you would need to obtain all the bits to be sure that it was non-trivial (if for example the first $n-1$ bits you try are all 0 except for the very least significant bit).

However it is possible to obtain relationships between bits in two factors.

This is easy to do for less significant bits, but becomes harder as you move up. If the complexity didn't increase in one direction, it would obviously lead a more efficient algorithm for factoring.

For example, take $N=pq$. Then $p=2p' + p_0$ and $q=2q' + q_0$. where $p_0$ and $q_0$ are single bits. Then $N=4p'q' + 2(p'q_0 + q'p_0) + p_0q_0$, so $N \equiv p_0 q_0 \mbox{ mod }2$. If N is odd, then $p_0 = q_0 = 1$, and so $N=4p'q' + 2(q' + p') + 1$. Now, if instead it was 0, 2 would have been a non-trivial factor, so lets ignore that case, and consider only $p_0 = q_0 = 1$. We can take $p= \sum_{i=0}^n 2^i p_i$ and $q= \sum_{i=0}^n 2^i q_i$.

Then we have $N = \sum_{i,j=0}^n 2^{i+j} p_i q_j$. This implies that $N \equiv \sum_{i=0}^n \sum_{j=0}^{m-i-1} 2^{i+j} p_i q_j \mbox{ mod }2^m$. This then gives you a relationship between the $m$ least significant bits of $p$ and $q$. Since we can also obtain similar relationships for $(m-1) ... 1$ this gives us a set of $m$ constraints that the bits need to satisfy, each containing at most $m$ terms in the sum. Naively, one could consider testing all possible values of $p_{m-1}...p_0$ and $q_{m-1}...q_0$,but in practice it is more efficient to simply find all possible pairs for the $2^1$ constraint, than use only these as the less significant bits when checking which pairs satisfy the $2^2$ constraint and so on up to the $2^m$ constraint. Unfortunately, how effective this is will depend on the number of factors, as well as other things, since if a number has a large number of small factors, there will be a huge number of possible ways of combining these, and so a huge number of legitimate strings for the least significant bits.

For example, if we consider $N = x!$, then we have $\ln{N} \approx x \ln x - x$. So the number of bits in $N$ scales roughly as $x$ times the number of bits in $x$. Now, if we consider how many different possible ways there are to find a factor of $N$ there are, we know that it must be at least $2^{x-1}$, since this is the number of ways of multiplying a subset of ${2 ... x}$, so there are an exponential number of factors. Even if we consider factors less than $\frac{x}{2} \ln x$ bits (less than approx $\sqrt{n}$) we find that there are more than $2^{\frac{x}{2}}$ possibilities, and thus more than $2^{\frac{x}{2}}$ unique bit strings satisfying all constraints up to $2^{\frac{x}{2}\ln x}$. Thus this approach is necessarily exponential in the worst case.

In the worst case to enumerate all such pairs (testing each possible pair) takes time $O(m^2 2^{2m})$.

Hope this is useful.


I guess there are at least 3 questions in your question. I don't have a satisfactory answer to all of them, so this isn't a complete answer. Hopefully there will be more answers that answer all your questions.

The question in the title: Can quantum algorithms with exponential speed-up be rederived using span-programs?

As you noted, the general adversary bound characterizes the quantum query complexity of all decision problems, including promise problems for which we have exponential speedups. So, in principle, there is a span program that solves the Abelian hidden subgroup problem, which is the query problem used in Simon's and Shor's algorithms. But whether there is an explicit span program for this is your next question.

Is there any work re-deriving Simon's or Shor's algorithms in the span-program framework?

I haven't heard of any such results. I don't know of a span program for Simon's problem or any other AHSP.

Is there a way to translate polynomial-method lower-bounds to general adversary lower bounds?

Yes, I believe there is. I can't seem to find the paper that has this result, but I can give you a link to a talk given by Jérémie Roland. In the abstract of the talk, he says the following:

  ... More precisely, we will show that the multiplicative adversary method, a variation of the original adversary method, generalizes not only the generalized adversary method, but also the polynomial method, so that it essentially encompasses all known lower bound methods. Therefore, this provides a constructive approach to cast polynomial lower bounds into the adversary method framework.

Update: The paper is now available online:
Explicit relation between all lower bound techniques for quantum query complexity by Loïck Magnin and Jérémie Roland


The problem seems to be NP-complete. My reduction is from Planar 1-in-3-SAT, just like in their paper. For each variable, take $2k$ vertices. Each of these is covered by two 4-sets and each 4-set covers two consecutive vertices. Thus, we need to take every second of the 4-sets for each variable, this corresponds to TRUE/FALSE. The other two vertices of the 4-sets are from the clauses. (If the number of negated and unnegated occurrences of some variable differs, then convert some of the 4-sets into 2-sets.) Each clause has 4 vertices; one in the center and the other three in a triangle. Any two vertices of the triangle are contained in a 4-set that belongs to its appropriate literal. The central vertex is in three 2-sets, one for each vertex of the triangle. Not sure how clear this was, so I've made a sketch:

https://photos.app.goo.gl/TMc49pfeT6RZA9Vb8

It is easy to see that this hypergraph is indeed planar.
The proof of the reduction is also quite straight-forward.
Let me know if you have any questions.


An answer to your problem tells you whether there exists a clique of size k. So, any such algorithm for your problem must be at least as slow as clique algorithms. See the wikipedia section on FPT and clique for more.


At least two of the literals $x$, $y$, $z$ are satisfied iff at least one literal in each pair $(x,y)$, $(x,z)$, $(y,z)$ is satisfied. Therefore it is a special case of 2SAT, and there is a polynomial-time algorithm for solving it.


Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?

Lets say that we have $s, d$ where $log(s(n))^{d(n) - 1} = o(n)$. Let $d'(n)$ be arbitrary and $s'(n) = 2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}$. Then we have that $log(s(n))^{d(n) - 1} = log(s'(n))^{d'(n) - 1}$. Thus, we have a question, for various interesting ranges of $s, d, s'$, which is not seemingly answered by Boppana:

$SIZE$-$DEPTH(s, d) =_? SIZE$-$DEPTH(2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}, d'(n))$

Thinking about the limit was overcomplicating this clearly and this is easy to see. It shows the size-depth tradeoff I expected, as well, where the new size goes up as the depth goes down, making the circuit "harder to beat" in both directions. I think, speaking of this, that you will be able to show that these classes are incomparable. Does anybody else have any thoughts on the relationship between the two classes and can you prove something about it?


Your construction does not work in general for the value of $k$ given.

Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have

$$
Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right),
$$
for $k \ll d$. Of course, in this case $\|f(y) - f(x)\|_2 = 0$ is a very bad approximation for $\|x - y\|_2 = 1$. So you almost certainly get infinite error.

This is why the Fast J-L Transform of Ailon and Chazelle uses a Walsh matrix rather than a Haar matrix: $WDx$, for $D$ picked as in your setup, is likely to have a lot of non-zero entries. This is related to the Uncertainty Principle. See also this CACM exposition.

More generally, Krahmer and Ward showed that if $M$ is a (possibly random) matrix that satisfies the restricted isometry property for submatrices of size at most $k$ (with sufficiently high probability), and $D$ is picked as above, then $f(x) = MDx$ satisfies the J-L condition for any $x, y$ with probability at least $1 - 2^{-\Omega(k)}$. This is in some sense a tight connection: a random matrix that satisfies the J-L condition for any $x, y$ with probability $1 - 2^{\Omega(k \log (n/k))}$, also satisfies the RIP property for submatrices of size up to $k$.

For more on this subject check out the lecture notes from Jelani Nelson's course. In particular, lecture 17 contains the Krahmer-Ward theorem. Lectures 9-12 introduce the JL lemma with the sparse and fast variants.


Here is a rather different application from what you may have had in mind. Linear programming has many practical applications. There are many algorithms for linear programming and those based on George Dantzig's simplex method are among the most commonly implemented. An important parameter of simplex is called the pivoting rule. Victor Klee and George Minty provides a set of polytopes on which the pivoting rule suggested by Dantzig would require an exponential number of pivoting steps. Since then, examples demonstrating an exponential lower bound have been discovered for nearly every deterministic pivoting rule.

Simplex can however use randomized pivoting rules. Gil Kalai in 1992 introduced a randomized pivoting rule and proved a sub-exponential upper bound for simplex with this rule. Also in 1992, Micha Sharir and Emo Welzl defined LP-type problems which include  standard linear programming and with    Jiří Matoušek also proposed randomized variants of simplex and proved subexponential upper bounds for this variant. Subexponential lower bounds were also discovered on LP-type problems, but till about 2010 there were no concrete examples of linear programs on which these lower bounds could be demonstrated. See these two posts on Gil Kalai's blog for another telling of this story, the connection to the Hirsch conjecture and links to the literature.

What does any of this have to do with parity games? A couple of steps are required to set up a connection. An open problem in parity games research till about 2009 was to determine if certain policy iteration algorithms for solving parity games might have exponential behaviour. See the papers of Marcin Jurdziński for more on this. Oliver Friedmann, starting in 2009, exhibited examples of parity games on which certain policy iteration algorithms required exponential time. By exploiting a connection between parity games and certain LP-type problems he derived sub-exponential lower bounds for various pivoting rules for simplex. (Note however that one of the results, which concerned the Random Facet algorithm was shown by Oliver Friedmann, Thomas Hansen and Uri Zwick to be erroneous.)

I hope you'll agree that's a pretty fascinating and convincing example of an application of parity games.

There is a more direct answer to your question as well. Suppose one wants to design a discrete controller that regulates how some physical system (thermostat, chemical plant, etc.) behaves based on the state of the system and the state of the environment. The question of whether a controller exists to provide the guarantees a designer wants can be reduced to solving parity games. So you can think of a parity game in terms of systems, environments and controllers.

Another setting is program analysis. Suppose you want to automatically determine if a  program satisfies some correctness property in the modal $\mu$-calculus. Model checking is one approach to solving this problem and $\mu$-calculus model checking is deeply connected to parity games.


What language feature allows programs to manipulate themselves?


Metric graph theory database search algorithms

This seems to be related to the subgraph isomorphism problem which is in general NP-complete, even without any weights. The corresponding Wikipedia article claims that it can be solved efficiently in certain cases, though.

If chemo- is anything like bioinformatics you will probably be interested in approximation algorithms in order to deal with noise, anyway. Also, given database lookup as application, there might be clever ideas for preprocessing that give you good amortised runtimes.

Found (not read) those:

http://www.springerlink.com/content/4751121q3575v041/

http://bioinformatics.oxfordjournals.org/content/23/2/232.full

http://portal.acm.org/citation.cfm?id=1368898

Disclaimer: Again, sorry for comment-style answer; I am not yet allowed to comment.


Evidence that there is some problem in BQP distinct from BPP?

Scott Aaronson has been addressing this topic: http://arxiv.org/abs/0910.4698

Related hardness results:

Boson sampling: http://arxiv.org/abs/1011.3245
Commuting circuits: http://arxiv.org/abs/1005.1407
DQC1 model: http://arxiv.org/abs/1509.07276
Extended Clifford circuits: http://arxiv.org/abs/1305.6190


Here's a simple argument that shows that QP is not known to be in PSPACE:

Assume $QP \subseteq PSPACE$. Then we have $P \subsetneq QP \subseteq PSPACE$, where the first inclusion is proper by the time hierarchy theorem.

This separates $P$ from $PSPACE$, which is not known to hold, so $QP \subseteq PSPACE$ must also not be known to hold.

Indeed we have that $PSPACE \subseteq QP \Rightarrow PSPACE \subsetneq EXP$, but $QP \nsubseteq PSPACE$ does not separate the two classes by the THT (as stated in the question).


From  Russell Impagliazzo's comment:

  As a way of formalizing
  what languages are in $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$,
  Regan introduced the complexity class $\mathsf{H}$.
  A language $L$ is in $\mathsf{H}$ if and only if $L$ is in $\mathsf{P}^O$
  relative to every oracle $O$ so that $\mathsf{P}^O=\mathsf{NP}^O$.
  Thus, $L$ is in $\mathsf{H}$ if the statement
  $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ relativizes.
  $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$.
  From Toda's theorem, and some of the lemmas in Toda's theorem,
  it is also true that $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ for every $q$.
  Basically, any oracle satisfying $\mathsf{P}^O=\mathsf{NP}^O$
  gives a new upper bound on $\mathsf{H}$.
  It is open whether $\mathsf{H}=\mathsf{PH}$.

And from Lance Fortnow's comment:

  Let $f(n)$ be any unbounded function.
  $\mathsf{H}$ is not contained in $\mathsf{AltTime}(f(n),\mathsf{poly})$ and
  if you could prove
  $\mathsf{P}=\mathsf{NP}$ implies $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ then $\mathsf{NP}$ is different than $\mathsf{L}$.

For definition of $\mathsf{H}$ see definition 6.3 in

Kenneth W. Regan, "Index sets and presentations of complexity classes", 1999


Is there a theory that combines category theory/abstract algebra and computational complexity?

[Computational complexity and category theory] seem like such natural pairs.

Given the prominence of computational complexity as a research field, if they were such natural bedfellows, maybe somebody would have brought out the
connection already?

Wild speculation.
Let me entertain the reader with thoughts about   why a categorical rendering of computational complexity is hard.  Arguably, the
key concept cluster in category theory is centering around universal
constructions / properties (with the associated apparatus of functors,
natural transformations, adjunctions and so on). If we can show that a
mathematical construction has a universal property, that gives a lot
of insight.
So if we wanted a categorical approach to computational complexity, we'd
need to find a convenient category and exhibit how key concepts of complexity theory (e.g. LOGSPACE
or NP-hardness) can be given by universal constructions using that category.  This has not
yet been done, and I think that this is because it's a really difficult problem.

I suspect that the reason for this difficulty is that the key object of
complexity theory, the Turing machine, is not well understood algebraically.  The
problem with TMs is that they are not naturally equipped with a nice
algebra that allows building up programs in a compositional way. By
that I mean that we don't usually program TMs by saying our target
program is the TM T which is composed as e.g. $T = T_1 \oplus T_2
\otimes T_3$ where the $T_i$ are 'smaller' TMs and $\oplus, \otimes$ are
algebraic operators on TMs: we just don't have (natural) algebraic operations on TMs that
enable us to build up TMs in stages in an insightful way1.  Instead, we construct TMs by specifying their two
components separately: the  control (a FSM) and the tape.
Neither control nor tape have good algebras
themselves.

Let's look at tapes first.  There are a couple of natural
ways to compose tapes, none of which appear to work for a compositional
description of TMs.

Glue them together like ordinal addition.
This isn't the right notion, because tapes are infinite and by
sticking them together like ordinal addition we obtain a double
infinite object that goes beyond finite computability, leading to
infinite computation / hypercomputation, which are interesting as
mathematical but don't correspond to feasible computation.
Stick them in parallel, e.g. two 3-head machines turn into a 6-head
machine. This doesn't tell us how the component machines interact
with each other.
Interleave tapes. One problem with this approach is that it's
unclear what the canonical interleaving might be, if any. Moreover,
interleaving will 'confuse' existing control, which tends to be
finely tuned towards a specific tape layout. So we can't reuse control directly.

With FSMs the situation is a bit better, because we do have computationally meaningful algebraic
theories of automata construction, the most well-know of which might
be process algebras like CSP, CCS, $\pi$-calculus, ACP and so on. But
none of them is a calculus of tape-head movements, which is what we'd
need if we wanted to compose TMs.

All in all, we are quite far away form a substantial algebraic /
categorical treatment of computational complexity, and we'd need
several conceptual advances to get there.

1 Note that this is
quite different from other computational formalisms like
$\lambda$-calculus and $\pi$-calculus, which are algebraic
calculi. Because they are algebraic, it has been easy to develop
type-theories for $\lambda$-calculus and $\pi$-calculus as a way to
constrain programs. However these calculi have powerful operations like
new-name generation, scope extrusion, $\alpha$-conversion and unlimited copying of terms, which
make them a priori unsuitable as basic formalisms for complexity theory.  Indeed one can easily show e.g. P = NP if one isn't careful. It was only in 2014 that Accattoli and Dal Lago showed  (in: Beta Reduction is Invariant, Indeed) that $\lambda$-calculus can be used for defining time-complexity if one is careful. No corresponding results are known for space complexity, or for $\pi$-calculus.


Can we fast generate perfectly uniformly mod 3 or solve NP problem?

I will use numbers starting from $0$ rather than $1$, as I find it much more natural.
Here are two classes of problems we can solve in this way:

Functions in TFNP (i.e., single-valued total NP search problems)
(This generalizes the example with one-way permutations. It includes as a special case decision problems from $\mathrm{UP\cap coUP}$.)
The setup is that we have a polynomial-time predicate $R(x,y)$, and a polynomial $p(n)$ such that for every $x$ of length $n$, there exists a unique $y$ of length $m=p(n)$ such that $R(x,y)$ holds. The computational task is, given $x$, find $y$.
Now, I will assume wlog that $m$ is even, so that $2^m\equiv 1\pmod3$. The algorithm is to generate a uniformly random $y\in[0,2^m)$, and output

$y$ (as a solution of the search problem) if $R(x,y)$;

$y-y'$ (as a random element of $\{0,1,2\}$) if $y-y'\in\{1,2\}$, and $R(x,y')$;

$y\bmod3$ (as a random element of $\{0,1,2\}$) if no $y'\in\{y,y-1,y-2\}$ solves $R(x,y')$.

If there were no solution of the search problem, the $2^m$ random choices would give $1$ and $2$ $(2^m-1)/3$ times, and $0$ $(2^m+2)/3$ times (one more). However, if $y$ solves the search problem, we tinkered with the elements $y,y+1,y+2$ (which hit all three residue classes) so that they only produce residues $1$ and $2$, which evens out the advantage of $0$. (I am assuming here wlog that $y<2^m-2$.)

PPA-$3$ search problems
A convenient way to define PPA-$3$ is as NP search problems many-one reducible to the following kind of problems. We have a fixed polynomial-time function $f(x,y)$, and a polynomial $p(n)$, such that for any input $x$ of length $n$, the induced mapping $f_x(y)=f(x,y)$ restricted to inputs $y$ of length $m=p(n)$ is a function $f_x\colon[0,2^m)\to[0,2^m)$ satisfying $f_x(f_x(f_x(y)))=y$ for every $y$. The task is, given $x$, find a fixpoint $y$ of $f_x$: $f_x(y)=y$.
We can solve this in the way in the question as follows: given $x$ of length $n$, we generate a random $y$ of length $m=p(n)$, and output

$y$ if it is a fixpoint of $f_x$;

otherwise, $y$, $f_x(y)$, and $f_x(f_x(y))$ are distinct elements. We can label them as $\{y,f_x(y),f_x(f_x(y))\}=\{y_0,y_1,y_2\}$ with $y_0<y_1<y_2$, and output $i\in\{0,1,2\}$ such that $y=y_i$.

It is clear from the definitions that this gives a uniform distribution on $\{0,1,2\}$, as the non-fixpoint $y$'s come in triples.

Let me show for the record the equivalence of the problem above with Papadimitriou’s complete problem for PPA-$3$, as this class is mostly neglected in the literature. The problem is mentioned in Buss, Johnson: “Propositional proofs and reductions between NP search problems”, but they do not state the equivalence. For PPA, a similar problem (LONELY) is given in Beame, Cook, Edmonds, Impagliazzo, and Pitassi: “The relative complexity of NP search problems”. There is nothing special about $3$, the argument below works mutatis mutandis for any odd prime.

Proposition: The following NP search problems are poly-time many-one reducible to each other:

Given a circuit representing a bipartite undirected graph $(A\cup B,E)$, and a vertex $u\in A\cup B$ whose degree is not divisible by $3$, find another such vertex.

Given a circuit representing a directed graph $(V,E)$, and a vertex $u\in V$ whose degree balance (i.e., out-degree minus in-degree) is not divisible by $3$, find another such vertex.

Given a circuit computing a function $f\colon[0,2^n)\to[0,2^n)$ such that $f^3=\mathrm{id}$, find a fixpoint of $f$.

Proof:
$1\le_p2$ is obvious, as it suffices to direct the edges from left to right.
$2\le_p1$: First, let us construct a weighted bipartite graph. Let $A$ and $B$ be copies of $V$: $A=\{x^A:x\in V\}$, $B=\{x^B:x\in V\}$. For each original edge $x\to y$, we put in an edge $\{x^A,y^B\}$ of weight $1$, and an edge $\{x^B,y^A\}$ of weight $-1$. This makes $\deg(x^A)=-\deg(x^B)$ equal to the degree balance of $x$ in the original graph. If $u$ is the given vertex of balance $b\not\equiv0\pmod3$, we add an extra edge $\{u^A,u^B\}$ of weight $b$, so that $\deg(u^A)=2b\not\equiv0\pmod3$, and $\deg(u^B)=0$. $u^A$ will be our chosen vertex.
In order to make the graph a plain unweighted undirected graph, we first reduce all weights modulo $3$, and drop all edges of weight $0$. This leaves only edges of weights $1$ and $2$. The latter can be replaced with suitable gadgets. For example, instead of a weight-$2$ edge $\{x^A,y^B\}$, we include new vertices $w_i^A$, $z_i^B$ for $i=0,\dots,3$, with edges $\{x^A,y^B\}$, $\{x^A,z^B_i\}$, $\{w^A_i,y^B\}$, $\{w^A_i,z^B_i\}$, $\{w^A_i,z^B_{(i+1)\bmod4}\}$: this makes $\deg(w_i^A)=\deg(z_i^B)=3$, and contributes $5\equiv2\pmod3$ to $x^A$ and $y^B$.
$3\le_p2$: Let me assume for simplicity $n$ is even so that $2^n\equiv1\pmod3$. We construct a directed graph on $V=[0,2^n)$ as follows:

We include edges $3x+1\to3x$ and $3x+2\to3x$ for each $x<2^n/3-1$.

If $x_0<x_1<x_2$ is a non-fixpoint orbit of $f$, we include edges $x_0\to x_1$ and $x_0\to x_2$.

The chosen vertex will be $u=2^n-1$. The first clause contributes balance $1$ or $-2\equiv1\pmod3$ to each vertex $\ne u$. Likewise, the second clause contributes balance $-1$ or $2\equiv-1\pmod3$ to vertices that are not fixpoints. Thus, assuming $u$ is not already a fixpoint, it is indeed unbalanced modulo $3$, and any other vertex unbalanced modulo $3$ is a fixpoint of $f$.
$1\le_p3$: We may assume that $A=B=[0,2^n)$ with $n$ even, and the given vertex $u\in A$ has degree $\equiv2\pmod3$.
We can efficiently label edges incident with a vertex $y\in B$ as $(y,j)$, where $j<\deg(y)$. In this way, $E$ becomes a subset of $[0,2^n)\times[0,2^n)$, which we identify with $[0,2^{2n})$. We define a function $f$ on $[0,2^n)\times[0,2^n)$ as follows.

On the complement of $E$: for each $y\in B$, and $j$ such that $\deg(y)\le 3j<2^n-1$, we make $f(y,3j)=(y,3j+1)$, $f(y,3j+1)=(y,3j+2)$, $f(y,3j+2)=(y,3j)$. Also, $f(3i,2^n-1)=(3i+1,2^n-1)$, $f(3i+1,2^n-1)=(3i+2,2^n-1)$, $f(3i+2,2^n-1)=(3i,2^n-1)$ for $3i<2^n-1$. This leaves out the point $(2^n-1,2^n-1)$, and $3-(\deg(y)\bmod 3)$ points $(y,i)$ for each $y\in B$ whose degree is not divisible by $3$.

On $E$: for each $x\in A$, we fix an efficient enumeration of its incident edges $(y_0,j_0),\dots,(y_{d-1},j_{d-1})$, where $d=\deg(x)$. We put $f(y_{3i},j_{3i})=(y_{3i+1},j_{3i+1})$, $f(y_{3i+1},j_{3i+1})=(y_{3i+2},j_{3i+2})$, $f(y_{3i+2},j_{3i+2})=(y_{3i},j_{3i})$ for $i<\lfloor d/3\rfloor$. This leaves out $\deg(x)\bmod3$ points for each vertex $x\in A$ whose degree is not divisible by $3$.

Since $\deg(u)\equiv2\pmod3$, two of its incident edges were left out; we make them into yet another $f$ cycle using $(2^n-1,2^n-1)$ as the third point. The remaining points are left as fixpoints of $f$. By construction, any of them will give rise to a solution of (1).


Randomness versus Quantumness in factorization

What is it that quantumness provides that sieve techniques cannot provide?

It is more a question why quantum computers are believed to be more powerful than classical  computation models. Short: Quantum computers provide superpositions of quantum states.

Randomized algorithms are restricted to be in a certain state with some (constant) error probablility. Quantumness provides the posibility of evaluating function on every possible state and afterwards measuring a certain state with some error probability.

What exact barrier does Shor's algorithm break that randomness cannot?

The quantum states represent the accepted states as well as the rejected states. Shor's algorithm evaluates the accepting states in such an extent that the accepting states are more likely to be measured. Also the quantum algorithm can manipulate all states at the same time. A randomized algorithm is bound to increase the probability of being in such a accepting state, looping often enough to get a certain probability (or extending some other variable).


Ranking the Difficulty of NP Hard Problems in Practice

While it's not inconceivable that the technical obstacles you mention could be overcome somehow, I think that there is very little motivation at present to do so, for the simple reason that (at least as far as I am aware) the difficulty of NP-hard problems in practice seems, empirically, to have little to do with their closeness to the 3-SAT phase transition.

Contrast this with some other ways to rank NP-hard problems in terms of difficulty: There is some empirical correlation between NP-hard problems that are easy in practice and NP-hard problems that are easy to approximate, or that are fixed-parameter tractable (in the sense of parameterized complexity).  Appropriate notions of reduction have been developed in these cases that partially explain the empirical observations.  However, there currently seems to be no empirical indication that most NP-hard problems that are difficult in practice are difficult because of their close relationship to 3-SAT instances near the phase transition.  So it does not make too much sense to develop a theory to "explain" something that does not appear to be true in practice.


A good rule of thumb with locally nameless is "pattern matching on a binder is opening". In particular, take a naive call-by-name normalization algorithm on terms with named binders that ignores variable capture (in OCaml syntax):

 let rec norm t = match t with
     | Var v -> Var v
     | Lambda (v, t') -> Lambda (v, norm t')
     | App(t, u) -> let t' = norm t in
                    let u' = norm u in
                    match t' with
                       | Lambda (v, t'') -> norm (subst v u' t'')
                       | _               -> App (t', u')

The locally nameless version is exactly the same, except that you need to open the lambdas right after pattern matching on one, i.e. instantiate the top level deBruijn index with a name. What name do you want to open with? Well it probably needs to be a name you haven't opened with "above", aka a fresh variable.

Well darn. We were kind of hoping to not have to care about generating fresh variables with locally nameless. No such luck. In OCaml, you can cheat a little and create a statefull fresh : unit -> name function that always produces a never-seen-before name.

You don't actually need to do this with the second pattern match! When opening a term and immediately substituting, you can skip a step and call instantiate directly. This mentions no names (and works on a "scope", a non "opened term" with 1 deBruijn variable still in it).

But then you have the fresh names in the normal form! You need to abstract over the name again before applying the Lambda constructor. This gives

 let rec norm t = match t with
     | Var v -> Var v
     | Lambda t' -> let v = fresh () in
                    let t'' = instantiate (Var v) t' in
                    Lambda (abstract v (norm t'))
     | App(t, u) -> let t' = norm t in
                    let u' = norm u in
                    match t' with
                       | Lambda t'' -> norm (instantiate u' t'')
                       | _               -> App (t', u')

Easy peezy (except for the implementation of fresh, which can be tricky)!


I don't know if this problem has another name, but it seems like it's easy to solve.
We first see that a weak incidence coloring of a graph $G$ corresponds to an edge coloring of the graph $G'$ obtained by subdividing each edge of $G$ once. This, in turn, corresponds to a vertex coloring of $L(G')$, the line graph of $G'$. This line graph consists of a collection of cliques, one for each vertex in the original graph $G$. Each vertex in each clique is adjacent to one and only one vertex in another clique.
Now, it is not hard to prove that $L(G')$ is a perfect graph by the strong perfect graph theorem (neither $L(G')$ or $\overline{L(G')}$ have any long odd cycles). This implies that the chromatic number of $L(G')$ is equal to the size of the largest clique in $L(G')$, which in turn implies that the weak incidence coloring number of $G$ is equal to $\Delta(G)$.


Turing-complete computation models on graphs

As in my comment, the configuration graph (Chapter 4.1.1. of Arora-Barak) is a simple way to view a Nondeterministic Turing Machine (NTM) as a graph. The vertices of the graph are labeled by configurations: the internal state of the NTM, the contents of the tape, and head positions. There is a  directed edge from vertex $c_1$ to vertex $c_2$ if the NTM can move from $c_1$ to $c_2$ in one step.

This is especially useful for arguing about space-bounded computation. If the space used by the NTM is bounded by $s(n)$, then on input size $n$ you only need to consider a configuration graph with $O(2^{s(n)})$ vertices. Then a lot of complexity results follow from algorithms for directed $s$-$t$ connectivity: Savitch's theorem (NPSPACE = PSPACE) follows from an algorithm that uses $O(\log^2 |V|)$ space, PSPACE in EXP (or, scaling down, L in P) follows from DFS,  etc. Similarly, you can show that directed connectivity is complete for NL under L reductions, so NL is equal to L if and only if there is a logspace algorithm for directed $s$-$t$ connectivity.


Find the maximum flux path between two nodes

The problem is known as "Maximum capacity path problem" or  "Widest path problem"

See the original paper: T. C. Hu, "The Maximum Capacity Route Problem", Operations Research Vol. 9, No. 6 (Nov. - Dec., 1961), pp. 898-900

or the linear time algorithm described in: A. P. Punnen, "A linear time algorithm for the maximum capacity path problem" (but I didn't download/read it)


The collection of tensors of a given rank, or even of tensors with rank at most $k$ is not a (Zariski-)closed set, so it cannot be described as the vanishing locus of any set of polynomials, regardless of their complexity. (However, over finite fields tensor-rank is $NP$-complete and over $\mathbb{Q}$ it is $NP$-hard but not known to be in $NP$. But these are the usual Boolean classes, not the Valiant analogues.)

The closure of the the set of tensors of rank at most $k$ is the set of tensors of border-rank at most $k$. Call a set of polynomials whose vanishing locus is the set of tensors of border-rank at most $k$ a system of (set-theoretic) defining equations for border rank at most $k$. Such defining equations are known for small $k$, but for most $k$ finding such defining equations is a long-standing open problem, related the border-rank and multiplicative complexity of matrix multiplication.

See Landsberg's Bulletin article Geometry and the complexity of matrix multiplication for an introduction and some references, and see Landsberg's recent book Tensors: Geometry and Applications (freely available introduction) for all that is known about defining equations for border-rank.


Is induced subgraph isomorphism easy on an infinite subclass?

If I'm not mistaken your question was answered by Chen-Thurley-Weyer-2008 modulo parameterized complexity assumptions.

I didn't read the paper carefully yet, but as far as I understood, there is a dichotomy in the sense that if $C$ is finite then the problem is in $P$, but if $C$ has an infinite number of graphs then the induced subgraph isomorphism is $W[1]$ complete (Corollary 4, page 6).

Thus it seems that unless the first level $W[1]$ of the $W$ hierarchy collapses to $FPT$, there is no such an infinite class of graphs whose induced subgraph isomorphism is in $P$.

There is another interesting result stating that if $P\neq NP$ then there are classes for which the induced isomorphism is neither in $P$ nor $NP$ complete.