Among an infinite variety of n x n board games, why are some interesting?

I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game attractive and fun:

simple rules;
simple "physical elements" needed to play it (e.g. a bounch of stones like in Mancala) ... clearly nowadays this condition is meaningless if the game can be played on a computer;
a clear ending/winning condition;
a well balanced (usually short) duration;
as game proceeds the "current position" should get simpler and should soon or later clearly reflect a draw or winning/losing condition;
the game contains tactical aspects (usually short term) or long term strategic aspects (usually long-term);
many games are played using dice, so a random component can make the game more balanced and attractive;
it abstracts an aspect of reality (war, conquer, destroy, survive, escape, build, ...);
the difficulty should be balanced and the players must have the sensation that if they play more games they can improve their playing skills and/or discover new (tactical/strategical) aspects of the game;
the game offers many strategies that can be chosen to win (a human player should not be able to learn a perfect winning strategy) and each match can lead to completely different positions and "situations";
errors are "scaled": if a player makes small error then he can recover if he plays well or the other player makes a similar error.

Two-players games usually share some basic settings or meta-rules (some of them also apply to one-player puzzles):

the board is finite and (usually) doesn't change during the game;
a move is well defined; and it is (usually) local;
player A and player B alternate during the game and a turn is usually a single move;
there is usually an initial position (if the elements of the game are not placed on th eboard during the game);
during the game there are some elements on the board (they are placed on the board at the beginning or during the game) and there is a clear distinction between elements owned by player A and elements owned by player B, i.e. both players have their avatars on the board :-)). A move can change the ownership of an element or kick it out of the baord;
there is a winner;
initially both players have allmost the same winning chances.

There are a lot of classic and popular two player games (that were invented before the computer age); and most of them have very different rules and settings: e.g. chess, go, card games, mancala, othello, hex, risk, master mind, scrabble, and so on. Many of them have been proved to be at least PSPACE-complete (the generalized version).

So, returning to your question, I think that there are enough evidences that:

there are no "special rules" (exept for some common meta-rules), but there is a mix of elements involved (the  list above can probably be further extended);
there is a a clear connection between the (underlaying) computational complexity and the addictiviness/fun of a game;

Though point 2. is also related to the age of the players (or how much a player "want to think" while playing); e.g. simpler games like "game of the goose" (which is purely random) or the $O(n^2)$ "connect the dots" are funny for children.

Oldest games like chess, checkers and go satisfy many of the (orthogonal) aspects underlined above, but each in a different way: e.g. chess has harder rules than checkers, but it is deeper from a tactical/strategical viewpoint.

I'm not an expert of their history, but I'm sure that initially there were many variations of them, and their rules/settings have "slowly been tuned" to better satisfy the above aspects. For example, in order to shorten the duration of a chess game and enter the middle game faster, rules were changed (see history of chess or History of chess variants). Go rules in ancient times were always passed on by word of mouth, and were usually not clear; and even nowadays there are many variants (two main variations are about scoring, i.e. winning conditions) (see for example The History of Go rules). Even draughts has many national variants.

As a further confirmation of point 1. and 2. you can examine how many addictive  video games (most of them are single player puzzles) have been created in the last years and have become "classics": candy crush, sokoban, snake, minesweeper, atomix, tetris, portal, ... they have completely different rules and settings, but they share a common point: they are theoretically hard :-)

From a theoretical point of view; a game is simply a path on a state graph (or state space) in which each node is a valid position and many of the above aspects are closely related to the structure of such a graph. We could write pages about such relation, but I think that a key concept is:

the players don't play (theoretical) perfect strategies, so a game is addictive if they can perceive the state space in a strategical/tactical way exactly like on a battlefield with hills, valleys, hidden parts that will be discovered later, positions that look good, positions that look bad, one or more target to reach, temporary disadvantages that will lead to future advantages, different ways to reach a target, the possibility of hindering the opponent's strategy, and so on ...


The amplitude $\alpha(n) = \Theta(n)$  for expander graphs. A random 3-regular graph is asymptotically almost surely an expander graph (see Wikipedia), so the expectation of the amplitude will be $\Theta(n)$, since the probability that it's not an expander graph goes to $0$ as $n$ goes to $\infty$.

For an expander graph with parameter $\beta$, for any set of $s$ vertices with $s \leq n/2$, there are $\beta s$ neighbors of the set. Now, let the number of vertices on level $j$ be $\ell_j$, with $\ell_0=1$. We then have from the expansion property that as long as $j$ is not too large (i.e., we haven't included half the vertices yet)
$$
\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}
$$
Now, look for the level $\ell_j$ which contains vertex $\frac{n}{3}$. That is, so $\sum_{i=0}^{j-1} \ell_i < n/3$ and $\sum_{i=0}^{j} \ell_i \geq n/3$. If this level is large, i.e., $\ell_j \geq n/6$, we are done. Otherwise, the next level has size
$$
\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},
$$
and we are done.

While this proof looks at the number of vertices in a level rather than the number of edges (which the OP asked about), there are always at least as many edges added in step $i$ as vertices in level $i$, since each vertex must be reached by some edge.


Nontrivial separation consequences of P!=NP

De Loera, Lee,  Malkin, and Margulies developed an algorithm for determining infeasibility of certain combinatorial problems using Hilbert's Nullstellensatz.

For example, they take the constraints of 3-coloring a graph and describe that problem as a system of polynomial equations.  They compute a set of certificate polynomials which verify that these polynomials have no solutions (using the Nullstellensatz).  To make this computation finite, they bound the degree of the certificates.  For the 3-coloring case, they were unable to find a non-3-colorable graph which required degree higher than four for the certificate.

If P $\neq$ NP, then P $\neq$ coNP and the degree of a Nullstellensatz Certificate for this problem is unbounded, as a finite bound would yield a polynomial-time algorithm.


Lattices and linear subspaces are closed under Minkowski sum. Thats more or less immediate from their definition. Lattices+linear subspaces are closed under Minkowski sum (i.e., a member of this set is for example a set of parallel lines in distance 1 from each other). Connected polygons with holes are closed under Minkowski sum. Rings [the set differences of two concentric disks] are closed under Minkowski sum (a disk is considered to be a ring, naturally). The set of line segments parallel to a certain direction are closed under Minkowski sum. Mushed potatoes are closed under Minkowski sum, but only if they are well cooked (or maybe not, it is too late)...

Also, the family of finite union of concentric rings is closed under Minkowski sum.


Are there more polynomial time problems with complexity lower bounds?

Here's one involving a 2 player pebble game. You decide if it's natural (:

T. Kasai, A. Adachi, S. Iwata. Classes of pebble games and complete problems. 1979

Theorem 3.1 has the EXPTIME-completeness of pebbling. Theorem 3.3 has the easiness of k-pebble.

A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984

Theorem 3.2 has the lower bound on k-pebble. Lastly, you might also be interested in:

T. Kasai and S. Iwata. Gradually intractable problems and nondeterminitstic log-space lower bounds. 1985

Sadly that these are all behind paywalls :(


Graphs in which every minimal separator is an independent set

Your graphs have been characterized by this paper http://arxiv.org/pdf/1103.2913.pdf.

Edit: In the paper above it is proved that graphs in which every minimal separator is an independent set are exactly those containing no cycle with exactly one chord.

Graphs containing no cycle with exactly one chord have been studied in depth by
Trotignon and Vuskovic, A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences,  J. Graph Theory 63 (2010) 31-67 DOI.
As a result of this paper, these graphs can be recognized in polynomial time. (However, this paper did not point out the connection to independent minimal separators!)

Edit (17 Sept 2013): Very recently (see here),
Terry Mckee describes all graphs in which every minimal vertex separator is a clique or an independent set. It turns out that these are the ''edge sums'' of chordal graphs and graphs in which every minimal vertex separator is an independent set.


Let $u$ denote the size of the union of the sets in $S$, $n\leq 2^u$ denote the size of $S$, $h\geq n$ denote the size of the output, and $S_i$ the set of sets resulting of the intersection of $i$ sets from $S$ (in this sense, $S=S_1$), maintained in lexicographical order. For all $i\in[1..n]$, $|S_i|\leq h$.

$S_2$ can be computed in time $un(n-1)/2\leq uh(h-1)/2$: each binary intersection takes at most time $u$, and there are at most $n(n-1)/2$ of them. $S_4, S_8, \ldots$ can be computed in time $uh(h-1)/2$ each in a similar way. Other $S_j$ which are not power of two can be obtained by combining those results, up to $S_n$.

The total running time would be  within $O(unh^2)$?


Algorithm for testing if a point belongs to a sequence of convex set or not

The obvious algorithm is to use binary search.

You'll need $\lg n$ iterations of binary search, where $n$ = the number of convex sets in your sequence.  (If you have an infinite family of convex sets, $\lg(|f(x)|/\epsilon)$ iterations are enough to approximate $f(x)$ to within $\epsilon$.)  In each iteration, for some value of $\lambda$, you test whether $x \in C_\lambda$.  You haven't specified the representation of the family of convex sets, but for typical representations, testing whether $x \in C_\lambda$ can be done in polynomial time.  So, the total running time will be polynomial.

To do better than this, I suspect the algorithm will need to depend upon how the sequence of convex sets $C$ is represented.  (Do you have a requirement for it to be represented in a particular way, or are you OK with any reasonable representation?  You might want to edit the question accordingly.  You might also want to specify whether this is a finite sequence or an infinite sequence, and how the sets are related.)

For instance, here's a special case where the problem is easier.  Suppose that the sequence of sets is represented as follows: you have a set of linear inequalities on $x_1,x_2,\dots,x_d,\lambda$, with constants $c_0,c_1,\dots,c_d$, so that each linear inequality has this form:

$$c_0 \lambda + c_1 x_1 + c_2 x_2 + \dots + c_d x_d \le 0.$$

Now suppose that the convex set $C_\lambda$ is defined as the set of points $(x_1,\dots,x_d)$ that satisfy all of these linear inequalities (notice the very specific kind of dependence on $\lambda$), and suppose that the linear inequalities are chosen so $C_{\lambda_1} \subset C_{\lambda_2}$ whenever $\lambda_1 > \lambda_2$.  Then you compute $f(x)$ efficiently using a very simple algorithm: you plug in $x$ into each of the linear inequalities, leaving $\lambda$ as the only unknown in each case, and find the largest value of $\lambda$ so that all of those inequalities are satisfied.  This only works if your sets have a certain form and are represented in a certain special way, which is why I say that your problem will probably depend upon how the sets are represented and what structure they might have.


If $\alpha \in O\left(\frac{\log\log n}{ \log n}\right)$, then you would have proved that $P = NP$, since $n^{\alpha} \in O(\log n)$ and $2^{n^{\alpha}} \in O(\mathrm{poly}(n))$.

On the other hand, for $\alpha \in \omega\left(\frac{\log\log n}{ \log n}\right)$ and $\alpha \in o(1)$, I think the most interesting thing that happens is breaking ETH with all its consequences (including breaking SETH and many other conditional lower-bounds on polynomial and parameterized problems).


Let PTH be the hypothesis that there exists a probabilistic time hierarchy. Suppose the answer to your question is true, i.e., "PTH implies $BPP \subseteq TIME[2^{n^{c}}]$" for some fixed $c$. Then, $EXP \neq BPP$ would be unconditionally true. Consider two cases:

If PTH is false, then $EXP \neq BPP$. This is the contrapositive of what Lance noted.
If PTH is true, then "PTH implies $BPP \subseteq TIME[2^{n^{c}}]$" so again $EXP \neq BPP$.

In fact, even an infinitely-often derandomization of BPP under PTH would entail $EXP \neq BPP$ unconditionally. So whatever barriers apply to proving $EXP \neq BPP$, they apply to proving statements of the kind "PTH implies derandomization".


Representing boolean function by a polynomial

Any function which has non-zero correlation with parity has degree $n$. That is, if $$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$$
then the unique multilinear expansion of $f$ contains the monomial $x_1\cdots x_n$. Indeed, since $(-1)^{x_i} = \frac{1-x_i}{2}$, the Fourier expansion of $f$ (expressed in terms of products of $\frac{1-x_i}{2}$) will contain the term $\prod_i \frac{1-x_i}{2}$, and the corresponding monomial $\prod_i x_i$ doesn't appear in any other term.

Nisan and Szegedy proved that functions of degree $d$ depend on at most $d2^d$ variables. For $d = 1$ we can be more exact: the function must depend on at most one coordinate.


In general, a state of $n$ qubits is a state of $n$ distingushable particles. Eg.
$|01\rangle$ means that the first particle is in the state $|0\rangle$, and the second is in the state $|1\rangle$.

How can be elementary particles distinguishable? Place two particles in different places. Eg. two electrons are in the positions $x_1$ and $x_2$, respectively. (Or two photons in two consecutive pulses, one in each.)

However, you can make the qubits indistinguishable by imposing a permutation symmetry, i.e. symmetrization and antisymmetrization.

And $n$ photons in the same place gives 'automatically' symmetrized state.


Complexity of Finding the Eigendecomposition of a Matrix

Ryan answered a similar question on mathoverflow. Here's the link: mathoverflow-answer

Basically, you can reduce eigenvalue computation to matrix multiplication by computing a symbolic determinant. This gives a running time of O($n^{\omega+1}m$) to get $m$ bits of the eigenvalues; the best currently known runtime is O($n^3+n^2\log^2 n\log b$) for an approximation within $2^{-b}$.

Ryan's reference is ``Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516''.

(I believe there is also a discussion about the relationship between the complexities of  eigenvalues and matrix multiplication in the older Aho, Hopcroft and Ullman book ``The Design and Analysis of Computer Algorithms'', however, I don't have the book in front of me, and I can't give you the exact page number.)


Decide the existence of a string homomorphism

It's discussed in one of the very first papers about strings and complexity, namely, Dana Angluin, Finding patterns common to a set of strings, J. Comput. System Sci.
21 (1980), 46-62.  Look at Theorem 3.6.  The problem is NP-complete.

It's also in A. Ehrenfeucht, G. Rozenberg, Finding a homomorphism between two words is NP-complete, Inform. Process. Lett. 9 (1979) 86–88.


Theoretical Applications for Approximation Algorithms

I strongly disagree with the last paragraph. Blanket statements like that are not useful. If you look at papers in many systems areas such as networking, databases, AI and so on you will see that plenty of approximation algorithms are used in practice. There are some problems for which one desires very accurate answers; for example say an airline interesting in optimizing its fleet scheduling. In such cases people use various heuristics that take substantial computational time but get better results than a generic approximation algorithm can give.

Now for some theoretical reasons for studying approximation algorithms. First, what explains the fact that knapsack is very easy in practice while graph coloring is quite hard? Both are NP-Hard and poly-time reducible to each other. Second, by studying approximation algorithms for special cases of a problem one can pin-point what classes of instances are likely to be easy or hard. For example we know that many problems admit a PTAS in planar and minor-free graphs while they are much harder in arbitrary general graphs. The idea of approximation pervades modern algorithm design. For example, people use data streaming algorithms and without the approximation lens is hard to understand/design algorithms because even simple problems cannot be solved exactly.


A Question on Convex Conjugate Duality for KL Divergence

To make it easier let's assume $X$ is finite, of size $n$ and associate the density of $Q$  with an $n$-dimensional vector $q$. Assume also that $q$ is everywhere positive - otherwise replace $X$ with the support of $q$. Then the conjugate is
$$
f^*_q(x) = \sup_p\  \langle x, p \rangle - \sum_{i = 1}^n{p_i\log(p_i/q_i)}.
$$
where the supremum is over the probability simplex $\{p\geq 0: \sum_i p_i = 1\}$. Since the simplex is compact and the function inside the supremum is continuous, the supremum is achieved at some $p$. Using Lagrange multipliers you get that for some real value $\lambda$ an optimal $p$ must satisfy $x_i - 1 - \log(p_i/q_i) = - \lambda$ for all $i$, which gives $p_i = q_ie^{x_i + \lambda-1  }$. Since $1 = \sum_i p_i$, we have $\lambda - 1 = -\log\left(\sum_i{q_i e^{x_i}}\right)$. Substituting, we get
$$
\begin{align}
f^*_q(x) &= \sum_i{q_i e^{x_i + \lambda- 1 }x_i} - \sum_i{q_i e^{x_i+ \lambda-1 }(x_i+ \lambda-1)}  \\
&= -(\lambda-1)\sum_i{q_ie^{x_i+ \lambda-1 }}  \\
&= -(\lambda-1)\sum_i{p_i}\\
&= -(\lambda-1) = \log\left(\sum_i{q_i e^{x_i}}\right),
\end{align}
$$
which is exactly the logarithm of the expectation of $e^{x_i}$ under $q$.


canonical complete problems for $\Delta^P_n$

(This is a slightly more detailed version of my earlier comment, in response to the asker’s request by email.)
Since $\Delta_k^{\rm P} = {\rm P}^{\Sigma_{k-1}^{\rm P}}$ by definition, it should be clear that the following problem is $\Delta_k^{\rm P}$-complete: fix some $\Sigma_{k-1}^{\rm P}$-complete problem L.  (For example, L can be the special case of QBF where there are k−1 groups of consecutive quantifiers of the same kind and the first quantifier is existential (∃).)  Then given a Turing machine M with the L oracle, a string x and a tally string 1t, decide whether M accepts the input x in time at most t.  (A tally string simply means a string on the unary alphabet, that is, a string of the form 1n.)
I would not mind calling this problem a “canonical” $\Delta_k^{\rm P}$-complete problem, but this may not be what you are looking for.
In my earlier comment, I removed the input string x and assumed it was always the empty string.  This variant is also $\Delta_k^{\rm P}$-complete because you can hardwire the input string into a Turing machine.


Languages whose Parikh image is recognizable

I seems that I was quite confused back then. This language class is precisely the language class of those languages, whose commutative closure is regular.
Let $\Sigma = \{a_1, \ldots, a_k\}$. One implication is given in the question. For the other, suppose the commutative closure of $L \subseteq \Sigma^*$ is regular, i.e., the set $p^{-1}(p(L))$ is regular.
Then,  $p^{-1}(p(L)) \cap a_1^* \cdots a_k^*$ is regular, bounded and has the same Parikh image as $L$ or its commutative closure. By an old result of Ginsburg (see below), we can write this language as a finite union of languages of the form $A_1 \cdots A_k$, where each $A_i$ is a regular subset of $a_i^*$. Now, the Parikh image of one such set has the form $R_1 \times \ldots \times R_k$ with $R_i \subseteq \mathbb N$ recognizable. So, by a condition written in the question, the Parikh image of $L$ is recognizable.
Alternatively, without citing other results, suppose we have a morphism $h : \Sigma^* \to M$ with $M$ finite such that $p^{-1}(p(L)) = h^{-1}(h(L))$. We can assume $M$ is commutative (for example, by taking the syntactic monoid).
Hence, the map $\varphi : \mathbb N_0^k \to M$ given by $\varphi(n_1, \ldots, n_k) = h(a_1)^{n_1} \cdots h(a_k)^{n_k}$ is a morphism.
Then, $p(L) = \varphi^{-1}(h(L))$ and so $p(L)$ is recognizable.
Now, identifying language classes whose commutative closure is regular is quite an active field of research. For example, see the second reference below.
S. Ginsburg, Bounded Regular Sets, Amer. Math. Soc. 17 (1966), 1043-1049.
Antonio Cano Gómez, Giovanna Guaiana, Jean-Éric Pin:
Regular languages and partial commutations. Inf. Comput. 230: 76-96 (2013)


A quick google search revealed Experiments on Data Reduction for Optimal Domination in Networks. If you look at their tables they cite a number of data sets for which the actual dominating set is given. They also use a number of random graph generators and publish the average dominating set size for these.

There's another paper from 2002: Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. I couldn't find an online copy, but I'm sure this paper also documents data sets and actual DS sizes.


complexity of CSPs with 2-variable constraints and multi-valued variables

With 3 values and binary relations, the CSP is still NP-complete (it is denoted with (3,2)-CSP). A quick reduction is from graph coloring:

add a variable $x_i \in \{1,2,3\}$ for each node; then for each edge $(x_i,x_j)$ add the constraint $x_i \neq x_j$


The book probably assumes an adjacency list representation. Each vertex is visited once, so to decide what color it should get, all its neighbors are checked, so each edge is crossed twice (once in each direction).

If you have an adjacency matrix representation, I think it will be $O(n^2)$.


Set cover in which some pairs of sets are forbidden

This problem is way harder than set cover. Here is why...

Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ with $n$ vertices, and a number $k$, and the question is whether the graph $G$ has an independent set of size $k$.

We assume that $k$ is large (say, polynomial in $n$).

It is not hard to form a set system, with $n$ sets, such that any cover of the set system requires at least $\Omega(k/\log n)$ sets, and any specific set of $k$ sets cover the ground set. To this end, have a "large" ground set $X$ (say, of size $t$), and generate $n$ random sets (independently), where you pick every element $x \in X$ to be in the $i$th random set with probability roughly $p = 10(\ln n)/k$. Let $R_1, \ldots, R_n$ be the resulting random sets, and observe that a union of any specific $k$ of them covers the ground set, with high probability. Indeed, the probability that an element of $X$ is not covered, by a specific $k$ sets is bounded by
$$
t (1-p)^k < 1/10,
$$
for $t = n^{O(1)}$.

Similarly, consider $k' = c (k/\log n)$ random sets, where $c$ is a sufficiently small constant. We claim that with high probability their union does not cover $X$. Indeed, the probability a specific element is covered by such $k'$ sets is
$1- (1-p)^{k'}$ which is a constant, say $\alpha < 1$. As such, the probability that these $k'$ random sets cover $X$ is at most $\alpha^t$. In particular, the probability that any of the possible sets of $k'$ random sets cover $X$ is bounded by
$$
\alpha^t * \binom{n}{k'} < 1/10,
$$
by taking $t$ to be larger than $20 (k/\alpha) \ln n$ (or some similar quantity).

Now, associate with the $v_i$ vertex in $G$, the set $R_i$. Forbid the pair $\{R_i, R_j\}$ if the edge $v_iv_j$ is in the graph $G$.

Any solution for the resulting instance, would be an independent set in $G$ of size $\Omega(k / \log n)$. The original independent set of size $k$ is a valid solution in the resulting instance (all with good probabilities). But that implies that using your problem, you can get a log approximation to independent set, which is an extremely unlikely event. More generally, a $\beta$ approximation, would imply a $O( \beta \log n)$ approximation for independent set. Since independent set can not be approximated to within $n^{1-\epsilon}$, you essentially get the same result for your problem.

PCP people might be able to derive the above from their known machinery...


What's the difference between proving weak normalization and implementing evaluator?

If you implement an evaluator for the terms of a language $A$ in a total system $B$, and you have furthermore proven that your evaluator is correct, that is for every $t$ well-typed in $A$,

$$\mathrm{eval}(t) \simeq_A t $$

where $\simeq_A$ is the equality in $A$, then you have only shown that $\simeq_A$ is decidable.

If furthermore $\simeq_A$ naturally leads to a notion of reduction $\rightarrow_A$, and $\mathrm{eval}(t)$ is always in normal form, then you have proven that every term $t$ in $A$ is equivalent to a term in normal form.

This is enough for consistency of $A$ but is not equivalent to weak normalization, unless $\rightarrow_A$ is furthermore church-rosser!

This is essentially the approach taken by normalization by evaluation.

A proof of weak normalization in a constructive logic naturally leads to an evaluator, as every $\forall\exists$ statement leads to an algorithm (correct by construction).

There is a nice article by Ulrich Berger, Program extraction from normalization proofs, which implements this idea for simply typed $\lambda$-calculus.

For your second question, here is a counter example. Consider the language $A$ to have only two terms, $\Delta$ and $\bot$, with the reduction rules

$$\Delta\rightarrow \Delta $$
$$\Delta\rightarrow \bot $$

Feel free to add types if you like. The computation rules are weakly normalizing and confluent.

In Coq, you might write the eval function thus:

Fixpoint eval (t : A) : A :=
  match t with
     | Delta => Bottom
     | Bottom => Bottom

It's not too hard to prove that if $t\leftrightarrow^* u$ then eval(t) = eval(u). Coq's reduction can be taken to be non-deterministic, in which case you have a counter-example to the SN "inheritance" that you expect.


Does there exist the idea of "RP-complete", like NP-complete?

Yes: the concept of "X-complete under Y-reductions" exists for any complexity class X and any class Y of reductions.  However, there may or may not be any complete problems under this definition, depending on what X and Y are. For example, it is well-known that NP has complete problems under polynomial-time, logspace and even first-order reductions, but it does not have complete problems under linear-time reductions as this would violate the time hierarchy theorem.

As far as I can see, it is open whether there is a class of reductions under which RP has complete problems. The issue is that it is a so-called semantic class: it is defined by a non-computable set of Turing machines, namely polynomial-time randomized Turing machines with the undecidable requirement that, for every input, either every path rejects or at least half accept. See this question for more details on the issues surrounding complete problems for semantic classes.


History and status of the graph matching problem

From the paper Approximate Graph Isomorphism:

  We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $π$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log{n})}$ time approximation scheme that for any constant factor $α < 1$, computes an $α$-approximation. We prove this by combining the $n^{O(\log{n})}$ time additive error approximation algorithm of Arora et al. [Math. Program., 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $α$-approximate for any constant factor $α$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.


The Complexity Zoo has a reference to that result in the description of the class AM[polylog]:

  […] [SS04] show that if AM[polylog] contains coNP, then EH collapses to S2-EXP•PNP. ([PV04] improved the collapse to AMEXP.)

In the Complexity Zoo, a class or a statement is caged when it looks very scary.  Examples of caged statements can be found in the descriptions of coNP/poly and SFk (not for the easily scared, reader discretion is advised).


Is there a P-complete problem on diophantine equations?

No , as far as i know diaphantine problem in general is undecidable thus equivalent to halting problem , if the equations are restricted to be quadratic then it is np-complete , and linear diaphantine equation can be reduced to integer programming problem and For linear Diophantine equation equations, integral solutions exist if and only if, the GCD of coefficients of the two variables divides the constant term perfectly.


What is the most important notion of sparsity for the design of efficient graph algorithms?

I think that by any reasonable standard an n × n × n three-dimensional grid graph would have to be considered sparse, and that rules out most candidate definitions involving surface embeddings or minors. (Sublinear treewidth would still be possible, though.)

My current favorite sparsity measure is degeneracy. The degeneracy of a graph is the minimum, over all linear orderings of the vertices of the graph, of the maximum outdegree in the directed acyclic orientation of the graph formed by orienting each edge from earlier to later vertices in the ordering. Equivalently, it's the maximum, over all subgraphs, of the minimum degree in the subgraph. So for instance planar graphs have degeneracy five because any subgraph of a planar graph has a vertex of degree at most five. Degeneracy is easy to calculate in linear time, and the linear ordering that comes from the definition is useful in algorithms.

Degeneracy is within a constant factor of some other standard measures including arboricity, thickness, and the maximum average degree of any subgraph, but those are I think harder to use.


Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

This answer is not a reference but rather to make some of the notions precise in your question. First, semicomputable does stand for what you say but I think there is a big difference between upper and lower semicomputable - in case of the former I have no clue how you would sample.

Second, do you have a measure or a semimeasure? In a semimeasure the sum of the probabilities is at most 1, so I again do not know how you would sample, as there is no full distribution (of course you can say that you normalize by dividing the sum of the probabilities but that might not be computable, you could never know when to give up a computational path).

Finally, if you have a lower semicomputable measure, then it is in fact equivalent to have a PTM that can sample with this distribution (although we must allow the sampling to run for arbitrarily long, as long as it stops eventually).

I think the best reference on the topic is Ming Li and Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications. For another available online see chapter 6.2 of László Lovász: Complexity of Algorithms at http://www.cs.elte.hu/~dom/complexitynew.pdf


A combinatorial embedding or signed rotation system is a combinatorial representation of a cellular embedding of a graph on some surface.  An embedding is a drawing of the graph such that no two edges cross; an embedding is cellular if every face is a disk.

Consider an undirected graph $G=(V,E)$.  It is helpful to regard each edge in $E$ as a pair of directed edges, or darts.  Each dart goes from one vertex, called its tail, to another vertex, called its head.  The reversal of a dart is obtained by swapping its head and its tail.  Let $\vec{E}$ denote the set of all darts.

A signed rotation system consists of two functions:

A successor permutation $\textit{succ} \colon \vec{E} \to \vec{E}$.  Specifically, $\textit{succ}(\vec{e})$ is the next incoming dart after $\vec{e}$ in "clockwise" order around $\textit{head}(\vec{e})$.  Thus, the cycles of $\textit{succ}$ correspond precisely to the vertices of $G$.
A sign function $\textit{sign}\colon E \to \{-1, +1\}$, which indicates for each edge whether the "clockwise" orders at the endpoints of that edge are consistent ($+1$) or inconsistent ($-1$).

This representation is not unique.  For example, reversing the cyclic order of incoming darts at any vertex $v$ and changing the signs of all edges incident to $v$ leaves the embedding intact.

The theorem you are asking about is the following:

  Any cellular embedding of any graph $G$ can be encoded by a signed rotation system, such that for some spanning tree $T$, every edge in $T$ is positive.

In fact, one can prove a stronger statement:

  For any spanning tree $T$ of any graph $G$, any cellular embedding of $G$ can be encoded by a signed rotation system, such that every edge in $T$ is positive.

If the underlying surface is orientable, we can choose a global "clockwise" orientation, which means any embedding onto that surface has a representation where all edges in $G$ are positive.

On the other hand, if the underlying surface is non-orientable, some edges must be negative.  Any one-sided cycle must include an odd number of negative edges (and therefore at least one negative edge), because moving once around a one-sided cycle reverses your local orientation.  That's what "one-sided" means.  Still, it is possible to ensure that every edge in your favorite spanning tree is positive.

The proof is straightforward induction over the tree $T$.


Approximation algorithm for finding the maximum common subgraph in two DAGs

Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem?

Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.

Any subgraph common to A and B corresponds to an independent set in G, and vice versa, no?

If this reduction is correct, then your problem is as hard to approximate as MIS; which is to say, forget about it. :-)


About the correspondence of left introduction and elimination of implication in Sequent Calculus and in Natural Deduction resp.

In computational terms, a sequent calculus term is a sequentialization of a lambda term. That is, viewed as a type system, sequent calculus can be seen as giving an evaluation order of a lambda-term.

So, suppose $\Gamma \vdash e_1 : A \to B$, and $\Gamma \vdash e_2 : A$.

In natural deduction, the term for implication elimination is $\Gamma \vdash e_1\;e_2 : B$ -- that is, application. However, note that this doesn't tell us whether to evaluate $e_1$ first or $e_2$ first.

In sequent calculus, a corresponding proof term assignment must look like

$$\mathsf{let}\; f = e_1 \;\mathsf{in}\;\mathsf{let}\;v = e_2\;\mathsf{in}\;\mathsf{let}\; x = f\;v \;\mathsf{in}\;x$$

or else it must look like

$$\mathsf{let}\; v = e_2\;\mathsf{in}\;\mathsf{let}\;f = e_1 \;\mathsf{in}\;\mathsf{let}\; x = f\;v \;\mathsf{in}\;x$$

Here, the let-form is the proof term corresponding to the use of the cut-rule, and since all of the left rules act only on hypotheses/variables, this forces us to bind all intermediate results to variables. This requirement ensures that we are forced to explicitly say which of $e_1$ or $e_2$ we reduce and bind to a variable first.

For purely functional languages, this explicitness doesn't matter, but as you add effects it becomes easier to work with sequent calculi. This is why things like calculi of control effects/classical logic are typically presented sequent calculus.


Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?

Note that in a sorting network, the number of times an element is compared is bounded by the depth of the network. There are several simple sorting networks of depth $O((\log n)^2)$. The AKS network has a depth of $O(\log n)$ with a huge constant (according to Wikipedia).


What's the bias of random polynomials with low degree over GF(2)?

Your question is equivalent to tail bounds on the weight distribution of Reed-Muller codes. Understanding weight distribution of Reed-Muller codes is an old and challenging question in coding theory, and several interesting results are known about it (the weight distribution is completely understood only for $d=1$ and $d=2$). As a great starting point, see "Weight Distribution and List-Decoding Size of Reed-Muller Codes" by Tali Kaufman, Shachar Lovett, Ely Porat, and the references therein.


Solving semidefinite programs in polynomial time

The ellipsoid method and interior point methods can be extended to solve SDPs as well. You can refer to any standard-texts on SDPs for details. Here's one:
Semidefinite Programming. Vandenberge and Stephen Boyd, 1996.


Max-cut equivalence with most likely assignment to an Ising model

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute.

In the formulation you give for the Ising model, we are trying to maximize $\sum_{ij\in E}\lambda_{ij}x_{ij}$, where $x_{ij}=1$ if $x_i=x_j$ and $x_{ij}=-1$ otherwise.  In maximum cut, we take each edge weight $w$ and try to maximize $\sum_{ij\in E}w_{ij}(-x_{ij})$ -- this is equivalent to maximizing the weight of the cut because the total weight remaining is completely determined by the cut.  So we just want to set $w_{ij}=\lambda_{ij}$ to make an equivalent formulation.

For minimum cut, the problem doesn't make any sense unless you have fields in the Ising model, either local or global.


Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders

In "Branching Programs and Binary Decision Diagrams" by Ingo Wegener [1] (very good, complete reference to check this kind of fact on branching programs), Section 5.7 deals with how you can transform a given $\pi_1$-OBDD $F_1$ into an equivalent $\pi_2$-OBDD $F_2$ by using syntactic rules. If you have a bound $B$ on the representation of $F_1$ by $\pi_2$-OBDD then you can do this in time polynomial in $|F_1|$ and $B$. He uses it to prove Corollary 5.7.11 which answers your question and a bit more: you do not need to assume the width is bounded.

Corollary 5.7.11 (in [1]): Given $F_1$ a $\pi_1$-OBDD and $F_2$ a $\pi_2$-OBDD, one can check if $F_1$ is equivalent to $F_2$ in time $O(|F_1| \cdot |F_2| \cdot \log |F_2|)$.

[1] Wegener, Ingo. Branching programs and binary decision diagrams: theory and applications. Society for Industrial and Applied Mathematics, 2000.


Converting a pictorial representation of a directed graph to a adjacency matrix

See

Christopher Auer, Christian Bachmaier, Franz-Josef Brandenburg, Andreas Gleißner, Josef Reislhuber:
Optical Graph Recognition.
Graph Drawing 2012, pp. 529-540
http://dx.doi.org/10.1007/978-3-642-36763-2_47


(* I post my answer as a Coq file. In it I show that supercoooldave's
   definition of a universal tree is not what he intended. His isUniv
   means "the tree has an infinite branch". I provide the correct
   definition, show that the universal tree is universal according to
   the new definition, and I provide counter-examples to
   supercooldave's definition. I also point out that the universal
   tree of branching type A has an infinite path iff A is inhabited.
   *)

Set Implicit Arguments.

CoInductive Tree (A : Set): Set := Node : (A -> option (Tree A)) -> Tree A.

Definition child (A : Set) (t : Tree A) (a : A) :=
  match t with
    Node f => f a
  end.

(* We consider two trees, one is the universal tree on A (always
   branches out fully), and the other is a binary tree which always
   branches to one side and not to the other, so it is like an
   infinite path with branches of length 1 shooting off at each node.  *)

CoFixpoint Univ (A : Set) : Tree A := Node (fun _ => Some (Univ A)).

CoFixpoint Thread : Tree (bool) :=
  Node (fun (b : bool) => if b then Some Thread else None).

(* The original definition of supercooldave should be called "has an
   infinite path", so we rename it to "hasInfinitePath". *)
CoInductive hasInfinitePath (A : Set) : Tree A -> Prop :=
  haspath : forall (f : A -> option (Tree A)) (a : A) (t : Tree A),
    f a = Some t ->
    hasInfinitePath t ->
    hasInfinitePath (Node f).

(* The correct definition of universal tree. *)
CoInductive isUniv (A : Set) : Tree A -> Prop :=
  isuniv : forall (f : A -> option (Tree A)),
    (forall  a, exists t, f a = Some t /\ isUniv t) ->
    isUniv (Node f).

(* Technicalities that allow us to get coinductive proofs done. *)
Definition TT (A : Set) (t : Tree A) :=
  match t with
    | Node o => Node o
  end.

Lemma TTid (A : Set) : forall t: Tree A, t = TT t.
  intros A t.
  destruct t.
  reflexivity.
  Qed.

(* Thread has an infinite path. *)
Lemma ThreadHasInfinitePath : hasInfinitePath Thread.
Proof.
  cofix H.
  rewrite TTid.
  unfold TT.
  unfold Thread.
  (* there is a path down the "true" branch leading to Thread. *)
  apply haspath with (a := true) (t := Thread).
  auto.
  auto.
Qed.

(* Auxiliary lemma *)
Lemma univChildNotNone (A : Set) (t : Tree A) (a : A):
  isUniv t -> (child t a <> None).
Proof.
  intros A t a [f H].
  destruct (H a) as [u [G _]].
  unfold child.
  rewrite G.
  discriminate.
Qed.

(* Thread is not universal. *)
Lemma ThreadNotUniversal: ~ (isUniv Thread).
Proof.
  unfold not.
  intro H.
  eapply univChildNotNone with (t := Thread) (a := false).
  auto.
  unfold Thread, child.
  auto.
Qed.

(* Now let us show that Univ is universal. *)
Lemma univIsuniv (A : Set): isUniv (Univ A).
Proof.
  intro A.
  cofix H.
  rewrite TTid.
  unfold TT.
  unfold Univ.
  apply isuniv.
  intro a.
  exists (Univ A).
  auto.
Qed.

(* By the way, it need not be the case that a universal tree has
   an infinite path! In fact, the universal tree of branching type
   A has an infinite path iff A is inhabited. *)

Lemma whenUnivHasInfiniteBranch (A : Set):
  hasInfinitePath (Univ A) <-> exists a : A, True.
Proof.
  intro A.
  split.
  intro H.
  destruct H as [f a t _].
  exists a.
  trivial.
  intros [a _].
  cofix H.
  rewrite TTid.
  unfold TT.
  unfold Univ.
  apply haspath with (t := Univ A); auto.
Qed.


Boolean error correcting code over $\mathbb{F}_q$

Yes. For example, a Reed-Solomon code contains a BCH code, which is a binary linear code, as a sub-code. These are called subfield-subcodes.


Connection between algebraic logic and computational complexity of logics?

The example you gave extends as follows:

SAT for arbitrary lattices (meaning, is a given formula satisfiable in some lattice) is polynomial-time decidable
SAT for modular lattices is Turing undecidable:
Freese, Ralph, Free modular lattices, Trans. Am. Math. Soc. 261, 81-91 (1980). ZBL0437.06006.
SAT for Boolean algebras is NP-complete

So while modular lattices are in between Boolean algebras and arbitrary lattices, they are the most complicated.


This problem is polynomially solvable.

Claim: solving the problem on input $a = (a_1, \ldots, a_n)$ and $b = (b_1, \ldots, b_n)$ using a partition $P$ is equivalent to choosing a multiset of numbers $X$ with $|X| = |P|$ such that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Assuming this claim, solving your problem is equivalent to finding the smallest set $X$ such that for each $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$. For any fixed $i$, this condition can be rewritten as $a_i \le x \le 1-b_i$. Thus, the problem is equivalent to finding the smallest set $X$ which includes at least one point from each interval $[a_i, 1-b_i]$.

It is easy to show that the following algorithm finds an optimal solution:

Algorithm: Initialize $X$ to be the empty set. Scan from 0 to 1. When leaving each interval during this scan, check whether the interval you are leaving already contains a point in $X$. If yes, continue without doing anything. If no, add the current value of the scan-line (i.e. the end of the interval) to $X$. Once you reach the end of the scan, output $X$.

Thus, all that's left is to prove the claim:

proof of claim:

First suppose we have a partition $P$ solving your problem. Then define $X = \{x_S~|~S \in P\}$ where $x_S = \max_{i \in S}a_i$.

If $i' \in \{1, \ldots, n\}$, then $i' \in S$ for some $S \in P$.

Since $i' \in S$, clearly we have that $a_{i'} \le max_{i \in S}a_i$. The RHS, however, is the definition of $x_S$, so this shows $a_{i'} \le x_S$.

By the conditions on the partition, $max_{i \in S}a_i + max_{i \in S}b_i \le 1$, or in other words $max_{i \in S}b_i \le 1 - max_{i \in S}a_i = 1 - x_S$. Simply applying the fact that $i' \in S$, we have that $b_{i'} \le max_{i \in S}b_i$. Putting this together, we see that $b_{i'} \le 1-x_S$.

Thus we have shown that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Next suppose that we have a set $X$ such that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Name the elements of $X$ as $x_1, x_2, \ldots, x_{|X|}$. Then let $S_j = \{i \in \{1,2,\ldots,n\}~|~a_i \le x_j ~\text{and}~ b_i \le 1-x_j\}$. By the property of $X$, every element of $\{1,2,\ldots,n\}$ is in at least one $S_j$. Then if we define $S_j' = \{i \in S_j~|~i \not\in S_{j'} ~\text{for}~j'<j\}$, we see that sets $S_1', \ldots, S_{|X|}'$ form a partition of $\{1,2,\ldots,n\}$.

We claim that this partition is a valid solution to your problem. Consider any part $S_j'$ in this partition. Since $S_j' \subseteq S_j$, we have that $\max_{i \in S_j'}a_i \le \max_{i \in S_j}a_i \le x_j$
and $\max_{i \in S_j'}b_i \le \max_{i \in S_j}b_i \le 1-x_j$,
and so we see that $\max_{i \in S_j'}a_i + \max_{i \in S_j'}b_i \le x_j + 1-x_j = 1$. This is sufficient to show that the partition is a valid solution to your problem.


Generate connected induced subgraphs as the satisfying assignments to a SAT instance

It's not possible if the variables are restricted to be only the given ones for the graph vertices. Consider a graph $G$ that has $2n+2$ vertices: $x$, $u_i$, $v_i$, and $y$ for $1\le i\le n$, formed by the union of $n$ edge-disjoint paths $x$--$u_i$--$v_i$--$y$. Also consider only the subgraphs that include both $x$ and $y$: if the whole graph has a small CNF formula for connected subgraphs, then so does this subset of subgraphs, obtained by setting the variables for $x$ and $y$ to true and then simplifying the formula.

The connected subgraphs that include both $x$ and $y$ do have a very simple $2$-DNF formula:
$$\bigvee\limits_{i=1}^n(u_i\wedge v_i).$$
However, when you convert this to its (unique) CNF form, it has $2^n$ terms (one for each way of excluding either $u_i$ or $v_i$ from the subgraph, for each $i$). So no polynomial-size CNF formula exists.

$G$ is not a grid graph but the same construction can easily be embedded into a grid by expanding $x$ and $y$ into larger connected subsets of grid points. As above, the whole graph can't have a small CNF formula, because if it did then you'd also have a small CNF formula for the connected subgraphs that include all the grid points representing $x$ and $y$, but we can write down the formula for this subset of the subgraphs and it does not have polynomial size.


Hardness of approximation without the PCP theorem

An example is this paper:

Guruswami, V., & Khanna, S. (2004). On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1): 30-40. link

Using the PCP-Theorem, Khanna, Linial, and Safra (2000) proved that it is NP-hard to color a
3-colorable graph using just 4 colors. Later, Guruswami & Khanna (2004) gave, among other nice things, a PCP-free proof for the same result.


Efficient recalculation of the maximum flow when edge capacities are reduced

In the worst case, even reduction of the capacity of a single edge may force you to recalculate the flow from scratch.

To see this, consider a flow network $(G,c,s,t)$, i.e., $G=(V,E)$ be a graph such that $s,t\in V$, $c:E\to\mathbb N$ is some capacity function, $s$ is a source vertex, and $t$ is a sink vertex.

Now define a new flow network $(G',c,u,t)$, as follows.   $G'=(V\cup\{u,v\}, E\cup\{(u,v),(v,t), (v,s)\}$ is a new graph.  The source vertex of the new flow network is $u$ and the sink vertex is $t$.  Assume that $c((u,v))=c((v,s))=c((v,t))=f^*$, where $f^*$ is the value of the max flow in the original network.

Assume now that I give you a maximum flow $f'$ for $G'$ (from $u$ to $t$), namely, $f'((u,v))=f'((v,t))=f^*$ and $f'=0$ for all other edges.  In other words, $f'$ pushes $f^*$ units of flow along the path $u \to v \to t$.

Now if we reduce $c(v,t)$ to 0, you have to compute the flow for the original network from scratch.


Natural notion for computational hardness

Just what makes growth rates such as O(n²) artificial — just the fact that it isn't one specific monotonic function? Or is it the fact that it's a family of functions in itself, and not just some simple number which comes from something obvious about the problem?

At the very least, your students should be able to grasp the purpose, and in a sense the meaning, of asymptotic notation by observing how the tediousness of performing arithmetic scales with the size of the numbers — that it gets more tedious for larger numbers, and that adding two n-bit numbers is less tediuous than multiplying them. Hopefully they should percieve a difference! If they can, then you have got them where you want them. Point out that the difference is smaller when you have smaller numbers: obviously the difference is one which grows with instance size. Point out to them the nested iterations in the multiplication algorithm. And now you have motivated caring about the difference between O(n²) time and O(n) time. Get them to do matrix computations next to give them a taste of O(n³), and point out the nested iterations there. They should get the idea after that.

I would say that exponential-time versus poly-time often amounts to "searching through a combinatorial explosion versus performing a bounded number of nested iterations", which is about as natural a distinction as possible between approaches to solving problems (e.g. in computer programming). But you cannot motivate complexity of problems of any sort, to people who do not themselves spend time solving problems and so who have no taste for the idea that certain ways of solving things (or solving different kinds of problems) take different amounts of work, and that differences between algorithms come from some place. You can't convince someone of these things unless they can have enough "empathy" for the computer to viscerally feel the extra work that is being done in one algorithm, versus another; to be aware of the layers of computing or of searching which it is doing, to actually hope that the problem has enough structure to narrow the solution space beyond just nested loops. They must be able to appreciate the existentially Sisyphian futility of trying to solve instances of SAT just by looking forlornly for a solution brute-force. This sort of perspective comes from solving problems oneself, and being self-aware of what one is doing; and I think it is perfectly natural to ask how much the tediousness of the task (i.e. how many computations you are doing) scales with the size of the problem.

If your students can't grasp this, tell them that the "difficulty" of adding numbers by high-school techniques is rated as 1; that of multiplying numbers is rated as 2; that sorting an unordered list has a rating between 1 and 1.000001 if you do it in the right way; and that there are no techniques for solving SAT whose rating is less than infinity; and move on from there — because you're not likely to do much better than this pedagogically without inventing a novel complexity measure, or obtaining more engaged students.


Complexity of universal computation on random input

Yes, T>0. I am not sure I correctly get all your conditions, so I suppose that each $A_i$ is an algorithm and each of them contains an upper bound for its running time. A constant fraction of the algorithms will be the following type: "Run U on ``This'' program and if it stops in less then k steps, then output something different from its output, otherwise stop after k steps". obviously U cannot run faster than such an algorithm. (Here faster means more than a constant factor faster.)

For your other question, you gotto be more specific about what kind of Turing-machines you allow. Probably the answer is no, see http://en.wikipedia.org/wiki/Linear_speedup_theorem.

Update 7/7 to Squark's comment: I see, you are right, I have proved that for every U the limsup >0. But if you take inf for all U, then you can take a U that knows the answer for the first many A_i and need not spend any time on them, and with high probability many of our random A_i will be from the first many, so T will go to 0. (Here I suppose that $t_i^U\le t_i$ which is not necessary, as programs can have never needed parts, but without this I cannot even prove $T<\infty$.)


Optimal preprocessing for certain types of queries

Construct an ordered balanced binary tree with $s_1,\dots,s_n$ in the leaves (in order).  In each internal node $v$ store the product of the leaves of the subtree rooted at $v$.  This preprocessing obviously runs in O$(n)$ time and space.

Now, to compute a product $s_i\circ\ldots\circ s_j$ (where $i<j$) walk the tree up from $i$ to the least common ancestor (LCA) of $i$ and $j$.  Collect the products stored in each right child hanging off the path, excluding the right child of the LCA.  In other words, as you go up from $u$ to its parent $v$, if $u$ is a left child of $v$, then pick up the product stored in $v$'s right child.  Similarly, walk up from $j$ to the LCA and collect the products stored in left children hanging off that path.  Multiply all these products, along with $s_i$ and $s_j$ in order.


Levin's universal algorithm is an algorithm such that $t(U,A) < s_V t(V,A) + t_V$. By modifying the algorithm (see for example Hutter's The Fastest and Shortest Algorithm for All Well-Defined Problems), you can make $s_V$ a universal constant, though definitely not $1$ as you require. For related work, consult work by Hirsch, Itsykson and their students, for example this technical report.

Edit: As Squark comments, the runtime of Levin's algorithm also depends on the runtime of $A$, since it has to verify its answers. To get a constant $s_V$, all you need to do is to set the speeds of the various algorithms in geometric progression (rather than arithmetical progression, like in Levin's original algorithm).


Counterexample for Corneil's efficient algorithm for Graph Isomorphism

Mathon has shown that the conjecture used by Corneil and Gotlieb is false. The first reference states this fact.

1- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199.

2- R. Mathon, Sample graphs for isomorphism testing, Congressus Numerantium, 21, pp.
499-517, 1978


Circuit complexity and statistical tests

I think I remember what lecture you're talking about. I remember he was saying that most statistical tests that are done can be carried out in $LOGSPACE$. (Comparing the number of $1$'s versus the number of $0$'s, computing standard deviation, etc.) But the output of Nisan's pseudorandom generator will fool all of these statistical tests, and still is not a truly random sequence. This lecture by Ryan O'Donnell describes the details.

An alternative way of defining "statistical test" is given by Blum and Goldreich.


Is there any known CCC closed under a probabilistic powerdomain operation?

The following is an extended comment, it does not answer your question in the terms you posed it but does give a semantics for higher-order probabilistic calculi which you may find of interest.

In the past few years there has been a very active line of research around so-called quantitative denotational semantics of linear logic, based on the idea (originally due to Girard [1]) that higher-order programs may be modeled by power series.  In the probabilistic case, this takes the form of so-called probabilistic coherence spaces (PCS), also introduced by Girard [2] and studied in depth by Danos and Ehrhard [3].  PCS yield models of both typed and untyped probabilistic calculi which are of a very different nature than power domains and other monad-related models.  In particular, PCS give what is thus far the only known fully abstract model of probabilistic PCF [4], which is notoriously difficult and seemingly impossible to achieve with power domains (cf. the work of Jean Goubault-Larrecq).

Apart from Ehrhard, quantitative semantics is now actively developed by Michele Pagani and coauthors, I suggest you look at his web page for additional references.

[1] Jean-Yves Girard, Normal functors, power series and $\lambda$-calculus. Annals of Pure and Applied Logic 37 (2):129-177, 1988.

[2] Jean-Yves Girard, Between logic and quantic: a tract. In Linear logic in computer science, CUP, 2004.

[3] Vincent Danos and Thomas Ehrhard, Probabilistic coherence spaces as a model of higher-order probabilistic computation. Information and Computation 209(6): 966-991, 2011.

[4] Thomas Ehrhard, Michele Pagani and Christine Tasson, Probabilistic coherence spaces are fully abstract for probabilistic PCF. In Proceedings of POPL, pp. 309-320, 2014.


What would be the consequences of PH=PSPACE?

$\mathsf{PH}$ collapses. A $\mathsf{PSPACE}$-complete problem must be in some level of $\mathsf{PH}$, say it's in $\mathsf{\Sigma_k P}$. Since it's $\mathsf{PSPACE}$-complete$=\mathsf{PH}$-complete (by assumption), $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$.


Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

Quantum annealing essentially offers a square-root speed-up over classical simulated annealing in many circumstances. So, yes, it is potentially a faster approach for some optimization problems, but the speed-up isn't enough to make most hard problems tractable.

Unfortunately, you cannot efficiently simulate quantum annealing classically, because any approaches we know of require you to keep track of the state of the system, which requires keeping track of exponentially many parameters (the amplitude of each possible classical state). Thus any attempt to simulate quantum annealing incurs a huge overhead which kills any advantage.


Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Compute the intersection of your CFG language with the regular language $\sum_{i=0}^k A^k$ (this amounts to multiplying the number of states by $k$ and adding a "dead end" state). Now check whether the result is empty: convert into a grammar (I think the result will have polynomial size) and "backtrack" from epsilon productions.

Edit: Kaveh mentioned that this is polynomial in $k$, so if $k$ is given as an input, the algorithm is exponential in $|k|$. However, Kaveh found a way to fix it. Convert the original automaton to a CFG, and replace all terminals by a fixed terminal. Now use an iterative algorithm to find the minimal size of a word generated by each non-terminal, as follows.

Initialize all lengths with $\infty$, and then iteratively update all lengths in the obvious way: given a production $A \rightarrow a^t \prod B_i$ (the order doesn't matter), put $f(A) = \min(f(A),t+\sum f(B_i))$. Claim: this converges in $O(n)$ iterations, where $n$ is the number of non-terminals. The reason is that in a tree generating the minimal-length word, no non-terminal is used twice; each "edge" takes at most one iteration to process (some edges can be "updated" in parallel).


Approximate 1d TSP with linear comparisons?

EDIT (UPDATE): The lower bound in my answer below was proven (by a different proof) in "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; Algorithmica 19:447-460 (1997).

  is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$ in $o(n\log n)$ time using a comparison-based algorithm?

No. Here's a lower bound.

Claim. For any $\epsilon>0$, every comparison-based
$n^{1-\epsilon}$-approximation algorithm
requires $\Omega(\epsilon n\log n)$ comparisons in the worst case.

By "comparison-based" I mean any algorithm that
only queries the input with binary (True/False) queries.

Here's an attempt at a proof. Hopefully there are no mistakes.
FWIW the lower bound seems likely to extend to randomized algorithms.

Fix any $n$ and any arbitrarily small but constant $\epsilon>0$.

Consider just the $n!$ "permutation" input instances
$(x_1,x_2,\ldots,x_n)$
that are permutations of $[n]$.
The optimum solution for any such instance has cost $n-1$.

Define the cost of a permutation $\pi$
to be $c(\pi) = \sum_i |\pi(i+1) - \pi(i)|$.
Model the algorithm as taking as input a permutation $\pi$,
outputting a permutation $\pi'$,
and paying cost $d(\pi,\pi') = c(\pi'\circ \pi)$.

Define $C$ to be the minimum number of comparisons
for any comparison-based algorithm to achieve
competitive ratio $n^{1-\epsilon}$ on these instances.
Since opt is $n-1$, the algorithm must guarantee cost at most $n^{2-\epsilon}$.

We will show $C\ge \Omega(\epsilon n\log n)$.

Define $P$ to be, for any possible output $\pi'$,
the fraction of possible inputs for which output $\pi'$
would achieve cost at most $n^{2-\epsilon}$.
This fraction is independent of $\pi'$.

$P$ also equals the probability that, for a random permutation $\pi$,
its cost $c(\pi)$ is at most $n^{2-\epsilon}$.
(To see why, take $\pi'$ to be the identity permutation $I$.
Then $P$ is the fraction of inputs for which
$d(\pi,I)$ at most $n^{2-\epsilon}$,
but $d(\pi,I) = c(\pi)$.)

Lemma 1. $C \ge \log_2 1/P$.

Proof. Fix any algorithm that always uses less than $\log_2 1/P$ comparisons.
The decision tree for the algorithm has depth less than $\log_2 1/P$,
so there are at less than $1/P$ leaves, and, for some output
permutation $\pi'$,  the algorithm gives $\pi'$ as output
for more than a $P$ fraction of the inputs.  By definition of $P$,
for at least one such input, the output $\pi'$ gives cost more than $n^{2-\epsilon}$.
QED

Lemma 2. $P \le \exp(-\Omega(\epsilon n\log n))$.

Before we give the proof of Lemma 2, note that the two lemmas together
give the claim:
$$C
~\ge~ \log_2 \frac{1}{P}
~=~ \log_2 \exp(\Omega(\epsilon n\log n))
~=~ \Omega(\epsilon n\log n).$$

Proof of Lemma 2.
Let $\pi$ be a random permutation.
Recall that $P$ equals the probability that
its cost $c(\pi)$ is at most $n^{2-\epsilon}$.
Say that any pair $(i,i+1)$ is an edge
with cost $|\pi(i+1)-\pi(i)|$,
so $c(\pi)$ is the sum of the edge costs.

Suppose $c(\pi) \le n^{2-\epsilon}$.

Then, for any $q>0$, at most $n^{2-\epsilon}/q$ of the edges have cost $q$ or more.
Say that edges of cost less than $q$ are cheap.

Fix $q=n^{1-\epsilon/2}$.  Substituting and simplifying, at most $n^{1-\epsilon/2}$ of the
edges are not cheap.

Thus, at least $n - n^{1-\epsilon/2} \ge n/2$ of the edges are cheap.
Thus, there is a set $S$ containing $n/2$ cheap edges.

Claim. For any given set $S$ of $n/2$ edges,
the probability that all edges in $S$ are cheap
is at most $\exp(-\Omega(\epsilon n \log n))$.

Before we prove the claim, note that it implies the lemma as follows.
By the claim, and the naive union bound,
the probability that any there exists such a set $S$
is at most
$${n\choose n/2} \exp(-\Omega(\epsilon n \log n))
~\le~ 2^n \exp(-\Omega(\epsilon n \log n))$$
$$~\le~ \exp(O(n) -\Omega(\epsilon n \log n))
~\le~ \exp(-\Omega(\epsilon n \log n)).$$

Proof of Claim.
Choose $\pi$ by the following process.
Choose $\pi(1)$ uniformly from $[n]$,
then choose $\pi(2)$ uniformly from $[n] - \{\pi(1)\}$,
then choose $\pi(3)$ uniformly from $[n]-\{\pi(1),\pi(2)\}$, etc.

Consider any edge $(i,i+1)$ in $S$.
Consider the time just after $\pi(i)$ has been chosen,
when $\pi(i+1)$ is about to be chosen.
Regardless of the first $i$ choices (for $\pi(j)$ for $j\le i$),
there are at least $n-i$ choices for $\pi(i+1)$,
and at most $2n^{1-\epsilon/2}$ of those choices will give the edge $(i,i+1)$
cost less than $n^{1-\epsilon/2}$ (making it cheap).

Thus, conditioned on the first $i$ choices,
the probability that the edge is cheap
is at most $\frac{2n^{1-\epsilon/2}}{n-i}$.
Thus, the probability that all $n/2$
edges in $S$ are cheap is at most
$$\prod_{(i,i+1)\in S} \frac{2n^{1-\epsilon/2}}{n-i}.$$
Since $|S|\ge n/2$, there are at least $n/4$ edges in $S$
with $n-i\ge n/4$. Thus, this product is at most
$$\big(\frac{2n^{1-\epsilon/2}}{n/4}\big)^{n/4}
~\le~(8n^{-\epsilon/2})^{n/4}
~=~\exp(O(n)-\Omega(\epsilon n \log n))
~=~\exp(-\Omega(\epsilon n \log n)).$$

QED


[Too long for a comment, hence, an "answer".]

It seems that, for boolean circuits, only logarithmic in the size improvements of the trivial depth are known: every circuit of size $S$ can be transformed to a circuit of depth $O(S/\log S)$ Paterson and Valiant. For boolean (and arithmetic) formulas, the depth can be reduced to $O(\log S)$ (known as Spira's theorem). For arithmetic circuits, we can do much better than in the boolean case: then the resulting circuit has depth only about $(\log S)(\log d)$ and size $O(S^3)$, where $d$ is the degree of the computed polynomial: Valiant, Skyum, Berkowitz and Rackoff. Earlier, Hyafil (see the citation in the above paper) has obtained a similar upper bound on the depth, but the size increased until about $S^{\log d}$.


Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

To turn my comment into an answer...

Andrej Bauer in this post makes the parenthetical claim

  An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.

He never explicitly defines acceptable or cites the theorem. I assume the OPs question is the following.

What theorem is Andrej Bauer referring to?

Here is a guess.  It seems that earlier in the post, Andrej is implicitly suggesting that an acceptable representation of the reals is one in which the following properties hold:

One can effectively approximate a real by a rational to within a given precision.
Addition, multiplication, and inverse are computable.
The less-then relation, $<$, is semi-decidable.
There is a computable function which takes in a rapid sequence of reals (that is a sequence $(x_n)$ of reals such that $|x_n - x_m| \leq 2^{\min{n,m}}$ and outputs the limit.

Actually (1) and (4) are enough to prove (2) and (3), since to preform those operations: one only needs to approximate the real by a rational, do the operation, and convert back to a real.  (Basic module of continuity will tell you how close the approximated answer is.  Also, one needs to be able to convert from a rational to the corresponding real.  This can be done by using (1) to find reals that are close enough to the rational, and then using (4) to take the limit of these approximations.)

Now, for any two representations satisfying (1) and (4) they are computably isomorphic.  From (1), one can go from the first representation to the rapid Cauchy representation.  (That is, represent a real as a rapid Cauchy sequence of rationals.)  From (4), one can go the other way, taking a rapid Cauchy sequence of rationals and computing the real it converges to (using the second representation).

As for the question about complexity, I think it can't be anything better than just computable, but I realize I don't know for sure, mostly, because I don't know how to formulate the question formally.


Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

Base on Komus's constraint, we add another constraint which ensures a Steiner Tree on $G^{'}=(V, E^{'})$, where $E'=\{(i,j): i,j \in V\}$:
$$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$where $cut(U,V)$ denotes the cut set of $(U,V)$.

Together with Komus's constraint, our model is obtained as follows:

  $$min \sum_{e \in E}c_e x_e$$
  subject to
  $$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$
  $$\sum_{e \notin E} x_e \le k-1$$

Base on Cao's comment, one more step is needed to prune the solution of our model: if $\sum_{e \notin E}x_e < k-1$, then we delete the largest $\Delta$ edges in the solution, where $\Delta=k-1-\sum_{e \notin E}x_e$. Then we get an optimal solution.


Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

Apparently, no. This is a generalization where the relationship between $k$ and $i$ is stochastic (i.e. defined by a distribution and not deterministic).
To recover the original bits-back argument, we would need to pick a value $i_k$ for each possible value of $k$ and force $p(i=i_k \vert x, k)=1$ and 0 if $i \neq i_k$. Naturally, we would need to extend the support of $k$ to the same of $i$. In this particular example, $k \in \{0, 1, 2, 3\}$


Complexity of SAT parameterized by treewidth

FPT results

The complexity of SAT, #SAT and MaxSAT parametrized by primal and incidence treewidth is FPT for all cases and of the form $2^{ck}\|F\|^d$ where $\|F\|=\sum_{C \in F} |var(C)|$ is the size of a reasonable encoding of a CNF $F$, $k$ is the (primal/incidence) treewidth and $c$ and $d$ are constants.

In this answer, I will denote by SAT(ptw) the problem SAT parametrized by primal treewidth. Same notations for #SAT(ptw), MaxSAT(ptw) and SAT(itw) for incidence treewidth.

For SAT(ptw), it is hard to pinpoint the exact first reference as their are many works going in this direction and proving similar results without being exactly stated this way. I would thus point to [1] where Alekhnovich and Razborov proves that SAT parametrized by branch-width is FPT. They also observe that branch-width is similar to treewidth up to a constant factor. I also advice to read the introduction of this paper to have a good overview of the previous literature on similar results.

For SAT(itw) and #SAT(itw), it is a consequence of Courcelle's Theorem that was first observed in [4], but, as observed by Szeider in [2], the hidden constants may be very high. For #SAT(ptw), an observation that exhaustive DPLL would run in FPT time with reasonable constant has been made in [3] by Bacchus, Shannon and Pitassi but without formally proving this. Explicit algorithms with better complexity bounds are given by Szeider and Samer in [5] for #SAT(itw) and #SAT(ptw).

For MaxSAT(ptw) and MaxSAT(itw), I do not know any reference doing it directly. I suspect the community to be aware of the fact that easy modifications in the algorithm for #SAT and thus too straightforward to be published anywhere. An notable exception is, that appeared much later, [6] where Sæther, Telle and Vatshelle give an algorithm for MaxSAT(ps-width), a parameter more general than treewidth. They also observe that it is roughly the same algorithm for #SAT and weighted MaxSAT.

All algorithms mentioned above can also be transformed into algorithms for weighted versions of our problems. One uniform way of seeing this is through the spectrum of Knowledge Compilation. Basically, what you can observe it that all these algorithms are implicitly rewriting, in FPT time, the CNF formula into a very restricted Boolean circuit (known in the literature of knowledge compilation as d-DNNF) computing the same Boolean function, see [7] where it is proven for a very general parameter. The catch is that many problems are tractable on this new representation such as (weighted) model counting, enumeration or finding a model with minimal Hamming weight, etc. Thus, everything that is ptime on d-DNNF becomes FPT on bounded treewidth CNF for free: change the representation in FPT time and solve it on the new circuit (that is also of FPT size).

This encompasses SAT, #SAT, weighted #SAT and also MaxSAT by working a bit more. Indeed, changing the representation of an UNSAT formula is quite easy: just output the 0 circuit. So it will not help you. However, compiling $F' = \bigwedge_{C \in F} s_C \vee C$ where you add in each clause of $F$ a fresh selector variable $s_C$ is more interesting. $F'$ has the same treewidth as $F$ (+ constant) and is of course satisfiable (set $s_C=1$ for every $C$). Now, solving MaxSAT($F$) is equivalent to finding the solution of $F'$ setting the smallest number of $s_C$ to $1$, something that can be done in polynomial time for d-DNNF. A proof of this can be found in my thesis, Section 3.2.2 [8].

Best complexity

In [5], the complexity bounds are given very explicitly. For #SAT(ptw) (and thus for SAT(ptw) as well), the complexity is $O(2^{k}kNd)$ where $N$ is the number of variables and $d$ is the maximal number of occurrence of a variable in the formula. Not that $Nd$ may not be linear in $\|F\|$ but is very close from it. A linear time (in the formula size) compilation algorithm can be found in the appendix of [9] which gives also a linear time algorithm for SAT, #SAT, maxSAT etc. The complexity is of the form $O(2^{ck}\|F\|)$ but the exact value of $c$ is not discussed here as it was not really necessary in this paper. I would say that a thorough analysis would give $c=1$ but I have not checked it carefully.

For SAT(itw), [5] gives a complexity of $O(2^k k (l+2^k) \|F\|)$ where $l$ is the size of the longest clause of $F$. If one wants linear time in $\|F\|$, one can rewrite $F$ as an equivalent 3-CNF without changing its incidence treewidth as shown by Lampel, Mengel and Mitsou in [10], which thus gives an equivalent 3-CNF which thus has primal treewidth at most $3k$ and now use the algorithm for primal treewith but it would spoil the constant in the exponent.

These are the best explicitly stated/known complexity upper bounds. I would not be surprised if they can still be improved, especially going from $4^k$ to $2^{k+O(1)}$ for incidence treewidth. This can be explained by the fact that these results are mostly interesting in theory where the precise constant is not important and the work to get it down is not really worth it. Friedrich Slivovsky mentioned in personal communication that there may be some algebraic trick in the algorithm of [5] for itw to get a better complexity bound but as far as I know, it has never been written formally.

References

[1] M.Alekhnovich and A.A.Razborov, Satisability, branch-width and Tseitin tautologies. In 43rd Annual IEEE Symposiumon Foundations of ComputerScience (FOCS'02)

[2] On fixed-parameter tractable parameterizations of SAT, Stefan Szeider, Theory and Applications of Satisfiability, 6th International Conference, SAT 2003

[3] Bacchus, Fahiem, Shannon Dalmao, and Toniann Pitassi. "Solving #SAT and Bayesian inference with backtracking search." Journal of Artificial Intelligence Research 34 (2009).

[4] Courcelle, Bruno, Johann A. Makowsky, and Udi Rotics. "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic." Discrete Applied Mathematics 108.1-2 (2001).

[5] Samer, Marko, and Stefan Szeider. "Algorithms for propositional model counting." Journal of Discrete Algorithms 8.1 (2010): 50-64.

[6] Sæther, Sigve Hortemo, Jan Arne Telle, and Martin Vatshelle. "Solving# SAT and MAXSAT by dynamic programming." Journal of Artificial Intelligence Research 54 (2015): 59-82.

[7] Bova, Simone, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. "On compiling CNFs into structured deterministic DNNFs." In International Conference on Theory and Applications of Satisfiability Testing, pp. 199-214. Springer, Cham, 2015.

[8] Structural restriction of CNF-formulas: application to model counting and knowledge compilation, Thèse de Doctorat, 2016.

[9] Capelli, Florent, and Stefan Mengel. "Knowledge compilation, width and quantification." arXiv preprint arXiv:1807.04263 (2018).

[10] Lampis, Michael, Stefan Mengel, and Valia Mitsou. "QBF as an Alternative to Courcelle’s Theorem." International Conference on Theory and Applications of Satisfiability Testing. Springer, Cham, 2018.


How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?

First, after each stage throw away any isolated vertices. With these vertices removed (even when the graph is disconnected) the number of vertices in the next stage will be at most twice the number of edges.

Next, use the fact that (with isolated vertices removed, in each stage after the first) $|V|\le 2|E|$ to simplify the time bound in each stage (after the first) from $O(|V|+|E|)$ to $O(|E|)$.

Finally, observe that at each stage $|E|$ goes down by a factor of two, so all these $O(|E|)$ bounds add in a geometric series to be linear in the size of the original graph.


You can trivially make a data structure with O(1) amortized concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same as was used in constructing that tree in the first place, so the overall time is still O(n log n)), but this is cheating.

For worst-case O(1) time, the authors claim it was an open problem for any data structure, so I don't think you're going to find an easy answer.


How to go about proving the basic operators in relational algebra are independent of each other?

Here are some hints:

Select: consider the relation $\{(1),(2)\}$.
Project: number of columns can't decrease.
Cross product: number of columns can't increase.
Union: consider the database $\{(1)\},\{(2)\}$ with identical attributes.
Difference: similar to union.


On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I don't know if you're still interested in this (old) question, and if I understood well the resource constraints you gave in the comment; however it seems that your problem (which is slightly different from usual RCSP problems) is NP-complete for planar (undirected or directed or directed acyclic) graphs of max-degree 3.

The easy reduction is from 3-SAT. Given a formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ clauses $C_1,...C_m$:

add a resource constraint set $M_k^+$ with two vertices for each positive literal $x_k$ in $\varphi$ and a resource constraint set $M_k^-$ with two vertices for each negative literal $\bar{x}_k$ in $\varphi$;
start building a graph from a source node $s$ and for each variable $x_i$ split the path in two lines: the upper one traverses one vertex of all the $M_k^-$ that correspond to a negative literal $\bar{x}_k$; the lower one traverses one vertex of all the $M_k^+$  that correspond to a positive literal $x_k$;
then for each $C_j$ split the path in 3 lines that traverse in parallel the 3 vertices corresponding to the literals of $C_j$ and that are picked from the corresponding $M_k^+$ or $M_k^-$;
finally add a sink node $t$.

A path from $s$ to $t$ exists if and only if the original formula is satisfiable (i.e.  without loss of generality you can ask for a path of length $\leq |V|$).

Informally when traversing the variable section $x_i$, if you pick the upper line (true assignment) then you must "use" one of the vertices of all the $M_k^-$ resource constraint sets that also contain a vertex that can be used later to traverse (satisfy) a clause containing $\bar{x}_i$. If you pick the lower line (false assignment) then you must "use" one of the vertices of all the $M_k^+$ resource constraint sets that also contain a vertex that can be used later to traverse (satisfy) a clause containing $x_i$. When traversing each clause at least one of the three vertices must be contained in a $M_k$ that has not be "used" yet (i.e. at least one of them can be used to satisfy the clause).

The following figure should make the reduction clearer. The resource constraint sets $M_k$ are represented with distinct colors (and for every color there are exactly 2 vertices).

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$

You can also easily make the graph directed, acyclic and bipartite. Let me know if you need further details (or if I completely misunderstood the problem :-).

As noted by Saaed the problem is fixed-parameter tractable with respect to $k$ (just consider all possible subsets of constrained nodes and for each combination run the shortest path algorithm).


I don't know if these graphs have a common name. But I think, one would call vertices with no outgoing edge rather a sink than a root.

This paper studies acyclic orientations of grid graphs. They call an orientation, which would correspond to the graphs you consider, acyclic orientations with a unique sink.


Is there an algorithm that's "like" cross-validation for approximation algorithms of NP-hard problems?

Crossvalidation is used to test the difference in behaviour between training and test data. There's no equivalent notion for approximations. However, for many problems it's possible (often via an LP relaxation) to get a good lower bound for a problem. This can be used to test the quality of a given approximation algorithm in practice.

For a good example of this, you should look at David Johnson's survey of experimental work on the travelling salesman problem.


In some fields (like e.g. Economics and Mathematics) single authored papers -are- a good thing to have when you go on the job market. In theoretical computer science, collaboration is much more common, and it is not unusual for even relatively senior researchers to have very few single authored papers. It is not at all suspicious if a student on the market has only papers with co-authors. This is partly because we publish more frequently, so it is ok that each individual paper has less signal about your specific contribution. This is not to say that single authored papers are not impressive, but credit is super-additive across authors, and all things being equal, you should prefer to have a better paper with more coauthors than a worse paper with fewer. This should push you towards collaboration, since collaborators make your research both more fun and generally stronger.

Of course in hiring decisions, committees will attempt to figure out whether you were a significant contributor to the papers you worked on or not -- but this will be done largely through the letters you obtain. If you have several good papers with the same senior co-author, that coauthor should write a letter for you, since they can explain in detail your contribution. It also helps if you have a clear research agenda of your own. Many papers on -your- topic with a rotating cast of coauthors conveys that you are leading the research direction, in contrast to a series of papers on disparate topics, each in the research agenda of your various coauthors.


Known properties of a specific class of quantum states

M. G. Parker and V. Rijmen have studied the quantum entanglement of binary and bipolar sequences in arXiv:quant-ph/0107106. I remember reading their paper long ago. They use a lot of terminology from coding theory, so now by just skimming through, I can't understand exactly what their result is, but you can have a deeper look.

Notice also that graph states are a special case of your states. In particular, $\psi$ is a graph state if and only if the sequence $x$ is generated by a quadratic polynomial in GF(2).


Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

Here is a proposition for an elementary proof:
Let $\mathcal A=(A,Q,q_0,F,\delta)$ be a DFA for $L$, we want to build a DFA  $\mathcal A'=(A,Q',q_0',F',\delta')$ for $f^{-1}(L)$. Intuitively, when reading a word $u$, $\mathcal A'$ will remember the state reached in $\mathcal A$ by $f(u)$, together with the action of $u$ on all states of $\mathcal A$. More formally, we take:

$Q'=Q\times Q^Q$
$q_0'=(q_0,\mathit{id})$
$F'=F\times Q^Q$
$\delta_a'(p,g)=(\delta_a(g(p)),\delta_a\circ g)$

Where $\delta_a:Q\to Q$ is the transition function associated with a letter $a$.
This ensures that after reading a word $u$, the first component of the state of $\mathcal A'$ gives the state reached by $\mathcal A$ on $f(u)$.


When does a bipartite graph have bounded treewidth?

I think there is no simpler characterization than just the fact that the treewidth of $G$ is bounded. The intuition for why is that by subdividing each edge of a graph we get a bipartite graph with the same treewidth. In particular, we have a very simple reduction from determining the treewidth of a graph to determining the treewidth of a bipartite graph.


What is the smallest result you publish on ArXiv?

ArXiv papers still need to be recognizable as papers. I'd only put something on the arXiv if I'd feel comfortable publishing it as a letter in a journal (like, say, Information Processing Letters). For stuff that's even smaller than that, but that I still want to put on some sort of public record, I'll just make a blog post.

But in your case, if you've written it up as a preprint anyway, and you clearly state in it how much or how little is new, then why not? ArXiv papers don't actually have to have any new research content — survey papers are also welcome — so a paper that's mostly a survey but that extends the problem a small step in some direction doesn't sound problematic to me.


What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?

You can decide if a quadratic polynomial $p: \mathbb{R}^n \rightarrow \mathbb{R}$ has real roots with some linear algebra. As you note, the general case should be hard.

Observe first that $p(x) \neq 0$ for all $x \in \mathbb{R}^n$ if either $p(x) > 0$ or $p(x) < 0$ for all $x$ (this follows by continuity). So it is enough to be able to decide if $p(x) > 0$ for all $x$. In general this is related to complexity-theoretic versions of Hilbert's 17th problem: a polynomial $p(x)$ is positive over the reals if and only if you can write $p$ as the sum of squares of rational functions and a positive constant $c$ (this is a theorem by Artin). Finding this decomposition or solving the decision problem is most likely hard in general, but the quadratic case is easy, because of the magic of the spectral theorem. For more information about the general case, look at Devanur,Lipton,Vishnoi, and Monique Laurent's survey.

Let us write $p(x) = p_2(x) + p_1(x) + c$ where $p_2$ is homogeneous of degree 2, $p_1$ is linear, and $c$ is a constant. Let us define $q(x_0,x) = p_2(x) + x_0p_1(x) + cx_0^2$ to be the homogenization of $p$, where $x_0$ is an additional variable.

Claim. $p(x) > 0 \Leftrightarrow \forall x_0 \neq 0: q(x_0,x) > 0$

The "if" direction is easy. In the non-trivial direction, assume $p(x) > 0$ for all $x$ and assume $x_0 \neq 0$:
$$
q(x_0,x) = x_0^2q\left(1,\frac{x}{x_0}\right) = x_0^2 p\left(\frac{x}{x_0}\right) > 0.
$$
QED

Notice also that, because $q(x_0, x)$ is continuous, if $p(x) > 0$ for all $x$ then $q(x_0,x) \geq 0$ for all $(x_0,x)$ (including $x_0 = 0$).

Since $q$ is homogeneous, we can write $q(x_0,x) = y^TQy$, where $Q$ is a symmetric matrix and $y = (x_0,x)$. By the above, if $p(x) > 0$ for all $x$, then $Q$ is positive semidefinite. Moreover, $q(x_0, x) > 0$ for all $x_0 \neq 0$ if and only if the kernel of $Q$ is a subset of the hyperplane $\{y = (0,x): x \in \mathbb{R}^n\}$. Both these conditions can be decided in polynomial time by computing the SVD of $Q$.


One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability:

  When Does a Dynamic Programming Formulation Guarantee the Existence
  of a Fully Polynomial Time Approximation Scheme (FPTAS)?


Mathematics degree for Theoretical Computer Science?

I would say there is no "one best/most appropriate route" to becoming a theoretical computer scientist, so it is more a matter of your personal tastes, and even what part of theoretical computer science you are most interested in, which you may not even know yet. I know of great TCS researchers who started out in pure math, and great TCS researchers who started out in CS or (even!) EE.

(And by the way, to the commenters: I know plenty of good TCS researchers who more or less abhor programming, and I also know plenty who are not only great programmers, but great software engineers.)

Whatever route you take, if you think you are really interested in TCS then you should immerse yourself in it, especially to try to find out which parts of it you are really interested in. Introductory classes on algorithms (many of which are purely theoretical and involve no programming, if you so desire) or the theory of computation are good places to start, and beyond that it is a matter of reading, asking professors for references and pointers, sitting in on introductory TCS grad classes if you have the opportunity, etc. From that point of view, your particular degree doesn't matter so much (unless e.g. if you do a mathematics degree your university would perversely prevent you from taking a course on algorithms or theory of computation).

However, it also sounds like it is still so early in your potential research career that it would be healthy to question why you are interested in TCS (even asking this question can lead you on a path to discovering exactly what parts of TCS you are really interested in, and give you better motivation for your future work), and to expose yourself to plenty of other topics to see if your true interests end up being elsewhere.


Which randomized algorithms have exponentially small error probability?

Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, this can be improved to a correctness probability of $1-2^{-k}$, using $O(r+k)$ random bits. (Note: while the authors use the specific constant 2/3 in the abstract, it can be replaced with any other constant greater than 1/2.)

If we take $k=r$, this means  that any BPP algorithm that achieves a constant error probability $< 1/2$, using $r$ random bits,  can be (non-trivially) improved to have error probability $2^{-\Omega(r)}$. Thus, (unless I misunderstood something), the error probability of $\leq 2^{-\Omega(r)}$ is achievable for every problem in BPP.


Finding k nearest neighbors for all points

$O(kn+n\log n)$. See

P.B. Callahan, S.R. Kosaraju, A decomposition of multidimensional
point sets with applications to k-nearest-neighbors and n-body potential ﬁelds, J. ACM 42 (1995) 67–90.

In some models of computation the $O(n\log n)$ part can be reduced or removed; see also

T. M. Chan, Well-separated pair decomposition in linear time?, Inf. Proc. Lett. 2008.


Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

The answer to the question is yes, assuming that (for all large $k$) $k$-SUM is not in $\text{DTIME}(n^{o(k)})$.
It also follows (by a result of Patrascu and Williams) that the answer is yes assuming the ETH holds.
The proof reuses the classical technique from the classical proof that, if any unary language is NP-hard, then P=NP.
Definitions

The question: Does there exist $k \geq 2$ such that there exist problems in $\text{DTIME}(n^k) - \text{DTIME}(n^{k-1})$ that are not computationally hard for $\text{DTIME}(n^{k-1})$ under nearly linear-time reductions?

The $k$-SUM problem: Given $n$ integers, are there $k$ of them that sum to zero?

ETH (the Exponential Time Hypothesis): 3-SAT is not in $\text{DTIME}(2^{o(n)})$.

Result
Theorem 1. Assume that (for all $k$), $k$-SUM is not in $\text{DTIME}(n^{o(k)})$.  Then the answer to the question is yes.
Proof. We show the contrapositive.  Assume that the answer to the question is no.  As observed in the post, this implies that, for all sufficiently large $k$, there is a unary language that is hard for $\text{DTIME}(n^k)$ under nearly linear-time reductions.  To complete the proof we show the following:
Lemma 1. Assume that, for some $c\ge 1$, for all sufficiently large $k$, there is a unary language that is hard for $\text{DTIME}(n^k)$ under $O(n^c)$-time reductions.  Then, for all $k$, $k$-SUM is in $\text{DTIME}(n^{2c+1}) \subseteq \text{DTIME}(n^{o(k)})$.
Proof. Fix such a $c\ge 1$ and an arbitrarily large $k$. Let $L\subseteq 1^*$ be the unary language that is hard for $\text{DTIME}(n^{k+1})$ under $O(n^c)$-time reductions.
Define the following generalization of $k$-SUM, called $k$-SUM'.  The input consists of $n$ integers, a target $t$, and a budget $d\le k$.  The question is whether any $d$ of the given integers sum to $t$.
To prove the lemma, we describe an $n^{O(c)}$-time algorithm for $k$-SUM' (which clearly generalizes $k$-SUM).
As $k$-SUM' is easily in $\text{DTIME}(n^{k+1})$, by definition of $L$ there is an $O(n^c)$-time reduction, say $f$, from $k$-SUM' to the unary language $L$.
We use the classical technique from the proof that, if there is an NP-hard unary language, then P=NP.  Namely, consider the following dynamic-programming algorithm for $k$-SUM' (presented here in recursive memoized form):

input: $k$-SUM' instance $I=((x_1, x_2, \ldots, x_n), t, d)$

if $n=0$ or $d=0$, return 'true' if $t=0$ and 'false' otherwise  (base case)

compute the reduction $f(I) \in 1^*$ (the time this takes and $|f(I)|$ are both $O(n^c)$)

if we've previously computed the answer for an instance $I'$ with $f(I')=f(I)$, return the same answer for $I$.  otherwise:

let $I_0$ be the $k$-SUM' instance $((x_1, x_2, \ldots, x_{n-1}), t, d)$

let $I_1$ be the $k$-SUM' instance $((x_1, x_2, \ldots, x_{n-1}), t-x_n, d-1)$

recursively compute the answers for $I_0$ and $I_1$

the answer for $I$ is 'true' iff the answer to $I_0$ is 'true' or the answer to $I_1$ is 'true'

memoize the answer for $I$ in the lookup table, under index $f(I)$

return the answer for $I$

The algorithm is correct by standard dynamic-programming reasoning along with the observation that any two $k$-SUM' instances that reduce to the same element of $L$ must have the same answer.
How much time does it take?
For each subproblem (not counting the recursive calls) the time is dominated by the the time to compute $f(I)$, which is $O(n^c)$.
Each subproblem $I'$ that arises in the recursion has size $O(n)$, so $f(I')$ is of the form $1^m$ for $m = O(n^c)$.  Thus, the number of "distinct subproblems" (whose answers are not already cached when they arise) is $O(n^{c+1})$ (we get an extra factor of $n$ because if a subproblem $I$ has an ancestor $I'$ with $f(I)=f(I')$, the answer for $f(I')$ won't be cached when $I$ is encountered).  It follows that the recursion tree has $O(n^{c+1})$ nodes, and the total time is $O(n^{2c+1})$.  $~~~\Box$


I think the reference you are looking for is the paper "Broadcasting algorithms in radio networks with unknown topology" by Czumaj and Rytter.  It seems this paper makes some improvements, but I think it depends on the specifics of the model.


Maximum flow for all edges in an undirected graph

There is a randomized algorithm for computing Gomory-Hu tree in $\tilde{O}(|E||V|)$ time when all edges have capacity 1.
Once you have the Gomory-Hu tree, you can process it so you can answer maximum flow queries between two vertices in constant time.


What is known about this binary representation polytope?

I think $S_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}.
$$

I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{0, 1\}^n$ induced by picking $y_i = 1$ with probability  $y^*_i$, independently for each $i$. If $y$ is sampled from that distribution, then, by linearity of expectation,
$$
\mathbb{E}\ x = \mathbb{E} \sum_{i = 0}^{n-1}{2^i y_i} = \sum_{i = 0}^{n-1}{2^i y^*_i} = x^*.
$$
Therefore $(x^*, y^*)$ is in the convex hull of $S_n$, which proves $Q_n \subseteq S_n$.

BTW, this didn't really use anything special about $S_n$. Whenever you have the convex hull of the set $\{(x, y): y \in S, x = Ay\}$, and the convex hull of $S$ has a concise extended formulation, the same thing will work. The main point is that $x$ is a linear function of $y$. Here we used the fact that the cube $[0, 1]^n$ has a very easy formulation in terms of inequalities.


Is clique-width preserved under edge contractions?

This recent paper finally proves that edge contractions do not preserve the property that a set of graphs has bounded
clique-width.


The simplex algorithm indeed visits all $2^n$ vertices in the worst case (Klee & Minty 1972), and this turns out to be true for any deterministic pivot rule. However, in a landmark paper using a smoothed analysis, Spielman and Teng (2001) proved that when the inputs to the algorithm are slightly randomly perturbed, the expected running time of the simplex algorithm is polynomial for any inputs -- this basically says that for any problem there is a "nearby" one that the simplex method will efficiently solve, and it pretty much covers every real-world linear program you'd like to solve.  Afterwards, Kelner and Spielman (2006) introduced a polynomial time randomized simplex algorithm that truley works on any inputs, even the bad ones for the original simplex algorithm.