This is a possible reduction from 3-partition which is strongly NP-complete.

Given a set $A = \{a_1,a_2,...,a_{3m}\}$ of $3m$ positibe integers, and a target sum $B$.

The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to satisfy the $Rx2$ in the middle.

We represent each $a_i$ with a unary chain $P_{a_i}$ made of $a_i+2$ write operations: the first operation is a $Wx2$ (green boxes in the figure), followed by $a_i$ write operations $Wy2$ (gray boxes), followed by a single $Wz2$ (blue boxes) write operation.

We add three auxiliary chains $P_{c_1}, P_{c_2}, P_{c_3}$. $P_{c_1}$ made with $4m$ write operations $Wx1$, $P_{c_2}$ made with $B \cdot m = \sum_{i=1}^{3m} a_i$ write operations $Wy1$,  $P_{c_3}$ made with $4m$ write operations $Wz1$.

Now we build the chain $P_0$ made only with read operations in the following way:
concatenate $m$ slot subsequences; each slot subsequence is made with:

a leading open sequence $Rx1\; Rx2\;  Rx1\;  Rx2\;  Rx1\;  Rx2\;  Rx1$, that forces to pop three operations $Wx2$ from three distinct $P_{a_i}$ and open those chains;
followed by a sum sequence $Ry1\; Ry2$ repeated $B$ times, that forces to pop $B$ operations $Ry2$ from the chains that are currently open;
followed by a trailing close sequence $Rz1\; Rz2\;  Rz1\;  Rz2\;  Rz1\;  Rz2\;  Rz1$, that forces to pop three operations $Wz2$ from the end of the chains that are currently opened.

Note that if a chain is opened and some $Wy2$ are still there and in order to complete the current close sequence  we pop them  (without a corresponding $Ry2$) to reach the final $Wz2$, in one of the next slot subsequences there will be not enough $Wy2$ to reach the close sequence. And if we are in the middle of a sum sequence and we need a $Wy2$ but we've already reached the end of all the currently opened $a_i$ chains, we cannot open another chain to recover a $Wy2$ to complete the sum sequence, otherwise in one of the next slot subsequences there will be not enough $Wx2$ to complete an open sequence.

The figure represents the instance: $A = \{ 3,3,2,2,2,2 \}$, $m=2$, $B=7$ (note that every $a_i$ should be between $B/4$ and $B/2$ to force exactly three elements in each slot sequence)

NOTE: as noted in the comments, the trailing $Rx1$ (resp. $Rz1$) of the open (resp. close) sequences are unuseful and they can be removed (and $P_{c1}, P_{c3}$ shortened to $3m$ elements).


Automated theorem proving in linear logic

Other resources could be found referenced in Kaustuv Chaudhuri's thesis "The Focused Inverse Method for Linear Logic", and you might be interested in Roy Dyckhoff's "Contraction-Free Sequent Calculi", which is about contraction but not about linear logic.

There are opportunities for efficient proof search in linear logic, but I don't think current work indicates that it's easier than proof search in non-substructural logic. The problem is that if you want to prove $C \vdash(A \otimes B)$ in linear logic, you have an extra question that you don't have in normal proof search: is $C$ used to prove $A$ or is $C$ used to prove $B$? In practice, this "resource nondeterminism" is a big problem in performing proof search in linear logic.

Per the comments, Lincoln et al's 1990 "Decision problems for propositional linear logic" is a good reference if you want to get technical about words like "easier."


Is there a list of canonical problems in distributed systems?

Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to?

I'm unaware of such a published list of problems.

Keep in mind that there are many different (and somewhat incomparable) models in distributed computing, ranging from the "benign" synchronous (fault-free) model where nodes execute in lock-step rounds and all messages are delivered
reliably in each round, to the asynchronous model where there are no bounds on
processing speeds and message delays and nodes themselves might crash or send
corrupted messages.
To further add to this variety, there are other requirements and assumptions
that are orthogonal to synchrony and faults: the initial knowledge of nodes
(network size, diameter of the network, maximum node degree, etc.), the ability
to query a failure detectors, whether nodes have unique identifiers, atomicity
of send & receive steps, the maximum size of a single message, and many more.

The actual model at hand often implies a very different nature of
question. (See [1] for more elaboration on these $2$ sub-communities in distributed computing.)
In models that are close to the fault-free synchronous model, researchers often
look at the complexity of local computation, for example, "What is the time and message
complexity for computing a vertex coloring?"

When looking at failures on the other hand, the questions are more related to solvability issues like "Is consensus solvable in this model?" or "Can we implement this fancy
failure detector under these assumptions?"

  If there is not a canonical list what is the current list of problems and what reductions exist?

There are many examples of such reductions in certain distributed computing
models, I'll limit my answer to the following 2:

Local computation in the (fault-free) synchronous model

[2] show reductions between many optimization problems, for example, Minimum Dominating
Set, Maximal Independent Set (MIS), Maximal Matching (MM), and Minimum Vertex
Cover (MVC): In particular, [2] show a lower bound of $\Omega(\sqrt{\log n} +
\log\Delta)$, where $n$ is the network size and $\Delta$ the max degree, for
computing a constant approximation of an MVC. From this, the same bound follows
for computing an MM, since any maximal matching is also a $2$-approximation of
an MVC. From this, you also get a bound on computing an MIS, because an
MIS-algorithm $A$ can be used to compute MM by simulating the execution of $A$
on the line graph.

Asynchronous Model with Crash Failures

Here the most studied problem is
fault-tolerant consensus and its many variations, since implementing basic primitives like atomic broadcast and or a synchronizer themselves require consensus.

For example, assuming access to failure detectors [3], gives rise to a classification of problems by looking at
the power of their respective failure detector.
We say that failure detector $S$ is the weakest failure detector for problem $P$, if, given any failure detector $T$ for $P$, you can also implement $S$.

Using this relation, we can define problem $P$ as being harder than problem $Q$, if
the weakest failure detector for solving $P$ can implement the weakest failure
detector for solving $Q$.
It has recently been shown that every problem has a weakest failure detector [4]; note however, that [4] is an existential result. For some problems, e.g., consensus, the weakest failure detector is known [5], while for other problems, e.g., $k$-set agreement, the weakest falure detector is still open [6].

  For example, I would say very naively that the leader election and mutual
  exclusion problems can be reduced to the consensus problem.

Sure, if you can solve consensus, you immediately have an algorithm for leader
election: Simply use the ID of each node as the input for the consensus
algorithm. The opposite way only holds in models where it is  guaranteed that the leader is eventually known to all.

[1] Pierre Fraigniaud: Distributed computational complexities: are you volvo-addicted or nascar-obsessed? PODC 2010.
http://doi.acm.org/10.1145/1835698.1835700

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
http://arxiv.org/abs/1011.5470

[3] Tushar Deepak Chandra, Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43(2): 225-267 (1996).
http://doi.acm.org/10.1145/226643.226647

[4] Prasad Jayanti, Sam Toueg: Every problem has a weakest failure detector. PODC 2008: 75-84.
http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4): 685-722 (1996)
http://doi.acm.org/10.1145/234533.234549

[6] Michel Raynal: Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results. Bulletin of the EATCS 103: 74-95 (2011)
http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61


A quadratic separation between $\log\chi_0$ and $\log\chi_1$ is proved in a paper by Göös, Jayram, Pitassi and Watson, see the ECCC report.

In Theorem 2 they construct a function $F$ with small $\log\chi_1(F)$, and they say "In fact, we prove Theorem 2 by showing that (the negation of) the function $F$ has high approximate nonnegative rank". Observe that $\log\chi_0(F)$ is at least the nonnegative rank of the negation of $F$.


I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it.

A great reference for oracle separations (for classes between P and PSPACE) is the following paper:

  Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. Izvestiya Mathematics 42 (2): 261

The paper shows (or gives a citation for) an oracle separation between almost every pair of classes that you might care about between P and PSPACE (e.g., it has classes like P, RP, BPP, UP, FewP, NP, MA, AM, other levels of PH, PH, IP, PSPACE, etc.).

For example, Theorem 8 shows an oracle problem in coRP that is not in NP. Since (relative to all oracles) coRP is in BPP and NP contains P, we get an oracle problem in BPP that is not in P.

As I mentioned in my comment, showing an oracle for which $\text{P}^A = \text{BPP}^A$ is easy. Let A be a EXP-complete language or a PSPACE-complete language.


Is the following optimization problem (another variant to a previous problem) NP-hard?

Lemma. The problem is NP-hard.

Proof. The proof is by reduction from Set Cover with sets of size at most 3 (which itself is NP-hard by an easy reduction from 3D-matching).  Given a collection of sets, each of size at most 3, and an integer $k$, the reduction outputs an instance of your problem where the set $S$ contains the edges of the following DAG: For each element $x$, create an element-vertex $v(x)$.  For each set $s$, create a set-vertex $v(s)$.  Create a root vertex $r$.  Add edges from every vertex (except the root) to the root.  For each set $s$ and element $x\in s$, add edge $(v(x), v(s))$.  All edges have weight 1, and $M\ge 3$ is the number of sets minus $k$.

To show that the reduction is correct, we show that there is a set cover of size $k$ if and only if there is a solution to your problem of cost $M+n$, where $n$ is the number of elements.

(only if). Assume there is a set cover of size $k$.  For the instance output by the reduction, consider a solution with the following edges.  From each element-vertex $v(x)$, take the edge to some $v(s)$ such that $x\in s$ and $s$ is in the set cover.  (Note that each $v(s)$ has at most $3\le M$ edges into it.) From each set-vertex $v(s)$ where $s$ is not in the cover, take an edge from $v(s)$ to the root.  In this solution, the root has $M$ chosen edges into it, and each element-vertex has an edge leaving it, so the total number of edges in the solution is $M+n$.

(if). Conversely, suppose the instance output by the reduction has a solution with $M+n$ edges.  Among these edges (by the ILP constraints), the root has at most $M$ (incoming) edges.  Likewise, the solution has at most one edge out of each of the $n$ element-vertices.  Since the solution has $M+n$ edges, and every edge either enters the root or leaves an element vertex, it follows that the solution has exactly $M$ edges entering the root, and exactly one edge leaving each element-vertex, and that no edge in the solution does both, that is, no edge goes from an element-vertex to the root.

It follows that the solution consists of exactly $M$ edges from set-vertices to the root, and exactly $n$ edges from element-vertices, which (by the ILP constraints) must go to the set-vertices that don't have edges to the root in the solution.  There are $k$ of those set-vertices.  Hence, there is a set cover of size $k$. $~~\Box$


Finding the penumbra of a Constraint Satisfaction Problem

Much of the attention paid to optimization variants of the constraint satisfaction problem (CSP) has focused on satisfying some number of constraints (MAX-CSP), or in the Boolean case on picking the solution which assigns as many variables as possible the value 1 (MAX-ONES, there is also MIN-ONES).

Instead, you are asking about a variant that could be called MAXIMUM PARTIAL CSP.  This was studied at least as far back as the late 1960s, but I'm not aware of it having an established name.  It is a natural problem, and it would be good to see more work investigating it.  Thank you for providing another potential application for this problem!

Ambler, A. P. and Barrow, H. G. and Brown, C. M. and Burstall, R. M. and Popplestone, R. J., A versatile system for computer-controlled assembly, Artificial Intelligence 6 129–156, 1975. doi: 10.1016/0004-3702(75)90006-5

A set of variable-value assignments is called a partial assignment.  One can write a variable-value assignment as a (variable, value) tuple.  Partial assignments are then simply functions from variables to values.  Props are partial assignments that don't violate any constraint.  Equivalently, a prop contains no partial assignment forbidden by some constraint (as a subset).

One way to express the optimization problem is as follows.

  MAXIMUM PARTIAL CSP:
  Input: CSP instance
  Output: prop $f$
  Criterion: maximize $|f|$

In an instance with $n$ variables, clearly a prop of cardinality $n$ will be a solution.  There may exist large props, with cardinality up to $n-1$, that are not contained in any solution.

In the terminology you propose, the set of props with maximum cardinality $k$ forms the penumbra, perhaps even with some additional leeway $d$ (so cardinality at least $k-d$).

The second part of your question also appears highly interesting, but I am not aware of any work related to it.

Footnote: The term prop is from my thesis; it is meant to convey the idea that such partial assignments are proper, and also that they support the set of solutions.  This is in contrast to a nogood, which is the accepted term to describe a partial assignment that cannot be extended to a solution.  The word "nogood" was introduced by Richard Stallman and Gerald Sussman in 1976, when RMS was still an AI researcher instead of software freedom activist.

Stallman, Richard M. and Sussman, Gerald Jay, Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis, MIT Artificial Intelligence Laboratory Memo No. 380, 1976. (PDF)


Relationship between symmetry and computational intractability?

This isn't exactly the "same" relationship between symmetry and hardness, but there is a close relationship between the symmetries of a Boolean function and its circuit complexity.  See:

  Babai, L., Beals, R., and Takácsi-Nagy, P.  Symmetry and complexity, STOC 1992.

Here's what they show. Let $G_{i} \leq S_{i}$ be a sequence of permutation groups. Let $s(G_{i})$ denote the number of orbits of $G_{i}$ in its induced action on $\{0,1\}^{i}$ (by permutation of the coordinates).  Let $\mathcal{F}(G)$ denote the class of languages $L$ such that $L \cap \{0,1\}^{n}$ is invariant under $G_{n}$.  Then all languages in $\mathcal{F}(G)$ have circuits of size at most $poly(s(G))$ and depth at most $poly(\log(s(G))$, and this is essentially tight.

In the opposite direction, several $NP$ problems whose witness sets have lots of symmetries end up being in $coAM$ (like $GI$), and so are not $NP$-complete unless $PH$ collapses.  In fact, the following paper shows that $NP$ problems whose witness sets have lots of symmetries are low for $PP$:

  Arvind, V., Vinodchandran, N. V. The counting complexity of group-definable languages. Theoret. Comput. Sci. 242 (2000), no. 1-2, 199--218.

(Note: whether or not "low for $PP$" indicates "unlikely to be $NP$-complete" is a little up in the air, as far as I know. Toda and Ogiwara showed that $PP^{PH} \subseteq BP \cdot PP$.  So under the "derandomization" assumption $BP \cdot PP = PP$, $NP$ is in fact low for $PP$, so being low for $PP$ is no obstacle to being $NP$-complete.  On the other hand, there is an oracle due to Beigel relative to which $NP$ is not low for $PP$.)

In a similar vein as the above, if every polynomial-time decidable equivalence relation has a polynomial-time complete invariant (function $f$ such that $f(x) = f(y)$ iff $x \sim y$), then any $NP$ problem whose witnesses have lots of symmetries reduces to the hidden subgroup problem for the automorphism group of its witnesses.  Admittedly, the hypothesis here is rather unlikely to hold, but it does give some connection between symmetry and quantum complexity.

Finally, the Mulmuley-Sohoni Geomectric Complexity Theory program is essentially about using symmetry to prove hardness, though the symmetry-hardness connection there is more subtle and less direct.


Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

I believe the problem to be coNP-complete.
I have uploaded it as an arXiv preprint.


About properties of adjacency matrix when a graph is planar

Computing determinant and permanent of planar graphs are as hard as computing them in general graphs. They are complete for GapL and #P respectively. See this paper by Datta, Kulkarni, Limaye, Mahajan for more details.


Can "$x(\lambda y.P\;)z$" be $\beta$-reduced?

The expression $x(\lambda y.P)z$ is not $\beta$-reducible (unless there is a redex inside $P$, that is, but no such reduction sequence can escape outside the $\lambda$). The reduction you mention is invalid even in $\lambda\eta$-calculus. The only explanation I can imagine is that the expression in your derivation was misbracketed, and should actually read $x((\lambda y.P)z)$.


Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum.

Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op.

Here is the intuition.  The problem in the post is

Is there a permutation matrix in the span of a given set of matrices?

This is essentially the same as

Is there a permutation matrix that (thinking of the matrix as a vector) satisfies some given linear constraints?

This in turn is the same as

Is there a perfect matching (in a complete bipartite graph) whose incidence vector satisfies some given linear constraints?

Reducing Subset-Sum to the latter problem is a standard exercise.

Here is the detailed proof.

Define the following intermediate problem:

  Matching-Sum:

  input: Complete, bipartite graph $G=(U,V,E)$ with non-negative
  integer edge weights, and non-negative integer target $T$.

  output: Does $G$ contain a perfect matching of weight exactly $T$?

  Lemma 1. Subset-Sum poly-time reduces to Matching-Sum.

Proving this is a standard homework exercise.  The proof is at the end.

  Lemma 2. Matching-Sum poly-time reduces to the problem in the post.

Proof of Lemma 2. Fix a Matching-Sum input: a complete bipartite graph $G=(U,V,E)$ with non-negative integer edge weights $w:U\times V\rightarrow \mathbb{N}_+$, and target $T\in \mathbb{N}_+$, where $U=\{u_1,\ldots,u_n\}$ and $V=\{v_1, \ldots, v_n\}$. For each $i,j\in\{1,2,\ldots,n\}$, define $M^{(ij)}$ to be the matrix in $\mathbb{R}^{(n+1)\times (n+1)}$ where $M^{(ij)}_{ij} = T$, and $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$, and all other entries are zero.  The reduction outputs the following set of matrices:
$$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$$
This defines the reduction.

Claim. The span of this set of matrices consists of
those matrices $M \in\mathbb{R}^{(n+1)\times(n+1)}$ satisfying
the linear constraints $M_{h,n+1} = M_{n+1,h} = 0$ for all $h\le n$ and
the linear constraint $$\textstyle\sum_{i=1}^n\sum_{j=1}^n M_{ij}\,w(u_i, v_j) = T\, M_{n+1,n+1}.$$

(Proof of claim. By inspection each matrix $M^{(ij)}$ in the set satisfies these constraints, so every linear combination of those matrices does.  Conversely, if $M\in\mathbb{R}^{(n+1) \times (n+1)}$ satisfies the constraints, then $M$ equals the linear combination $M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$ of the matrices, where $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$.  Note in particular that, by the various definitions and the linear constraints,
$$\textstyle M'_{n+1,n+1} = \sum_{ij} \alpha_{ij} w(u_i, v_j)
= \sum_{ij} M_{ij} w(u_i, v_j)/T
= (T\, M_{n+1,n+1})/T = M_{n+1,n+1}.
$$
This proves the claim.)

Now we show the reduction is correct.  That is, the given graph $G$ has a weight-$T$ matching if and only if the set of matrices spans a permutation matrix.

(Only if.) First suppose the given graph $G$ has a weight-$T$ perfect matching $M'$.  Let $M\in\{0,1\}^{(n+1)\times (n+1)}$ be the corresponding $n\times n$ permutation matrix, with an extra row and column added such that $M_{n+1,n+1} = 1$ and $M_{h,n+1}=M_{n+1,h}=0$ for all $h\le n$.
Then $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ is the weight of $M'$, that is, $T$, and $M_{n+1,n+1}=1$, so the linear constraints in the claim hold, and the span of the given set of matrices contains the permutation matrix $M$.

(If.) Conversely, suppose the span contains any permutation matrix $M$.  By the claim, the only non-zero entry in row $n+1$ or column $n+1$ is $M_{n+1,n+1}$, so (as $M$ is a permutation matrix) it must be that $M_{n+1,n+1} = 1$.  So deleting the last row and column gives an $n\times n$ permutation matrix. Let $M'$ be the perfect matching of $G$ corresponding to that $n\times n$ permutation matrix.  The weight of $M'$ is $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$, which (by the claim) is $T M_{n+1,n+1} = T$. So the given graph has a weight-$T$ matching, proving Lemma 2.$~~\Box$

Here's the delayed proof of Lemma 1:

Proof of Lemma 1. Given Subset-Sum instance $(w,T)\in\mathbb{N}^n_+ \times \mathbb{N}_+$, the reduction outputs the Matching-Sum instance $(G=(U,V,E), T)$ where $U=\{u_1, u_2, \ldots, u_{2n}\}$, $V=\{v_1, v_2, \ldots, v_{2n}\}$, for each $i\in\{1,\ldots,n\}$, edge $(u_i, v_i)$ has weight $w_i$, and all remaining edges have weight zero.

For any perfect matching with edge weights summing to $T$, the set $S=\{i : (u_i, v_i)\in M, i\le n\}$ is a solution to the given Subset-Sum instance (as these are the only non-zero weight edges in $M$).

Conversely, given any solution to the Subset-Sum instance, say $S\subseteq\{1,\ldots,n\}$ with $\sum_{i\in S} w_i = T$, the set of edges $\{(u_i, v_i) : i \in S\}$ is a partial matching with weight $T$, and it extends easily to a weight-$T$ perfect matching by adding, for example, the following set of (zero-weight) edges:

$$\{(u_{i+n}, v_{i+n}) : i\in S\} \cup \bigcup_{i\in\{1,\ldots,n\}\setminus S}\{(u_i, v_{i+n}), (u_{i+n}, v_{i})\}.$$

This proves Lemma 1. The theorem follows from Lemmas 1 and 2. $~~~\Box$

p.s. As an aside, according to this answer, the restriction of Matching-Sum to instances with polynomially-bounded edge weights is in P.  But I'm sure that the restriction of the problem in the post to matrices with polynomially-bounded (integer) entries remains NP hard.


I think your looking for Back to Direct Style by Olivier Danvy


This problem is the same as the Vertex Cover problem for $3$-uniform hypergraphs:
given a collection $H$ of subsets of $V$ of size $3$ each, find a minimal subset $U\subseteq V$ that intersects each set in $H$.

It is therefore NP-hard, but fixed parameter tractable.
It is also NP-hard to approximate to within a factor of $2-\epsilon$ for every $\epsilon>0$. This was shown in the following paper:

Irit Dinur, Venkatesan Guruswami, Subhash Khot and Oded Regev.
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover,
SIAM Journal on Computing, 34(5):1129–1146, 2005.


Confidentiality of "partial private keys" in certificateless public key crypto

The best way to answer this is to look at the security model in that paper.  If the adversary is allowed to request the partial private key for the target identity (i.e. the one it uses in the left-right query during the attack), then partial-private-keys are not meant to be kept secret.  If the adversary is not allowed to do so, then they must remain confidential.

After scanning their model, it seems that all partial private keys are readily supplied to adversary via Extract-Partial-Private-Key-of-A queries. This means they don't need to be kept secret.

I've got to run now, but I'll edit later if I've gotten this wrong.


Are runtime bounds in P decidable? (answer: no)

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M'$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.

If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M'$ would be $O(n^2)$. If $M$ never halts then the run time of $M'$ is at least $n^3$.

Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M'$ is $O(n^2)$ or $O(n^3)$.


No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in Bletchely Park, was Turing-complete.

When asking such a question, it should be understood that no physical computer is Turing-complete, since it cannot handle arbitrarily large inputs. But even if we abstract this issue away (in any reasonable way), bombes are not Turing-complete. It could be fun to come up with an appropriate model and determine the exact complexity class covered by bombes.


How can we express "$P=PSPACE$" as a first-order formula?

Firstly, I want to address the comments to the question, where it was suggested that "false" expresses $P = PSPACE$ because the statement is false. While this might be a good joke, it is actually very much harmful to think this way. When we ask how to express a certain sentence in a certain formal system, we are not talking about truth values. If we were, then when someone asked "How do I write down the fact that there are infinitely many primes?" we could answer "3 + 3 = 6", but this clearly will not do. For the same reason "false" is not a valid answer to "how do I write down $P = PSPACE$?". I think Frege and Russell tried hard to teach us that lesson. Ok, now to the answer.

Let me show how to express $PSPACE \subseteq P$, the other direction is similar, and then you can put them together in a conjunction to get $PSPACE = P$. In any case, for your purposes it may be sufficient to express just $PSPACE \subseteq P$, depending on what you are doing.

Using techniques similar to those in the construction of Kleene's predicate $T$,
we can construct a bounded quantifer formula $accept_{space}(k, m, n)$ (which thus resides in $\Sigma^0_0 = \Pi^0_0$) saying "when we run the machine encoded by $k$ and bound its space usage to $|n|^m$, the machine accepts the input $n$." Here $|n|$ is the length of $n$. An informal way of seeing that such formulas exists is this: given $k$, $m$, and $n$ we can compute primitive recursive bound on how much time and how much space we are ever going to need (i.e., at most $|n|^m$ space and at most $2^{|n|^m}$ time). We then simply search through all possible execution traces which are within the computed bounds--such a search is rather inefficient, but it is primitive recursive and so we can express it as a bounded formula.

There is a similar formula $accept_{time}(k, m, n)$ in which the running time is bound by $|n|^m$.

Now consider the formula:
$$\forall k, m . \exists k', m' . \forall n .
accept_{space}(k,m,n) \Leftrightarrow accept_{time}(k',m', n).
$$
It says that for every machine $k$ which uses at most space $|n|^m$ there is a machine $k'$ which uses at most time $|n|^{m'}$ such that the two machines accepts exactly the same $n$'s. In other words, the formula says $PSPACE \subseteq P$. This formula is $\Pi^0_3$.

We can improve this if we are willing to express instead the sentence "$TQBF$ is in polytime" , which should be good enough for most applications, as TQBF is PSPACE complete and so it being in polytime is equivalent to $PSPACE \subseteq P$. Let $k_0$ be (the code of) a machine which recognizes TQBF in space $|n|^{m_0}$. Then "$TQBF \in P$" can be expressed as
$$\exists k', m' . \forall n . accept_{space}(k_0, m_0, n) \Leftrightarrow accept_{time}(k', m', n).$$
This formula is just $\Sigma^0_2$. If I were a complexity theorist I would know if it is possible to do even better (but I doubt it).


Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits.

If you can sort the bits then it is easy to compare the result to $k$ and
compute restricted threshold.

On the other hand, assume that we have an circuits to compute restricted threshold.
We can do a parallel search to find the number of ones in the input and
output the sorted list.

These preserve circuit depth. So if you come up with a new $\mathsf{NC^1}$ circuit to compute the restricted threshold then it will give a depth $O(\lg n)$ sorting circuit.
So if we come up with a simple argument for showing majority is in $\mathsf{NC^1}$
you have found a simple depth-$O(\lg n)$ sorting circuit
(other than the one based on AKS sorting network).

Note that it is easy to implement the restricted threshold using majority by adding new 1 and 0 inputs to the majority gate.

Previously this answer claimed that it can be done using divide and conquer and the fact that binary addition is in $\mathsf{AC^0}$. That only shows that majority is in $\mathsf{AC^1}$ and $\mathsf{NC^2}$ since we have unbounded fan-in gates in the binary addition if we do it directly. However it can be done with a bit more work.

We have to use the trick called three-for-two to remain in depth $O(\lg n)$.

  three-for-two binary addition:
  given three binary numbers $a,b,c$ we can compute two binary numbers $x,y$ such that
  $a+b+c = x+y$.

Another method is to use signed digit representation of integers where addition can be done in depth $O(1)$ and fan-in 2. (The idea is to use the flexibility that a number can be represented in more than one way to make sure that carries do not propagate).

See section 4 and exercise 4 in

David Mix Barrington and Alexis Maciel, "Advanced Course on Computational Complexity", lecture 6, IAS/PCMI, 2000.


If you only think of Booleans as 0 and 1, then it is natural to include them as subtypes of natural numbers and integers. But as soon as you start applying operations to them, then things start to fall apart.

Consider what happens when you define the + operation on Booleans. You have two choices:

Make + the same as OR, so 1+1=1. But then you have the problem that + on Booleans is no longer the same as + on Integers, which it should be.  More precisely, we have the following $(Integer)1_{Bool}+ (Integer)1_{Bool}\neq (Integer)(1_{Bool}+1_{Bool})$, where $1_{Bool}$ is true and $(Integer)\_$ is performing a cast from Bools to Integers. This means that there is a problem with coherence in the subtyping relation is we make this choice.
The second choice is to define + on Booleans so that 1+1=2. But now the operation takes you out of the world of Booleans. Semantically, this is not problematic ($\sqrt{-1}$ takes you out of the world of Real numbers), but it does suggest that you do not gain much by treating Booleans as numbers.

Generally, the way Booleans/Integers are treated in languages like C is that Integers can be used in places where Booleans are expected, which does not really follow the usual subtyping rules.

Ultimately, the operations you apply to Booleans are not the same as the ones you apply to Naturals and Integers, so, from the perspective of coherence, you should not really consider them to be related by subtyping.

Edit:
A third alternative, suggested by Peter Taylor in comments, is to make + be XOR. This results in the subtype relation boolean < short < integer < long, where + is addition-modulo-overflow. That's fairly natural, programmatically.


I believe that the notation AC first appears in Cook's "A Taxonomy of Problems with Fast Parallel Algorithms" from 1985. On page 11 (page 12 of the journal) we read:

  To state a more general form of this result we introduce the following terminology.

  Definition. $AC^k$, for $k=1,2,\ldots$, is the class of problems solvable by an ATM in space $O(\log n)$ and alternation depth $O(\log^k n)$.

This class is actually a uniform version of AC.

There follows an alternative characterization by Ruzzo and Tompa, appearing in a technical report by Stockmeyer and Vishkin, and later on in "Constant depth reducibility" by Chandra, Stockmeyer and Vishkin from 1984. They use the notation SIZE-DEPTH(poly, constant) (see page 3).

Cook goes on to mention another unpublished characterization by himself and Ruzzo. Further results due to Ruzzo are mentioned, including $AC^k \subseteq NC^{k+1}$ ("On uniform circuit complexity", Ruzzo, 1981). The latter paper (as well as Ruzzo's earlier paper also mentioned) doesn't contain the notation AC, but rather a myriad of other notations, emphasizing the notion of uniformity used.

All these papers mention alternating Turing machines a lot, giving credence to the hypothesis that A stands for alternating.


For $L$-Lipschitz functions on a metric space $(X,\rho)$ with $\epsilon$-packing number $M(\epsilon)$, the $\gamma$-shattering dimension is $M(2\gamma/L)$, as proved here:
http://ieeexplore.ieee.org/document/6867374/


No unconditional lower bound is known for any $k \geq 2$ in the multitape TM model (or any model stronger than it).

Ravi Kannan studied this problem in "Towards separating nondeterminism from determinism" (1984). In the process of trying to show $NTIME(n^k) \neq TIME(n^k)$ he managed to prove the following: there is some universal constant $c \geq 1$ such that for every $k$, $NTIME(n^k) \not \subseteq TIME-SPACE(n^k,n^{k/c})$. Here, $TIME-SPACE(n^k, n^{k/c})$ is the class of languages recognized by machines using time $n^k$ and space $n^{k/c}$ simultaneously. Clearly $TIME-SPACE(n^k,n^{k/c}) \subseteq TIME(n^k)$ but it is not known whether they are equal.

If you assume for some $k \geq 2$ that $NTIME(n^k) = TIME(n^k)$, you get interesting consequences. $P=NP$ is obvious, but it also implies that ${\sf NL} \neq {\sf P}$. This can be proved using an "alternation-trading" argument. Basically, for every $k$ and every language $L \in {\sf NL}$, there is a constant $c$ and some alternating machine that recognizes $L$ and makes $c$ alternations, guesses $O(n)$ bits per alternation, then switches to a deterministic mode and runs in $n^k$ time. (This follows, for example, from playing around with the constructions in Fortnow, "Time-Space Tradeoffs for Satisfiability" (1997).) Now if $TIME(n^k) = NTIME(n^k)$ then all these $c$ alternations can be removed with only a small amount of overhead, and you end up with a $TIME(n^k)$ computation that recognizes $L$. Hence ${\sf NL }\subseteq TIME(n^k) \neq {\sf P}$. Probably no such alternating simulation exists, but if you can rule it out, then you'll have the lower bound you seek. (Note: I believe that the above argument is also in Kannan's paper.)


Which cryptographic protocols are secure against quantum computer attacks?

"Quantum Computers" may give you significant speedup in many types of attacks.
These speedups may not necessarily be exponential like the current Shor's algorithm usage for breaking RSA.
You may find more information here: https://security.stackexchange.com/questions/116596/will-quantum-computers-render-aes-obsolete


It seems that this problem in full-generality is though. These two references might be helpful to you.

Here [1] the pure-state discrimination of MUBs is studied in a cryptographic set-up. The optimality of different  measurement schemes is rigorously discussed. It also includes a good bunch of useful references about distinguishability of pure quantum states.
For particular choices of pure-state ensembles the Pretty Good Measurement  is proven to be optimal in this task. This [2] is a nice exposition on this topic, although not focused on MUBs.

If you are interested in more restricted scenarios that the ones considered above, regard that there are some factors that influence the complexity of this problem. The following two are considered in several references:

The choice of quantum states to distinguish (in this case the choice of MUBs). This issue is important [3] to find efficient implementations of optimal POVMs.
The particular probabilities $p_{i,j}$ of receiving the $i$th state of the $j$th basis $B_k$ as an input [1][2] (in your notation).

Also, in cryptographic applications the next two seem to be relevant [1]:

If you are using this states to encode some information the particular functions used to encode and decode this information.
Other: ability to store qubits between measurements, some given knowledge about the bases used.

Hope it helps.


Quantum query complexity and certificate complexity

In the paper Negative weights make adversaries stronger, Lee, Spalek, and Hoyer give a function for which $ADV^{±}(f)= \Omega( ({C_0(f)C_1(f)})^{0.549})$, where $ADV^±$ denotes the general adversary lower bound. This lower bound has since been proved to characterize quantum query complexity.

This function is obtained by composing a function on a few bits bits with itself $d$ times. You get in the end $C_0(f)=C_1(f)=3^d$ and thus $C(f) \in o(Q_2(f))$.


Asking optimal questions to differentiate object in set

On the one hand, what you're asking sounds like binary search. On the other hand, the adaptivity makes it feel more like active learning: think of the "thing you're trying to learn" as a hypothesis and the "queries" as being labels of objects. Since this question is primarily about finding the right terminology, do look at the active learning literature and see if it captures the spirit of what you want.


What is the name of a graph with local clustering coefficients equal to zero?

As pointed out in comments by Joshua Grochow, this is a definition of triangle-free graph.


Can we confirm that 2-SAT can indeed be transformed into Horn-SAT in this manner?

Resolution in this context is broader than unit propagation, since a 2-CNF might not have any unit clauses. Instead resolution refers to the inference rule that given a pair of clauses $C = (x \vee y), \hat{C} = (\neg x \vee z)$ that contain a variable and its negation respectively, we can infer the new clause $(y \vee z)$. In addition, let $(x \vee x), (\neg x \vee \neg x)$ infer the empty clause $()$ which we will declare not satisfiable.

See here for an excellent explanation of why repeated application of this resolution rule will always lead to the empty clause iff the 2-CNF was unsatisfiable.

If the 2-CNF is satisfiable, then set $z_C = 1$ for every clause $C$ occurs in or that is inferred by resolution on the 2-CNF, and $0$ for every other clause. Every implication is satisfied, and every unit clause is satisfied. So the Horn formula is satisfied.

If the 2-CNF formula is unsatisfiable, then resolution will generate the empty clause. By the implications in the generated Horn formula, setting $z_C=1$ for each clause $C$ in the 2-CNF implies $z_{empty}=1$. But the unit clause $\neg z_{empty}$ prohibits this. Therefore, the Horn formula is unsatisfiable.


Density of answers for NP complete problems?

You are defining what is known as sparse sets. Mahaney's theorem states that sparse $NP$-complete (under Karp reduction ) sets exist if and only if $P=NP$. So, your theorem is just one direction of that theorem.


Counting words accepted by a regular grammar

For a DFA, in which the initial state is state $0$, the number of words of length $k$ that end up in state $i$ is $A^k[0,i]$, where $A$ is the transfer matrix of the DFA (a matrix in which the number in row $i$ and column $j$ is the number of different input symbols that cause a transition from state $i$ to state $j$). So you can count accepting words of length exactly $k$ easily, even when $k$ is moderately large, just by calculating a matrix power and adding the entries corresponding to accepting states.

The same thing works for accepting words of length at most $k$, with a slightly different matrix. Add an extra row and column of the matrix, with a one in the cell that's both in the row and the column, a one in the new row and the column of the initial state, and a zero in all the other cells. The effect of this change to the matrix is to add one more path to the initial state at each power.

This doesn't work for NFAs. I suspect the best thing to do is just convert to a DFA and then apply the matrix powering algorithm.


Let us consider your "base problem" and the special case of $p = 1/2$.

Assume that we are given a graph $G = (V,E)$ and a positive integer $k \le |V|$.

Construct an instance of your problem as follows:

Our "alphabet" is $A = V \cup \{ 0,1,\dotsc,k-1 \}$.
The sets $s_i$ are indexed with $i \in I = E \cup \{ \bot \}$.
For each $e = \{u,v\} \in E$ we have $s_e = \{ 1,2,\dotsc,k-1, u, v\}$.
We also define $s_\bot = \{ 0,1,\dotsc,k-1 \}$.

Observations:

There is a trivial solution $s$ of size $2k-2$: just take a subset $s \subseteq A$ with $\{1,2,\dotsc,k-1\} \in s$ and $|s| = 2k-2$. Clearly $|s \cap s_i| \ge k-1$ for all $i$.
There cannot be a solution of size $2k+1$ or larger: it would imply $|s \cap s_\bot| > k = |s_\bot|$, a contradiction.
If there is a solution $s$ of size $2k-1$, we can pad it with an arbitrary element to obtain a solution of size $2k$.

Hence the key question is whether there exists a solution $s$ of size $2k$.

Assume that we have a solution $s$ of size $2k$. Then $s_\bot = \{0,1,\dotsc,k-1\} \subseteq s$. Hence $s = \{0,1,\dotsc,k-1\} \cup X$, where $X \subseteq V$ and $|X| = k$. Moreover, if $e = \{u,v\} \in E$, we must have $|s \cap s_e| \ge k$, which implies $e \cap X \ne \emptyset$. That is, $X$ is a vertex cover of size $k$.
Conversely, if we have a vertex cover of size $k$, we can construct a solution of size $2k$.

Hence it is NP-hard to find an optimal $s$. The same idea can be used to show that the problem is hard for any $0 < p < 1$.

Edit: Now a natural question is whether there is an approximation algorithm – for example, can one always find a feasible solution $s$ that is within a constant factor of the largest feasible solution.

However, this does not seem to be the case. It seems that it is actually NP-hard to find any non-trivial solution (i.e., a solution $s \ne \emptyset$), at least for certain values of $p$. The construction is a bit messy, though, but I can try to work out the details if needed.

Anyhow, it seems that to get anything positive (with provable performance guarantees), you need to relax your constraints a bit.


What kind of answer does TCS want to the question "Why do neural networks work so well?"

There are a bunch of "no free lunch" theorems in machine learning, roughly stating that there can be no one master learning algorithm that performs uniformly better than all other algorithms (see, e.g., here http://www.no-free-lunch.org/ ). Sure enough, deep learning can be "broken" without much difficulty:
http://www.evolvingai.org/fooling

Hence, to be provably effective, a learner needs inductive bias --- i.e., some prior assumptions about the data. Examples of inductive bias include assumptions of data sparsity, or low dimensionality, or that the distribution factorizes nicely, or has a large margin, etc. Various successful learning algorithms exploit these assumptions to prove generalization guarantees. For example, (linear) SVM works well when the data is well-separated in space; otherwise -- not so much.

I think the main challenge with deep learning is to understand what its inductive bias is. In other words, it is to prove theorems of the type: If the training data satisfies these assumptions, then I can guarantee something about the generalization performance. (Otherwise, all bets are off.)

Update (Sep-2019): In the two years since my posted answer, there has been a great deal of progress in understanding the inductive bias implicit in various DL and related algorithms. One of the key insights is that the actual optimization algorithm being used is important, since uniform convergence cannot explain why a massively over-parametrized system such as a large ANN manages to learn at all. It turns out that the various optimization methods (such as SGD) are implicitly regularizing with respect to various norms (such as $\ell_2$). See this excellent lecture for other examples and much more:
https://www.youtube.com/watch?v=zK84N6ST9sM


"Directed" problems that are easier than their "undirected" variant.

Counting Eulerian circuits for directed graphs is doable in polynomial time using the BEST theorem, while apparently, the same problem for undirected graphs is #P-complete.


This is true as long as you're only reducing towards a weak head normal form. But if you want to go further, you start reducing under lambdas. If you're looking at the pure lambda-calculus (typed or not), you must be reducing under lambdas if you're reducing closed terms. And when you're reducing under lambdas, you're no longer operating on closed terms.

Here's an example that starts with a closed lambda-term where all binding sites use unique names, proceeds to a term with repeated but non-capturing binders, then reaches a term with capture, which requires alpha-conversion to proceed. The initial term is not simply-typed, but you can remedy this by changing it to $(\lambda w. (\lambda z. w z z) (\lambda x. \lambda y. x y))$ which is simply-typed and shows the same binding-related issues.

$$
\begin{array}{rl}
(\lambda \underline{z}. \underline{z} \underline{z}) \underline{(\lambda x. \lambda y. x y)}
\quad \to &
(\lambda \underline{x}. \lambda \color{blue}{y}. \underline{x} \color{blue}{y}) \underline{(\lambda x. \lambda \color{red}{y}. x \color{red}{y})}
\\ \to &
(\lambda \color{blue}{y}. (\lambda \underline{x}. \lambda \color{red}{y}. \underline{x} \color{red}{y}) \underline{\color{blue}{y}})
\\ \to &
(\lambda \color{blue}{y}. \lambda \color{red}{y}. \color{blue}{y} \color{red}{y})
\end{array}
$$

That last step requires alpha-conversion, to make the blue $y$ and the red $y$ distinct.

Your proof sketch is correct as long as you apply the beta rule in a context that does not bind any variable. If you extend the proof to the lambda context case, it fails when $x$ is in the context.


Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

The problem you have described is fully dynamic DAG reachability (also referred to as fully dynamic transitive closure on DAGs).
It's called fully dynamic since people also study the versions where only deletions are possible (then it's called decremental reachability), and where only insertions are possible (called incremental reachability).

There are a few tradeoffs between the update time and the query time. Let $m$ be the number of edges and $n$ the number of vertices.
For DAGs, Demetrescu and Italiano (FOCS'00) gave a randomized data structure which supports updates (edge inserts or deletes) in O($n^{1.58}$) time and reachability queries in O($n^{0.58}$) time (node inserts/deletes are also supported, in O(1) time); this result was extended by Sankowski (FOCS'04) to work for general directed graphs. Also for DAGs, Roditty (SODA'03) showed that you can maintain the transitive closure matrix in total time O($mn+I·n^2+D$), where $I$ is the number of insertions, $D$ the number of deletions and of course the query time is O($1$).

For general directed graphs, the following (update, query) times are known:
(O($n^2$), O(1)) (Demetrescu and Italiano FOCS'00 (amortized), Sankowski FOCS'04 (worst case)), (O($m\sqrt{n}$), $O(\sqrt{n}$)) (Roditty, Zwick FOCS'02), (O($m+n\log n$), O($n$)) (Roditty, Zwick STOC'04), (O($n^{1.58}$),O($n^{0.58}$)) and (O($n^{1.495}$),O($n^{1.495}$)) by Sankowski (FOCS'04).

Obtaining a polylogarithmic query time, without increasing the update time too much is a major open problem, even for DAGs.


What's the relationship between "free theorems" and "free objects"

There is no relationship.  They both use the word "free", but with different meanings of the word "free".  It's just an accidental collision, which will happen when you have a language like English with a fixed number of words and the number of concepts we want to talk about exceeds the number of words in the language.

A free group is, roughly, a group that is about as generic as possible (it has no special structure).  Here, the word free means "having no non-trivial strucutre", i.e., free of special equalities.

In contrast, a free theorem about some code (e.g., a function) is one that follows automatically from the type signature of that code.  Here, the word free means "at no cost" or "with no extra reasoning about the code required"; it's an automatic consequence of the type signature, regardless of the implementation/code of the function.


Number of SAT checks that are needed to find all combinations of subset of boolean variables of a propositional formula

If you really want to enumerate all the assignments, then you really need to find a satisfying assignment and then block it by a clause. E.g. if you find a satisfying assignment $a_1=a_2=a_3=0$ you'd block it by $a_1\lor a_2\lor a_3$.

One, relatively easy improvement, is to reduce the found assignment to a (prime) implicant. For instance, if $a_1\rightarrow f$, then you know that all assignments with $a_1=1$ are satisfying ($a_1$ is an implicant). You can reduce an existing satisfying assignment to an implicant by throwing one variable at a time. Similar approach published first (I think) here [1].

Somewhat more general problem is quantifier elimination, i.e. you're given $\exists X. f$ with some free variables $Y$, where $X$ and $Y$ are sets of variables. The output is a formula $f'$ that has only free variables $Y$ and has the same set of satisfying assignments as $\exists X. f$. Some recent  papers on the problem [2][3].
(am a coauthor of the [3]).

[1] McMillan: Applying SAT Methods in Unbounded Symbolic Model Checking. CAV 2002

[2] Goldberg,Manolios: Quantifier elimination via clause redundancy. FMCAD 2013

[3] Klieber et: al Solving QBF with Free Variables. CP 2013


Best resources for string searching or pattern matching exercises

Are you already familiar with the main algorithms in the area? Are you familiar with this site a huge and well-maintained list of references in pattern matching?

I don't see how one could come up with a list of exercised for string matching, except "implement all main approaches and test them on a lot of data". And data is really easy to come by: you can grab any text file and it will do (you can create a positive example by seeking to a random location in the text file and getting n characters, and for a negative example any random string will do).

I'd read up on KMP, Boyer-Moore, automata methods, and the naive algorithm and implement them, and then think about the problem trying to make your algorithms faster.

There is a huge literature in the area, of course, and the first link I posted can steer you in that direction.


When replacing an edge with a graph gadget preserves graph isomorphism?

Just a summary of my (very informal / wrong?) comments/ideas above:

Every connected gadget $GA$ with two or more nodes, that doesn't introduce an asymmetry between $u$ and $v$ should be fine. In other words suppose $maxdeg(GA)=n$, and that $X$ is a star with a central node $x$ and $n+1$ leaves, $Y$ is a star with a central node $y$ and $n+2$ leaves.

The $GA$ preserves isomorphism if and only if the two graphs $X \cup GA \cup Y$, in which $x$ is replaced with $u$ and $y$ is replaced with $v$, is isomorphic to the graph $Y \cup GA \cup X$ in which $y$ is replaced with $u$ and $x$ is replaced with $v$.

This construction can also be used to check if a small fixed $GA$ preserves isomorphism.

Furthermore, the problem of deciding if $(GA,u,v)$ preserves isomorphism is GI-complete: given two graphs $G_1,G_2$; build the following gadget $GA$: add 4 new nodes $u,x,y,v$ and edges $(u,x),(x,y),(y,v)$, then add an edge from $x$ to all the nodes of $G_1$ and an edge from $y$ to all the nodes of $G_2$. $G_1,G_2$ are isomorphic if and only if $GA$ preserves isomorphism.


The complexity of comparing a power to some threshold

The problem is decidable in polynomial time (in fact, in uniform $\mathrm{TC}_0$). We can recast the question as follows: given positive integers $a,b,c,d,e$, find the sign of
$$\Lambda=e\log(a/b)-\log(c/d).$$
First, note that we can test whether $\Lambda=0$: if we assume w.l.o.g. that $\gcd(a,b)=\gcd(c,d)=1$, then $da^e=cb^e$ implies $a^e\mid c$ and $b^e\mid d$; in particular, apart from the trivial case $a=b=1$, equality can hold only if $e\le\max\{\log c,\log d\}$, in which case we can evaluate $a^e,b^e$ in polynomial time.

Likewise, we can rule out the case when $(a/b)^{e_1}=(c/d)^{e_2}$ for some positive integers $e_1,e_2$. The argument above shows that if this is the case, then $e_1,e_2\le\max\{\log a,\log b,\log c,\log d\}$, hence we can find $e_1,e_2$ by brute force in polynomial time, and then it suffices to compare $e$ with $e_1/e_2$.

Thus, suppose $a/b$ is not a rational power of $c/d$, which implies $\Lambda\ne0$. Write $\alpha_1=a/b$, $\alpha_2=c/d$, $\lambda_1=\log\alpha_1$, $\lambda_2=\log\alpha_2$, $\beta_1=e$, $\beta_2=-1$. Note that the logarithmic height $h(\alpha_1)=\max\{\log a,\log b\}$, $h(\alpha_2)=\max\{\log c,\log d\}$, and $\lambda_1,\lambda_2$ are linearly independent over $\mathbb Q$. By some version of Baker’s theorem (e.g., the “explicit result by Baker and Wüstholz” in http://en.wikipedia.org/wiki/Baker%27s_theorem#Statement), we have

$$\log\lvert\Lambda\rvert>-Ch(\alpha_1)h(\alpha_2)\log\beta_1$$

for some constant $C$ (note that in the statement given in the link, we have $n=2$ and $d=1$, hence $C$ is really independent of the input data). The number on the right-hand side is polynomial in the length of the input, and it thus suffices to approximately evaluate $\Lambda$ with polynomially many bits of precision, which can be done by standard numerical algorithms in polynomial time.

(If you want to look for more information, the keyword is “linear forms in logarithms”.)


Using negative results to prove positive results in computability theory

In some sense, this is what the theory of parametricity is all about.

Data abstraction is how we ensure that no client of a module can access the elements of a module except according to the interface exposed by the module.
We rely on this to ensure that the internal invariants of data structures cannot be broken by the clients of a module -- eg, if you access a balanced tree only via the published interface, then it follows that the tree will always be balanced.

So we use a negative property -- that no possible client can break the abstraction boundary -- to deduce a positive one -- that the data representation invariant always holds.


Models of computation strictly between classical and quantum in terms of query complexity

One easy way to come up with such a model is to first create a restricted model of quantum computation that can still do something non-classical, and then just give it classical computation for free.

An examples of this strategy is the one clean qubit model (along with a BPP machine). Some references: On the Power of One Bit of Quantum Information, Computation with Unitaries and One Pure Qubit and Estimating Jones polynomials is a complete problem for one clean qubit.

Another example would be to have a log-depth (or polylog depth) quantum circuit with access to a classical computer. This will yield something like $BPP^{BQNC}$.


graphs where vertex coloring is in P but independent set is NP complete

Supposedly the reference "NP-complete problems on a 3-connected cubic planar graph and their applications" by Uehara (a paper I haven't actually seen) proves that independent set is NP-complete even for triangle-free planar graphs. But by Grötzsch's theorem they are always 3-colorable, and testing for smaller numbers of colors than 3 is easy in any graph, so they can be optimally colored in P.

Circle graphs have the opposite property: for them, coloring is NP complete but the independent set problem is easy.


Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems?

There has been various brand of work for formalizing such tricky code. The one I know about are (but I'm no expert on the topic):

using "temporal logic" to study distributed systems; one important tool beeing the TLA+ tool is a program that verifies properties of specifications expressed in temporal logic; googling for "TLA+ dining philosopher" links to this 2007 PhD thesis (PDF) that has a TLA specification of the dining philosophers on page 24
using "concurrent separation logic" to verify implementation of concurrent programs, including rather low-level primitives. See for example the 2014 paper GPS: Navigating Weak Memory with Ghosts, Protocols, and Separation by  Aaron Turon, Viktor Vafeiadis and Derek Dreyer has correctness proofs for lock-free queues, circular buffers and "ticket locks", implemented in C using the C11 atomic concurrency pri


What are TCS conjectures that were proved for primes and small values but then turned out to be false?

Note: This is more like an extended comment than an answer.

Here is a problem from combinatorics whose status is similiar in flavor to that of Evasiveness Conjecture:

  Background. A Latin square of order $n$ is an $n × n$ matrix in which each element from {1, . . . , n} occurs exactly once in each row and column. Two Latin squares of order $n$ are said to be orthogonal if you get $n^2$ distinct ordered pairs when you superimpose them. A set of Latin squares are said to
  be mutually orthogonal if every pair of them are orthogonal. Let $N(n)$
  denote the maximum number of mutually orthogonal Latin squares of order
  $n$.

It is known that $N(n)\leq n-1$ for all $n$. If $n$ is a prime power then we know that $N(n)=n-1$, but for general values of $n$ the status of lower bounds is wide open.


Complexity of smooth non-linear functions

Note that proving that evaluation of $f$ takes at least as much time as integer multiplication only shows that it needs time $\Omega(M(n))$; while this is generally assumed to be at least $n\log n$, no superlinear bound has been proven. (However, I disagree that this wouldn’t yield anything nontrivial, as was formerly stated in Joshua Grochow’s answer. For one thing, there are plenty of analytic functions such as exp, log, sin where this $\Omega(M(n))$ bound is close to optimal up to one more logarithmic factor. For another thing, we normally regard a proof of NP-completeness of some problem as a strong evidence that it is hard, despite that with the current state of knowledge it doesn’t imply any superlinear lower bound either.)

As pointed out by Joshua Grochow, you cannot say anything useful about the complexity of evaluation of analytic functions at integers. The correct statement you are looking for is that approximation of smooth functions on short real intervals is at least as hard as integer multiplication. This indeed follows from Taylor expansion, though in full generality there are some messy details where the devil is (in particular, we a priori know nothing about the coefficients of the Taylor series).

As usual in this context, it is convenient to restrict attention to time bounds obeying some basic regularity conditions. Let me say that $T(n)$ is a reasonable bound if $T$ is nondecreasing, and
$$c_1T(n)\le T(2n)\le c_2T(n)$$
for some constants $1<c_1\le c_2$. Commonly encountered bounds of polynomial growth involving powers of $n$, $\log n$, and similar, are all reasonable.

In order to avoid issues with representation of real numbers, we will only considered real functions on bounded intervals. An $n$bit approximation of $x$ is then a dyadic rational $x'$ written in the usual binary notation with $n$ bits after the radix point, such that $|x-x'|\le2^{-n}$. A function $f\colon[a,b]\to\mathbb R$ can be computed in time $T(n)$, if given a dyadic rational $x\in[a,b]$ with $n$ bits after the radix point, we can compute in time $T(n)$ an $n$bit approximation of $f(x)$.

  Proposition: If $T$ is a reasonable bound, and $f\colon[u,v]\to\mathbb R$ (where $u<v$ are real) a nonlinear $C^3$ function that can be computed in time $T(n)$, then multiplication of $n$bit integers can be computed in time $O(T(n))$.

Proof:

Note that any Turing machine computing $f$ must read the whole input (at least for some inputs of every length $n$), thus we must have $T(n)\ge n$.

Since $f''(x)$ is continuous and not constantly $0$, we can find $x_0\in(u,v)$ of the form $x_0=k2^{-l}$ such that $f''(x_0)\ne0$. Since $f(x_0+x)$ is also computable in time $O(T(n))$, we can assume that $u<0<v$ and $f''(0)\ne0$. Likewise, $f(2^{-l}x)$ is computable in time $O(T(n))$ for fixed $l$, hence we may in fact assume $[u,v]=[-1,1]$.

By Taylor’s theorem, we have
$$|a_0+a_1x+a_2x^2-f(x)|\le M|x|^3,\qquad x\in[-1,1],$$
for some constants $a_0,a_1,a_2,M\in\mathbb R$, where $a_2\ne0$. We can compute $f(x)-a_0$ in time $O(T(n))$ by subtracting an $(n+1)$bit approximation of $a_0=f(0)$ from an $(n+1)$bit approximation of $f(x)$, hence we can assume $a_0=0$.

Then we can also compute $a_1x$ in time $O(T(n))$ using a $(2n+m)$-bit approximation of $f(2^{-(n+m)}x)$, where $m$ is a suitable constant: we have
$$|2^{n+m}f(2^{-(n+m)}x)-a_1x|\le|a_2|2^{-(n+m)}|x|^2+M2^{-2(n+m)}|x|^3
\le(|a_2|+M)2^{-(n+m)},$$
hence it is enough to take $m>\log_2(|a_2|+M)+1$. This means we can compute $f(x)-a_1x$, hence we can as well assume $a_1=0$.

Using the same trick once more, we have
$$|2^{2(n+m)}f(2^{-(n+m)}x)-a_2x^2|\le M2^{-(n+m)},$$
hence we can compute $a_2x^2$ on $x\in[-1,1]$. By scaling, we can compute it on any fixed bounded interval, and we can also compute
$$a_2xy=\tfrac14\bigl(a_2(x+y)^2-a_2(x-y)^2\bigr).$$
Now we need to get rid of the $a_2$ factor. Since
$$xy=a_2x(a_2ya_2^{-2}),$$
it is enough to compute the constant $a_2^{-2}$ (meaning, given $n$ in unary, compute an $n$bit approximation of $a_2^{-2}$ in time $O(T(n))$). This can be done with Newton iteration: $a_2^{-2}$ is the unique root of the function $g(x)=1-(a_2^2x)^{-1}$. Thus, if $x_0$ is a suitable good appromixation to $a_2^{-2}$, the sequence given by
$$x_{k+1}=x_k-\frac{g(x_k)}{g'(x_k)}=2x_k-a_2^2x_k^2=2x_k-a_2x_k(a_2x_k1)$$
converges quadratically to $a_2^{-2}$. In order to approximate $a_2^{-2}$ to $n$ bits, we need $O(\log n)$ iterations; the final iteration needs to be computed with $n$ bits of precision, the last but one with $n/2$ bits, and so on, hence the total time is linear in
$$T(n)+T(n/2)+T(n/4)+\cdots\le(1+c_1^{-1}+c_1^{-2}+\cdots)T(n)=O(T(n)).$$
Thus, we can approximate $xy$ for $x,y\in[0,1]$ to $n$ bits of precision in time $O(T(n))$. Then we can multiply two $n$bit integers by scaling them to $[0,1]$, approximating the product, and scaling back.


Let your original state machine $M(k)$ have $n$ states and transition relation $t(s,s')$, where each transition $t(s,s')$ updates the global variables $x_1,...,x_k$ by applying function
$(x'_1,...,x'_k) = f_{t(s,s')} (x_1,...,x_k)$.
Then $M(k)$ is equivalent to a standard FSM with $n(2r+1)^k$ states, where each state encodes a tuple $(s,x_1,...,x_k)$ with each $x_i$ encoding one fixed value in $[-r,r]$, and new transition relation $t'$

$t'( (s,x_1,...,x_k), (s',x'_1,...,x'_k)) \Leftrightarrow t(s,s') \wedge [(x'_1,...,x'_k) = f_{t(s,s')} (x_1,...,x_k)]$.


Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

This is less of a mathematical answer than a philosophical one, but I prefer to think of a RAM model that allows constant-time manipulation of integers with some number B of bits that is unknown but at least as large as $\log_2 S$, where S is the amount of space that the algorithm requires. Because, if the integers weren't that big, how could you even address your memory? For polynomial time and space algorithms it's the same as O(log n) bits, but for exponential space algorithms it avoids the problem.

Of course, if S exceeds the amount of memory you actually have, your algorithm won't run at all. Or, it will run by paging information into and out of memory and you should be using a memory hierarchy model instead of the RAM model.


Does the Hindley-Milner type system (i.e. STLC with prenex polymorphism) have a category-theoretic model?

Apart from what's already written in the slides you linked to, let me describe one possible approach.
For studying type inference semantically we need a model in which a term can have many types, or none. This naturally leads to Curry-style typing, i.e., we think of $t : A$ as a relation where both the term $t$ and the type $A$ are meaningful by themselves. (The opposite is Church-style typing where a term is always formed together with its type, and it cannot stand on its own.)
We can proceed as follows:

Give a model of untyped terms, such as a model of the untyped $\lambda$-calculus.
Give a model of types.
Define a "has type" relation between terms and types.

A concrete well-known example of this are PER models (although they model entire System F, not just Hindley-Milner):

Consider any model of the untyped calculus, for example, a reflexive domain $D$.
The types are the partial equivalence relations on $D$ (symmetric transitive relations on $D$).
$t \in D$ has type $T$ when $(t,t) \ni T$.

PERs have a rich structure (they form a CCC), for instance the exponential of $S$ and $T$ is the PER $S \Rightarrow T = \{(f,g) \in D \times D \mid \forall (x,y) \in S . (f x, g y) \in T\}$. This is all well-known.
Polymorphism in this model amounts to taking intersection of partial equivalence relations. For instance, $\lambda x . x$ has type $T \Rightarrow T$ for every PER $T$, and so it also has the type $\bigcap_{X \in \mathsf{PER}(D)} (X \Rightarrow X)$, which is the interpretation of $\forall \alpha . \alpha \to \alpha$.
You'll have to find something more nuanced to capture Hindley-Milner without capturing System F. That's what Kammar and Moss set out to do.


Non-isomorphic minimal non-deterministic finite automata

See the paper (postscript)

Arnold, Dicky, Nivat. A note about minimal non-deterministic automata


Finding the shortest path in the presence of negative cycles

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem.  If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.


Hardness of additive approximation to Graph Coloring problem.

Let $G$, with $\chi(G) \geq 3$ (otherwise you have an exact algorithm).

Now construct a graph $H$ consisting of $k$ copies $G_1,\ldots,G_k$ of $G$, with all possible edges between $u$ and $v$ for $u \in G_i$, $v \in G_j$, $i\not=j$.

Now use the additive constant algorithm for the graph $H$, which will find a coloring of, at most, $k\cdot\chi(G) + k$ colors. Since the colors in each copy of $G$ will be distinct, by the Pigeonhole principle, you have one of the copies with at most $\chi(G)+1$ distinct colors, which is better than a 2-approximation.


Understanding efficient classical simulation of quantum computing

Brief (negative) answer

This claim is incorrect as soon as you have three (or more) qubits, as shown by the GHZ paradox, briefly described below, which shows a 3-partite Bell inequality which is beaten by a state stabilized by Pauli operators, which can be prepared and measured by Clifford operations. This paradox is named after Greenberger, Horne and Zeilinger, who found it in 1989 (2007 arXiv reprint here).

The point is that the Gottesman-Knill theorem does not care about locality, but on simplicity. The Gottesmann-Knill theorem (wiki, arXiv) gives a polynomial hidden variable theory for a state constructed with Clifford gates. Nothing prevents this theory to be nonlocal, as the GHZ state shows, but its complexity is bounded : a $n$-qubit state is described by $2n²$ binary hidden variables.

On the other hand Bell inequalities characterize local hidden variable theories, without taking care of their complexity. The violation of a Bell inequality by the GHZ states means that it cannot be described by a model where each player has access to a different local hidden variable.

Details of the GHZ paradox

The paradox can be explained by the following game, with 3 cooperating players and a referee. the referee asks a question, either $X$ or $Y$ to each player, which answers ±1 without communicating with the other players. The referee either asks $X$ to all the players or asks $X$ to one of them and $Y$ to the others. The players win if the product of their answers obeys the equality below corresponding to the question asked:
$$\begin{align}
XXX&=+1\\XYY&=-1\\YXY&=-1 \\YYX&=-1
\end{align}$$
It is easy to see that the above set of equation is not consistent, and tha no local hidden variable theory allows to win the game with a probabiliyt greater than 3/4.

On the other hand, if each of the player has a qubit of a GHZ state $|\mathrm{GHZ}\rangle:=(|000\rangle+|111\rangle)/\sqrt2$, they can win with certainty. Indeed, $|\mathrm{GHZ}\rangle$ is stabilized by the following Pauli operators :
$$\begin{align}
S_0&=+XXX\\S_1&=-XYY\\S_2&=-YXY \\S_3&=-YYX.
\end{align}$$
Therefore, measuring the Pauli operators corresponding to the referee’s question allows the players to always win the game, and therefore violate a Bell inequality with certainty. Furthermore, this state can be prepared from Clifford operations, which invalidates the idea expressed in the paragraph you cite.


Are there published algorithms for on-line creation of AVL trees from ordered streams?

If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that location.


Hardness of finding if a vertex lies on a simple directed path between two vertices

I just found a reduction from the two disjoint paths problem. Given a directed graph $G = (V, E)$ and two pairs $(s_1, t_1)$ and $(s_2, t_2)$, we can add a new vertex $w$ to the graph and an edge from $t_1$ to $w$ and from $w$ to $s_2$.

The new graph admits a simple path from $s_1$ to $t_2$ through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$.


Where is $MA$ more relevant than $\exists BPP$?

$\def\mr{\mathrm}$First, standard derandomization assumptions (the existence of a language in $\mr E$ that requires circuit size $2^{\Omega(n)}$) imply $\mr{promise\text-BPP=promise\text-P}$, hence
$$\mr{MA=\exists BPP=NP},$$
thus any difference between the two classes is likely just an artifact of our incomplete knowledge.
Having said that, there are several results in complexity theory involving $\mr{MA}$ that are not known to hold for $\exists\mr{BPP}$. In particular, there is a group of results of the form
$$\begin{align*}
\mr{PP\subseteq P/poly}&\implies\mr{PP=MA},\\
\mr{PSPACE\subseteq P/poly}&\implies\mr{PSPACE=MA},\\
\mr{EXP\subseteq P/poly}&\implies\mr{EXP=MA},\\
\mr{NEXP\subseteq P/poly}&\implies\mr{NEXP=MA}.
\end{align*}$$
(The first three results are due to Babai, Fortnow & Lund, the last one is due to Impagliazzo, Kabanets & Wigderson.)
If you allow me larger time bounds, an often quoted related result is that
$$\mr{MA\text-EXP\nsubseteq P/poly}$$
(here, $\mr{MA\text-EXP=MA\text-TIME}(2^{n^{O(1)}})$ is the exponential analogue of $\mr{MA}$). In fact, this result can be improved, nevertheless it is not known to be true for $\mr{NEXP^{BPP}}$ (which is the exponential analogue of $\exists\mr{BPP}=\mr{NP^{BPP}}$).


The meaning of: a program P posseses a property R

I cannot see the article and have to guess. The text makes clear that they are using the symbol $\supset$ as notation for implication. So you could read it as

  In order to prove that a program $P$ possesses a property $R$, one has only to prove the implication
  $W(P) \implies R$.

See the Wikipedia page on material implication for other notation for implication.


The problem is in RP in both (A) and (B) by a variation of Lovasz's algorithm:
Fix a finite field $F$ of characteristic $2$ on at least $q=4m\max_i |a_i|$ elements.
Consider the graph's Tutte matrix $T(r)$ where you replace indeterminate $x_{ij}$ by $y_{ij}r^{a_{ij}+q/4}$, where $y_{ij}=y_{ji}$ is a uniformly and independently randomly chosen element in $F$ and $r$ is an indeterminate. Now observe that the determinant equals $\sum_{\mbox{Matching }M} \prod_{ij\in M} y_{ij}^2r^{2a_{ij}}$.
Hence, you can solve for the coefficient of $r^{q/2}$ in the polynomial $\operatorname{det} T(r)$ to see if there is a zero-sum matching. Compute the determinants of the numerical matrices $T_r$ obtained after replacing $r=1,2,\ldots, q$ in $T(r)$, and use interpolation to recover the coefficient. It is non-zero with probability at least $1-m/q$ if and only if the graph had a zero-sum matching.
Update: In (C) the problem is NP-complete.
Consider an instance $b_1,b_2,\ldots, b_n$ and $t$ to Subset Sum, i.e. is there a subset $I\subseteq [n]$ such that $\sum_{i\in I} b_i=t$?
We can embed this in a Zero-sum matching problem as follows. Consider the bipartite graph with biadjacency matrix $\begin{bmatrix}I_n & I_n & 0\\I_n & I_n & 0\\0 & 0 & 1 \end{bmatrix}$, where $I_n$ is a $n\times n$ identity matrix, and weights $\begin{bmatrix}B & 0_n & 0\\0_n & 0_n & 0\\ 0& 0 & -t \end{bmatrix}$
where $0_n$ is a $n\times n$ all-zero matrix and $B=\operatorname{diag}(b_1,b_2,\ldots,b_n)$ is a $n\times n$ diagonal matrix.
Now observe that there is a zero-sum perfect matching if and only if there is a solution to the Subset Sum instance.


Generalized geography on solid grid graphs

Just to complete my comment:

GG remains PSPACE-complete on planar bipartite directed graphs with maximum degree 3 (see
D. Lichtenstein, M. Sipser: GO Is Polynomial-Space Hard. J. ACM 27(2): 393-401 (1980) )

But (vertex) GG on undirected graphs is in P (see this Q&A and this paper) so it is in P also for grid graphs.

For directed solid grid graphs I didn't find any reference, however, I think there is an easy way to simulate a planar bipartite directed graph; the following idea should work:

Both the "diamond" structure (A) and the crossover gadget (C), can be converted into an equivalent (directed) solid grid graph gadget (B) and (D).


Function that is guaranteed to be one-way if one-way functions exist?

Yes, such a function was found by Levin himself, published somewhat recently:

The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.


Finding a biased coin using a few coin tosses

The following is a rather straight-forward $O(n \log n)$ toss algorithm.

Assume $1-\exp(-n)$ is the error probability we are aiming for. Let $N$ be some power of $2$ that is between say $100n$ and $200n$ (just some big enough constant times $n$). We maintain a candidate set of coins, $C$. Initially, we put $N$ coins in $C$.

Now for $i=1,\dots,\log N$, do the following:
Toss each coin in $C$ for $D_i = 2^i  10^{10}$ times (just some big enough constant).
Keep the $N/2^i$ coins with most heads.

The proof is based on a couple of Chernoff bounds. The main idea is that we half the number of candidates each time and thus can afford twice as many tosses of each coin.


Sample complexity for learning Boltzmann Distribution parameters

Under appropriate smoothness conditions (satisfied by the Boltzmann distribution), the maximum likelihood is asymptotically normal. Meaning: the vector $\sqrt n(\theta-\hat\theta)$ will have approximately normal distribution, with mean $0$ and covariance matrix given by the inverse Fisher matrix, see Section 9 here:
http://www.stat.cmu.edu/~larry/=stat705/Lecture9.pdf


Regular expressions without union but with backreferences

If you are allowed to use complementation to express $\Sigma^*$ as $\emptyset^{C}$, the resulting language class includes the pattern languages (see, e.g., this survey by Kai Salomaa).

As shown by Angluin, the membership problem for pattern languages is NP-complete. (This holds even if you consider pattern languages that are generated by patterns that do not contain terminal symbols.)

So, membership for this class is as hard as for the full class of regular expressions with backreferences.


Inherent limitation of Switching Lemma for finer lower bounds

I think you can't beat the $\exp(n^{\Omega(1/d-1)})$ lower bound. Here's a construction that should work for computing parities:

In order to compute parity of $n$ variables, partition them into groups of size $t \approx n^{1/d}$, compute parity of each group and recursively compute the parity of parities. That is, start with a parity tree of fan-out $t$. The depth of this tree would be $d$.

Then, replace each parity gate with a CNF or DNF or size $\approx \exp(t)$. This way you get a circuit of depth $2d$. It is possible to alternate between CNFs and DNFs at different levels so the circuit collapses to depth $d$. This way you get a depth $d$ circuit of size $\approx \exp(n^{1/d})$ that computes the parity of $n$ bits.

Now, since switching lemma is tight for the parity function, you shouldn't hope to get a better lower bound for more sophisticated functions just relying on that.


What you're asking for has been called "correlated product" security for a trapdoor function.  See this paper by Rosen and Segev, which lays out the definition.  Your question fixes $k$ from their Definition 3.2 to $2$;  as you (and their paper) note, we know that the RSA trapdoor function with exponent $e\leq k$ is not correlated-product secure.

I don't know how to give a reduction to plain RSA to prove what you want, and I'd guess that it's very hard.  The best I can think of is to try to prove this under the so-called Phi-hiding assumption (see Cachin, Micali, Stadler, Eurocrypt'99, or reference below).  This may follow by combining Theorem 3.3 of 1 (which says that a lossy trapdoor function is correlated-product secure) with Section 5 of this this paper by Kiltz, O'Neill, and Smith that shows the RSA function is lossy under that assumption.  I haven't checked that the parameters works out, though.


Fitting minimum number of rectangles of width/height 1 into a 2D grid

Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a reduction to maximum independent sets in bipartite graphs. But I think this one is also polynomial, via a different reduction to the same problem.

Draw a graph $G$ that has a vertex for every unit-length line segment that separates two squares of $P$, and that has an edge connecting the vertices for every two perpendicular line segments that share an endpoint. Then the partitions of $P$ into unit-width rectangles correspond one-for-one with independent sets of $G$. If a vertex $v$ of $G$ corresponds to a line segment $s$, then $v$ belongs to a given independent set exactly when the two squares separated by $s$ belong to the same rectangle as each other in the corresponding partition.

Under this correspondence, we have the equation $R=S-I$ where $R$ denotes the number of rectangles in a given partition, $S$ denotes the number of squares in $P$, and $I$ denotes the cardinality of the independent set; this is easy to see by induction on $I$, by removing one independent set element at a time. Since $S$ is fixed, minimizing $R$ is the same as maximizing $I$, and the optimal partition of $P$ corresponds to the maximum independent set of $G$. But $G$ is a bipartite graph (horizontal segments are adjacent only to vertical segments and vice versa) so its maximum independent set may be found in polynomial time (see König's theorem on Wikipedia).


I think the idea of unifying type and term-level fixpoints is natural, though I have to admit I'm not sure that reducing the number of constructions of a system is not always a recipe for conceptual simplicity.

One source I have for a system that takes this approach is the $\Pi\Sigma$ system:

$\Pi\Sigma$: Dependent Types Without the Sugar, Altenkirch, Danielsson, Löh and Oury.

You might also want to look at these slides by Khulmann on equi-recursive types versus iso-recursive types: equi-recursive types embody the kind of type-level recursion you are interested in (iso-recursive types have explicit folding and unfolding). As you suspect, type-checking with equi-recursive types is tougher (but not impossible!).

As a final remark, adding equi-recursive types to an otherwise consistent system does not make it inconsistent, if positivity constraints are respected.


Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to a permutation of $\Sigma^*$, and permutations can in principle be computed with zero thermodynamic cost.


Are theoretically sound pseudorandom generators used in practice?

The notion of "theoretically sound" pseudorandom generators is not really well defined. After all, no pseudorandom generator has a proof of security. I don't know that we can say that a pseudorandom generator based on the hardness of factoring large integers is "more secure" than, say, using AES as a pseudorandom generator. (In fact, there is a sense that it is less secure, since we know of quantum factoring algorithms but not quantum algorithms to break AES.)

What we do have mathematical proofs for are various composition results, saying that if you compose block-ciphers or hash functions in certain ways you can get pseudorandom generators or pseudorandom function. Some such results are widely used in practice, e.g., HMAC. But it's true that the results that achieve a PRG and start with just assuming that the basic component is a plain one-way function are not efficient enough to use for applications (and this is at least partly inherent). So, typically we need to assume a  PRG/stream cipher/block-cipher/hash function as a basic primitive, and start building other things from it. The issue is not really about asymptotic analysis since essentially all cryptographic reductions (except perhaps for Levin's universal PRG) can be made concrete and so give concrete guarantees under concrete assumptions.

But even though they are not based on one-way functions, there is a sense in which constructions such as AES are "theoretically sound" because:
(1) There are formal conjectures about their security.
(2) There is work to try to refute these conjectures, and also derive implications from them.

And indeed, people are aware that for many applications, it would not be smart to use PRG's such as LSFR that do not satisfy (1) and (2) above.


Is every recursive language recognized by a mortal Turing machine?

Here are two results cited in Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators":

Theorem 3: The class of mortal Turing machines is exactly the class of the constant running time Turing machines.

$ConstT = \{ M \mid \exists s $ s.t. for all initial configurations $C$, $M$ halts in no more than $s$ steps $\}$

So I think that we can derive the following: given a mortal Turing machine $M$, let $M', s$ be the corresponding constant time TM and its running time. The language recognized by $M$ over alphabet $\Sigma = \{0,1\}$ is exactly:

$$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$$

So the class of languages recognized by mortal Turing machines is a proper subset of the class of regular languages. For example you can use  $L = \{(0|1)^*1^*\} $ to fool every constant time TM.

Things get interesting when we try to decide if a Turing machine is mortal because we have to face with arbitrary (finite) initial tape and state.

Theorem 4: the set of mortal Turing machines is recursively enumerable.


The number of cliques in a graph: the Moon and Moser 1965 result

I don't have a copy of Moon & Moser at hand, but: the maximum number of distinct maximal cliques in an $n$-node graph (with $n>1$) is $3^{n/3}$, $4\cdot 3^{(n-4)/3}$, or $2\cdot 3^{(n-2)/3}$, according to the value of $n$ mod 3. I think it's a little easier to see this in the complementary form of counting maximal independent sets.

The lower bound is what you're really asking for, and is mostly given already in the comments above: form a graph from the disjoint union of copies of $K_2$ and $K_3$, using as many copies of $K_3$ as possible. Each maximal independent set has exactly one node from each of these complete subgraphs from which the formula follows.

I seem to recall that the upper bound proof of Moon and Moser involved transforming a graph into the lower bound form (or the complementary form for maximal cliques), at each step not decreasing the number of independent sets or cliques. But there's a different way of proving it that leads to worst-case-optimal backtracking algorithms for listing all the cliques or independent sets (see e.g. my paper arXiv:cs/0011009), which I'll only sketch here because the details are a bit tedious. If there's a vertex $v$ of degree three or more in the given graph $G$, then each maximal independent set of $G$ is either a maximal independent set in $G\setminus v$ or it includes $v$ and is a maximal independent set of the graph formed from $G$ by removing $v$ and all of its neighbors. By induction (plugging in the formula for the number of independent sets in these two smaller graphs, with some case analysis mod 3) the bound follows. On the other hand, if no high degree vertex exists then the graph is a disjoint union of paths and cycles, in which one can calculate the number of independent sets directly.


Set of languages that can represent every c. e. languange

$\newcommand{\CE}{\mathsf{CE}}$
$\newcommand{\NN}{\mathbb{N}}$

Because the set of c.e. languages over some alphabet $\Sigma$ is computably isomorphic to the set of c.e. subsets of $\NN$ (via a computable bijection between $\NN$ and $\Sigma^{*}$), we may as well consider c.e. subsets of $\NN$.

Let $\CE$ be the family of all c.e. subsets of $\NN$. Scott's graph model of the untyped $\lambda$-calculus is $\CE$ equipped with the application operation
$$X \cdot Y = \{n \in \NN \mid \exists k_1, \ldots, k_m \in Y . \langle [k_1, \ldots, k_m], n\rangle \in X\}$$
where $\langle {-}, {-} \rangle : \NN \times \NN \to \NN$ is a pairing function e.g., $\langle u, v \rangle = 2^u (2 v + 1)$, and $[k_1, \ldots, k_m]$ is the coding of finite lists, e.g., $[] = 0$ and $[k_1, \ldots, k_m] = \langle k_1, [k_2, \ldots, k_m]\rangle$. Think of $\langle [k_1, \ldots, k_m], n\rangle \in X$ as encoding information of the form "if input contains all of $k_1, \ldots, k_m$ then output $n$".

Now we can ask whether it is possible to generate all of $\CE$ using application and starting from some generators. The answer is positive. In fact, there is a single $G \in \CE$ such that by forming all possible applications
$$G, G \cdot G, (G \cdot G) \cdot G, G \cdot (G \cdot G), (G \cdot G) \cdot (G \cdot G), \ldots$$
we get precisely $\CE$. You can read more about it in Dana Scott's "Datatypes as lattices", SIAM J. of Computing, Vol 5. No. 3, 1976, pp. 522–587.


Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier?

I think the reason PostBQP contained in PP makes it easier to show QMA in PP is that it's easy to show QMA in PostBQP. (Note that we don't really need PostBQP contains PP, we only need the reverse containment, which is easier to show.)

QMA can be shown to be in PostBQP in exactly the same way that one would show MA is in PostBPP (also known as BPPpath). First use error amplification to reduce the error of the MA machine to something more than exponentially small in the size of the witness. Now if you use a random witness, in the yes case there will be some probability of it being accepted (although exponentially small), whereas in the no case the probability of acceptance will be even lower. In the quantum case, we choose the maximally mixed state as the witness and use strong error amplification for QMA. (Both of these ideas are explained in John Watrous' survey on quantum complexity theory.)

Now we need to use the power of post-selection to distinguish these two cases. This is not too hard, but it might sound complicated when I explain it. If you have a machine that accepts yes instances with probability $1/2^k$ (say) and no instances with probability $1/2^{k+4}$. Let our machine with the power of post-selection do the following: With probability $1/2^{k+2}$ just set the post-selection bit (let's call this the PSB) to 1 and the output bit to 0 and end the computation. Otherwise just run the previous machine and set the PSB and the answer bit equal to the output of the computation.

Now in the yes case, with probability $1/2^{k+2}$ the machine with have the PSB equal to 1 and answer bit equal to 0, and with probability at least $1/2^k$ it will have the PSB equal to 1 and answer bit equal to 1. So conditioned on the PSB being 1, there's a much higher chance that it accepts than rejects. Similarly, in the no case, conditioned on the PSB being set to 1 there will be a higher chance of rejecting than accepting.

You might have to tweak the constants a bit to make this idea work exactly, but I think it contains all the ideas needed to make the proof go through.


"Natural" decidable problems known not to be in NP.

One possibility is a problem that is EXPSPACE-complete. NP is trivially in PSPACE, which is strictly contained in EXPSPACE. One problem that is EXPSPACE-complete is deciding whether a regular expression that allows exponentiation is all of $\Sigma^*$.


Standard reference for basic model theory definitions

Here is one possibility, but other people might use different words. I will use first-order logic as a running example.

Language

The language is a collection of expressions, which are syntactic entities, i.e., finite configurations without any a priori meaning. A language is described by the grammar, which determines which finite configurations are valid expressions.

A language may have several kinds of expressions, for instance terms and formulas, each obeying their own grammar.

The expressions of a language may be represented in different ways. When they are written as strings of characters that is called concrete syntax. When the expressions are represented as abstract mathematical configurations (usually trees of some sort) that is called abstract syntax. The process of passing from the concrete to the abstract syntax is parsing.

When we manipulate the language in a mathematical way it is best to use the abstract syntax so we do not have to deal with silly things like parentheses and spaces.

It may happen in certain situations that the language is so complicated that simple grammatical rules do not suffice to describe the valid expressions. For example, in type theory you may have to prove that a certain expression is valid, and the proof can be arbitrarily complex. In such situations people may speak of "pre-expressions" or "pre-terms" described by the grammar.

First-order logic: there are two kinds of expressions, the terms and the formulas. In each particular situation we also have a list of chosen constant symbols, function symbols, and relation symbols. For instance, the first-order language of an ordered fields has (in addition to the usual logical connectives, $=$, and variables) the constant symbols $0$ and $1$, the function symbols $+$, $\times$, $-$, and the relation symbol $<$.

Structure

It is our intention to give the language a mathematical meaning. For this purpose we first need to describe the mathematical objects that parts of the language map to. Such a mathematical object, or collection of objects, or a category, is called a structure. The structures have to be sufficiently rich to support the interpretation of all the parts of the language.

First-order structure: is a carrier set $S$ together with a list of constants (elements of $S$), functions (mapping from $S^n \to S$) and relations (subsets of $S^n$).

Interpretation

An interpretation is the mapping of the language into the structure. It may be called the "interpretation function".

In complicated situations one might provide an interpretation in several layers, in which case you could the first layer pre-interpretation, etc.

First-order interpretation: The terms are mapped to the elements of the carrier set $S$, the formulas are mapped to propositional functions (mapping from $S^n$ to truth values). A formula is valid in a given interpretation if it is mapped to the propositional function which always gives the value "true".

Formal system

A formal system consists of a language and rules for deriving judgements.

First-order logic: In first-order logic there is just one kind of judgement, $$\phi_1, \ldots, \phi_n \vdash \phi$$ whose intuitive meaning is "$\phi$ is proved from hypotheses $\phi_1, \ldots, \phi_n$".

Just to give you another kind of judgement: in programming languages a typical judgement might be $e \Downarrow v$ with the intuitive meaning "program $e$ computes to value $v$".

Theory

The notion of a theory is somewhat specific to logic (it makes less sense when we speak about programming languages or type theory) where we have a notion of a logical formula.

Given a specific language, say that a set $T$ of logical formulas is deductively closed if any formula that can be derived from formulas in $T$ is again an element of $T$.

Every set of formulas $T_0$ has the deductive closure, which is the least set $T$ that contains $T_0$ and is deductively closed. We get $T$ from $T_0$ by adding to $T_0$ all of its consequences, and consequences of consequences, and so on.

A theory is a deductively closed set of formulas. It is usually (but not necessarily) gives as the deductive closure of a chosen set of formulas called the axioms.

Model

Given a theory $T$ and a structure $S$, a model is an interpretation of the language of $T$ into $S$ such that every formula in $T$ is valid in $S$.


Self-referentially defined graph structures

"Dangerous reference graphs and semantic paradoxes", Rabern, Rabern & Macauley, Journal of Philosophical Logic.Here

http://philpapers.org/rec/RABDRG


Is there a good notion of non-termination and halting proofs in type theory?

Because one of the principal applications of Type Theory in formalizations has been to study programing languages and computation in general, a lot of thought has gone into ways of representing possibly non-terminating programs.

I won't make a complete survey here, but I'll try and give pointers to the main thrusts of different directions.

The "relational" approach: you can define your hypothetical programs as relations say, $F\ x\ y$ which holds iff $f$ is defined at $x$ and $f(x)=y$. This is usually what is done with the Kleene T-predicate. This works just as well in type theory formalizations as it does in classical logic, (though of course you can't prove $\forall x (\exists y, F\ x\ y)\vee (\neg\exists y, F\ x\ y)$).

A more sophisticated way to do this is the "Bove-Capretta" method (see Modelling Recursion in Type Theory, which for each recursive function, defines an "accessible predicate" which encodes the fact that a given computation is finite. The function definition takes an extra argument which is a proof that the given inputs are accessible. To define the function without this extra predicate, you need to prove that every possible combination of inputs is accessible.
The "coinductive" approach: this is possibly the most explored approach, and what Andrej's comments refer to. A computation of type $A$ is defined as the inductive type (from Andrej's link, by Capretta, Altenkirch & Uustalu:

codata Delay A =
| Now : A -> Delay A
| Later (Delay A)

This codes a possibly infinite stream of Later tokens ("ticks" of computation) maybe ending with a result Now a. Non-termination is equivalent to being bisimilar with the program

loop = Later loop
and termination can be defined by an inductive predicate over Delay A:

data Terminates : Data A -> Prop =
| Term_now : forall x, Terminates (Now x)
| Term_later : forall d, Terminates d -> Terminates (Later d)

I think the agda-istas have a lot to say about this which they call the partiality monad (see e.g. Danielsson).
The "partial type theory" approach: this is a bit more experimental (the theory is still being worked out), but there are some type theories that are being developed to cope with the fact that there are essentially two types of functions we want to write in type theory: the proof terms and the programs. It turns out to be tough to get a reasonable theory of these things (and retain consistency of the theory), but a serious attempt is made here by Casinghino et al, and a similar effort by Kimmel et al.

I'm sure there are other approaches I'm not aware of, and I'd be happy if someone wants to complete this list.

I should probably note that adding a termination oracle to a (consistent) type theory is a lot like adding a truth oracle for $\Pi^0_1$ sentences, with relatively well understood consequences.

There are other, quite fruitful interactions between type theory and complexity theory, usually under the umbrella of implicit computational complexity.