Here is a possible alternative to a padding argument, based on Schöning's generalization of Ladner's theorem. To understand the argument, you need to have access to this paper (which will unfortunately be behind a pay wall for many):

  Uwe Schöning. A uniform approach to obtain diagonal sets in complexity
  classes. Theoretical Computer Science 18(1):95-103, 1982.

We will apply the main theorem from that paper for $A_1$ and $A_2$ being languages and $\mathsf{C}_1$ and $\mathsf{C}_2$ being complexity classes as follows:

$A_1 = \varnothing$ (or any language in $\mathsf{P}$)
$A_2 = \text{SAT}$
$\mathsf{C}_1 = \mathsf{NPC}$
$\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

For the sake of clarity, the fact we will prove is $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ implies $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.

Under the assumption that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ we have $A_1\not\in\mathsf{C}_1$ and $A_2\not\in\mathsf{C}_2$. It is clear that $\mathsf{C}_1$ and $\mathsf{C}_2$ are closed under finite variations. Schöning's paper includes a proof that $\mathsf{C}_1$ is recursively presentable (the precise definition of which can be found in the paper), and the hardest part of the argument is to prove that $\mathsf{C}_2$ is recursively presentable.

Under these assumptions, the theorem implies that there exists a language $A$ that is neither in $\mathsf{C}_1$ nor in $\mathsf{C}_2$; and given that $A_1\in\mathsf{P}$, it holds that $A$ is Karp-reducible to $A_2$, and therefore $A\in\mathsf{NP}$. Given that $A$ is in $\mathsf{NP}$ but is neither $\mathsf{NP}$-complete nor in $\mathsf{NP} \cap \mathsf{P/poly}$, it follows that $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.

It remains to prove that $\mathsf{NP} \cap \mathsf{P/poly}$ is recursively presentable. Basically this means that there is an explicit description of a sequence of deterministic Turing machines $M_1, M_2, \ldots$ that all halt on all inputs and are such that $\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$. If there is a mistake in my argument it is probably here, and if you really need to use this result you will want to do this carefully. Anyway, by dovetailing over all polynomial-time nondeterministic Turing machines (which can be simulated deterministically because we don't care about the running time of each $M_k$) and all polynomials, representing upper bounds on the size of a Boolean circuit family for a given language, I believe it is not difficult to obtain an enumeration that works. In essence, each $M_k$ can test that its corresponding polynomial-time NTM agrees with some family of polynomial-size circuits up to the length of the input string it is given by searching over all possible Boolean circuits. If there is agreement, $M_k$ outputs as the NTM would, otherwise it rejects (and as a result represents a finite language).

The basic intuition behind the argument (which is hidden inside Schöning's result) is that you can never have two "nice" complexity classes (i.e., ones with recursive presentations) being disjoint and sitting flush against each other. The "topology" of complex classes won't allow it: you can always construct a language properly in between the two classes by somehow alternating between the two for extremely long stretches of input lengths. Ladner's theorem shows this for $\mathsf{P}$ and $\mathsf{NPC}$, and Schöning's generalization lets you do the same for many other classes.


Finding similar vectors in subquadratic time

There may be a way to shoe horn the Johnson-Lindenstrauss theorem into this problem.  Essentially, J-L states that you can project high dimensional data into lower dimensional spaces in such a way that the pairwise distances are nearly preserved.  More practically, Achlioptas has a paper called Database-friendly random projections: Johnson-Lindenstrauss with binary coins that does this projection in a random way, which works pretty well in practice.

Now, certainly, your similarity function is not exactly the same as something that would fit into the J-L theorem.  However, it looks like a distance function and perhaps some of the theory above may help.


Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this classical paper by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L_1$ distance.


When we use a proof of unsatisfiability to derive an interpolant, isn't using the interpolant to check satisfiability now redundant?

If the formula is satisfiable you cannot construct an interpolant. If the formula is unsatisfiable, you know that the final states are not reachable in at most $k$ steps. You do not know about reachability of final states in $k+1$ or more steps.

If the formula you suggest is unsatisfiable, you can replace the sub-formula $I$ of $A$ with the interpolant and check for satisfiability. If this new formula is unsatisfiable, you know that the error state is not reachable in $k+1$ steps. Something significant just happened. We were able to determine that the final states are not reachable in $k+1$ steps using only $k$ unwindings.

Interpolant computation can repeat until the formula is unsatisfiable, in which case you are stuck, or until a new interpolant implies the disjunction of the old interpolants. The second case is another advantage of interpolants. We use them to detect fixed points. Detecting a fixed point with just the bounded model checking formula is not easy.

A one-line intuition I once heard was: interpolation is a poor person's quantifier-elimination.


I looked into whether there is a generally accepted hypothesis in complexity theory, which implies that there must exist an NP-complete language that cannot be accepted in polynomial time on almost all inputs (as defined in the question).

Interestingly, the most "standard" hypotheses do not seem to imply it. That is, it does not appear to follow (unless I overlooked something) from P$\neq$NP, P$=$BPP,
NP$\neq$coNP, E$\neq$NE, EXP$\neq$NEXP, NP$\neq$PSPACE,  NP$\neq$EXP, NP$\not\subseteq$P/poly, PH does not collapse,  etc.

On the other hand, I found one, slightly less standard, hypothesis, which does imply the existence of the sought NP-complete problem, albeit not a natural one.  In the theory of resource bounded measure the fundamental hypothesis is that NP does not have $p$-measure zero, denoted by
$\mu_p($NP$)\neq 0$. Informally, this means that NP-languages within E do not form a negligible subset. For details, see a survey here. In this theory they prove, among many other things,  that
$\mu_p($NP$)\neq 0$ implies the existence of a P-bi-immune language in NP. A language $L$ is P-bi-immune if  neither $L$ nor its complement has an infinite subset in P. Such a language satisfies our requirement in a strong way.

However, it still remains unclear whether an example exists that represents a natural problem.


Showing that interval-sum queries on a binary array can not be done using linear space and constant time

I wouldn’t be so sure such an algorithm doesn’t exist; there are certainly algorithms that get very close. Below, $\log n$ is $\log_2n$, $\log^{(k)}n$ is $\mathop{\underbrace{\log\dots\log}_{k\text{ times}}}n$, $\log^*n$ is iterated logarithm, and $\tilde O(t(n))$ is $O(t(n)\operatorname{polylog}(t(n)))$.

  Proposition: There are algorithms that achieve

  space $O(n\log^{(k)}n)$ and query time $O(1)$ for any constant $k$;
  space $O(n)$ and query time $\tilde O(\log^*n)$.

The algorithms work as follows. There are parameters $k>0$ and $n=b_0>b_1>\dots>b_k>0$ depending on $n$. We split the input size-$b_0$ array into size-$b_1$ blocks (level 1); we split each level-1 block into size $b_2$ blocks (level 2); and so on up to level $k$. (Let us pretend all $b_i$ are powers of $2$, to avoid issues with divisibility.) Then:

For each $i=1,\dots,k$ and each level-$i$ block, we store the number of set bits in the interval from the beginning of the block down to the nearest level-$(i-1)$ block boundary.
In order to resolve a query, we sum the $k$ stored numbers corresponding to the index, and count the set bits before the index in its level-$k$ block. We do all this for $x$ and $y$ separately, and subtract the results.

(If the $b_i$ parameters are not easy to compute, we might also store them.)

This arrangement uses space
$$n\sum_{i=1}^k\frac{\log b_{i-1}}{b_i},$$
and query time
$$O(k+b_k).$$

In the proposition, for 1., we let $k$ be constant, and put $b_i=\log^{(i)}n$ for $0<i<k$, $b_k=1$.

For 2., we can take $k=\log^*n$, and
$$b_i=i(\log i)^3\log^{(i)}n.$$
The space is then bounded by roughly
$$n\sum_{i=1}^k\frac{\log^{(i)}n+2\log i}{i(\log i)^3\log^{(i)}n}\le
n\sum_{i=1}^\infty\frac{3}{i(\log i)^2}=cn$$
for some constant $c$.


Here's a Levcopoulos-Petersson sorting algorithm reference, but a different one somewhat older than the one in Andreas' answer:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for Presorted Files", WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 382, London, UK: Springer-Verlag, pp. 499–509, doi:10.1007/3-540-51542-9_41.

There's a description of the algorithm in http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting from which the O(n log k) bound is easy to see. More precisely the time for the algorithm is $O(\sum\log k_i)$ where $k_i$ is the number of intervals containing input item $x_i$. In a $k$-idiotic sequence, each $k_i$ is uniformly bounded by $k$ so the total time is just $O(n\log k)$.


Here's an argument that you need time quadratic in the number of polygons. More precisely,
you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for any $k=O(n^{\delta})$ and any $\epsilon,\delta>0$ It's a reduction from the orthogonal vectors problem, the problem of finding two disjoint binary vectors among a set of $n$ $k$-dimensional binary vectors, for which the non-existence of an algorithm with time $O(n^{2-\epsilon})$ is a standard conjecture in fine-grained complexity (see e.g.  Abboud et al, "More consequences of falsifying SETH and the orthogonal vectors conjecture"). Here orthogonality is measured in $\mathbb{Z}^k$, i.e. it means that the vectors have disjoint subsets of nonzero coordinates.

Given a set of vectors among which we wish to find an orthogonal pair, consider a regular $k$-gon $P$, whose vertices correspond to the coefficients of our vectors. For each vector $x$ construct a polygon $p(x)$ as the convex hull of the $k$-gon vertices for which $x$ has a nonzero coefficient. To make sure that none of these polygons contains each other, shrink each $k$-gon by a factor $1-\gamma |x|$ for some very small number $\gamma$, so that when one vector is dominated by another its polygon is shrunk more.

Next, form two more regular $k$-gons $Q$ and $R$, concentric with $P$, where $Q$ is slightly smaller than $P$ (so that all its vertices are inside the shrunken copies of vertices of $P$) and $R$ is slightly bigger (both close enough that the construction below produces convex polygons). For each vector $x$, construct a second polygon $q(x)$, a convex $k$-gon that, on each ray from the origin through a vertex of $P$, $Q$, and $R$, chooses either a vertex of $Q$ or $R$: a vertex of $Q$ when the corresponding coefficient of $x$ is nonzero, and a vertex of $R$ when it is zero.
We can make sure that all vectors have at least one zero coefficient in order to ensure that no $q(x)$ is contained inside a $p(y)$, and we can do the same variable-shrinking trick to ensure that no two $q$'s are nested.

With this construction, the only remaining containments of polygons are that a polygon $q(x)$ contains another polygon $p(y)$. This happens if and only if $x$ and $y$ are orthogonal. So if we could solve your polygon question in sub-quadratic time, we could also solve the orthogonal vectors problem in sub-quadratic time, conjectured to be impossible.


Could chromatic number be easy to calculate when colouring is hard for some graph class?

Yes. Since 3-COLORING is FNP-complete, for any problem in FNP we can construct a graph G that is 3-colorable if and only if the problem has a solution. So you can pick your favorite problem from TFNP\FP (if it's not empty!), like finding a factor of a composite number, or a second Hamiltonian-cycle in a 3-regular graph, and convert it into a graph.

In more detail with the example of finding a factor.
We will fix an algorithm that converts a composite number $N$ into a graph $G(N)$ such that from $G(N)$ you can decode the value of $N$.
Compositeness of $N$ is a necessary for $G(N)$ to be in our class.
Moreover, any proper $3$-coloring of $G(N)$ can be converted into a proper divisor $d$ of $N$.
This can be done, e.g., by writing up a CNF that describes whether a given $d$ encoded in binary as $x_1\ldots x_{n}$ divides a fixed $N$ (that also has $n$ digits in binary, but these are not variables).
From satisfiability of a CNF there is a standard reduction to 3-COLORABILITY such that you can easily convert a proper $3$-coloring back to an $x_i$ satisfying assignment.
Thus solving the coloring problem, you would find a divisor $d$.
Moreover, by adding some simple extra gadgets, you can also decide whether a graph is of this form or not.
Our class is formed by graphs created this way, which are thus all $3$-colorable.


Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?

The general problem when $H$ is not fixed is NP-hard: Take $H$ to be a cycle of length $|V(G)|$ and it amounts to testing whether $G$ is hamiltonian.

I think that the state of the art on this is the FPT algorithm of
Grohe, Kawarabayashi, Marx and Wollan. The dependency on $G$ is cubic, but the one on $H$ seems impractical, since it relies quite heavily on the Robertson-Seymour theory.


Find all pairs of values that are close under Hamming distance

As stated, your approach is problematic, because if 2 bitmaps have evenly spaced differences then in any rotation, there will be differences on some high order bits.

You can generalized your approach by permuting the bit position in a more complex fashion. Indeed, if you select a random permutation of bits, then all differences between 2 bitmaps with distance $5$ will appear in the 16 low-order bits with probability better than $1/50$. So repeating a few hundred times you should find a very large proportion of your bitmap pairs. For each trial, the number of pairs to test (with the same 16 high bits) is close to $64\cdot N$ (for $N\approx 2^{22}$).

However, I would also try the following approach. Built a list of your bitmaps modified in at most 2 bit positions and sort this list. If there are collisions within this list, you have two bitmaps within distance $4$. Then enumerate all values of your initial bitmaps modified three positions and search them in the list to find pairs of bitmaps at distance $5$.
The memory cost of this approach requires storing $529\cdot N$ elements and the number of elements to search in the second phase is $4960\cdot N$.

Additional information:

The probability that $5$ differences are located in the $16$ low
order bit after a random permutation of the $32$ bit-positions is
just a quotient of two binomials:
$$ \frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217
$$
Construction of the lists, for each element in the original list, put in the augmented list: the element itself, all elements differing in one position and all elements differing in two positions (keeping the information about the original element). The number of copies for each element is $1+32+\binom{32}{2}=529.$ Any collision within this list (detected after sort) corresponds to two original element at distance at most $4$. Note that each pair can be detected several times so you will need to remove duplicates (but this was already the case with your initial algorithm).
For the final pass, it is preferable to prune the augmented list of elements to keep only those at exact distance $2$ from their original element. Then, for each original element, create the $\binom{32}{3}=4960$ elements at distance $3$ and search them within the augmented list. Once again, you need to remove duplicates since each pair is going to be detected $\binom{5}{3}=10$ times. [With extra care, you can probably anticipate/avoid most duplicates but I am not sure whether it is worth the effort.]


The main reason for avoiding sets in semantics of types is that a typical programming language allows us to define arbitrary recursive functions. Therefore, whatever the meaning of a type is, it has to have the fixed-point property. The only set with such a property is the singleton set.

To be more precise, a recursively defined value $v$ of type $\tau$ (where typically $\tau$ is a function type) is defined by a fixed-point equation $v = \Phi(v)$ where $\Phi : \tau \to \tau$ can be any program. If $\tau$ is interpreted as the set $T$ then we would expect every $f : T \to T$ to have a fixed point. But the only set $T$ with this property is the singleton.

Of course, you could also realize that the culprit is classical logic. If you work with intuitionistic set theory, then it is consistent to assume that there are many sets with fixed-point property. In fact, this has been used to give semantics of programming language, see for example

  Alex Simpson, Computational Adequacy for Recursive Types in Models of Intuitionistic Set Theory, In Annals of Pure and Applied Logic, 130:207-275, 2004.


Bounds on approximating frequency moments

There's been a fair bit of progress. On the specific problem of $F_k$, there is a matching upper and lower bound of $n^{1-2/k}$ for $k > 2$. The upper bounds come from this paper by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.


Does cryptography have an inherent thermodynamic cost?

As I mentioned in my comment above, and as you allude to in the question, every computation can be made reversible, and by simply retaining the extra bits, there is no inherent thermodynamic cost.

Every circuit generated by using Toffoli gates and ancillas to replace irreversible gates becomes as efficient to reverse as it is to compute assuming you have access to all output bits. This is clearly not the case for the functions considered in cryptography, since many ancillae are used and discarded. It is by keeping secret this extra bits that makes the computation hard to reverse.

However, by computing the function reversibly, making a copy of the subset of bits corresponding to the output, and then inverting the function the total energy cost for computing and inverting the function will be zero, while the only cost incurred will be in making the copy of the output bits, which depends only on the number of output bits and not the function being computed. This is clearly the best you can do, since it costs the same energy as simply writing the output string to an empty register.

Turning to your restated question:

  "Are there any trapdoor one-way
  functions that can be implemented
  using only reversible logical
  operations, without additional scratch
  space?"

The answer is trivially no. If you apply the inverse of each gate in reverse order you compute the inverse of the function. Assuming a model where gates act on a fixed number of qubits at a time, then the inverse of each elementary reversible gate can be applied in constant time. Hence such a function is as easy to invert as to compute (up to a multiplicative constant), and hence is not a trapdoor function.


Understanding proof of Theorem 3.3 in Karp's "Probabilistic Recurrence Relations"

In some cases the recurrence for $T$ does not determine it uniquely. We take the following interpretation of $T$, which gives the minimum $T$ consistent with the recurrence.

Repeatedly substitute $T(x) = a(x) + T(h(x))$ to expand $T(x)$ as the (random) sum
$$
T(x) = a(x) + a(h(x)) + a(h(h(x))) + \cdots = \sum_{j=1}^\infty a_j
$$
where $a_i = a(h^{(i-1)}(x))$,
in which $h^{(0)}(x) = x$ and and $h^{(i+1)}(x) = h(h^{(i)}(x))$.

lemma. With this definition of $T$,
we have $K_r(x) \le \sup_i K^i_r(x)$.

Proof.
Inspecting the definitions of $K^i_r$ and $K_r$, we have
$$
K_r(x) = \Pr[\textstyle\sum_{j=0}^\infty a_j > r]
~~\mbox{and}~~
K^i_r(x) = \Pr[\textstyle\sum_{j=0}^{i-1} a_j \ge r].
$$
To prove the lemma, we will show something slightly stronger, namely
$$
\Pr[\textstyle\sum_{j=0}^\infty a_j > r] ~~=~ \sup_i \Pr[\textstyle\sum_{j=0}^{i-1} a_j > r].
$$
Define random variable $T = \min\{i : \sum_{j=0}^{i-1} a_j > r\}$ to be the first step at which the sum of terms exceeds $r$ (with $T=\infty$ if that never happens).
Rewriting the desired equation in this notation, we want to show
$$
\textstyle \Pr[T < \infty] ~=~ \sup_i \Pr[T \le i].
$$
But that equation follows from basic definitions as follows:
$$
\Pr[T < \infty]
= \sum_{j=0}^\infty \Pr[T = j]
= \lim_{i\rightarrow\infty} \sum_{j=0}^i \Pr[T=j]
= \lim_{i\rightarrow\infty} \Pr[T \le i]
= \sup_i \Pr[T \le i ].$$
QED


Graph with minimum number of edges having given sets of nodes as its paths

This problem is NP-complete, even for the special case $|P_k|\le 3$. I will give a reduction from Vertex Cover. I will refer to the sets $P_1,\ldots,P_k$ in the question as constraints: binary or ternary, depending on their cardinality.

Let $(V',E',k)$ be an instance of Vertex Cover: Is there a subset $S$ of $k$ vertices from $V'$ such that $S$ covers (that is, intersects) all edges in $E'$?

We add a distinguished vertex $\bullet$; that is, $V=V'\cup\{\bullet\}$. We add binary constraints for all pairs of vertices in $V'$: for each $\{i,j\}\subseteq V'$, we add the constraint $\{i,j\}$. We then add ternary constraints for each edge in $E'$: for each $\{i,j\}\in E'$, we add the constraint $\{i,j,\bullet\}$.

We ask whether there is a graph with $\binom{|V'|}{2}+k$ edges that satisfies the above constraints. The answer (yes or no) is an answer to the Vertex Cover question.

Why would that work? Because of the binary constraints, we know that edge $\{i,j\}$ is selected. So, the only task that remains is to pick between $\{i,\bullet\}$ and $\{j,\bullet\}$. That's exactly the task we have in the original Vertex Cover problem: Pick which endpoint of an edge we use to cover it.


I know of two semi-related trends that may be of interest (so this would be an extra answer to your question, but not the answer).

First, some progress has been made recently on the problem known as "Affine Image Matching", given two images A and B, how much an affine transformation can make A look like B (see 10.1007/978-3-642-13509-5_2 which proves that Affine Image Matching is uniform-TC0 complete).

Second, there has been studies of image transformations in the context of weighted automata.  A weighted automaton, which weights a word by an element of a semiring, describes fractal like images (intuitively, because of the loops of the automaton).  Nonetheless, actual algorithms have been invented to compress real-world pictures in weighted automata; a rational (weighted) transduction on such representations is then an image transformation.  See Chapter 11 of the Hanbook of Weighted Automata or the older Chapter 10, Volume 3 of the Hanbook of Formal Languages.


What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I can answer this part:

  Would it then be correct if I say there is an FPTAS for SDP?  I have not seen that stated anywhere, so that's probably not right.  But why?

The statement is correct, but we do not often see it because a stronger statement holds and is more important than this weaker statement.

An FPTAS is a polynomial-time algorithm which, given a problem and an accuracy parameter 1k, outputs a (1+1/k)-approximate solution.

But for SDP, the ellipsoid method and the interior-point method provide polynomial-time algorithms which, given a problem and an accuracy parameter 1k, output a (1+2−k)-approximate solution.  Note that the approximation factor is much better than what is required for an FPTAS.


Some observations:

First, let's take a different parameter called c. The problem is to find a minimum weight connected subgraph which connects at least c vertices in S. Now c=2 is the easy problem you refer to, and c=|S| is the Steiner tree problem.

I think for c=$|S|^\epsilon$, the problem is still NP-hard. The reduction would basically add lots of useless terminals connected to the rest of the graph with very high edge weights, so that these vertices will never be picked in the min weight tree, and the min weight tree will only have the vertices we wanted. For example, an algorithm to solve this problem for c=|S|/2 can be used to solve the Steiner tree problem by just taking the instance of Steiner tree, and doubling the number of terminals and connecting them to the rest of the graph with large edge weights.

As you mentioned, the c=2 case is in P. Similarly, for any constant c', the c=c' case is easy by a brute force search.


Here's a slightly different perspective on Fredrik's answer. It's generally the case that impredicative Church encodings of types will satisfy the relevant $\beta$ laws, but will not satisfy the $\eta$ laws.

So this means we can define a dependent pair as follows:

$$
\exists x:X.\;Y[x] \triangleq \forall \alpha:\ast.\; (\Pi x:X.\;Y[x] \to \alpha) \to \alpha
$$
Now, note that $\pi_1$ is easily definable:
$$
\pi_1 : \exists x:X.\;Y[x] \to X \triangleq \lambda p:(\exists x:X.\;Y[x]).\;p\;X\;(\lambda x\;y.x)
$$
However, you cannot define the second projection $\pi_2 : \Pi p:(\exists x:X.\;Y[x]).\; Y[\pi_1\;p]$ -- try it! You can only define a weak eliminator for it, which is why I wrote it with an existential.

However, the second projection is realizable, and in a parametric model you can show that it has the right behavior, too. (See my recent draft with Derek Dreyer on parametricity in the Calculus of Constructions for more on this.) So I think that the $\pi_2$ projection fundamentally demands some strong extensionality properties for it to make sense.

In terms of the sequent calculus, the weak eliminator has a rule that looks a bit like:

$$
\frac{\Gamma, x:X, y:Y[x],\; \Gamma' \vdash e' : C}
     {\Gamma, p:\exists x:X.\,Y[x],\; \Gamma' \vdash \mathsf{let}(x,y)=p\;\mathsf{in}\;e' : C}
$$
Here, the implicit well-formedness conditions imply that $p$ cannot occur free in $\Gamma'$ or $C$. If we relax that condition, we get the split rule, which has a left-rule that looks like
$$
\frac{\Gamma, x:X, y:Y[x],\; [(x,y)/p]\Gamma' \vdash e' : [(x,y)/p]C}
     {\Gamma, p:\exists x:X.\,Y[x],\; \Gamma' \vdash \mathsf{let}(x,y)=p\;\mathsf{in}\;e' : C}
$$
That substitution reminds me an awful lot of the Girard/Schroeder-Heister elimination rule for equality. I asked a question about this rule a while back, and David Baelde and Gopalan Nadathur give the state-of-the-art version in their LICS 2012 paper, Combining Deduction Modulo and Logics of Fixed-Point Definitions. I think Conor McBride has spent some time thinking about the relationship between the identity type and the Schroeder-Heister equality, so you might want to see what he thinks.


The problem is in coNLOGTIME, for example using the following algorithm. As is well known, one can determine the length of input $n$ in binary in DLOGTIME. Then, read off at most $\log n$ bits from the end of the input to find $j$ (if it is longer, reject). This also determines $i=n-1-\lfloor\log(j+1)\rfloor$ (I am assuming one character for the separator), so it remains to check that $i>j$, and that the beginning of the input is indeed a valid unary encoding: only the last part uses nondeterminism. (That is, the problem would be in DLOGTIME if it were defined so that any string of length $i$ counted as a unary encoding of $i$.)


Are there presentations of set theory in terms of lambda-calculus?

There is a really interesting approach to a set theory-like foundational system that I am rather fond of: Grue's Map Theory. The basic idea is to take the (untyped!) $\lambda$-calculus as a base foundation, and to represent a set $S$ as a term $f$ such that

$$ S=\{f(x)\mid x\in\Phi\}$$
where $\Phi$ represents the well founded functions ($x\neq\bot$ in the Scott semantics). It doesn't look like there is any proof assistant based on it though, so I have no idea how it would work in practice.


Complexity of Comparative Independent Set Decision Problem

This problem is indeed complete for the class of polynomial time Turing machines with access to an NP oracle with log many queries (also known as $\Theta_2^p$).  The result appears in a 2000 FST TCS paper by Spakowski and Vogel titled "$\Theta_2^p$-Completeness: A Classical Approach for New Results."  The proof presented there and a proof that I arrived at independently both rely on the $\Theta_2^p$-completeness criterion of Wagner ("Bounded Query Classes" SIAM Journal on Computing archive Volume 19 Issue 5, Oct. 1990).


Finding the longest path between two nodes in a bidirectional unweighted graph

Williams (2009) [arXiv version] gives a randomized $2^k poly(n)$ time algorithm finding a path of length at least $k$ in a graph on $n$ vertices. The paper contains pointers to previous deterministic and randomized algorithms. Many of these algorithms can probably be modified to find a $k$-path whose endpoints are given in the input.


If N is a power of two, I believe O(N log N) operations suffice, even for a somewhat more restricted problem in which all items start on one of the queues and must end up in reverse order on one of the queues (without the input and output lists).

In O(N) steps it is possible to start with all elements on one queue, play "one for you one for me" to split them into alternating subsets on the other queue, and then concatenate them all back into one queue. In terms of the binary representations of the positions of the items, this implements a rotate operation.

In O(N) steps it is also possible to pull off pairs of elements from one queue, swap them, then put them back, reversing all pairs. In terms of the binary representations of the positions of the items, this complements the low order bit of the position.

By repeating O(log N) times an unshuffle and a pairwise swap, we can complement all the bits of the binary representations of the positions — which is the same thing as reversing the list.


What is the complexity of this edge coloring problem?

This problem is NP-hard and APX-hard; see: Adamaszek and Popa,
Approximation and Hardness Results for the Maximum Edge $q$-coloring
Problem, Lecture Notes in Computer Science 6507 (2010) 132-143.

The parameterized complexity aspects of this problem is addressed in this recent paper.


Adjective for: algorithm that outputs its input if it is one of its outputs?

In mathematics we would say $f$ is an idempotent function. It's a widely known term and I suppose most TCS people should also recognize it.


Capacity of Uniquely Solvable Puzzle (USP)

Like many other questions, the answer to this one can be found in Stothers' thesis. A local USP is a CWP in which the only way in which a 1-piece, a 2-piece and a 3-piece can fit together is if their union is in $S$. Clearly a local USP is a USP, and a construction from [CKSU] shows that the USP capacity is achieved by local USPs (we are going to show that constructively).

Coppersmith and Winograd construct an almost 2-wise independent distribution $S$ on $2^V$ with the following two properties: (1) $\Pr[x \in S] = (|V|/2|E|)^{1-\epsilon}$, (2) For any $x,y,z \in V$ such that the 1-piece of $x$, the 2-piece of $y$ and the 3-piece of $z$ together form a vector $w \in V$: if $x,y,z \in S$ then $w \in S$.

We choose a random subset $S$ of $V$ according to the distribution, and for each edge $(x,y) \in E$, we remove both vertices $x,y$. The expected number of vertices left is roughly $(|V|^2/2|E|)^{1-\epsilon}$. The resulting set $T$ is a local USP: if there are $x,y,z \in T$ in which the 1-piece of $x$, the 2-piece of $y$ and the 3-piece of $z$ fit, forming a piece $w$, then $x,y,z,w \in S$, and so all of $x,y,z$ are removed from $S$.


There are some references I could find:
General-purpose computation with neural networks: A survey of complexity theoretic results, 2003 and Counting hierarchies: polynomial time and constant depth circuits, 1993.

It appears that neural networks are considered threshold circuits; i.e. those circuits using MAJORITY gates. In (2) it is the case that a depth $d$ neural network has complexity $TC^0_d$ (here's a link to link to complexity zoo entry about $TC^0$).

Since $TC^0$ containts $ACC^0$, which is $AC^0$ with arbitrary MOD gates, then $AC^0 \subset TC^0$. Also, it is mentioned in the zoo that such circuits with depth 3 are strictly more powerful than those of depth 2.

In On the computational power of sigmoid versus Boolean threshold circuits,1991 it is mentioned that for a constant depth $d$, Boolean and real-valued threshold circuits (with polynomially bounded weights) are essentially the same.


Where's the Flaw in Blum-Feldman-Micali's Method

I have not read the details of their flawed protocol, but I've heard about it on several occasions.  My impression was that their error was in how they used the PRG seed.  Their protocol puts the pseudorandom generator (PRG) seed in the public common reference string, and they attempt to argue that PRG security forces some statistical property of the PRG output to hold even with a known seed.  While it is possible to do this in a sound way (the signature schemes of Hohenberger and Waters here and here spring to mind), something went wrong in their argument.


How do you encode Lamping's abstract algorithm using interaction combinators?

I am not aware of any implementation of Lamping's algorithm directly in the interaction combinators.  I do know that the presence of integer labels is a necessary feature of Lamping's algorithm, even for EAL-typable terms, because the labels reflect the nesting of so-called exponential boxes in proof nets, and Lamping's algorithm is essentially the execution of proof nets using the geometry of interaction, as first observed by Gonthier, Abadi and Lévy.  So the question of implementing the algorithm in the interaction combinators boils down to representing exponential boxes in proof nets using the combinators. This is essentially what Mackie and Pinto did in their paper.

Of course, Mackie and Pinto's encoding adresses all $\lambda$-terms, which use full linear logic boxes, whereas EAL-typable terms use elementary linear logic boxes, which are simpler (they are so-called functorial boxes).  However, I do not believe that this simplification would have a notable impact on interaction combinator implementations.  This is because boxes are a global feature (they identify arbitrarily big subnets to be duplicated/erased), whereas the interaction combinators (as any interaction net system) are completely local (reduction only modifies bounded subnets), so the challenge is to represent such global features locally.  Now, global duplication/erasing in EAL is identical as in full linear logic, that is why I do not expect that an interaction combinator implementation of EAL would radically differ from the one proposed by Mackie and Pinto.


Inference in typed lambda calculus theories

At least the problem of whether 2 terms are equal modulo the theory of Cartesian Closed Categories (or $\beta\eta$ conversion) is decidable, because (in part) of the normalization property.

Another, more categorical way to see this is by extracting a conversion algorithm through normalization by evaluation which gives decision procedures for equality in categories which can naturally be embedded in the presheaf or sheaf category over sets.

See e.g. Altenkirch, Dybjer, Hoffmann & Scott, Normalization by Evaluation for Typed Lambda Calculus with Coproducts

for the version with products and coproducts (the version for just CCCs without coproducts can be found in the references).

An account which gives examples of implementations can be found here.

Solving more complex questions than conversion, or solving conversion questions in the presence of datatypes like the natural numbers becomes undecidable rather quickly. I'm not aware of much work on algorithms for such systems, which I would be interested in as well. One could try simply encoding the equational theory into a first-order logic prover like Vampire, but I don't know how well that would work. It would be an interesting experiment!


Definition of a prefix-free Turing machine

If you were using a self-delimiting machine as described, you have to change your notion of what it means for the machine to accept a string. You want to say that the machine accepts a string $\omega$ if it halts in an accept state with the read head on the last symbol. The idea is to think of the computation as a loop: it first asks whether $\omega\upharpoonright 1$ is in the language, then whether $\omega \upharpoonright 2$ is, and so forth, and it halts if it finds a prefix of $\omega$ in the language or if it runs out of bits of $\omega$.

The point is that if the input tape contains an infinite juxtaposed sequence of nonempty words from the language, the prefix free machine can be used to parse out the individual words from the sequence.  The definition of a prefix-free machine from the book is designed for this sort of application, not for the problem of deciding whether an individual word is in the language.


When does automaton stay unchanged after string homomorphism?

Let $\mathcal{A} = (Q, A, \cdot, q_0, F)$ be the minimal DFA of your language $L$. If I understand correctly, you would like to have a permutation $\sigma$ on $A$ such that
$$
q \cdot \varphi(a) = q \cdot \sigma(a)
$$
for every state $q$ and letter $a$. This will happen if and only if, there exists $\sigma \in \mathfrak{S}(A)$ such that, for each letter $a$,
$$
\varphi(a) \in \bigcap_{q \in Q} L(q, q \cdot \sigma(a))
$$
where, given two states $p$ and $q$, $L(p, q) = \{u \in A^* \mid p \cdot u = q\}$.

For instance, in your example, you get the following conditions when $\sigma$ is the identity
\begin{align}
 \varphi(a) \in L(0,0) \cap L(1,1) &= \{ u \in A^* \mid |u|_b \text{ is even }\} \\
 \varphi(b) \in L(0,1) \cap L(1,0) &= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\
\end{align}
and the following conditions when $\sigma$ is the transposition $(1\ 0)$
\begin{align}
 \varphi(a) \in L(0,1) \cap L(1,0) &= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\
 \varphi(b) \in L(0,0) \cap L(1,1) &= \{ u \in A^* \mid |u|_b \text{ is even }\} \\
\end{align}
which, altogether, gives your condition.


Max flow: either saturate an edge or avoids

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$
$$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$
$$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "saturate edge or avoid" flow of value $c((v,t))$.


Complexity of constructing minimum depth decision trees

I think I can see a fairly easy reduction from 3DM. Let $B=\{0^J\}$, i.e., it is a singleton set with the only zero element. The points of $A$ correspond to the points of the 3DM that are to be matched. If a triple is matchable, then there is a coordinate where these 3 points are 1, while all other points are 0. The equivalence is straightforward.

I think an interesting question left open is if A is given (as part of the input), and our goal is to separate it from $\{0,1\}^J\setminus A$.


How do continuations represent negations (under the Curry–Howard correspondence)?

When one associates negation with continuations, it is probably not ideal to think of it in terms of an 'empty' type. Continuation passing can be done with respect to any result type, and if that type is held abstract, it works a lot like 'false' in that there is no introduction rule for it.

With respect to the paper you linked (I'm by no means an expert on it, and just skimmed it, really), I think it might help to study the reduction rules. It appears to me that the goal of the logic is to construct an expression $e : +\mathsf{int}$ and reduce that expression to a numeral $n$. This means that the continuation $\bullet : ¬int$ is not something that would be valid as a program in itself. Rather it is a clue that the abstract 'result type' is actually $\mathsf{int}$, because we are interested in using continuation-based computations that eventually result in integers. $\bullet$ is something that immediately completes the computation, hence the rules:

$$(begin)\ \ \ \  e : +int \leadsto \langle e | \bullet \rangle$$
$$(end)\ \ \ \  \langle n | \bullet \rangle \leadsto n$$

I don't know what happens if you have $\bullet$ involved in other situations, or if you can, but I might expect it to abort other continuations and end the computation. It seems more like it can only be the initial continuation based on the rules, though.

Now, one answer to your question is that this system is not even trying to reason about uninhabited types. It is using a correspondence between the logical rules and control flow, without the specific semantic meaning of negation. One thing you might want to check out is linear logic, because it actually has two sorts of 'false' or zero, one which is about control flow, and one which is about emptiness. The linearity is important for keeping them separate.

In that setting, $⊥$ is the 'false' that has to do with control flow, and it gets things like double negation elimination and excluded middle (with a corresponding 'or' that is more related to representing functions via continuations than it is disjoint union), while there is also $0$, which gets the principle of explosion (which is arguably the distinct part of the empty type1). An interesting thing about this setting is that even though the logic seems classical, it is actually constructive because of the more restricted rules. Double negation by the 'control flow' bottom $⊥$ is just a different (possibly more convenient) way of structuring a program that computes the doubly-negated type (and 'excluded middle' is a decomposed identity function).

Fillinski's 'Linear Continuations' might be a good place to start reading, although there are probably other references as well.

In the continuation-with-abstract-result-type setting, you can also interpret explosion, but it has sort of a different meaning. Effectively such interpretations are always 'delimited' somewhere, even if it's only the end of your program. Explosion means that if you somehow get a value of the abstract result type, you can throw away your current continuation and jump to the delimiter. So it is an 'abort' operation. Linear logic doesn't allow this; all continuations must be used (and used exactly once), so explosion must be justified by involving an 'impossible' situation, like having a value of an empty type.


Max-weight connected subgraph problem in planar graphs

In the "The NP-Completeness Column: An Ongoing Guide" number 14, Johnson writes "... Vergis [49]. Transformation from STEINER TREE IN GRAPHS [ND12]...". I don't have access to the Vergis' paper, however a possible reduction can be the following.

Steiner Tree (ST) in graphs problem

Instance: an undirected graph $G = (V,E)$, a subset of the vertices $R \subseteq V$, called terminal nodes; a non-negative integer $k$

Question: is there a subtree of $G$ that includes all the vertices of $R$ (a spanning tree for $R$) and that contains at most $k$ edges?

The problem remains NPC even for planar graphs (M. Garey and D. Johnson. The rectilinear Steiner tree problem is NP-complete).

Given an instance of planar ST, for now suppose that you can assign arbitrary weights to nodes. If $|R|=p$ and $|E|=q$ , you can assign weight $q+1$ to the nodes of $R$ and you can add a middle node to every edge of $E$ and assign weight $-1$ to it. Assign weight $0$ to the remaining nodes in $V \setminus R$. The original graph $G$ has a spanning tree for $R$ with at most $k$ edges if and only if in the transformed graph you can find a subgraph of target weight greater or equal to $W = p(q+1) - k$.

Informally to reach the $p(q+1)$ quantity you must include all the nodes of $R$ in the subgraph, and you must include at most $k$ middle nodes (corresponding to the edges of $G$) that have negative weight -1 to keep them connected.

You can reduce the the max degree of the whole graph to three in this way: if $D = \max\{deg(u_i) \mid u_i \in V\}$ just transform each node $u_i$ to a circular chain of $D$ nodes (and adjust the value of $p$ accordingly). Connect the inbound edges to distinct nodes of the chain (that will have degree 3).

And if you want to use only weights $+1,-1$ then you must:(A) assign $+1$ to all the nodes of the circular chains corresponding to nodes in $V\setminus R$,(B) transform every middle node to a linear chain of nodes of weight $-1$ and length $l_E = |V\setminus R|+1$, and(C) further expand the circular chains (with weight +1) corresponding to the nodes of $R$ to at least length $l_R = l_E( |E| + 1)$; and set target weight $W =pl_R - kl_E$.
Informally, the expanded chains and the new target make the $+1$ weights of the nodes corresponding to $V \setminus R$ (point A) irrelevant.


Maintaining the value of a polynomial over a dynamically updated input

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then maintain the value at each gate in the circuit. When you change the $i$-th bit of $y$, simply propagate that change along the DAG of the circuit, starting from the input $y_i$. If the circuit has size $s$, this takes $O(s)$ time and space. This could be much smaller than the number of monomials (which corresponds to the size of algebraic circuits of depth only 2).


What are the prospects of research in database field?

As usual, to have an idea of what is happening in a field, have a look at the major conferences: SIGMOD/PODS, VLDB, ICDT, to name a few.


I believe the class you are looking for is $PSPACE$. Suppose you have $exp(n^k) = 2^{O(n^k)}$ processors fitting the requirements:

  Every computer reads the polynomial number of polynomial sized messages it received in  the previous time step.
  Every computer runs some polytime computation that can depend on these messages.
  Every computer passes a message (of polylength) to each of its neighbours.

This can be modeled by having a circuit with $poly(n)$ layers, where each layer has $exp(n^k)$ "gates", and each "gate" does a polynomial time computation (satisfying part 2) with polynomial fan-in (satisfying part 1), and has polynomial fan-out (satisfying part 3).

Since each gate computes a polynomial time function, they each can be replaced by a polynomial size circuit (with AND/OR/NOT) in the usual way. Note the polynomial fan-ins and fan-outs can be made to be 2, by only increasing the depth by a $O(\log n)$ factor. What remains is a $poly(n)$ depth uniform circuit with $exp(n^k)$ AND/OR/NOT gates. This is precisely alternating polynomial time, which is precisely $PSPACE$.


tournament selection in genetic algorithms

Here's the basic framework of a genetic algorithm.

N = population size
P = create parent population by randomly creating N individuals
while not done
    C = create empty child population
    while not enough individuals in C
        parent1 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        parent2 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        child1, child2 = crossover(parent1, parent2)
        mutate child1, child2
        evaluate child1, child2 for fitness
        insert child1, child2 into C
    end while
    P = combine P and C somehow to get N new individuals
end while

There's a little more to it than this basic skeleton, as there are things like crossover rates where you might not always do crossover, opportunities for additional operators, etc., but this is the basic idea at least.

Most often, the "while not enough individuals in C" can be thought of as "while size(C) < N"; that is, you want the same number of offspring as parents. There are plenty of other ways, but that's a good way to start at least. I'm not sure if this is what you mean by having 20% of the chromosomes in the next iteration or what, but for now, just go with it.

So then the question of how to do tournament selection can be addressed. Note that selection is only that one step of the process where we pick individuals out of the population to serve as parents of new offspring. To do so with tournament selection, you have to pick some number of possible parents, and then choose the best one as the winner. How many possible parents should be allowed to compete is the value of k I mentioned earlier.

func tournament_selection(pop, k):
    best = null
    for i=1 to k
        ind = pop[random(1, N)]
        if (best == null) or fitness(ind) > fitness(best)
            best = ind
    return best

Let k=1. Looking at the pseudocode, this yields purely random selection. You pick one individual at random and return it.

Let k=10*N. Now we have a pretty high probability of picking every member of the population at least once, so almost every time, we're going to end up returning the best individual in the population.

Neither of these options would work very well. Instead, you want something that returns good individuals more often than bad ones, but not so heavily that it keeps picking the same few individuals over and over again. Binary tournament selection (k=2) is most often used.

In this basic framework, you can't end up with an empty population. You'll always have N individuals in the population and you'll always generate N offspring. At the end of each generation, you'll take those 2N individuals and prune them down to N again. You can either throw all the parents away and just do P = C (generational replacement), you can keep a few members of P and replace the rest with members of C (elitist replacement), you can merge them together and take the best N of the 2N total (truncation replacement), or whatever other scheme you come up with.


Note that $T=S$ and $T=\emptyset$ are trivial solutions.

With the constraints $T \neq \emptyset$ and $S\setminus T \neq \emptyset$ the problem seems (unless the proof below is wrong :-) NP-complete. A possible reduction is from PARTITION: given a set $A$ of $n$ positive integers $A=a_1,..a_n$, can $A$ be partitioned in two sets $A = A_1 \cup A_2$ such that $\sum_{a_i\in A_1} a_i = \sum_{a_j \in A_2} a_j$?

Let $M = \sum_{a_i \in A}a_i$; without loss of generality we can assume that $M$ is even.

You can pick $S = A \cup \{a_{n+1}, a_{n+2}\}$ with $a_{n+1}= a_{n+2}=-M/2$; so we have $\sum_{s \in S}s = 0$ (right hand side of the equation of your problem).

The original PARTITION problem has a solution if and only if your problem has a solution.

$(\Leftarrow)$ Suppose that there exists $T$ such that $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s|\le\sum_{s\in S}s$ = 0. So the absolute value of the difference of the sums is zero: $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s| = 0$  $T$ cannot contain both $a_{n+1}$ and $a_{n+2}$, otherwise  $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s| > 0$ because at least one element $a_i>0$ must be contained in $S \setminus T$ and $|-M/2 -M/2 - a_i| > M$. For the same reason $S \setminus T$ cannot contain both $a_{n+1}$ and $a_{n+2}$. So $a_{n+1} \in T$ and $a_{n+2} \in S \setminus T$, and their contribution to the absolute value of the difference of the sums is $0$. So the remaining elements must be partitioned in such a way that the sum of the elements in $T$ equals the sum of elements in $S \setminus T$ in order to have an absolute value of the difference of the sums equal to $0$.

$(\Rightarrow)$ If the original partition problem has a solution, then it is easy to see that if $T = A_1 \cup a_{n+1}$ we get an absolute value of the difference of the sums equal to $0$.


Lower bounds for constant-depth formulae?

This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (http://eccc.hpi-web.de/report/2013/169/).

As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula.

Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can be computed by a constant-depth circuit of depth $d$ and size $S = O(n^3)$, but any constant-depth formula (or even a $\sqrt{\log n}$-depth formula) needs size $S^{\Omega(d)}$ to compute it.

(Forgot to say this before: Thanks to Benjamin Rossman for letting me know about this result.)


How hard is it to determine the chromatic number of a unit distance graph?

Okay, this seems easy. Below I sketch why it is NP-hard to decide if a unit distance graph has a $3$-coloring. They key observation is that in a $3$-coloring any two vertices $u$ and $v$ at distance $\sqrt 3$ must get the same color if the two vertices at unit distance from them are also present in the graph. With this gadget we can convert the decision problem of the $3$-colorability of any graph $G$ into the decision problem of the $3$-colorability of a unit distance graph $G'$as follows.

Map the vertices of $G$ into the plane such that no two are at unit distance. Connect every two adjacent vertices with a polygonal path that consists of segments of length $\sqrt 3$ and one segment of length $1$. Add the endpoints of the segments to the vertices of $G'$, and also the two vertices at unit distance from the ends of segments of length $\sqrt 3$. Now $G'$ is $3$-colorable if and only if $G$ is $3$-colorable if there are no additional coincidences among the vertices of $G'$ but we can pick the paths in a generic way.

With a little more care, we can also show that the problem remains NP-complete if we restrict it to planar unit distance graphs. For this, we need to use that it is NP-hard to decide whether a planar graph with maximum degree $4$ has a $3$-coloring. We can repeat the previous construction, just if we map the vertices of $G$ far away in the plane, then the respective paths won't cross. (For this reduction, maximum degree $6$ would suffice.)
This also proves that it's NP-hard to decide whether the chromatic number of a coin graph is $3$ or $4$.

A similar construction also shows that deciding whether a unit distance graph is $4$-colorable is also NP-complete using that there is a unit distance graph in whose only $4$-coloring two given vertices at distance $\frac 83$ must get the same color. Using this gadget, $\frac 83$ can play the role of $\sqrt 3$ in the previous construction.


Ramanujan graphs have second eigenvalue $\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ (with $D$ the degree of the graph), while random graphs only achieve $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ w.h.p. In fact, in general we have that $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$, with the $o(1)$ term going to $0$ with $D$ held constant (as the number of vertices $N\rightarrow \infty$), so in some sense these are optimal.


$\epsilon$-nets with respect to the cut norm

Here is an easy estimate.  Here we call a set S⊆X an ε-net of a metric space X when for every point x∈X, there exists a point s∈S such that the distance between x and s is at most ε.  If you want a strict inequality in the definition of ε-net, you can tweak the value of ε slightly.

It holds that ||A||∞ ≤ ||A||C ≤ n2||A||∞, where ||A||∞ denotes the entrywise max-norm of an n×n matrix A.

It is easy to construct an ε-net of the metric space ([0,1]N, d∞) with size ⌈1/(2ε)⌉N, and it is not hard to show that this size is the minimum.  (To show the minimality, consider the ⌈1/(2ε)⌉N points whose coordinates are multiples of 1/⌈1/(2ε)−1⌉ and show that the distance between any two of these points is greater than 2ε.)  By setting N=n2 and combining this with the aforementioned comparison between the cut norm and the max-norm, the minimum cardinality of an ε-net with respect to the cut norm is at least ⌈1/(2ε)⌉n2 and at most ⌈n2/(2ε)⌉n2.

Update: If my calculation is correct, a better lower bound Ω(n/ε)n2 can be obtained by the volume argument.  To do this, we need an upper bound on the volume of an ε-ball with respect to the cut norm.

First we consider the “cut norm” of a single vector, which is the maximum between the sum of positive elements and the negated sum of negative elements.  It is not hard to show that the volume of an ε-ball in ℝn with respect to this “cut norm” is equal to

$$ \varepsilon^n \sum_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!}
= \varepsilon^n \sum_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!} $$

$$ = \frac{\varepsilon^n}{n!} \sum_{r=0}^n \binom{n}{r}^2
= \frac{\varepsilon^n}{n!} \binom{2n}{n}
= \frac{(2n)!\varepsilon^n}{(n!)^3}. $$

Next, since the cut norm of an n×n matrix A is greater than or equal to the cut norm of each row, the volume of an ε-ball in ℝn×n is at most the nth power of the volume of an ε-ball in ℝn.  Therefore the size of an ε-net of [0,1]n×n must be at least

$$ \frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2}, $$

where the last equality is a boring calculation in which we use Stirling’s formula: ln n! = n ln n − n + O(log n).


Is there a generalization of information theory to polynomially knowable information?

Yes. Time-bounded Kolmogorov complexity is at least one such "generalization" (though strictly speaking it's not a generalization, but a related concept). Fix a universal Turing machine $U$. The $t(n)$-time-bounded Kolmogorov complexity of a string $x$ given a string $y$ (relative to $U$), denoted $K^t_U(x | y)$ (the subscript $U$ is often supressed) is defined as the shortest string $p$ (a "program" for $U$) such that $U(p,y)=x$ and such that the computation of $U(p,y)$ takes at most $t(|x|)$ time. If you take this as your definition of "conditional information", then you can likewise define all the usual concepts from information theory.

However, in this time-bounded setting, not all of the usual theorems of information theory are known to hold. For example, symmetry of information is known to hold for usual Kolmogorov complexity (no time bound), but not known to hold for time-bounded. See, for example, Chapter 6 of Troy Lee's thesis.

If you are concerned that this applies to strings rather than distributions, I suggest reading the following papers, which say that in fact Kolmogorov complexity of strings and Shannon entropy of distributions are very closely related:

Grunwald and Vitanyi. Shannon Information and Kolmogorov Complexity
Hammer, Romashchenko, Shen, Vereshchagin. Inequalities for Shannon Entropy and Kolmogorov Complexity.

(On the other hand, there are some properties that are known not to be shared between the two, see Muchnik & Vereshchagin, Shannon Entropy vs. Kolmogorov Complexity.)


Efficient verification of Kemeny-optimal rankings

The following decision problem is NP-complete:
Kemeny Score
Input: An election ($n$ partial or full rankings of $m$ candidates) and a positive integer $k$.
Question:: Is there a ranking with $\sum_i d(r, q_i) \leq k$?

This decision problem is often seen as "natural decision problem" behind Kemeny voting. It is trivially in NP since computing the Kendall-Tau distance is in P. For NP-hardness see for example [Bartholdi, Tovey and Tick, Social Choice and Welfare 1989] or [Dwork, Kumar, Naor, and Sivakumar, WWW 2001].

However, the problem you describe above looks more like an optimization problem. To answer your question I refer to the Kemeny Winner problem which is $P_{||}^{NP}$-complete (see [Hemaspaandra, Spakowski, Vogel, TCS 2005]). Thus, already deciding whether a candidate is an (optimal) winner in Kemeny's system is presumable not in NP.


We are going to show that in MLTT with propositional truncation the type
$$\textstyle
\prod_{A:U_0}\prod_{B:U_0}
(\|A\| \to A) \times (\|B\| \to B) \to (\|A + B\| \to A + B)
$$
has no inhabitants. Assume it did.
We shall work in a specific model of MLTT with propositional truncation, namely  assemblies over number realizability. It is not too important what this model is precisely, except for the following facts:

there is an object of reals $\mathbb{R}$ in which
$\Pi (x : \mathbb{R}) \; \|(x < 1) + (x > 0)\|$, and
every map $\mathbb{R} \to \mathsf{bool}$ is constant.

Hoever, using the above type, we may inhabit
$$\Pi(x : \mathbb{R}) \; \|x < 1\| + \|x > 0\|,$$
contradicting the fact that every map $\mathbb{R} \to \mathsf{bool}$ is constant.
To do so, consider any $x : \mathbb{R}$ and instantiate $A = \|x < 1\|$ and $B = \|x > 1\|$ (and use the fact that $<$ maps into propositions).


Number of subsets on a set with partial order

See three closely related questions Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits? and Is counting maximal cliques in an incomparability graph #P-complete? and https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset

They are all on antichains rather than downward-closed sets but downward-closed sets correspond one-for-one with the antichains of their maximal elements.

I believe both of the cstheory questions have answers with references that also answer your question: no, the problem is #P-complete.


Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?

This answer is based on the assumption that equivalence of two regexes is defined as they recognize the same language.  It does not answer the current question.

You have a common misunderstanding that reluctant quantifiers change the set of strings a regular expression matches.  It does not, and it only changes which options are tried first.

For example, if you perform a regex match 'aaaa' =~ /a+/ in Perl, it finds the first match in the string aaaa, and remembers which substring it matched in a special variable.  Even if there are more than one substring of aaaa which matches the given regex, the matches other than the first match are ignored.

Whether quantifiers are greedy or reluctant affects what the first match is among many matches, but the set of matches does not change.  In this sense, the set of strings which a regex matches is unchanged no matter whether you use usual greedy quantifiers or reluctant quantifiers.


Autoencoders and information compression

In the other situation when in your notation $k>>d$, in one of our papers we did analyze one such autoencoder in details to be able to say something about what you are asking. Does our Theorem 3.2 here, https://arxiv.org/pdf/1708.03735.pdf help? It took us about 15 pages of laborious calculation to get this - hopefully its helpful! :D

The "??" in the statement is a LaTeX error. It was meant to refer to the previous Theorem 3.1.


Let you want to represent integer values from 0 to 999. You need 3 digits, each has 10 states, 30 states overall. When using binary digits, you need 10 digits with 2 states, 20 states overall, So binary representation is more "dense". In general case, p*ln(N)/ln(p) states is required. This formula has minimum at p=e. However, this is pure theoretical speculation. Numeral system with the base 3 is slightly more dense than that of 2, and 3-based computers were really built, but appeared more complex than binary computers.


Which formalism is best suited for automated theorem proving in set theory?

There are numerous ways of formalizing set theory:

ZFC uses first-order logic and a primitive relation $\in$
NBG uses first-order logic, a primitive relation $\in$, and a primitive predicate $S$
Church's type theory is multi-sorted and uses infintely many types
Type theory is similar to set theory, but not quite the same
Second-order arithmetic, through some coding tricks, can express many things we usually want to express in analysis
etc.

But this is all quite irrelevant to what you are doing. You seem to be using automated theorem provers as "black boxes" to prove simple theorems in set theory. This is a hit-and-miss activity: some theorem provers will prove some simple things, and others will prove other simple things, but they will all fail on statements that mathematicians consider "completely trivial". Such is the state of automated theorem proving.

Rather than worrying which particular formalism you are using, you should investigate which automated theorem prover is good for what. It is also very likely that you do not actually need set theory. It would be helpful if you described what you're doing, but not here, this should go on cstheory.stackexchange.com. There perhaps we can suggest a good way of formalizing whatever you are doing.


Formalizing the theory of finite sets in type theory

I know it can be done 'elegantly' in a dependently typed system. But, from a classical point of view, the resulting definitions seem extremely alien.

Can you explain what you mean by "alien"? It seems to me that you
formalize the concept of finite set in precisely the same way in
type theory and in set theory.

In set theory, you proceed by defining the set $Fin(n)$ as
$$
  \mathrm{Fin}(n) \triangleq \{ k \in \mathbb{N} \;|\; k < n \}
$$
Then, you define the finiteness predicate as:
$$
  \mathrm{Finite}(X) \triangleq \exists n\in\mathbb{N}.\; X \simeq \mathrm{Fin}(n)
$$
Where $A \simeq B$ means isomorphism of sets.

In type theory, you can do exactly the same thing!
$$
  \mathrm{Fin}(n) \triangleq \Sigma k:\mathbb{N}.\; \mathsf{if}\; k < n\,\mathsf{then}\; \mathsf{Unit} \;\mathsf{else}\; \mathsf{Void}
$$
Note that $\mathrm{Fin}(n)$ is a type with $n$ elements (since the second component of the pair is
proof-irrelevant). Then, you can define the finiteness type constructor as:
$$
  \mathrm{Finite}(X) \triangleq \Sigma n:\mathbb{N}.\; X \simeq \mathrm{Fin}(n)
$$
Where $A \simeq B$ means isomorphism of types.


Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P

1a) yes by the inclusion.
b) Not sure what you mean by "it". If P=PSPACE then A and B are both in P.

2a) Not necessarily, A could be much easier than B.
b) There are relativized worlds where P=FewP<>NP.
c) No, RP^UP does not necessarily contain NP. Don't confuse UP with Promise-UP.


(I'm assuming that by 'axiom schemas', you have in mind the work of Gimenez)

Extensionally, W-types and Gimenez' axiom schemas are equivalent.

However, in an intensional setting, you won't go far with W-types: they are too extensional (by the very definition of the encoding) to be fit for programming. This has been discussed by several authors, especially :

Conor McBride: http://mazzo.li/epilogue/index.html%3Fp=324.html
Peter Dybjer, "Representing inductively defined sets by wellorderings in Martin-Löf's type theory"
Guogen & Luo, "Inductive data types: well-ordering types revisited"


Rademacher complexity beyond the agnostic setting

(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, you will not be able to give any meaningful risk decay rates (which is what Rademacher complexities enable you to do). Alternatively, you could assume something about the distribution (trivial case: it has finite support). Then you can get distribution-dependent rates.

(b) For unbounded losses, you typically need additional assumptions such as convexity or tail decay. See, eg,
https://papers.nips.cc/paper/3894-smoothness-low-noise-and-fast-rates
and
http://proceedings.mlr.press/v32/kontorovicha14.html

(c) It looks like you're looking for a lower bound on the risk in terms of Rademacher complexity. Any such result would have to be distribution-dependent. Since Rademacher complexity is majorized by covering numbers (via Dudley's integral) and also minorized by these (Sudakov inequality), you could probably use the covering-number characterization of learnability:
https://www.sciencedirect.com/science/article/pii/030439759190026X


Reference request: Depth- (or Breadth-) first search with hints?

The Reachability Wikipedia page lists several solutions, although the only one which works for general graphs involves computing the transitive closure, which it sounds like you want to avoid.
This is additionally for exact computations of the path.


In System F à la Church, can we automatize type inference for the for-all elimination?

I'm not really sure I've understood the question.
First, I try to reduce your problem to the following unification problem:

Given a system F type τ(X) with a free (type) variable X, and a type σ.
Is it possible to find a type γ such that τ(γ) = σ ?

Here is a pseudo-code (with an exception raised when not unifiable) for
solving this problem.

unify (X, σ) = σ
unify (Y, Y) = Y
unify (τ₁ → τ₂, σ₁ → σ₂) = unify(τ₁,σ₁) → unify(τ₂,σ₂)
unify (∀Y.τ(Y), ∀Y.σ(Y)) = ∀Y.unify(τ(Y),σ(Y)) (with Y a fresh variable)
unify (_,_) = raise Not_unifiable

You can prove (by induction) that γ = τ(unify(τ(X),σ) works if and
only an exception is not raised.

Now for your problem you can take

f (ΛX.t) (r) = match type of t with "τ₁ → τ₂" => unify (τ₁, type of r) | _ => fail end

(of course your function f should take as argument a context if your terms are open).


NPI-candidate hereditary graph property?

Is there a particular style of problem you are looking for, or anything related to a hereditary graph property? Two common types of problems would be
(1) recognition: does a given $G$ have the hereditary property? or
(2) find the largest (induced or not) subgraph $H$ in $G$ having the hereditary property.

As I'm sure you are familiar, (2) is NP-complete (Mihalis Yannakakis: Node- and Edge-Deletion NP-Complete Problems. STOC 1978: 253-264) But I'm not sure if you are specifically only asking about problems of type (1) (recognition problems.)

There are a few recognition problems of hereditary graph classes which are still open. I think the one-in-one-out graphs are open to recognize and clearly in NP.

Graphclasses.org also reports that the related class of opposition graphs is still open to recognize (and these are also clearly in NP.) Apparently, so is the class of Domination graphs.

A large list of open (and unknown) recognition status can be found on that site, and pretty much all of those properties appear to be hereditary.

http://www.graphclasses.org/classes/problem_Recognition.html

There is one recognition problem they list under GI-complete, which is not a hereditary property ... so it is interesting to think that perhaps deciding a hereditary problem may indeed have a dichotomy theorem.


The complexity of determining if a fixed graph is a minor of another

There is a preprint by Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed that claims a quadratic time algorithm: "The disjoint paths problem in quadratic time". It is formatted as a conference submission rather than a journal paper so I'm not sure it's possible to verify the details, though (I haven't really tried, myself).

A very recent survey by Kawarabayashi cites this as the best known result for the closely related disjoint paths problem: Ken-ichi Kawarabayashi (2011), "The Disjoint Paths Problem: Algorithm and Structure", WALCOM: Algorithms and Computation, LNCS 6552, pp. 2–7, doi:10.1007/978-3-642-19094-0_2.

I don't know whether this means that the $O(n\log n)$ claim in Kothari's comment is vapor or whether it means that it's still at an earlier stage of being written up.


Surprising algorithms for counting problems

I don't know if the following problems reduce or not to computing the determinant, but I will list anyway:

1) Counting the number of paths in a DAG from a node $v_0$ to a node $v_f$.
But this is not surprising. Simply determining whether $v_f$ is reachable from $v_0$ is in NL, and thus in DET. I have no idea about the counting version.

2) Counting the number of solutions of problems definable in MSO-logic in structures of bounded Tree width.  See for example the paper which buids on works of Courcelle, Arnborg and others.

3) If you have a function $f:\{0,1\}^{n}\rightarrow \{0,1\}$, that can be expressed by a bolean circuit of logarithmic tree width, than you can
count the number of inputs $x$ such that $f(x)=1$ by devising a quantum
circuit $U_f$ which sends $|x\rangle|0\rangle$ to $|x\rangle|f(x)\rangle$,
and classically simulating the probability of measuring $|1\rangle$ in the
second register after the application of $U_fH^{\otimes n}|0\rangle|0\rangle$ using these results.


OK, fine. Since people seem to keep liking this question, I decide to answer this question myself.

TLDR : yes, F<:+bot is undecidable, as shown a proof of translation from it to F<: in the following link by myself: https://gitlab.com/JasonHuZS/AlgDotCalculus/blob/master/agda/FsubBot.agda

bot⇒full : ∀ {Γ S U} → List.map _* Γ ⊢ S * <: U * → Γ ⊢F S <: U
full⇒bot : ∀ {Γ S U} → Γ ⊢F S <: U → List.map _* Γ ⊢ S * <: U *

Despite such intuitive fact, I have to emphasize that, in the presence of subtyping, a syntactical extension of an undecidable language does not have to generate yet another undecidable language. More specifically, the decidability is a very global property of a language which depends on every interaction of the rules, and should not be assumed if a proof is not present.

In the case of F<:, the proof can easily discharge all usage of bot, merely because in F<:+bot, there isn't other creative way of using bot, to a point that it turns the translation of derivation tree to a non-trivial level.

In particular, I am working on another calculus (D<: in another source code), in which bot has so creative behavior to a point that the translation from it to F<: does not generally hold, and therefore, the calculus could be decidable, or, if it's undecidable, F<: does not reside in it as a sub-language.


Complexity of finding even cuts for a graph

Such a cut exists if and only if the graph has an even number of spanning trees, which can be checked in polynomial time by using the matrix-tree theorem. See http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf


Decidability of diophantine equations over {=, +, gcd}

($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$, and $\le$:
$$\begin{align*}
\gcd(a,b)=c&\iff c\ge0\land c\mid a\land c\mid b\land\forall d\:(d\mid a\land d\mid b\to d\mid c)\\
&\iff c\ge0\land c\mid a\land c\mid b\land\exists u,v\:(a\mid u\land b\mid v\land c=u+v).
\end{align*}$$
Thus, any existential sentence over the structure $\langle\mathbb Z,+,\gcd\rangle$ (or even $\langle\mathbb Z,{\le},+,\gcd\rangle$) can be (in polynomial time) converted to an equivalent existential sentence over the structure $\langle\mathbb Z,{\le},+,|\rangle$, which can in turn be converted to an equivalent existential sentence over the structure $\langle\mathbb N,+,|\rangle$ in the obvious way. The last problem is decidable by the result of Lipshitz [1] quoted in the question.
Reference:
[1] Leonard Lipshitz: The Diophantine problem for addition and divisibility, Transactions of the American Mathematical Society 235 (1978), pp. 271–283, doi: 10.1090/S0002-9947-1978-0469886-1.


Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$

This would imply that L⊊NP since L⊆TISP(poly(n),n^k) k∈N


Which areas of computer science have lots of overlap with physics?

[The following is more an extended comment with pointers than a real answer.]

If you were in France, a good answer would be combinatorial physics.  I say "if you were in France" because, for reasons that escape me but that must be mostly historical, in France combinatorics is considered part of theoretical computer science :-)  In the rest of the world, combinatorics is considered to be a branch of mathematics, so I guess it is more correct to say that combinatorial physics is about interactions between physics and discrete math, rather than CS.

Anyway, in my lab (which is a CS lab) there's a research group which focuses on several aspects of combinatorics, in particular combinatorial physics.  This is by no means the only example in France of a combinatorics group in a CS lab whose research overlaps with physics; another example off the top of my head is this one in Bordeaux. Some of the members of these groups are theoretical physicists.

The "official" recognition of combinatorial physics as a research field of its own is very recent, as you may read in this blog post, which contains some pointers and basic info about it.  Computer science is explicitly mentioned a couple of times, although maybe not exactly in the sense you would expect, but I am sure that my colleagues from those research group would be able to give you more precise answers.  Maybe you can start checking out their web pages for additional info.


What are good set size estimation algorithms for small sets (around 10-50 elements)?

2^32 is only 4 billion; and doubtful you will saturate even a small fraction of that if you are watching IPs. Just store it all. A radix tree will compact as it saturates since you can flag entire subdomains as saturated.


Boolean circuits which correspond to L/poly

$\mathsf{L}/\mathrm{poly}$ can be characterized by polynomial size skew circuits. A boolean circuit is called skew if every AND-gate has at most one child that is not an input gate. Skew circuits and branching programs can simulate each other with polynomial blow-up, so polynomial size skew circuits and branching programs compute the same class of functions, which is $\mathsf{L}/\mathrm{poly}$.

A proof of these simulations can e.g. be found in this paper by Balaji, Krebs and Limaye.


Fast algorithm to find pair of triangles with a common edge in a complete graph

There's a straightforward algorithm.  For each edge $(u,v)$, compute the multiset of products of weights of paths of length 2 from $u$ to $v$:

$$S_{u,v} = \{\text{wt}(u,t) \cdot \text{wt}(t,w) : (u,t) \in E \land (t,w) \in E\}.$$

These multisets can be computed in at most $O(|V| \cdot |E|)$ time.  In practice it suffices to enumerate all edges $(u,v)$, then enumerate all edges $(u,t)$ incident on $u$, then check whether $(t,w)$ is an edge.

Next, for each edge $(u,v)$ and each pair of values $x,x' \in S_{u,v}$, plot the point $(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$ on the scatterplot.  This can be done in at most $O(|V|^2 \cdot |E|)$ time.

It might not be easy to do asymptotically significantly better than this.  For a complete graph, the scatter plot can have $\Theta(|V|^4)$ points, so there is no hope for an algorithm whose running time is faster than $O(|V|^4)$ on complete graphs; and this algorithm takes $O(|V|^4)$ time on complete graphs, so it is asymptotically optimal for such graphs.  For sparse graphs, this algorithm takes $O(|V|^3)$ time, and there might be some hope to get the running time a little faster for sparse graphs.

If it's still too slow, rather than creating the entire scatterplot, you could sample the points on the scatterplot and plot that.  One way to do that is to compute the multisets $S_{u,v}$, then for each edge $(u,v)$ sample a bunch of pairs of values $x,x' \in S_{u,v}$ and plot the points $(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$ on the scatterplot for each such pair.  If there are a lot of points on the scatterplot, plotting a random sample of the points should also be sufficient for visualization purposes and should give you a good sense of the "shape" of the scatterplot.


VC-dimension of infinite set of triangle wave

First of all, presumably you want the VC-dimension of your class of composed with the sign function, which yields a class of Boolean functions (otherwise, VC-dim is not defined). With that out of the way, the answer is: It's infinite. That will be the answer for any periodic function class that contains all possible frequencies and crosses the x-axis. For a concrete proof for this sine wave, see Theorem 9 here:
https://www.cs.bgu.ac.il/~karyeh/fat-add.pdf


Clifford group quantum operations and classical computation

As pointed out in a comment above, if it were possible to coherently implement a Toffoli gate using Clifford group gates, then the Clifford group would be universal for quantum computation. It was noted in Section 5 of this paper that something even stronger is true: informally speaking, if there exists a class of quantum circuits which can be simulated efficiently classically, and which is universal for classical computation, then BQP=BPP. Thus we would expect simulable classes of quantum circuits not to be universal for classical computation.

Clifford group circuits themselves are particularly weak, and correspond to the complexity class Parity-L, as was shown here.


Why does the transformation in the proof for SL=L preserve connectedness of s and t?

The proof of Theorem 4.1 states that:

  Let $S$ be the connected component of $G$, such that $s \in S$.
  By the arguments above, $S \times [N]$ is a connected component of $G_{\mathrm{reg}}$, and $G_{\mathrm{reg}}|_{S\times [N]}$ is non-bipartite. [...]

  By Lemma 3.2 and Lemma 3.3, we have that $\lambda(G_{\exp}|_{S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell}) \leq 1/2$. In particular, we have that $S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell$ is a connected component of $G_{\exp}$.

In particular, if $t \in S$ then both $s'$ and $t'$ belong to the connected component $S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell$.

Lemma 3.2 only works when $G$ is non-bipartite and $\lambda(H) \leq 1/2$. Perhaps one of these conditions wasn't satisfied in your examples?


Addding edges to spanning tree without destroying planarity

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of $n$ points $(x_i,y_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes have the same sign have length approximately $\sqrt n$ (according to the Erdős–Szekeres theorem).  Add to $G$ one edge for each point $(x_i,y_i)$ in $S$, whose endpoints are the vertices at positions $x_i$ and $n+y_i$ in the path.

Now consider any planar graph sandwiched between $T$ and $G$, and draw it in the plane such that $T$ lies along a horizontal line (possibly causing the other edges to curve rather than being straight, but without crossings). We can partition the edges added to $T$ into four classes: the ones that stay below the line, the ones that stay above the line, the ones that wrap around the left endpoint of $T$, and the ones that wrap around the right endpoint of $T$ (wrapping around exactly two endpoints of $T$ doesn't help — all such edges can be deformed topologically so that they stay above or below the line — and wrapping around more than twice is not possible). In each of these four classes, a subset of non-crossing edges must correspond to a monotonic polygonal chain in $S$. Therefore, the total number of added edges is at most $4\sqrt n + O(1)$.

The Erdős–Szekeres theorem can be used in the other direction to find large subsets of edges that don't cross each other when $T$ is a path. I'm not entirely sure what happens when $T$ isn't a path, but it seems likely to me that the size of the planar subsets you can find only goes up in this case, so that (in the case of a linear number of edges and bounded vertex degree) $\Theta(\sqrt n)$ is the right bound on the number of added edges you can always find.


Lower Bound on the difference between uniform and prefix-free complexity

Lance Forthnow's example works to separate decision complexity and prefix-complexity: $Ku(0^n) \le O(1)$ for all $n$, and at the same time $K(0^n) > \log n$ for infinitely many $n$.

Note that $Ku(x) \le C(x) + O(1)$ where $C(x)$ denotes the plain complexity of $x$.

Decision complexity can also be lower than the logarithm of a priori probability. The argument is similar as the standard argument to separate plain and prefix complexity: we take advantage of the length of a program to encode an initial segment of a string. More formally, consider a long anough string $x$ such that for each $i < |x|$ we have $M(x_1...x_i) \le M(x_1...x_{i-1})/2$. Clearly we have $KM(x_1...x_i) \ge i$. Let $n \le |x|$ be a number whose binary representation is an initial segment of $x$. A uniform program of length $n - \log n + O(\log \log n)$ is obtained as follows: if $i \le \log n$ return the $i$-th bit of $n$ in binary, if $i \ge \log n$, return the corresponding bit in a literal representation of $x_{1 + \log n}...x_n$. For this program, we need to encrypt $\log n$ and $x_{1 + \log n}...x_n$. [The value $n$ can be recovered from $\log n$ and the length of the program.]


What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

An old paper by Italiano (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) gives a data structure that supports edge insertions in $O(n)$ amortized time and reachability queries in constant time. I'm not aware of better incremental algorithms.


Complete axiomatization of relation algebras without ${}^-$ and $\top$

The equational theory of the signature $S=\{\vee,\wedge,.,\epsilon,^\smile\}$ is decidable. See this paper by Andréka and Bredikhin.
The idea is to associate to every term $t$ over $S$ a graph $G_t$. Then Andréka and Bredikhin show that two terms $t$ and $u$ are equivalent iff there is a graph homomorphism from $G_t$ to $G_u$ and a graph homomorphism from $G_u$ to $G_t$. Testing graph homomorphism between finite graphs is decidable, hence the equational theory is also decidable.
The equational theory of $S$ is not finitely axiomatizable, due to the paper of Andréka and Mikulas you have cited. However, contrarily to what is claimed in this paper, the restrictions of the signature to, say, $\{., \cap, \epsilon\}$ is not finitely axiomatizable, as shown in this paper.


Is the running time of Boyer-Moore linear?

Here is a true sublinear string matching algorithm, on all alphabet sizes, which answers the question Kaveh posted. My question was: Is Boyer-Moore actually linear on small alphabets?

The log base below is $|\Sigma|$, and (ceiling of) $logM$ (often just one) is implied.

Preprocess the Pattern into a lookup table, with $M-logM+1$ keys, each key having size $logM$, and with associated key positions in the Pattern. Converting sequences of $logM$ letters into array indices is the only tricky part. The table size is $|\Sigma|$ raised to ceiling of $logM$, for easy indexing.  Each bucket is a short, possibly empty, list of key positions.  Run time: $O( MlogM )$.

Main: Skip through Text positions $k$ by $(M - logM + 1)$, constructing a $logM$ sized search key at Text positions $k$ thru $k + logM -1$. Look up the search key in the table. If found, naively attempt to match the Pattern at Text[$k$ - key position].  The naive attempt almost certainly fails in $logM$ comparisons. The only tricky part is that a key may occur in multiple Pattern positions.  The expected number of test positions is $O(1)$.  Expected run time: $O( (N/M)logM )$.

Post: Garbage collect the preprocessing space, $O(MlogM)$.

A proof that Main is optimal for $N>M^2$, on all alphabet sizes, is needed.


How hard is it to reduce termination to partial correctness?

One way to answer this is to consider the computational complexity of the decision problems for the classes of partial correctness and termination queries that are known to be decidable.  Abstract interpretation using the polyhedral domain can infer the partial correctness annotations you mention in cases where the required annotations are conjunctions of linear inequalities.  Computing the abstract post-condition is exponential in the number of variables.  Then there is the overhead of finding the fixed point.  See Cousot's early papers for more on this and the Apron library if you want to play with it directly.

Finding variant functions is decidable when the variant functions are linear.  I couldn't find a complete characterization of the complexity of this, but "Termination of Linear Programs" by Tiwari has a section that discusses complexity.  See also "A Complete Method for the Synthesis of Linear Ranking Functions" by Podelski and Rybalchenko.  Also, Byron Cook has done work on leveraging abstract interpretation to help construct termination arguments.  See, for example, "Ranking Abstractions" and "Variance Analyses from Invariance Analyses".  These may give further insight into the relationship between partial correctness and termination.

Links:

http://www.csl.sri.com/users/tiwari/html/cav04.html
http://www7.in.tum.de/~rybal/papers/vmcai04-linear-ranking.pdf
http://www.dcs.qmul.ac.uk/~hyang/paper/esop08.pdf
http://research.microsoft.com/terminator/popl07a.pdf


Decomposing k-connected graphs into (k+1)-connected components

The following recent paper seems to be related to your question:

Connectivity and tree structure in finite graphs
Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein

http://arxiv.org/abs/1105.1611


Counting grid colorings that avoid certain features

If you want bounds for a fixed $k$ (rather than an asymptotic expression/formula that works for all $k$), one approach might be to use random sampling: repeatedly choose a random coloring, check whether it meets your criteria, and count how many of the trials were successful.  This gives you an estimate of the fraction of colorings that meet your criteria.  This can be converted into a rough estimate of the total number of colors that meet your criteria (just multiply by $k^{mn}$).

You can then use a Chernoff bound to get upper and lower bounds on the number of colorings that meet your criteria, where these bounds hold with probability $\ge 1-2^{-100}$ (taken over the random trials).  In other words, you would have to be extremely unlucky in your choice of random trials for those bounds to be wrong.


Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

If you have a graph with maximum degree $\Delta$, then the greedy algorithm finds a coloring with $\Delta+1$ colors, so for $k = \Delta+1$ the assumption that you are given a proper $k$-coloring does not change the complexity of the problem. It is known that independent set is NP-hard to approximate within factor $\Delta^{1 - o(1)}$, and Unique Games-hard to approximate within factor $\frac{\Delta}{O(\log^2\Delta)}$, which, for $k=\Delta$ is within a $\log \Delta$ factor from the upper bound you cite. (I prefer to write approximation factors as bigger than 1, so I am thinking of the upper bound you cite as $\frac{k}{2}$.)

However, it's still interesting to close these logarithmic gaps. This paper by Bansal may contain useful ideas.


If P=NP, there must be polynomial-time algorithms for NP-complete problems.  However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.


Are there websites for TCS announcements that maintain mailing-lists  or web feeds?

I think dmanet is one of a good sites for this, it also emails open positions for job and education in CS. But it's good for Europe.


Is there a non Turing-complete model of computation whose halting problem is undecidable?

You can easily build artificial models which are not Turing complete but the halting problem for them is undecidable. E.g. take all TMs that do not halt on anything but $0$.
Regarding the statement:
You cannot disprove a statement that is not precise enough. Almost none of the words in the statement is well-defined (please provide the definition for them if this is not the case).


Termination of the Bellman-Ford algorithm in asynchronous distributed model

I found the answer. The alpha synchronizer will do it.

Here is the full paper: Baruch Awerbuch (1985). Complexity of Network Synchronization


Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?

I understand the proof as follows.
Start with an arbitrary execution of the above algorithm. In this execution each operation on $TS[i]$ and $Val[i]$ has already been linearlized by assuming that these are single-writer multi-reader atomic registers. Therefore, by assumption, the schedule linearizes these low level operations.

The remainder of the proof shows that there exists some unique assignment of distinct times for each high-level operation such that the following are true.

For each such operation that starts at time $t_s$ and ends at time
$t_e$, the assigned time $t_a$ is in the interval $[t_s,t_e]$.
The sequence of high-level  reads and writes, as determined by this assignment of times, satisfies the linearlizability.


Minimal DFA satisfying a finite view of a language

As you already know from the comments, finding the minimal DFA satisfying a finite set of positive and negative examples is $\mathsf{NP}$-hard. However, not all hope is lost, if you are willing to modify your learning paradigm slightly then we can get back into $\mathsf{P}$.

Assume that you are trying to learn a an unknown DFA $W$ which is minimal for some language $L_W$. If you allow the oracle membership queries and to act as a teacher by answering the following question: Given a proposed DFA $G$ does it recognize $L_W$? If not, can you provide a counter-example?

Note that if the oracle has access to $W$ it can compare $G$ to $W$ in poly-time, since testing equality between regular languages is easy. Generating a counter-example can also be done in polynomial time.

In this framework, you can learn $W$ in polynomial time using Angluin's (1987; pdf) algorithm (or Schapire's refinement of it; see section 5.4.5). For more info about this model, here are two questions on cstheory and CS.SE about it:

Lower bounds for learning in the membership query and counterexample model
Are there improvements on Dana Angluin's algorithm for learning regular sets


Here's an $\Omega(\log(\frac{1}{\epsilon\cdot \delta}))$ lower bound following the discussion here with Yuval, and another one with Ross Berkowitz.
I assume for simplicity that the sampling process chooses $k$ completely random elements $v_1,\ldots,v_k$ of $F_2^n$ and outputs their span $V$.
A little extra work is needed to bound the probability that the $k$ vectors sampled are not independent, and in fact, this might be problematic when $k$ is close to $n$.
Denote $\ell\triangleq \log(1/\epsilon)$, and let $S$ be an affine subspace of co-dimension $\ell$. Let $S_0$ be the linear subspace of which $S$ is a shift.
Denote by $T\triangleq F_2^n/S_0$ the quotient space, which is a linear space of dimension $\ell$ who's elements are the cosets of $S_0$ in $F_2^n$. For each $v_i$ denote by $\bar{v}_i\in T$, the coset in which $v_i$ landed.
Denote by $T'\subset T$ the linear span of $\bar{v}_1,\ldots,\bar{v}_k$.
Assume $k\triangleq (\ell-1) + t$, we can lower bound the probability of the event $T' \subsetneq T$ by $2^{-t}$:
Condition on $\bar{v}_1,\ldots,\bar{v}_{\ell-1}$ being linearly independent - this can only decrease the probability of $T'\subsetneq T$.
Denote $T''\triangleq \mathrm{span}(\bar{v}_1,\ldots,\bar{v}_{\ell-1})$
Now, there is a probability of at least $2^{-t}$ that the rest of the $\bar{v}$'s all land in $T''$, and in such a case $T'\subsetneq T$
Now, note that $V\cap S \neq \emptyset$ is exactly equivalent to $x\in T'$ for some fixed $x\in \{0,1\}^{\ell}$ (that correspond to the what coset $S$ is of $S_0$). Furthermore, conditioned on the event $T'\subsetneq T$ $x\notin T'$ with probability at least $1/2$. Thus $V\cap S = \emptyset$ with probability at least $2^{-t}$. So we need $2^{-t}\leq \delta$ which implies $k\geq (\ell-1) + \log(1/\delta) = \log(1/\epsilon) + \log(1/\delta) -1$.


Efficient update of reachable set of a node in a digraph

You can check the Dynamic Transitive Closure Problem of a Digraph. The transitive closure (or reachability) problem in a digraph $G=(V,E)$ consists in finding
whether there is a directed path between any two vertices in $G=(V,E)$. The general idea
is to maintain some kind of structure in order to quickly respond to queries of the form:

is there a path connecting u and v? Now add/delete an edge $e \in E$: is there a path connecting u and v?

Some algorithms respond in $O(1)$ time but need $O(n^2)$ space. Some respond yes/no and some also give you an actual path though I do not remember the exact complexity to get the path.

For your case you have to check all nodes of $S$ against all other nodes $V-S$.

The easiest way to do it is to run BFS every time for every node in $S$. It depends on the application.

Take a look in the bibliography below:

D. Yellin, Speeding up dynamic transitive closure, Acta Informatica 30 (1993), pp.369-384.
[I86] G. Italiano, Amortized Efficiency of a Path Retrieval Data Structure, Theoretical Computer Science, 48 (1986), pp. 273-281.
[I88] G. Italiano, Finding Paths and Deleting Edges in Directed Acyclic Graphs, Information Processing Letters, 28 (1988), pp. 5-11.

Hope this helps!


Favorable graph decomposition for dense graphs to solve independent set problem

The problem is that most decompositions (I know of) are themselves much harder to compute/approximate than INDEPENDENT SET.

However, if your graphs are really very dense, their complements might be sparse. Thus, it might be worth considering solving CLIQUE in the complement of the input graph. This can be done in $O(nd\cdot 1.45^d)$ time (Eppstein, Löffler, Strash), where $d$ is the degeneracy of the input graph (which is even smaller than the treewidth).