Highest lower bound on NP problems (TSP)

The best known lower bounds for TSP are essentially the same as those for 3SAT (within polylogarithmic factors), and they apply the fact that there are very efficient reductions from 3SAT to Hamiltonian Path. (So, a good algorithm for Hamiltonian path would imply one for 3SAT, but certain lower bounds show that sufficiently good algorithms don't exist for 3SAT.)

For the best 3SAT lower bounds known, see this answer. The bottom line is that the only non-trivial lower bounds known for these problems impose a space restriction on the candidate algorithm, as well as a time restriction. So for example, we can say TSP cannot be solved in $n^{1.5}$ time and $O(log n)$ space, but we don't know if TSP can be solved in $n^{1.5}$ time (with no space restriction).


Is it decidable whether the output length of a transducer is bounded by the input length?

The other contributor deleted his answer, maybe to let me extend my above comment, so here it is.

Let $T$ be a possibly nondeterministic transducer, and $L$ be a regular language.  Modify $T$ into a transducer $T'$ that checks that its input is in $L$ (by, e.g., changing the state set into the Cartesian product of the state sets of  $T$ and $L$, and modifying the transition function so that the $L$ part of the states is properly updated, while retaining the behavior of $T$.)

A branch of $T'$ is a sequence $\rho_1 C_1\rho_2 C_2 \cdots \rho_n C_n \rho_{n+1}$ such that $\rho_1\rho_2 \cdots \rho_{n+1}$ is an accepting simple path in $T'$, and each $C_i$ is a strongly connected component of $T'$ the states of which include the destination of $\rho_i$ (and the origin of $\rho_{i+1}$).  The branch is tame if:

The input length of the path $\rho_1\rho_2\cdots\rho_{n+1}$ is greater than or equal to its output length;
For any $i$, any simple cycle in $C_i$, the input length of the cycle is greater than or equal to its output length.

Fact: $\big[$ For any $x, y$, $x[T']y$ implies $|y| \leq |x|$ $\big]$ iff all branches are tame.

The proof is rather immediate.  The latter property being decidable (as the number of branches is bounded, and the number of simple cycles too), this shows that the problem of the question is decidable.


Sorting algorithm with a complexity smaller than $n \log n$?

Without looking at any details, why do your say your algorithm beats $O(N\log N)$?

In your notation, $N\log N = n\log n\log(n\log n) = n\log n\log n + n\log n\log\log n = O(n\log^2n)$.

No contradiction.


Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete:

  Instance: An integer $k$; a $k$-partite graph $G=(V,E)$
  Question: Does $G$ contain a $k$-clique?

Here is a construction that shows NP-completeness of your problem variant:

Let $G$ and $k$ be as in the proof in Garey and Johnson
Let $H_1$ be a graph on $k+2$ vertices: The $k-3$ vertices $v_1,\ldots,v_{k-3}$ induce a clique, and the five vertices $u_1,\ldots,u_5$ induce an odd cycle $C_5$. Every $u_i$ is connected to every $v_j$.
It is easy to see that $\omega(H_1)=k-1$ and $\chi(H_1)=k$.
Let $H_2$ be an independent set on $2|V|+2k^2$ vertices.
Create a graph $G'$ by taking the disjoint union of $G$, $H_1$ and $H_2$, and by adding all the edges between $H_2$ on the one side and $G\cup H_2$ on the other side.

It can be verified that:

$\alpha(G')=2|V|+2k^2$. (Take all vertices in $H_2$.)
$\chi(G')=k+1$. (Note that $G\cup H_2$ is $k$-colorable, and that $H_1$ adds one more color.)
$\omega(G')=\max\{\omega(G),k-1\}+1$. (Note that $\omega(G\cup H_2)=\max\{\omega(G),k-1\}$, and that $H_1$ adds one more vertex to this.)

Hence the knowledge of $\omega(G')$ would allow us to decide whether $\omega(G)=k$.


There seem to be many ways to tackle this problem, but one simple way would be to use the Blum Blum Shub PRNG. This PRNG is defined by the recurrance relation $x_{i+1} = x_i^2 \mbox{ mod }N$, where $N$ is a semiprime. To get a random bit out of this you can simply take the bit parity of $x_i$. What's nice about this is that since $x_{i+k} = x_i^{2^k}\mbox{ mod }N = x_i^{2^k \mbox{ mod } \lambda(N)}\mbox{mod }N$ you can directly calculate any step in time constant in $k$ (i.e. $O(\log(N)^3)$ or faster depending on which multiplication algorithm you use for the modular exponential). Thus is you have $M$ machines, then for the machine indexed by $y$ you can use the generator $x_{i+1,y} = x_i^{2^M \mbox{mod }\lambda(N)}\mbox{ mod }N$, where $x_{0,y} = x_0^{2^y \mbox{ mod }\lambda(N)}\mbox{ mod }N$, where $x_0$ is your seed. Conveniently this generates exactly the same stream of numbers as if you used a single stream and distributed it's output to each of the machines in turn.

This isn't the fastest of PRNGs, though, so it will only be useful if the overhead of whatever you are doing in the simulation is significantly more than the cost of the PRNG. However it is worth pointing out that it will be much faster for certain combinations of $M$ and $N$ than others, particularly if the binary representation of $2^M \mbox{ mod }\lambda(N)$ contains few 1s or is small.


Minimum equivalent digraph with respect to sources and sinks

Let's assume that $D$ contains only sources and sinks, since the input can be translated into an equivalent such input easily.

Then, note that, in any solution $D'$ for $D$, each vertex $v$ corresponds to a biclique in the underlying undirected graph $G$ of $D$ (the biclique between all sources that reach $v$ in $D'$ and all sinks that are reached from $v$ in $D'$).

I conjecture that, if $D'$ is optimal, then it contains a vertex-cut that 1:1 corresponds to an optimal biclique covering of $G$. Then, any minimum vertex-cut in $D'$ corresponds to an optimal biclique covering in $G$. However, since BICLIQUE COVER (aka BIPARTITE DIMENSION) is NP-complete, your problem is unlikely to admit a polynomial-time algorithm unless my conjecture fails.

Note that, even if my conjecture holds, technically this argument does not prove NP-hardness of your problem, since the reduction is not a Karp- but a Cook reduction.


Suppose that $A$ is an $m\times n$ matrix, and let $\mathcal{A}$ be the corresponding linear operator whose matrix (w.r.t. the standard basis) is $A$. Let $W\subseteq \mathbb{R}^m$ be the span of the columns of $A$, or, equivalently, the range of $\cal A$. I am going to treat $\mathcal{A}$ as an operator from $\mathbb{R}^n$ to $W$. As long as $A$ has full column rank, the operator $\mathcal{A}$ is an injection, so it is invertible on its range: let $\mathcal{A}^{-1}:W \to \mathbb{R}^n$ be its inverse.

You are asking about the quantity
$$
\min_{x \neq 0}\frac{\|\mathcal{A}x\|_p}{\|x\|_p} = \min_{y \in W\setminus \{0\}}\frac{\|y\|_p}{\|\mathcal{A}^{-1}y\|_p} = \left(\max_{y \in W\setminus \{0\}}\frac{\|\mathcal{A}^{-1}\|_p}{\|y\|_p}\right)^{-1}
$$

So, your quantity $f_p(A)$ is the operator norm of $\mathcal{A}^{-1}$, taken as an operator from the normed space $(W, \|\cdot\|_p)$ to $(\mathbb{R}^n, \|\cdot\|_p)$. In the special case when $A$ is square, this is just an $\ell_p \to \ell_p$ operator norm. Otherwise it's the norm of an operator from a subspace of $\ell_p$ to $\ell_p$.

If you insist on matrix notation, then you can take $B$ to be a matrix whose rows form an orthonormal basis of $W$. Then $B^\top B$ is the orthogonal projection onto $W$, and, since it acts as identity on the column span of $A$, $B^\top BA = A$. Moreover, if $A$ has full column rank, then $BA$ is an invertible square matrix. So, using the  substitution $z = BAx$, you get

$$
\min_{x \neq 0}\frac{\|\mathcal{A}x\|_p}{\|x\|_p}
= \min_{x \neq 0}\frac{\|B^\top BAx\|_p}{\|x\|_p}
= \min_{z \neq 0}\frac{\|B^\top z\|_p}{\|(BA)^{-1}z\|_p}
= \left(\max_{z \neq 0}\frac{\|(BA)^{-1}z\|_p}{\|B^\top z\|_p} \right)^{-1}
$$
This is the inverse of the $\mathcal{B}_p \to \ell_p$ operator norm of $(BA)^{-1}$, where $\mathcal{B}_p$ is the norm on $\mathbb{R}^n$ defined by $\|z\|_{\mathcal{B}_p} = \|B^\top z\|_p$. (Of course this is the same as above: the subspace $(W, \|\cdot \|_p)$ of $\ell_p$ is isometric to the normed space $(\mathbb{R}^n, \|\cdot\|_{\mathcal{B}_p})$; we've just committed to some basis for it.)


You might be interested in Scott Aaronson's recent paper Why Philosophers Should Care About Computational Complexity, to appear in Computability: Gödel, Turing, Church, and Beyond, edited by B. J. Copeland, C. Posy, and O. Shagrir, MIT Press, 2012. ECCC TR11-108, arXiv:1108.1791.


Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

There are two loanable copies at The National Library of Israel.

Here is a scanned copy.


what is a model of computation, mathematically?

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words over a finite alphabet), an early attempt of an overarching mathematical definition was the abstract family of acceptors, which encompasses Turing machines, finite automata,  stack automata,  pushdown automata and similar notions: Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA. IEEE. pp. 128–139. Needless to say, that notion does not describe L-systems, nonuniform circuit families, quantum devices, probabilistic models, membrane computing etc.


Simple question about pseudorandom generator

I assume you mean a cryptographic PRG.

Let's assume on the contrary that the $G'$ is not secure. So let $A$ be a probabilistic Turing machine that distinguishes the output of $G'$ from uniformly random bits.

Let $x_1,x_2$ be $k$ bit random strings, and let $z_1,z_2$ be $k+1$ bit random strings.

We have that $A$ distinguishes the distribution of strings $D_0 : G(x_1)G(x_2)$ and
$D_2: z_1z_2$.

Consider now the hybrid distribution of strings given by $D_1: G(x_1)z_2$.

By the triangle inequality $A$ also distinguishes between either $D_0$ and $D_1$ or between $D_1$ and $D_2$.

Assume without loss of generality that  $A$ distinguishes between $D_0$ and $D_1$.
Then we can break $G$ as follows. On input $y$, pick uniformly random $k$ bit string $x_1$ and give the string $G(x_1)y$ to $A$.


Resource listing models with known VC dimension

Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded depth/fanin (Lemma 8.6 in Bartlett and Anthony, Neural Network Nearning) or the VC-dim of a neural network with a certain number of nodes (Thm. 3.6 in Kearns & Vazirani,  An Introduction to Computational Learning Theory.


The Relationship between P^NP and the Permanent

I think you misunderstood the definition of $\mathsf{FPRAS}$.

  Let $f: \Sigma^*\rightarrow Z^+$ be a
  function in $\#\mathsf{P}$. An
  algorithm $A$ is an $\mathsf{FPRAS}$
  for $f$ if for each $x\in \Sigma^*$,
  and error parameter $\epsilon >0$,
  \begin{align*} Pr[|A(x)-f(x)] \le \epsilon f(x)] \ge 3/4 \end{align*} and the running time of $A$
  is polynomial in $|x|$ and
  $1/\epsilon$.

So if you want to reduce the error to exponentially small, then the running time will also become exponential!

Note that both of the results you mentioned show that approximating counting can be done within the second level of the polytime hierarchy $\mathsf{PH}$ or so. On the other hand, $\#\mathsf{P}$ is the class of exact counting, which is widely believed to be harder than approximate counting. Otherwise, $\#\mathsf{P}$ is also contained in  $\mathsf{FP}^\mathsf{NP}$, which implies that $\mathsf{PH}$ will collapse at least to the second level.


"Easy to check" is the understatement of the century: can you actually carry out your proposed plan of "just" writing down all the registers/RAM cells, etc? You're right that it takes finite time, but a large amount of finite time. Our best algorithms for performing this check are exponential in the size of the input on the tape, and a strong version of the $P\neq NP$ conjecture states that there is no algorithm that achieves a faster (subexponential) runtime uniformly over all inputs.

So the P=NP problem is a finitary version of the halting problem. The latter has no algorithmic solution when input length is unbounded. The former admits a brute-force solution, but the amount of time required to find it is so large that for all practical purposes it's as good as unsolvable.

Edit: My statement that the halting problem can't be decided by any algorithm because the "input length is unbounded" is inaccurate, since for DFAs the latter also holds but the languages they accept are of course decidable. But certainly when the number of configurations is finite -- as is the case for a finite-tape TM -- a brute-force search solves the halting problem. Somewhat confusingly, the finiteness of the number of configurations is actually not necessary for decidability, as the DFA example shows.


Winning strategy in the game of triplets

This isn't a complete proof, but here's some justification for why known conjectures imply that the game may be computationally hard to solve. Namely, I'm going to argue that finding the correct first move is already probably tricky.

As a first step, we argue that the triplets game is harder (in the appropriate sense) than the $\textrm{Denser Induced Subgraph}$ game defined as follows.

Two players, A and B, alternate picking vertices on a common graph G. Vertices can only be picked once. When no more vertices remain to be picked, the subgraphs induced by each player's choices are compared.  The player with the larger number of induced edges is declared the winner.

Proof outline:
Given an instance of the $\textrm{Denser Induced Subgraph}$ game with graph $G = (V,E)$, we construct a $\textrm{Triplets}$ instance as follows. Without loss of generality, assume $G$ has no isolated vertices. The set of elements in our instance will be $V \cup (E \times \{0,1\})$. For each edge $e \in E$ between vertices $u$ and $v$, we have two triplets of the form $(u, v, (e, 0))$ and $(u, v, (e, 1))$. Additionally, for each vertex $v \in V$, we throw in four additional triplets of the form $(v,v,v)$. This completes the reduction.
Now imagine the proceedings of the $\mathrm{Triplets}$ game. As long as some vertex from $V$ has not been picked, the choice of such a vertex strictly dominates that of any element from $E$. Indeed, picking an element from $E \times \{0,1\}$ only ever gives a potential score increase of $1$ (and also blocks the opponent from at most $1$ point), while picking an element from $V$ automatically gives a score increase of $4$, with potential for more.
Therefore, under optimal play, the first $|V|$ rounds will correspond to both players picking elements from $V$. After these rounds, the players alternate picking up the even-sized collection of triples that have not yet been claimed, which correspond to exactly the edges whose endpoints have been picked once by each player. Any reasonable strategy here, for either player, ends up picking up exactly half of those available triplets. The game ends with a sequence of NOOP moves on the already-picked-up triplets.
Let $V_A$ be the vertices chosen by player A, and $V_B$ those chosen by B. The score for player A is the sum of (i) four points per vertex chosen from the $(v,v,v)$ triplets (ii) two points per induced edge created from these vertices, and (iii) one point for each split edge. Therefore, the score is $4|V|/2 + 2|E[V_A]| + (|E| - |E[V_A]| - |E[V_B]|)$, where $E[S]$ is the set of edges induced by $S$. Since the first and last terms are ultimately equal for both players, the player with the larger induced subgraph wins. $\square$

With this in mind, we can appeal to some of the work in the literature of detecting dense subgraphs. There's a ton of relevant work out there on this that one can appeal to, but for simplicity of analysis I'll appeal to a particular conjecture on the difficulty of finding dense random graphs in sparse random graphs (I believe that this dependence can be removed with just a little more thought, but this is not meant to be a formal proof).

The Planted Dense Subgraph Problem (informal). Let $G = (V,E)$ be a random graph sampled from the Erdos-Renyi distribution $G(n, 1/\sqrt{n})$. With probability $1/2$, we return $G$ as is. Otherwise, we let $V'$ be a uniformly random subset of $V$ of size $\sqrt{n}$. For each $u,v$ pair in $V'$, we add an edge $(u,v)$ to $E$ independently with probability $n^{-1/4}$. Only then do we return $G$. The problem is to, given only the output of the above, correctly identify whether or not the Erdos-Renyi graph was augmented.
The Planted Dense Subgraph Conjecture (informal). No polynomial-time algorithm can solve the Planted Dense Subgraph problem with probability at least $51\%$.

Suppose that the graph was augmented, and there is an unusually dense component. Since no poly-time algorithm can reliably detect this dense subgraph's presence, it also cannot reliably sample a vertex from this dense component (e.g. due to self-reducibility). Therefore, since (from Player A's perspective) it is selecting a random vertex from a pure Erdos-Renyi graph, it does not matter much which vertex A picks (up to a small change in its scoring that will end up not mattering1). However, if Player B is omniscient, it can reliably sample a vertex from the dense component on its first shot. This process repeats a superconstant number of times before B's choices begin unveiling the dense component to A (otherwise, a polynomial-time algorithm can traverse every path in this game tree to constant depth in order to solve the Planted Dense Subgraph problem). If the process repeated $r$ times before A catches on, then the first $r-1$ rounds can be seen as "freebie" rounds for B, while the $r$th round is the beginning of A and B fighting over the dense component, with B getting the first move and (by your strategy stealing argument) a winning subset.
Once the dense component is exhausted, the two players resume fighting over the rest of the graph. While A has chosen $r$ more vertices here than B has, B's first $r$ vertices are worth $\Omega(n^{1/4})$ times as much, and thus B is ultimately the winner.
1. By some type of concentration and pigeonhole argument, the difference between making the first choice and the second choice should not be more than $O(1)$ in the final score.

Therefore, despite the game being very weakly solved for player A, it's unlikely that it's computationally feasible for A to play out even the first move of the winning strategy.
An approach based on the hardness of the "normal" densest subgraph problem should not be difficult to attain here, either, and composing the reduction with a hardness of approximation result likely can be used to get some kind of hardness based on more mainstream conjectures (eg ETH). I'm not sure what the difficulty of moving up to NP-hardness (or beyond) may be.


Finding number of cycles of length $k$ in a graph

When $k$ is part of the input, the problem of deciding if $G$ contains a simple cycle of length $k$ is NP-complete. For every fixed $k$, the problem can be solved in either $O(VE)$ time, or $O(V^\omega \log V)$ time. Flum and Grohe [1] showed that counting cycles and paths of length $k$ in both directed and undirected graphs, parameterized by $k$, is #W[1]-complete.

For $3 \leq k \leq 7$, one can count the $k$-cycles in $O(V^\omega)$ time, where $\omega < 2.376$ is the exponent of matrix multiplication. This is the result of Alon, Yuster and Zwick [2]. The paper also contains methods for finding simple cycles of length exactly $k$, where $k \geq 3$.

[1] Flum, Jörg, and Martin Grohe. "The parameterized complexity of counting problems." SIAM Journal on Computing 33.4 (2004): 892-922.

[2] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.


More generally, the Immerman-Szelepscényi method gives that $ALTSPACE(a(n),s(n))$ is in $NSPACE(a(n)s(n))$.  The proof idea is: Calculate the number of reachable configurations in the first alternation; from each such reachable state, calculate the number of reachable configurations in the second alternation; and iterate $a(n)$ times backtracking in the "obvious" fashion.  Each iteration uses only $s(n)$ space to store the counts of reachable configurations.

Combining this with Savitch's theorem gives the following results:

Corollary: $ALTSPACE(\log n, \log n)$ is in $SPACE((\log n)^4)$.  More generally, a language computable in polylogarithmic space with polylogarithmically many alternations is computable in deterministic polylogarithmic time.

Corollary: Similarly, a language computable in polynomial space with polynomially many alternations is in deterministic polynomial space.

I don't know any references for these $ALTSPACE$ results or whether they have been noticed before, or even for the notation.  Leonard Berman[B] used the notation "$STA$" for "Space/Time/Alternation" classes.

[B] L. Berman, "The Complexity of Logical Theories", Theoretical Computer Science 11 (1980)
71-77.


$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos here - sorry about the self-promotion!). The problem here is to select $k$ vertices (centers) so that all other vertices are at distance at most $r$ from the closest center. This generalizes $k$-Dominating Set (which corresponds to $r=1$). More strongly, the problem is $W[1]$-hard parameterized by vertex cover and $k$.

The catch with our reduction is that we need to produce an edge-weighted graph, i.e. we need the edges to have different lengths. We can replace weighted edges with paths, but then this only proves W-hardness when the problem is parameterized by feedback vertex set. Indeed, if all edges have uniform weights then the problem is FPT parameterized by vertex cover.

This example reinforces Daniel's point (which I agree with) that it would be surprising to find a problem that is W-hard by vertex cover, without having some additional input given besides the graph.


Why would one ever use an Octree over a KD-tree?

The cells in a $kD$-tree can have high aspect ratio, whereas octree cells are guaranteed to be cubical. Since this is a theory board, I'll give you the theoretical reason why high aspect ratio is a problem: it makes it impossible to use volume bounds to control the number of cells that you have to examine when solving approximate nearest neighbor queries.

In more detail: if you ask for an $\epsilon$-approximate nearest neighbor to a query point $q$, and the actual nearest neighbor is at distance $d$, you typically end up with a search that examines every data structure cell that reaches from the inside to the outside of an annulus or annular shell with inner radius $d$ and outer radius $(1+\epsilon)d$. If the cells have bounded aspect ratio, as they are in a quadtree, then there can be at most $1/\epsilon^{d-1}$ such cells, and you can prove good bounds on the time for the query. If the aspect ratio is not bounded, as in a $kD$-tree, these bounds do not apply.

$kD$-trees have a different advantage over quadtrees, in that they are guaranteed to have at most logarithmic depth, which also contributes to the time for a nearest neighbor query. But  the depth of a quadtree is at most the number of bits of precision of the input which is generally not large, and there are theoretical methods for controlling the depth to be essentially logarithmic (see the skip quadtree data structure).


Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions.  Consequently, the complexity will be $O(1)$, if you consider $\ell$ and $k$ as fixed and look at the asymptotics as $n$ increases.

Why are there only finitely many possible problem instances?  Because when $\Sigma$ and $\ell$ are fixed and $\Sigma$ is finite, there are only finitely many subsets of $\Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \cdots \cup \Sigma^{\ell}$.


Complexity of convolution in the max/plus ring

There is a more general question on mathoverflow, and I asked a similar question on CS.SE. jbapple provided a good answer. To quote:

"Necklaces, Convolutions, and X+Y", By Bremner et
al. shows a
$O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm
for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in
the nonuniform linear decision tree model.

Any improvement to this bound will shed light to a few tough open problems like sorting $X+Y$ and all pair shortest path.
If one of the functions is convex/concave, we can solve the problem in $O(n\log n)$ time. See "Speeding up Dynamic Programming", By Eppstein et al..


Decomposing Single Crossing Minor Free graphs

If I understood your statement correctly, then it is false:
In a graph of maximum degree $3$ the $4$-connected components are all single vertices (and therefore planar AND of treewidth $\leq 1$). However we can make graphs of maximum degree 3 that contain arbitrarily large cliques as minors.


A matching $M$ is called perfect for a graph $G$ when all vertices of a graph are matched in $M$.

Computing the number of perfect matchings is a well-known #P-complete problem and shown to be equivalent to computing the permanent of the biadjacency matrix of the graph. Now note that each perfect matching, by removing edges produces $2^{n}-1$ different matchings (consider each subset of edges, which is a smaller matching, we do not consider the empty set). Also, each perfect matching prohibits exactly $\binom{n}{k}$ matchings of size $k$ from being maximal but non-perfect, since they are subsets of this perfect matching. Given those kinds of restrictions, one can certainly upper bound the number of perfect matchings given the number of matchings and perhaps it is also to use additional information to do a precise calculation.

Perhaps you should take a look at the paper "Two-dimensional monomer-dimer systems are computationally intractable" (reference 5 in the wikipedia article). It seems to rely on the fact that counting matchings (all of them, see the comments) remains #P-complete for planar graphs. Interestingly enough, counting perfect matchings for planar graphs in in $P$, i.e. can be computed in polynomial time (in a deterministic way).


What is the importance of a TCS researcher in a mostly applied CS department?

I am really not qualified to give an informed answer to your question, but there are many reasons for which a theory-oriented researcher might be a good fit for a more applied environment.

The main reason that comes to mind is this: good theoretic foundations are invaluable for a thorough understanding of an application which in turn increases trust, efficiency and decreases mental effort. In general it allows work to proceed much faster, as the foundations provide a mental reference that can be easily extended or made explicit.

I'm sure there are many examples in complexity theory, where an abstract approach has led to fantastic practical improvements in concrete implementations, but the field I am the most familiar with is "theory B", in which programing language design has greatly benefited from advances in pure computing theory research.

Haskell is a particularly good example. On the theory side, we have simple core languages like system $\mathrm{F}_\omega$ which have proven to be a very useful base for the core language of the GHC compiler. The research in type inference/reconstruction and more recently, on dependent types has guided the foundations of the Haskell design, including the Hindley-Milner architecture and GADTs. Monads, of course, were introduced in the from the most abstract domain of mathematics to the computing world by Moggi, a theorist.

More pragmatically, knowledge of the theory of operational semantics turns out to be an invaluable tool for language extensions: the paper which introduces Software Transactional Memory in Haskell has explicit operational semantics for the small sub-language containing the STM constructs. This creates a reference for the implementation, and the ability to prove properties about a correct implementation, creating trust and understanding.

All this point to the fact that having a strong theory background is an important asset of every research team, including those with a strong application theme.


There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs.

Stephan Kreutzer and Ken-ichi Kawarabayashi: The directed grid theorem.    arXiv:1411.5681 [cs.DM]

EDIT (June 16, 2015):

A short version of their paper appears here:

Ken-ichi Kawarabayashi, Stephan Kreutzer. The Directed Grid Theorem. In: Rocco A. Servedio, Ronitt Rubinfeld (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing 2015. pp. 655-664


Learning Mixture of Univariate Gaussians

Sorry, but there is lots of evidence that not only is this problem a pain in the univariate case, but moreover that having few dimensions actually makes things worse.

For evidence of the difficulty, please see Proposition 15 in Section 6 ("Exponential dependence on $k$ is inevitable") and the related Figure 1 of the following paper, the follow-up to Ankur Moitra and Greg Valiant's original joint work with Adam Kalai:

  Ankur Moitra and Greg Valiant, "Settling the Polynomial Learnability of Mixtures of Gaussians", FOCS 2010.

Proposition 15 states that there exist two mixtures of $k^2$ Gaussians on the line whose $L^1$ distance is exponentially small in $k$.  Since the construction is careful and the distribution parameters are well-behaved (polynomially-sized), this dependence on $k$ is real, and thus any algorithm whose performance depends on statistical distance will run into trouble.

For evidence that few dimensions actually forms a bad regime, please see the following very recent work:

  Daniel Hsu and Sham Kakade, "Learning mixtures of spherical Gaussians: moment methods and spectral decompositions", ITCS 2013.

This work presents a spectral method for recovering spherical mixtures of Gaussians.  So far, so good: univariate Gaussians are spherical.  However, this algorithm requires the $k$ individual means to span a rank-$k$ subspace (and the performance depends on the condition number of these points, meaning you can't just perturb your univariate instance in a $k$-dimensional space and then closely recover your original Gaussians).  As such, you could view their circumvention of the Moitra-Valiant lower bound as coming from an increase in dimension (and of course by maintaining the speherical nature you find from 1-d).

The above two papers have lots of excellent discussion, techniques, nice references.  This is not my field and I can only offer a very surface intuition for what is going on.  In the univariate case, things are really crowded, so the contribution of different Gaussians is confused and it's hard to disentangle them.  In the high-dimensional case, basically everything is far apart and low density; it's hard to get crowded, and easy to pick out points of high density (which now must reside near means).

I only have one other thing to point out, and that's the connection to $k$-means.  $k$-means has a DP in the 1-d case; google tells me it's from the 40s, and while I haven't seen that reference, we can cook up a DP fairly easily:  make your table have size $n\times k$, where $n$ is the number of points, and use "optimal $k$-means cost using $j\leq k$ means and the first $m\leq n$ data points" as your subproblem, noting that each mean owns a contiguous subset of the data.  As I tried just now to adjust this to the Gaussians case, it was interesting to see how the differences between these two scenarios became acute.  First, the hard vs. soft clustering aspect means we can't just knock out contiguous subsets and claim they are owned by some Gaussian (furthermore, for univariate Gaussians of differing variances, the regions where one or the other dominates aren't just two intervals..).  Second, we have no relationship between the variances, the univariate assumption really doesn't help us there (it would seem we need more; and of course, $k$-means is like knowing a fixed (common) variance up front).

So, oh well.


Why REFL rule is primitive in HOL Light?

DEDUCT_ANTISYM_RULE only applies to propositions, while REFL applies to all terms of all types. Your suggestion only shows that every propositions is equal (equivalent) to itself, but it could not be used to show that ever number equals itself.


Techniques for proving bounds on integrality gap in LP(SDP)

This is somewhat heavy machinery for what you want, but there's been a large body of work on techniques for designing ever more refined LPs (SDPs) that get closer and closer to the desired integer program. A good reference that reviews these approaches is by Monique Laurent: A comparison of the Sherali-Adams, Lovasz-Schrijver and Laserre Relaxations for 0-1 programming.

Apart from that, I am not aware of a single good source of references: I assume you've at least perused the relevant chapters in Vijay Vazirani's book ?


Required delta between proceedings and journal versions

It depends. If you write a paper and exhaustively include all of the relevant materials, then you should submit the paper to a journal (if you think the journal you choose is more valuable then a conference on the basis of impact factor, reputation and other metrics). If you only describe part of the work, then it may be better to submit to a conference and later, when you have new/updated results, then you may consider submitting again to a journal. What constitutes a significant difference is of course highly variable and depends on your particular work. A very rough rule of thumb is that journal versions differ for at least 30% from corresponding conference versions. However, there are exceptions. And, finally, you should carefully decide the venue. Especially in TCS, a conference may be extremely valuable, in some cases even more than a journal. I do not think that the review process applied in some highly valued conference is worse than the average review process applied in journals. This is strictly dependent on the particular conference or journal, and on the reviewers an editor finds available.


Results in Theoretical CS independent of ZFC

While I am not aware of any such results, other than your own, I think you could broaden the scope somewhat and ask: what results in TCS have been proved using (any kind of) non-standard axioms. By non-standard here I mean something other than classical logic with ZF (or ZFC).

A beautiful example of the kind of work I have in mind are Alex Simpson's results on properties of programming languages using synthetic domain theory. He uses intuitionistic set theory with axioms that contradict classical logic.

Also, Alex and I used intuitionistic axioms with anti-classical continuity principles to show results about Banach-Mazur computabilty.

However, none of the mentioned examples have an "open" status, like your proofs, because we know that the non-standard axioms we used can be understood simply as working inside a model of intuitionistic mathematics, where the model can be shown to exist in ZFC. So the non-standard setup is really a way of getting things done more elegantly, and in principle they could be done in straight ZFC (although I am afraid to think about how exactly that would go).


Looking for a nice problem inside SC but not in the first two levels

I don't have a suggestion for a natural problem in $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$, but I do have a suggestion for your side question, of why finding such a problem seems difficult. I think this has something to do with the folk-idea that people can only really comprehend (or maybe are only interested in? or both?) math that is a few quantifier alternations deep. For example, the definition of limit is two quantifiers deep (for all epsilon there exists a delta...); the definition of "$L \in \mathsf{NP}$" is two quantifiers (there exists a machine such that for all inputs...), and the statement "$\mathsf{P} \neq \mathsf{NP}$" is three quantifiers deep.

With regards to $\mathsf{PH}$, this is somewhat borne out by the fact that there are lots of natural problems that are $\mathsf{NP}$-complete, many natural problems that are $\mathsf{\Sigma_2 P}$-complete, and only a few known natural problems that are $\mathsf{\Sigma_3 P}$-complete (see the compendium by Schaefer and Umans). The most natural problems known to be complete for higher levels of $\mathsf{PH}$ come from logic itself, which is less surprising since within a given logic one often has the notion of "$k$-many quantifier alternations," or at least some natural way to simulate it. These perhaps fall into the same category as "accepting problems for NTMs," which you've declared "not nice enough" for this question.

It might also be worth mentioning that the same thing happens in the world of computability, which maybe suggests that it has to do more with our understanding of alternating quantifiers and less with complexity per se. Lots of natural problems are known to be $\mathsf{\Sigma^0_1}$-complete (equivalent to the halting problem), and many natural problems are known to be complete for the second and third levels of the arithmetic hierarchy. But as you go to higher levels of the arithmetic hierarchy fewer and fewer natural problems are known to be complete for those levels. I'm not sure I know of a natural problem complete for $\mathsf{\Sigma^0_4}$, and I've never heard of a natural problem complete for $\mathsf{\Sigma^0_5}$ (though maybe there is).

With regards to polylogarithmic space bounds, I think a similar reasoning applies, but even more so. Since $\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$, even problems that are in the "first few" levels of the "$\mathsf{NL}$ hierarchy" are all in fact in $\mathsf{NL}$ (the hierarchy collapses), which is contained in log-squared space.


Can a fully homomorphic encryption be used for oblivious code execution?

Unfortunately, there is a result that theoretically forbids "oblivious code execution":
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (Im)possibility of Obfuscating Programs, ADVANCES IN CRYPTOLOGY — CRYPTO 2001.
Here are the links:

http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html
http://eprint.iacr.org/2001/069
http://www.springerlink.com/content/telalqdcx3n600uf/

The abstract reads:

Informally, an obfuscator $\cal O$ is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) $P$ and produces a new program $\cal O(P)$ that has the same functionality as $P$ yet is "unreadable" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the "unreadability" condition in obfuscation as meaning that $\cal O(P)$ is a "virtual black box," in the sense that anything one can efficiently compute given $\cal O(P)$, one could also efficiently compute given oracle access to $P$.
In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of functions $\cal F$ that are inherently unobfuscatable in the following sense: there is a predicate $\pi$ such that (a) given any program that computes a function $f$ in $\cal F$, the value $\pi(f)$ can be efficiently computed, yet (b) given oracle access to a (randomly selected) function $f$ in $\cal F$, no efficient algorithm can compute $\pi(f)$ much better than random guessing.
We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only approximately preserve the functionality, and (c) only need to work for very restricted models of computation $\rm{TC}$ $0$). We also rule out several potential applications of obfuscators, by constructing "unobfuscatable" signature schemes, encryption schemes, and pseudorandom function families.


Can one return to a TCS research job after an excursion to a non-research industry job?

Let me disagree with the other responses.

While there are clearly notable examples of people who can transition to industry and back (see other answers), going to a non-research industrial position, even for a couple years, will make it very hard to return to academia, unless you're already very famous.

The reason is not because academics look down on industry or will think you "impure," but rather that it's very hard to stay active publishing when your job requires all your work time be spent on something else.  And if you haven't published anything for a couple years, it will be nearly impossible to convince a hiring committee to choose you over people who have. (Again, this doesn't apply if you already have a Turing award, etc.)

But if you can find the time to stay active in research and publish while working in your industry position, then you can still be competitive.  It's just likely to be a losing battle, and your other job responsibilities will realistically probably end up taking priority over research on-the-side.


Regarding proper form of production rules of Context-free tree grammars

After a couple of hours of thinking I found at least proper form of grammar. Thanks to @Sylvain's commentary and link to Fisher's paper, which given me a clue.

Proper context-free tree grammar, which yield language coincides with $\{a^nb^nc^n|n>0\} $ will have simplest form:

$G=\{\Sigma,N,S,P\}$, where $\Sigma=\{a,b,c\}$, $N=\{S_t,F,A,B,C\}$, $S=\{S_t\}$, and set of production rules:

$S_t\rightarrow F(a,b,c)\\
F(x_1,x_2,x_3)\rightarrow F(A(a,x_1),B(b,x_2),C(c,x_3))$

That is it. Core idea is to wrap "stack" into subtrees of the form $A(a,x_1)$.

Thereby we receive following productions:

$S_t\Rightarrow F(a,b,c)$, $yield(F(a,b,c))=abc$
$S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))$, $yield(F(A(a,a),B(b,b),C(c,c)))=aabbcc$
$S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))\Rightarrow F(A(a,A(a,a)),B(b,B(b,b)),C(c,C(c,c)))$,
and so on.


Well, here's a possible solution:

The reduction will be from 3SAT.

Input: $m$ DNF clauses $(\varphi_1,\ldots,\varphi_m)$ over $n$ variables $(x_1,\ldots,x_n)$.

Reduction:
Create a set of items composed of two items for every variable: $x_i, \overline x_i$, corresponding to a $True$ assignment to either the variable $x_i$ or its negation, plus one auxiliary item $t$.
Let the price of all items $\{x_i,\overline x_i\}_{i=1,…,n}$ be $1$, and the price of $t$ be $1.5$.

Create two sets of consumers:

Set 1: Validity rankings: this set of consumers will encode the validity constraints on the assignments to $x_1,\ldots,x_n$. Namely, that exactly one out of every $\{x_i,\overline x_i\}$ is set to $True$ (i.e., taken by the algorithm).
For every $i=1,\ldots,n$ create four partial rankings:

$\sigma_{i1}: x_i\succ t\\
\sigma_{i2}: \overline x_i \succ t \\
\sigma_{i3}: x_i \succ \overline x_i \\
\sigma_{i4}: x_i \succ \overline x_i$

Taking $t$ can never hurt, so we assume that it's always chosen. If both $x_i$ and $\overline x_i$ are selected, we get a payoff $4$. If none of them is selected, we get a payoff of $3$. If one of them is chosen, we get a payoff of $4.5$.

Set 2: Clause rankings.
For each clause of the form $\varphi_j=\ell_{j1} \vee \ell_{i2} \vee \ell_{j3}$, we create a ranking: $\sigma_j: \ell_{j1} > \ell_{j2} > \ell_{j3}$. If $\varphi_j$ is satisfied, it means that at least one of the items corresponding to $\ell_{j1}, \ell_{j2}$, and $\ell_{j3}$ is selected, which gives an extra payoff of $1$ from ranking $\sigma_j$.

Now, the 3CNF formula is satisfiable if and only if there is a set of items that gives a payoff of $m+4.5n$.


The way I understand the difference is that ownership types constrain
the shape of the object graph, and substructural systems (like
separation logic) manage permissions to access the heap.

In the original work on ownership types, the idea is to maintain the
invariant of owners as dominators. An object $o$ is dominated by
an object $d$, if every path from the root set to $o$ contains $d$. So
$o$ is only reachable from $d$. So the system is designed so that
class declarations are parameterized by their owners, and then this
fact gives you a derived frame condition for $o$: its state cannot
change unless a method on its owner $d$ is invoked.

In contrast, substructural systems like linear types and separation
logic rely on the idea of resources. Each region of the heap is a
resource, and if you don't possess the resource you can't touch it.
This makes frame conditions very easy: they always hold.

One superficial difference (which nevertheless confused me for a long
time) was that ownership types were types, and separation logic was a
program logic. Luckily, while ownership types were born in a
type-theoretic setting, people have applied these ideas to program
logics as well.

The two main pieces of theoretical work I know on this are Kassios's
work on dynamic frames, which Bannerjee and Naumann (and their
students) systematically exploited in their work on regional logic.

As I understand it, their basic approach is to take Hoare logic, and
then:

Add a new type of region variables, which you use to associate objects and regions.
Add an effect system to Hoare logic to track the regions reads and writes touch.
Use the effects to determine if an assertion is frame-respecting or not.
If it is, you can frame it, and if it isn't, you can't.

Each approach has benefits and weaknesses.

Ownership makes frame properties significantly less convenient to
use than in substructural approaches, since you have to compute frame
conditions.
On the other hand, algorithms on DAGs support prettier inductive
proofs in an ownership style, since you can decouple the footprint
from the pointer structure. In a separation-style spec, the natural
thing is to give an inductive invariant on a spanning tree.  But if
the spanning tree the algorithm computes is ever different than the
one your invariant has, you're in for a world of hurt.

My general sense is that separation is easier to use than ownership,
since we need frame properties for nearly every command in an
imperative program. (Dave Naumann argues that region logic is more amenable to automation, since the assertion logic remains plain old FOL, and so
you can use off-the-shelf theorem provers and SMT solvers.)

EDIT: I just found the following paper by Matt Parkinson and Alex Summers, The Relationship between Separation Logic and Implicit Dynamic Frames, where they claim to give a logic unifying the two methods.


There is hardly any natural problem which is believed to be in P/poly but not in P. The artificial examples can be adapted to answer your question.

Assume $E \neq NE$, then there is a unary language L in NP which is not in P -- unary means that all the strings in the language have the form $1^n$ for some n.

Then define L' to be the set of all strings x such that $1^{length(x)}$ is in L. This is in NP, it is in P/poly, and it is not in average polynomial time


Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

Your question is related to how to represent the geometric intersection objects. Pairwise comparisons can get a geometric intersection graph, however, the problem is that two objects are possibly not close to each other in this intersection graph, even originally their geometric distance is very short. So it is easy to find counterexamples for the specific question you asked: whether this implies that there exists a nontrivial point of intersection of all $n$ polytopes.

Given a geometric intersection graph, deciding which graph class it belongs to, the so-called recognition problem is not easy: Shaefer [1] proved that for intersection graphs of convex sets, the recognition problem is  $\exists \mathbb{R}$-complete(It lies between NP and PSPACE).

[1] M. Schaefer. Complexity of some geometric and topological problems. In Proc. 17th Int. Symp. Graph Drawing (GD), pages 334–344, 2009.


Application of weak determinantal identities to GCT?

Determinantal identities can be useful, but perhaps not exactly in the way you think. As far as I know, however, the identities do not all "reduce to" the symmetries of the determinant (except for the fact that the symmetries of the determinant characterize it). Whenever one has some determinantal identities, they can often be massaged into getting equations for the orbit closure of the determinant - the closure of the set of homogeneous polynomials that are linear projections of the determinant. The family of these orbit closures (one for each size $n$) is a natural geometric object capturing the complexity class $\mathsf{VP}_{s}$.

Some work in this direction by Landsberg & Ressayre was reported here (Section 2.2), but I don't know if the actual paper has appeared yet.

A somewhat related paper, which gives some equations that vanish on the determinant orbit closure is:

  Landsberg, Manivel, & Ressayre. Hypersurfaces with degenerate duals and the Geometric Complexity Theory program. Comentarii Mathematici Helvetici 88(2):469-484, 2013. (arXiv version)

That paper, as with Mignon-Ressayre, uses the rank of the Hessian, rather than explicitly from a determinantal identity. However, the rank of the Hessian can be seen as closely related to Segre's identity $\det_{n^2}(Hess(\det_n(A)) = (-1)^{\binom{n+1}{2}}(n-1)\det(A)^{n(n-2)}$, which is the identity reportedly used above.

You might also be interested in the following paper, which shows that any reduction from perm to det which respects the symmetries of perm (see the paper for precise definitions) must have exponential blow-up:

  J. M. Landsberg and Nicolas Ressayre. Permanent v. determinant: an exponential lower bound assumingsymmetry and a potential path towards Valiant's conjecture. Differential Geom. Appl., in press,
   2017. (arXiv version)


This is supervised learning with a vector-valued output, i.e. learning a vector to vector mapping.  There's a large literature on this in the neural network community. One application is generating control signals for a physical device (e.g. pointing a camera based on visual input).  Here's a typical reference:

Suh, I.H. and Kim, T.W. Fuzzy membership function based neural networks with applications to the visual servoing of robot manipulators.  IEEE Transactions on Fuzzy Systems, 2(3):203-220, 1994.

From another angle, this can be viewed as multitask learning, a currently popular area in machine learning.   If one knows more about constraints among the output values, then it could usefully be viewed as a structured prediction problem, also recently popular.


What's the relation between the dominating set and vertex cover?

Since there is no single minimal dominating set nor minimal vertex cover, I interpret your question as:

  There exist one minimal dominating set $D$ and one minimal vertex cover $C$ such that $D \subseteq C$.

No.

If by any graph you also consider non-connected graphs, then you have a trivial counterexample in $G=(V,E)$ with $V\neq\emptyset$ and $E=\emptyset$,
i.e. at least one vertex and no edges.
The minimal vertex cover is $C=\emptyset$, since there are no edges to cover,
but the only dominating set is $D=V$, and clearly $D\not\subseteq C$.

Even if you restrict it to connected graphs, the answer is still no. Consider the cycle graph $G=(V,E)$ of six vertexes $V=\{a,b,c,d,e,f\}$ and $E=\{(a,b), (b,c), (c,d), (d,e),(e,f),(a,f)\}$.

The vertex cover sets of minimal size have three elements, obtained by skipping one vertex in two: $\{a,c,e\}$ and $\{b,d,f\}$.
The dominating sets of minimal size are obtained with opposing vertexes, $\{a,d\}$, $\{b,e\}$, and $\{c,f\}$.

None of the dominating sets is a subset of any vertex cover set.


Partition graph into complete disjoint subgraphs while maximising sum of edge weights

In addition to Correlation Clustering, this is known as Clique Partitioning or Weighted Cluster Editing, see e.g.

M. Grötschel and Y. Wakabayashi, A cutting plane algorithm for a clustering problem, or
Sebastian Böcker, Sebastian Briesemeister, and Gunnar W. Klau, Exact Algorithms for Cluster Editing: Evaluation and Experiments.


Are quasi-polynomial sized circuits for 3-SAT trivial?

If what you are studying worked out, it definitely would not be trivial.

It would imply that 3SAT has (non-uniform) circuits of size $n^{O(\log n)}$. Then, every language in $NP$ (and the polynomial time hierarchy) would have quasi-polynomial (i.e., $n^{O(\log^c n)}$) size circuits.

Even if it took $2^{2^n}$ preprocessing time to produce a data structure of size only $2^{O(\log^2 n)}$ which could then correctly answer arbitrary 3SAT queries of size $n$ in $2^{O(\log^2 n)}$ randomized time with high probability, 3SAT would have quasi-polynomial size circuits, using the known translation of randomized algorithms to circuits. This would not improve the known algorithm time bounds because of the preprocessing, but it would still be extremely interesting as a non-uniform result.

What do you mean by "to within an error that can be adjusted to an arbitrary amount"? Is the algorithm randomized?


Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

Yes, in some sense at least.  See the following paper:

Megiddo, Nimrod. "On finding primal-and dual-optimal bases." ORSA Journal on Computing 3.1 (1991): 63-65. PDF available here.

It shows that:

  if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and
  the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for
  the general linear programming problem.

(Note the details of the result though: it is about finding an optimal basis and deals with strongly polynomial-time algorithms.)


Is there any book on the philosophical implications of Theoretical Computer Science?

Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" https://arxiv.org/abs/1108.1791


What is the recommended software for drawing data structures such as graphs and trees?

The MO thread Per links to is pretty good, and this thread on tex.SE is also handy. The main tools that I've used:

TIkz/PGF
Ipe
Inkscape/Illustrator

I know that Mac folks swear by Omnigraffle, but I have zero experience with it myself. The main criteria for me are:

Generating PDF
Integrating LaTeX (with source styles for bonus points)
Being able to do color/shading etc easily. (Ipe 7 fails on that count)


Perhaps this is a possible weird reduction from 3SAT. The idea is to use the set $S$ with restricted degree to simulate a true/false assignment to the variables using their odd/even distance from the clauses that contain them.

Given a 3CNF formula with $n$ variables; let $c$ be the maximum among the number of occurrences of the variables in the clauses, and let $k = c+2$.

Build $G$ in the following way:

add a source node $s^T$ linked with $k+1$ nodes of degree 1 (a "fan");
for every variable $x_i$ add a triangle made of three nodes $\{x_i^S,x_i^+,x_i^-\}$ and edges $(x_i^S,x_i^+)$ (left side), $(x_i^S,x_i^-)$ (base), $(x_i^+,x_i^-)$ (right side);
add edges from $s^T$ to every $x_i^S$;
add $k-2$ fan nodes to $x_i^S$;
for every clause $C_j$ add a node $C_j^T$ linked with $k+1$ fan nodes of degree 1;
if positive variable $x_k \in C_j$ then add a direct link from $C_j^T$ to $x_k^-$; if negative variable $\bar{x}_k \in C_j$ then add a link from $C^T_j$ to $x_k^-$ with an intermediate node $z_{jk}$

The resulting graph $G$ has a connected, bipartite subgraph ($S\cup T=V$) in which the nodes of only one of the two set (suppose $S$) has max dregree $k$ if and only if the original 3CNF formula is satisfiable.

First of all the fan of the source node $s^T$ forces it to be in the unrestricted set $T$; and the fan of every clause $C_j^T$ forces it to be in $T$, too. Furthermore all nodes $x_i^S$ connected to $s^T$ are forced in the set $S$.

Now, for every variable, only one among $x_i^+, x_i^-$ can be put in $T$ (traverse the base of the triangle or pass through its vertice) because $x_i^S$ is in $S$ and its $k-2$ fan nodes must be connected, so we must drop edge $(x_i^S,x_i^+)$ or edge $(x_i^S,x_i^-)$). Suppose we choose $x_i^+$, and drop the edge $(x_i^S,x_i^-)$; hence $x_i^-$ falls in $S$, and we can use the edges from it
to safely connect (satisfy) all the clauses (all because $k=c+2$) that contain $x_i$ and are directly connected to $x_i^-$, but not the clauses that are connected through $z_{ij}$ (which must be in $T$) because in that case $C_j^T$ would fall in $S$. Similarly, if we choose to put $x_i^-$ in $T$ then we can conect all the clauses that contain $\bar{x}_i$ (through $z_{ij}$ which now is in $S$).

At the end the graph $G$ is connected only if every clause contains at least one variable made true by the assignment.


Is there a survey of the field of quantum automata?

You can check the recent survey by Ambainis and Yakaryilmaz: Automata and Quantum Computing. It is comprehensive and points the essential literature with some open questions.

Moreover, here is a list of papers published on quantum automata until 2015.


How much computational power fits into a cubic centimeter?

The statement I made wasn't particularly well written. I was referring to a combination of the Margolus-Levitin theorem (which gives the minimum time to move between two orthogonal states, and hence a lower bound on the time required to perform a gate) and the Schwarzschild radius (which gives the minimum radius of a system of some fixed energy before it forms a black hole). Combining the two of these leads to an upper bound on the number of gates which can be performed in a fixed region of spacetime. You can think of this as the maximum number of gates per unit time which can be performed.

The idea to combine the two theorems comes from Seth Lloyd, who uses such an approach to show limits on the computational power of the universe(link). He also has another paper where he looks at the maximum performance that can be achieved by a 1kg computer of volume 1liter  (something he calls the ultimate laptop and which is almost exactly your question). See arXiv. He obtains a limit of $10^{51}$ operations per second on $10^{31}$ bits.
Due to the finite age of the universe and the finite speed of light, when combined with Lloyd's results, you obtain a constant upper bound on preprocessing.


Examples of Universe inconsistency in normal use of dependent types

This is a hard question to answer, in part because it's unclear what it means to get something "by accident". Regularly, though, people run into the Universe Inconsistency error of Coq, as some quick googling will show (e.g. here). This certainly sometimes happens by accident, sometimes in the attempt at showing inconsistencies or testing the limits of the prover.

One of the big sources of universe inconsistencies unsurprisingly comes from trying to formalize category theory in Coq, as is mentioned in this article by Gross, Chlipala and Spivak.

In most cases, it's hard to tell whether the inconsistency comes from an actually inconsistent statement, or just a limitation of the proof checker, which sometimes has counter-intuitive restrictions on universes, particularly in the allowed parameters for inductive types. This is actually a somewhat tricky subject (see the official definition and Chlipala's more accessible discussion).


This is treated extensively in the statistics literature, under the topic of regression.  Two standard references here are Wasserman's book "all of nonparametric statistics" and Tsybakov's "introduction to nonparametric estimation".  I'll talk briefly about some of the standard stuff, and try to give pointers outside of statistics (this is a common topic and different fields have different cultures: prove different kinds of theorems, make different assumptions).

(Kernel regressors, sometimes called the Nadaraya-Watson Estimator.)  Here you write the function at any point as a weighted combination of nearby values. More concretely,
since this is in the statistics literature, you typically suppose you have some examples $((x_i,f(x_i)))_{i=1}^n$ drawn from some distribution,
and fix some kernel $K$ (can think of this as a gaussian, but zero mean is what matters most), and write
$$
\hat f(x) := \sum_i f(x_i) \left(\frac{ K(c_n(x-x_i)) }{ \sum_j K(c_n(x-x_j))}\right),
$$
where $c_n\to\infty$ (you are more sensitive to small distances as $n$ increases).
The guarantee is that, as $n\to\infty$, a probilistic criterion of distortion
(expectation of sup-norm, high probability, whatever) goes to zero.
(It hardly matters what $K$ looks like---it matters more how you choose $c_n$.)
(Basis methods.)  A similar thing is to choose some family of "basis functions", things like Wavelets or piecewise linear functions, but really anything that forms a (possibly overcomplete) basis for the vector space $L^2$, and determine a weighted linear combination of scaled and translated elements.
The techniques here differ drastically from (1.); rather than plopping down basis functions centered at data points, you carefully compute the weight and location of each in order to minimize some distortion criterion.  (Typically, their quantity is fixed a priori.) One approach is "basis pursuit", where you greedily add in new functions while trying to minimize some approximation error between $\hat f$ and $f$.  To get a sense of the diversity of approaches here, a neat paper is Rahimi & Recht's "uniform approximation of functions with random bases".  Perhaps I should say that the grand-daddy of all of these is the Fourier expansion; there's a lot of good material on this in Mallat's book on Wavelets.
(Tree methods.)  Another way is to look at a function as a tree; at each level, you are working with some partition of the domain, and return, for instance, the average point.  (Each pruning of the tree also gives a partition.)  In the limit, the fineness of this partition will no longer discretize the function, and you have reconstructed it exactly.  How best to choose this partition is a tough problem. (You can google this under "regression tree".)
(Polynomial methods; see also splines and other interpolating techniques.)  By Taylor's theorem, you know that you can get arbitrarily close to well behaved functions.  This may seem like a very basic approach (i.e., just use the Lagrange interpolating polynomial), but where things get interesting is in deciding which points to interpolate.  This was investigated extensively in the context of numerical integration; you can find some amazing math under the topics of "clenshaw-curtis quadrature" and "gaussian quadrature".  I'm throwing this in here because the types of assumptions and guarantees here are so drastically different than what appears above.  I like this field but these methods suffer really badly from the curse of dimension, at least I think this is why they are less discussed than they used to be (if you do numeric integration with mathematica, I think it does quadrature for univariate domains, but sampling techniques for multivariate domains).

Considering various restrictions to your function class, you can instantiate the above to get all sorts of other widely-used scenarios.  For instance, with boolean valued functions, thresholding (1.) will look a lot like a nearest-neighbor estimator, or an SVM with some local kernel (gaussian).  A lot of the above stuff suffers from curse of dimension (bounds exhibit exponential dependence on the dimension).  In machine learning you get around this either by explicitly constraining your class to some family (i.e., "parametric methods), or by an implicit constraint, usually something relating the quality of the approximants to the target function complexity (i.e., an analog of the weak learning assumption in boosting).

By the way, my favorite theorem related to neural net approximation  is Kolmogorov's superposition theorem (from 1957!).  It says that any multivariate continuous function $f:\mathbb{R}^d \to \mathbb{R}$ has the form
$$
f(x) = \sum_{j=0}^{2d}h_j\left(\sum_{i=1}^d g_{j,i}(x_i)\right),
$$
where each $g_{j,i} : \mathbb{R}\to\mathbb{R}$ and $h_j:\mathbb{R}\to\mathbb{R}$ is (univariate) continuous.  Note that unlike neural nets, the $g$'s and $h$'s may all differ.  But even so, given that there are only $\Theta(d^2)$ functions floating around, I find this totally amazing.

(You only asked about function classes, but I figured you'd be interested in methods as well.. if not.. oops)


What are practically computable properties of Labelled Transition Systems?

The formulas of Hennessy-Milner logic are very easy to prove about labelled transition systems. However, this logic is inexpressive enough (there is no way to state properties of infinite paths) that you will probably wish to consider some extension to it, such as linear temporal logic. LTL has a decidable, but PSPACE-complete, problem.

The SPIN model checker is a widely-used tool for model-checking LTL properties.


Let $f(G)=1$ iff $G$ is not $(k-1)$-colorable. Then $f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs, just like the $k$-clique function does. So, the lower bounds for clique hold also for $f$.


Example of something that’s different for generic and random oracles?

P = UP with a generic (assuming P = PSPACE) but they are separate relative to a random oracle.

In the other direction P = Promise-BPP relative to a random but separate relative to a generic. Can't think of a non-promise class off the top of my head.

I can track down some references if you need.

Update: If you want a non-promise version, $P^{NP} = S^p_2$ with a random oracle (because $S^p_2 \subseteq ZPP^{NP}$) but they separate with a generic oracle (example in my paper with Yamakami).


Sure.  Write routines that compute each of Godel's primitive recursive functions, and write a routine for an unbounded search operator.  The set of functions you can compute this way is equivalent to the set of functions Turing machines can compute.  More information here.

The downside is that any input to your universal program would need to be framed in terms of those simple operations.  Of course, that is what compilers are for.


SETH says that for all $\delta < 1$ there is a $k$ such that $k$-SAT requires $2^{\delta n}$ time to be solved in the worst-case. The computational model is generally taken to be the random-access machine or pointer machine model, which allows for $O(\log N)$ time access to a storage of $N$ items, and is generally assumed to also be probabilistic with bounded error.

As far as I know, it is open whether $2^{\delta n}$ time algorithms on such a model can be translated into two-tape Turing machines running in $2^{\delta n} \cdot poly(n)$ time. Nevertheless, proving that such a translation is not possible would separate multitape Turing machines from random access machines, which would have several very intriguing implications. For one, it would prove that SAT is not solvable in quasi-linear time on multitape Turing machines (because, if SAT could be solved with such multitape machines, then random-access machines can be efficiently simulated with multitape Turing machines). Note that many computational primitives (such as sorting, circuit evaluation, simple dynamic programming) can be implemented efficiently on multitape Turing machines. One relevant reference for these issues is Regan, "On the Difference Between Turing Machine Time and Random-Access Machine Time."

To address your specific questions: no, a multitape Turing machine is not automatically implied here, but yes, such an "algorithm" for SAT (under the usual random-access model) would break SETH.


If you work on a university campus, there's likely a large building nearby full of study carrels and magazine racks called a "LIE-BURY".  Deep in the bowels of such buildings, one can often find images of old research papers inscribed onto thin sheets of cellulose fiber extracted from wood and cotton, called "paper", and then bound into larger brick-sized objects called "books".  (At least according to Wikipedia, this is the reason we call our research reports "papers".  Who knew?!)

Surprisingly, despite the crudeness of the technology that produced them, these so-called "books" are often significantly easier to read than their more modern electronic counterparts.

One serious disadvantage of this approach is that one must actually walk all the way across campus, but we all must occasionally suffer for our art.


I think $K_4$-minor-free graphs have at most $2n - 3$ edges for $n \geq 2$, and this is tight. Here's one way of looking at it.

It is well-known that the $K_4$-minor-free graphs are exactly the graphs of treewidth at most two, see http://en.wikipedia.org/wiki/Forbidden_graph_characterization . Standard theory on treewidth tells us that a graph of treewidth at most 2 is 2-degenerate (see http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29 ), which means that all induced subgraphs have a vertex of degree at most two. So to count the number of edges in a $K_4$-minor-free graph, we can do the following: we find a vertex of degree at most two, and delete it. We remove one vertex, and at most two edges. What we're left with is still $K_4$-minor-free (since minor-freeness is preserved when deleting vertices), so if the graph is not yet empty then we know it is 2-degenerate, and has another vertex of degree at most two. If we keep removing vertices of degree at most two then we delete $n$ vertices until the graph is empty, and for each removed vertex we delete at most two edges. Hence the number of edges is at most $2n$.

Now observe that when removing the second-to-last vertex, there are only two vertices left so there can be only one edge that is removed in that step. Similarly, when we've removed all but one of the vertices then there can be no edges left, so in the last step we don't remove any edges. This shows that the number of edges is at most $2n - 3$ because we save 1 in the second-to-last step, and 2 in the last step.

To see that this is tight, start with a graph on two vertices and one edge. Now repeatedly select two adjacent vertices, and add a new vertex with edges to the selected two. The constructed graph will have treewidth two (since it is a 2-tree, see http://en.wikipedia.org/wiki/K-tree ) and will therefore be $K_4$-minor-free, and the number of edges you build in this way is $2n-3$.


Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?

For total UP the answer is yes, because the question "Is the i'th bit of the solution 1?" is in $NP \cap co-NP$.


Producing colouring of maximal planar graphs G from colouring of dual of G

The simple but useless answer is that I don't know of such a scheme. However, more to the point: proving that such a scheme worked would be tantamount to proving the 4-color theorem. It is very easy to prove that duals of maximal planar graphs have 4-colorings (in fact 3-colorings except for $K_4$ by Brooks' theorem), so if you could prove that a 3- or 4-coloring of the dual graph could always be converted into a 4-coloring of the primal graph then you would have also proved that a 4-coloring of the primal graph exists.

Perhaps there are more, but the only widely-accepted alternative proofs of the 4-color theorem reported by the Wikipedia article are the ones by Robertson, Sanders, Seymour, and Thomas (in connection with a faster algorithmic version of the theory) and Werner and Gonthier (in connection with a formalized proof in Coq). I think both are in roughly the same style of Appel and Haken, of proving that a reducible configuration exists, rather than using dual colorings.


Are resource savings for the evaluation of $k$ dependent instances in parallel possible?

Assume $C'(X)$ is a logically equivalent but minimized version of $C(X)$. Then $C'(X) \notin  SIZE(poly(X))$, unless the polynomial hierarchy collapses.

To see this, assume $C'(X) \in SIZE(poly(X))$, i.e. $C'(X) \in P/poly$. As noted in the original post, this would imply $NP \in P/poly$, but then the claim follows from Karp-Lipton.

Thus, even the existence of a poly-sized circuit equvialent to $C(X)$ is unlikely. Or, in turn, a generalization of direct product theorems to the dependent case appears plausible under complexity theoretic assumptions.


"is Zero knowledge Proof same as commitment schemes?"

No, although if one makes soundness be only computational

(i.e., arguments rather than proofs) ,  then existence of such zero-knowledge protocols

is equivalent to existence of instance-dependent commitment schemes.

"How can prover A prove that he is in the possession of some value 'X'

without disclosing 'X' to B. 'X' could be A's last name or A's telephone number"

How would the verifier check validity of the claimed 'X' if A did disclose 'X' to B?

Your hashing remark suggests that what you're thinking

about is actually proving knowledge of a preimage:

i.e., both parties know 'Y', and A is proving knowledge of a 'W' such that  H(W) = Y .


Proving properties about a compilation from one problem into another

Let's assume that the weights are integers (for both A and B), and that m must be onto.  You could also assume that m must be a bijection (i.e., one-to-one and onto) and it would make no difference; the proposition you present is still false.

The reason is that all weighted digraphs (I'm assuming that's what you mean, not that it matters) are isomorphic to each other.

Let's prove:  There exists a mapping m : B -> A s.t. for all instances I_B of B, the solution S(m(I_B)) = S(I_B).

To show this, we will construct this mapping m.  Further, we'll show that m is a bijection.

We will divide the set of all digraphs into partitions.  Each partition will contain all graphs of a particular number of nodes N, and a particular solution structure that makes all graphs in the partition isomorphic to each other, in the sense that all solutions paths are the same.  (We index each node in an N-node graph from 1 to N, and consider two solution paths to be identical iff they contain exactly the same indexes in the exact same order and both have N nodes.)

Observe that each such partition has a countably infinite cardinality, due to the fact that there are infinitely many weight possibilities for each edge.  (Proof omitted.)

Thus, to construct m, all we must do is map every member of a partition (in B) to another member of the corresponding partition (in A).  Obviously, B contains extra graphs, but both have all partitions with the same cardinality as the set of natural numbers.

Now, we have that m is a bijection because every element in each partition of B maps to a unique element in the corresponding partition of A...and every element of every partition of B can be mapped to for each partition of A.


Lexicographic perturbation for euclidean shortest path instances?

I think you're unlikely to get a good answer, because this is tied up in difficult and unsolved algebraic problems. The issue is that Euclidean path lengths (for points with integer coordinates) can be expressed as sums of square roots, but we don't know how small the difference between two distinct sums of square roots can be. Because of this, we also don't know how far apart the shortest path length and second-shortest distinct path length between a given pair of vertices can be, and therefore we don't know how small we have to make a perturbation to prevent it from changing the shortest path to a path that wasn't originally shortest.

For the same reason, shortest paths in Euclidean graphs are not really known to be solvable in polynomial time, in models of computation that take into account the bit complexity of the inputs, even though Dijkstra is polynomial in a model of computation allowing constant-time real-number arithmetic. So asking for a polynomial time algorithm for a more complicated variant of the problem in which the bit complexity is unavoidable seems likely to have a negative answer.


Regular languages from category-theoretical point of view

There has been a lot done applying category theory to regular languages and automata. One starting point is the recent papers:

Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages
by Bart Jacobs
A Bialgebraic Approach to Automata and Formal Language Theory by James Worthington.

In the first of these papers, the structure of regular expressions is treated algebraically and the languages generated are dealt with coalgebraically. These two views are integrated in a bialgebraic setting.  A bialgebra is an algebra-coalgebra pair with a suitable distributive law capturing the interplay between the syntactic terms (the regular expressions) and the computational behaviour (languages generated). The basis of this paper is algebra and coalgebra, as treated in computer science under the umbrellas of universal algebra and coalgebra, rather than what one sees in mathematics (groups etc).

The second paper uses techniques that come from the more traditional mathematical treatment of algebra (modules etc) and coalgebra, but I'm afraid that I don't know the details.

Neither treats Kleene star as an adjunction, as far as I can tell.

More generally, there is a lot of work applying category theory to automata instead of regular expressions. A sample of this work includes:

Bloom S.L.; Sabadini N.; Walters R.F.C. Matrices, Machines and Behaviors. Applied Categorical Structures, Volume 4, Number 4, December 1996 , pp. 343-360(18)
Michael A. Arbib, Ernest G. Manes: A categorist's view of automata and systems. Category Theory Applied to Computation and Control 1974: 51-64
M.A. Arbib and E.G. Manes. Adjoint machines, state-behaviour machines, and
duality. Journal of Pure and Applied Algebra, 6:313-344, 1975.
M.A. Arbib and E.G. Manes. Machines in a category. Journal of Pure and Applied
Algebra, 19:9-20, 1980.
Jirí Adámek and Vera Trnková's book  Automata and Algebras in Categories, as pointed out in a comment.

Finally, there's the work on iteration theories, Iteration theories: the equational logic of iterative processes by Stephen L. Bloom and Zoltán Ésik, which focusses on iteration (e.g., Kleene star), but from a more general perspective, where regular languages are just one thing that falls under the theory.


Efficiently computable variants of Kolmogorov complexity

Gzip.  Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. Clustering by Compression


Graph labelling where vertices with a common neighbour get different labels

`Special labelling' is not exactly $L(0,1)$-coloring, but is very close. In $L(0,1)$-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do not allow this. Special labelling is already studied in the literature under the name injective coloring.

An injective colouring of a graph $G$ is a colouring $c$ of the vertices
of $G$ that assigns different colours to any pair of vertices that have a
common neighbour.

There are a number of papers on injective coloring. The main graph classes studied are planar graphs [1,2,3], chordal graphs [4], regular graphs [5], and sparse graphs [6]
References
[1] Bu, Yuehua; Qi, Chentao; Zhu, Junlei; Xu, Ting, Injective coloring of planar graphs,  ZBL07300884.
[2] Lužar, Borut; Škrekovski, Riste; Tancer, Martin, Injective colorings of planar graphs with few colors, Discrete Math. 309, No. 18, 5636-5649 (2009). ZBL1209.05093.
[3] Bu, Yuehua; Wang, Chao; Yang, Sheng, List injective coloring of planar graphs.,  ZBL06986943.
[4] Hell, Pavol; Raspaud, André; Stacho, Juraj, On injective colourings of chordal graphs, Laber, Eduardo Sany (ed.) et al., LATIN 2008 Berlin: Springer (ISBN 978-3-540-78772-3/pbk). LNCS 4957, 520-530 (2008). ZBL1136.68463.
[5] Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique, On the injective chromatic number of graphs, Discrete Math. 256, No. 1-2, 179-192 (2002). ZBL1007.05046.
[6] Cranston, Daniel W.; Kim, Seog-Jin; Yu, Gexin, Injective colorings of sparse graphs, Discrete Math. 310, No. 21, 2965-2973 (2010). ZBL1209.05075.


Approaching Number Theory conjectures through Graph Theory

There are some results proven by graph theory, however I am not sure whether those results are good examples you want. Because number theory has offsprings by cross-breeding with some other fields, like arithmetic combinatorics and additive number theory

In number theory, Szemerédi's theorem that was formerly the Erdős–Turán conjecture is a good example proven by graph theory. (Although it is not necessary to prove by graph theory. Other proofs are using different approaches, e.g., Hillel Furstenberg uses ergodic theory, and Timothy Gowers uses both Fourier analysis and combinatorics)

And this result leads to Green–Tao theorem.


Complexity of transforming a balanced bipartite graph into regular graph?

Transform G into a weighted flow network N: connect the source s to all nodes in A by arcs of capacity n/2 and cost 0, connect all nodes in B to the sink t by arcs of capacity n/2 and cost 0, and connect each A-node u to each B-node v by an arc of capacity 1, with cost -1 if (u,v) is in G and 1 otherwise.

The maximum flow in N is n^2/2. Its cost can be written as -|E|+d, for some d >= 0. This d is the minimum edit cost of transforming G into a balanced n/2-regular bipartite graph with partition A,B.


The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis

Here is a philosophical answer that may entertain you.

Gödel's incompleteness theorems are about the formal system of Peano arithmetic. As such they say nothing about models of computation, at least not without some amount of interpretation.

Peano arithmetic easily shows existence of non-computable functions. For example, being a  classical theory expressive enough to talk about Turing machines, it shows the particular instance of excluded middle which says that every Turing machine halts or runs forever. Nevertheless, from the work of Gödel an important notion of computability arose, namely that of a (primitive) recursive function. So it is not the theorems themselves that connect to computability, but rather the method of proof which establishes them.

The gist of the incompleteness theorems can be expressed in an abstract form using provability logic, which is a kind of modal logic. This gives the incompleteness theorems a wide range of applicability well beyond Peano arithmetic and computability. As soon as certain fixed-point principles are satisfied, incompleteness kicks in. These fixed-point principles are satisfied by traditional computability theory, which therefore falls victim to incompleteness, by which I mean existence of inseparable c.e. sets. Because the provable and refutable sentences of Peano arithmetic form inseparable c.e. sets, the traditional Gödel's incompleteness theorems can be seen as a corollary to incompleteness phenomena in computability. (I am being philosophically vague and your head will hurt if you try to understand me as a mathematician.)

I suppose we can take two stands on how all this relates to the informal notion of effectivity ("stuff that can actually be computed"):

For all we know, we are just a rather large finite automaton, capable of contemplating fictional super-heroes called "Turing machines" that are able to calculate with unbounded numbers (gasp!). If this is the case, Gödel was just a very good story-teller. How his stories translate to effectivity is then a matter of some (necessarily inaccurate) application of imagination to reality.
Because incompleteness phenomena arise naturally in many contexts, and certainly in all reasonable notions of computability, we conclude that the same has to be the case for effectivity. For example, suppose we could send Turing machines into black holes to compute a la Joel Hamkin's infinite-time Turing machines. This gives us immense computational power in which the halting oracle is a kindergarten toy. But still, the model satisfies the basic conditions that allow us to show the existence of inserparable sets. And therefore once again, computation is not all-powerful and incompleteness is a fact of life.


Ordering of a DAG minimizing some definition of cost

This problem is NP-complete, as the following reduces to it:
https://cstheory.stackexchange.com/a/1936/419

The sketch of the reduction is as follows.
From a set of tasks $T$ with $n$ tasks and some costs (not to be confused with your cost function!), we will make a DAG that has $N$ indegree 0 vertices (sources), and $N$ outdegree 0 vertices (sinks), where $N$ is some big ($poly(n)$ size) number to be specified later.
The DAG will also have an indegree $N$ vertex that has to come right after the sinks, and, similarly, an outdegree $N$ vertex that has to come right before the sources.
For each task, we have a vertex that must be between the indegree $N$ vertex and the outdegree $N$ vertex by adding an edges from and to them, respectively.
This achieves that the task-vertices are not mixed with the sources and sinks.

Finally, for every task $t$ with a positive cost $c(t)$ we add $nc(t)$ edges from some sources, and for every task $t$ with a negative cost $c(t)$ we add $nc(t)$ edges to some sinks.
This achieves that the edges between the tasks won't matter, only the costs will determine the thickness cost that you've defined.

I don't know anything about approximation and heuristics.


Honest Majority unconditional coinflipping without private channels

What you are describing is called the common coin problem and has been introduced in [1]. One way to do this is to elect a leader and then let that leader flip a coin, for example, by using the lightest bin protocol[2].

Intuitively speaking, this works as follows:
We have $n$ processes (=parties) and choose $m=n/\log n$ bins.

In every round, every participating process chooses one of these $m$ bins uniformly at random and broadcasts this choice.
The bad processes get to choose after observing the choices of the good processes.
So at the end of a round every process knows exactly which process chose which bin. All processes that chose the lightest bin (i.e. the one with the fewest members) continue to the next round, while all others stop participating.

The trick is to keep the initial ratio of good processes to bad processes. How can the adversary try to prevent this? Clearly, the adversary's strategy is to make many bad processes survive until the next round, i.e., many bad processes are in the lightest bin. But since the good processes will be distributed almost uniformly among the bins, the adversary cannot place too many bad processes into the lightest bin, otherwise it will no longer be the lightest! (Once you have reached a constant number of participants you switch to $m=2$ bins.)

This protocol elects a good process as the leader with constant probability as long as a majority of processes is good, i.e., you will get an unbiased common coin with constant probability.

[1]: M. Ben-Or and N. Linial. “Collective coin flipping”.
In Advances in Computing Research, S. Micali, ed.,
vol. 5: Randomness and Computation, JAI Press,
Greenwich, CT, 1989, 91–115.

[2] Uriel Feige: Noncryptographic Selection Protocols. FOCS 1999: 142-153


Evidence for "an":

Ajtai, Miklós, János Komlós, and Endre Szemerédi. "An O(n log n) sorting network." Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983.
Asadpour, Arash, et al. "An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem." SODA. Vol. 10. 2010.
Bracha, Gabriel. "An O(log n) expected rounds randomized Byzantine generals protocol." Journal of the ACM (JACM) 34.4 (1987): 910-920.
Hwang, F. K. "An O(n log n) algorithm for suboptimal rectilinear Steiner trees." Circuits and Systems, IEEE Transactions on 26.1 (1979): 75-77.
Tarjan, Robert E., and Christopher J. Van Wyk. "An O(n log log n)-time algorithm for triangulating a simple polygon." SIAM Journal on Computing 17.1 (1988): 143-178.
Yao, Andrew Chi-Chih. "An O (|E| log log|V|) algorithm for finding minimum spanning trees." Information Processing Letters 4.1 (1975): 21-23.

Of course, these examples alone merely suggest that "an" is acceptable. This list does not show that "an" is necessarily standard or preferred nor does it show that "a" is unacceptable.


One-Way Functions vs. perfectly binding commitments

In a recent work with Rafael Pass, it is shown that without those extra complexity assumptions of Barak-Ong-Vadhan, noninteractive commitments can not be based on one-way functions in a black-box way. In fact even with these extra assumptions (when formalized as some kind of hitting property assumed in addition to one-way-ness) still a black-box separation holds:

http://eprint.iacr.org/2012/523.pdf

(the construction of Barak-Ong-Vadhan is non-black-box).


NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

The following paper shows that the Hamiltonian cycle problem is NP-complete in maximal planar graphs:

  A. Wigderson
  The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
  Technical Report #298, Department of EECS, Princeton University, February 1982.
  https://www.math.ias.edu/avi/node/820

In a maximal planar graph, every face is a triangle; hence the dual of a  maximal planar graph is cubic. It is easy to see that the dual of a maximal planar graph is triply connected.

Therefore your problem is NP-complete.


If P=NP, could we obtain proofs of Goldbach's Conjecture etc.?

Indeed!

If P=NP, not only we can decide whether there exists a proof of length n for Goldbach's Conjecture (or any other mathematical statement), but we can also find it efficiently!

Why? Because we can ask: is there a proof conditioned on the first bit being ..., then, is there a proof conditioned on the first two bits being ...., and so on...

And how would you know n? You'll just try all possibilities, in increasing order. When we make a step in the i'th possibility we also try a step in each of the possibilities 1..(i-1).


Parameterized complexity of graph intersection number

The problem has been studied under the name Edge Clique Cover, and the observations you make regarding data reduction have been used to get a kernel with 2^k vertices. It is a long standing open problem whether a polynomial kernel exists. I don't know about good bounds on the running time, see http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf


Statistical distance between uniform and biased coin

Denote the random bits by $x_1,\dots, x_n$. By definition, the statistical distance between $U$ and $D$ is at least $\Pr_U\left(\sum x_i \geq t\right) - \Pr_D\left(\sum x_i \geq t\right)$ for every $t$. We choose $t = n/2 + \sqrt{n}$.

Note that $\Pr_U\left(\sum x_i \geq t\right) \geq c_1$ for some absolute constant $c_1 > 0$. If $\Pr_D\left(\sum x_i \geq t\right) \leq c_1/2$, then the statistical distance is at least $c_1/2$, and we are done. So we assume below that $\Pr_D\left(\sum x_i \geq t\right) \geq c_1/2$.

Let $f(s) = \Pr\left(\sum x_i \geq t\right)$ for i.i.d. Bernoulli random variables $x_1,\dots, x_n$ with $\Pr(x_i = 1) = 1/2-s$. Our goal is to prove that $f(0) - f(\varepsilon) = \Omega(\varepsilon \sqrt{n})$. By the mean value theorem,
$$f(0) - f(\varepsilon) = -\varepsilon f'(\xi),$$
for some $\xi \in (0, \varepsilon)$. Now, we will prove that $-f'(\xi) \geq \Omega(\sqrt{n})$; that will imply that the desired statistical distance is at least $\Omega(\sqrt{n} \varepsilon)$, as required.

Write,
$$f(\xi) = \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^k \left(\frac12+\xi\right)^{n-k},$$
and
$$\begin{align}
f'(\xi) &= \sum_{k\geq t} \binom{n}{k} \left(-k \left(\frac12 - \xi\right)^{k-1} \left(\frac12+\xi\right)^{n-k} + (n-k) \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k-1}\right) \\
&= -\sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k}\frac{k/2 + k\xi - (n-k)/2 + (n-k)\xi}{(1/2 - \xi)(1/2 +\xi)}.
\end{align}$$
Note that
$$\frac{k/2 + k\xi - (n-k)/2 + (n-k)\xi}{\left(1/2 - \xi\right)\left(1/2 +\xi\right)} =
\frac{(2k-n)/2 + n\xi}{(1/2 - \xi)(1/2 +\xi)} \geq 2(2t - n)  = 4\sqrt{n}.$$
Thus,
$$\begin{align}-f'(\xi) &\geq 4\sqrt{n} \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k} \\&= 4\sqrt{n} f(\xi) \geq 4\sqrt{n} f(\varepsilon) \geq 4\sqrt{n}\cdot (c_1/2).\end{align}$$
Here, we used the assumption that $f(\varepsilon) = \Pr_D(x_1+\dots+x_n \geq t) \geq c_1/2$. We showed that $-f'(\xi) = \Omega(\sqrt{n})$.


What characterizations exist for the grammars that can express subsets of the context-free languages?

Every context free language over a one letter alphabet (or equivalently every langauge recognized by unary PDAs, unary DPDAs or 1 counter machines) is regular.

See: S. Ginsburg, H. Rice: "Two families of languages related to ALGOL", Journal of the
ACM, 9: 350–371, 1962.

For what regards PDAs with bounded stack reversals they are equivalent to bounded context-free languages. In general a language $L$ over alphabet $\Sigma$ (with $|\Sigma|\geq 2$) is bounded if and only if there exists non empty words $w_1,w_2,...,w_n$ such that $L\ \subseteq w_1^*w_2^*...w_n^*$; but not all bounded languages are context-free (for a characterization of bounded CFG languages by finite union of stratified linear sets see Ginsburg's theorem). I don't know much about them, but they have been studied intensively, see for example: Oscar H. Ibarra, Bala Ravikumar , On Bounded Languages and Reversal-Bounded Automata (citing and cited articles).

EDIT: another result is that linear LR(1) languages are equivalent to the class of languages accepted by deterministic one-turn PDA (M. Holzer, K. J. Lange, On the Complexities of Linear LL(1) and LR(1) Grammars)


When does randomization speed up algorithms and it "shouldn't"?

I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best known deterministic algorithms are $\tilde O(n^4)$ assuming GRH (deterministic Miller–Rabin) or $\tilde O(n^6)$ unconditionally (variants of AKS).


Separation of  space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project

Perhaps you'd be interested in switching networks. According to Potechin's Bounds on monotone switching networks for directed connectivity, one way to separate L from NL is to show that there is no polysize switching network for directed connectivity. There is in fact a (trivial) polysize switching-and-rectifier network for directed connectivity. The difference between the two models is that the former is undirected and the latter directed.

Potechin has been working on separating L and NL, but so far his method only works for monotone networks. See also his STOC 2012 paper with Siu Man Chan. (More papers are on the way.)


Determining the distribution of results of a simple algorithm

I suspect you won't get a closed form solution for the distribution you're looking for. Think of the seemingly easier problem where $k$ is always chosen to be exactly $2$, and where you get the set $\{1\}$ "for free". This problem is just like asking for a closed-form distribution of the cardinality of the connected component in the Erdos-Renyi graph $G(n,s)$ that contains a specific vertex $v_1$. I'm pretty sure that there's no known closed-form description of this distribution, and that in fact the lower order terms are poorly understood, especially around the critical value $s \sim n \log n$.