Expressing a set of 0-1 strings by Extended Formulation

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a linear system

\begin{equation}
\label{equation:ExtForm}
Ex + Fy  = g, y\geq 0
\end{equation}

in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real
matrices with $d,r$ columns respectively and $g$ is a column vector
such that $x\in P$ if and only if there exists $y$ such that the equation above holds.

Thus the formulation you described in your question seems to be incorrect.
In special the right side of the inequality is expected to be a vector and not
a number.

I believe that the way in which you represent strings as extremal points of a
polytope is somewhat arbitrary. But a sort of canonical way is to represent
a string $x$ over $\{0,1\}^n$ by a vector $v\in \mathbb{R}^n$  such that
$v_i=x_i$.

However these extremal points are usually meant to represent the solutions to
a given combinatorial problem. For instance, in the cut polytope is the convex hull
the characteristic vectors of all cuts in the complete graph $K_n=(V_n,E_n)$:

\begin{equation}
\label{equation:CutPolytope}
CUT(n) = conv\{ \chi^{\delta(X)\in \mathbb{R}^{E_n}} | X\subseteq V_n\}
\end{equation}

where $\delta(X)$ is the set of edges from $X$ to its complement $\overline{X}$.
Similarly, the stable set polytope is the convex hull of the vectors corresponding
to the characteristic functions of all stable sets of $G$.

\begin{equation}
\label{equation:StableSet}
STAB(G) = conv\{\chi^S \in \mathbb{R}^V | S \mbox{ is a stable set of $G$}\}
\end{equation}

The TSP polytope $TSP(n)$ is the convex hull of all vectors corresponding to the characteristic functions of sets of edges representing the tours in $K_n$:

\begin{equation}
\label{equation:TSP}
TSP(n) = conv\{\chi^F \in \mathbb{R}^{E_n} | F\subseteq E_n \mbox{ is a tour of } K_n\}
\end{equation}

The interest on extended formulations stems from the fact that some polytopes,
such as the Permutahedron,which have an exponential number of facets admit extended formulations with a polynomial number of inequalities. However, recently Fiorini, Massar, Pokutta, Tiwary and De Wolf proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities.


What's the difference between "adaptive sorting" and "sorting almost sorted data quickly"?

I think the importance of "sorting almost sorted data quickly" in the database community is because of good streaming and/or parallel algorithms for k-sorting and for k-sorted id generation. (e.g. http://link.springer.com/chapter/10.1007%2F978-3-540-77050-3_2#page-1) Adaptive sorting is a more general topic: for instance, reverse order would not be what the database community cares about, but would be perfectly reasonable to exploit more generally.


Bipartite matching with degree domination

There does not always exist a matching with your property in a bipartite graph.

Consider for example the graph $G = (V, E)$ where

$V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$ and
$E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}$

This graph is bipartite (with $V_1 = \{a_1, a_2, a_3, b_1, b_2, b_3\}$ as one part and $V_2 = \{c_1, c_2, d_1, d_2, x\}$ as the other). Every vertex in this graph except $x$ has degree $3$. Vertex $x$ has degree $6$.

Suppose, for the sake of contradiction, that a matching $M$ with your property exists. Consider any two adjacent vertices $v_1$ and $v_2$ that have the same degree. It turns out that the conditions on $M$ imply that both of these vertices have the same matched-or-not status (i.e. either both or neither of the vertices must be matched in $M$). This can be proved very simply by contradiction: suppose one vertex (wlog $v_1$) is matched and the other is not; then since there is an edge between them, the given property on $M$ tells us that $deg(v_1) > deg(v_2)$, which is a contradiction.

Thus, the matched-or-not status of adjacent vertices of the same degree is the same. Then if a set of vertices has the property that every vertex has the same degree and the subgraph induced by these vertices is connected, we can apply this rule multiple times to conclude that all vertices in the set must have the same matched-or-not status. In particular, in $G$ the matched-or-not status of every vertex in $V \setminus \{x\}$ must be the same since these vertices all have degree-$3$ and are connected. In other words, either every vertex in $V \setminus\{x\}$ is matched in $M$, or no such vertex is matched in $M$. If the matched-or-not status for these vertices is "matched" then every vertex in the $V_1$ part of the bipartition is matched in $M$; this is impossible since there are more vertices in $V_1$ than in the other part $V_2$. If the matched-or-not status for these vertices is "not matched" then the only vertex in $G$ that can be matched in $M$ is $x$; since a non-empty matching (as $M$ must be) matches at least two vertices, we see that this case is also impossible.

By contradiction, a matching $M$ with the property in question does not exist in $G$.


Yes, this is a corollary of the Three Color Theorem, see at the bottom here:
http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html


To what extent can the mathematics of Reals be applied to Computable Reals?

The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 and Defintion 11.2.10 of the HoTT book.)

The following theorem is valid in any topos (a model of higher-order intuitionistic logic):

  Theorem: There is a Cauchy-complete archimedean ordered field, and in fact any two such fields are canonically isomorphic.

Moreover, in intuitionistic logic (not to be confused with intuitionism) we can do a lot of real analysis (sequences and limits, derivatives, integrals, continuity, uniform continuity, etc.) which is then valid in any topos. If we take the topos of sets we get the usual real analysis. By taking a different topos we get a different kind of real analysis – and there is a topos which yields precisely the computable reals and computable real analysis.

This of course is the effective topos, in which the real numbers are the computable reals (speaking vaguely, the reason for this is that the effective topos is constructed in such a way that everything in it is automatically computable). The answer to your question is

  Definitions, constructions, and theorems in intuitionistic real analysis are automatically translated to definitions, constructions and theorems about computable reals when we interpret them in the effective topos.

For instance, the theorem "every uniformly continuous map $f : [0,1] \to \mathbb{R}$ attains its supremum" is intuitionistically valid. When we interpret it in the effective topos we get the corresponding version for computable maps on computable reals which are computably uniformly continuous.

You also ask about the "divergence" between real analysis and its computable version. The answer is that results which rely on the law of excluded middle or the axiom of choice (although countable choice is ok) are not intuitionistic, and therefore cannot be validated in the effective topos. However, we should note that (contrary to popular opinion) most analysis can be done intuitionistically.

The effective topos is just one of many realizability toposes. When we interpret intuitionistic analysis in other realizability toposes we get alternative models of real number computatability, including computation with oracles which you allude to. The "relative Kleene function realizability topos" (whatever that is) gives the so called Type II computability on reals in which computable maps operate on all reals, not just the computable ones.

I tried to explain this once in the notes "Realizability as the Connection between Computable and Constructive Mathematics", and before that in my Ph.D. thesis.


A conjecture related to the Cerny conjecture - counterexample/reference request

I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of this lecture.


Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

One result of this kind was proved by Lipton "On proving that a graph has no large clique: A connection with Ramsey theory". He connects lower bound conjectures with purely graph theoretic results, showing that if $NP$ is not contained in $coNTIME(n^{O(\log n)})/(\log \log n)$, then the inapproximability of $MAX-CLIQUE$ implies that there are graphs with neat Ramsey-theoretic properties. (See the paper for definitions.) I have no idea if any progress has been made on proving whether or not such graphs actually exist.


Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions:

  Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$.

Such functions are known to exist; see, e.g., Chapter 6.3 of Ryan O'Donnell's Analysis of Boolean functions (2014) (or the online version).


Entropy of a byte in a compression algorithm?

I define a random variable X which samples a bit uniformly at random from C∗. Should I expect Prob[X = 0] to be close to 1/2?

Roughly, yes. The compression algorithm is lossless (bijective), so the entropy of the input is the same as the entropy of the output. Under your hypothetical, the output's length is asymptotically larger than its entropy, so asmyptotically larger than the input's entropy. So the compression algorithm does not reach the Shannon entropy bound.

To see one somewhat-formal argument for why the output's length is asymptotically larger than its entropy, suppose for simplicity the length is $n$ and formalize your hypothesis by, e.g. supposing the fraction of ones is always at least $p$, with $p > 0.5$. Using a Chernoff bound, the total number of such strings is at most $q 2^n$ where $q = 2^{-cn}$  for some constant $c > 0$, and so the maximum entropy of the output is at most the log of this number, which is $n(1-c)$, which is significantly smaller than $n$.

OK, this isn't totally formal, but I hope it's a useful answer.


Data structure for dynamic memory allocation

Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some Functions Concerning Dynamic Storage Allocation", which shows that allocating $m$ bytes in blocks of size between $n$ and $N$ requires $\Omega(m \log (N/n))$ bytes of memory.

Additionally, the buddy system achieves this bound and can be done in logarithmic time.


Kleinberg-consistency of spectral clustering

Answering my own question, with a hat tip to Misha Belkin (private correspondence). It is easy to see that the unnormalized mincut and the RatioCut algorithm (see here for precise definitions
http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf
) are Kleinberg-consistent. This is because the intra-cluster distances/similarity does not influence the objective function in any way.

The Ncut-based clustering algorithm, however, is not Kleinberg-consistent. This can be seen by making the similarity weights within some cluster sufficiently large that it is able to absorb nearby clusters with negligible extra charge.


Can any computational challenge be transformed to proof-of-work?

(Note:  Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced relatively efficiently. Their PoW instance $\Psi(\mathcal{C})$ is as hard as a worst-case Orthogonal Vectors, even if the input instance $\mathcal{C}$ is easy, so that they avoid a major drawback of the solution described below.

The solution described below might benefit from its simplicity---it can be described to a non-expert---but it seems to me to be much less interesting theoretically.)

A solution is possible if one makes the strong assumption that "the fastest algorithm for $\mathcal{C}$ is fundamentally randomized" (and if we model a cryptographic hash function as a random oracle). One way to formalize this is to say that

$\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$ (otherwise, I guess it's not really a valid challenge);
the fastest randomized algorithm for $\mathcal{C}$ runs in expected time $T$ on a typical instance; and
there exists an efficiently computable function $f$ from $\{0,1\}^k$ to the domain of solutions to $\mathcal{C}$ for $k \approx \log_2 T$ such that there always exists an $s \in \{0,1\}^k$ with $f(s)$ a solution to $\mathcal{C}$.

Notice that the assumption that $k \approx \log_2 T$ implies that brute-force search of $\{0,1\}^k$ is essentially the optimal algorithm for $\mathcal{C}$. So, this is quite a strong assumption. On the other hand, if $\mathcal{C}$ does not satisfy these properties, then it's hard for me to imagine satisfying both your conditions (2) and (4).

Then, given a hash function $H : \{0,1\}^* \to \{0,1\}^k$, which we model as a random oracle, we define $\Psi_H(\mathcal{C}; r)$ as follows, where $r \in \{0,1\}^\ell$ for some $\ell \gg k$ is the random input to $\Psi_H$. The goal is to output $x \in \{0,1\}^*$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. In other words, $(r,x)$ should hash to "good random coins" for the above algorithm.

Let's see that this satisfies all of your conditions.

"The function $\Psi$ is randomized, using some (public) random sequence $r$." Check!
"Solving $\Psi(\mathcal{C})$ is typically as hard as solving $\mathcal{C}$." Notice that the simple randomized algorithm for $\Psi_H(\mathcal{C},r)$ runs in expected time at most $2^k$ plus polynomial overhead, and by assumption $2^k \approx T$ is essentially the running time of the optimal algorithm for $\mathcal{C}$.
"If a solution $x$ is found for $\Psi(\mathcal{C})$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal{C}$." This can be done by computing $f(H(r,x))$, which is a solution to $\mathcal{C}$ by assumption.
"Knowing a solution for $\mathcal{C}$ does not help in finding a solution for $\Psi(\mathcal{C})$." By definition, solving $\Psi_H(\mathcal{C}; r)$ requires finding $x$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. Since we modeled $H$ as a random oracle, we can lower bound the expected running time of any algorithm that solves this problem by the optimal expected query complexity of the query problem in which $H$ is given by a black box and we are asked to find a solution to the same problem. And, again because $H$ is a random oracle, the expected query complexity is just the inverse of the fraction of elements $x \in \{0,1\}^k$ that are solutions (up to a constant factor). By assumption, the optimal expected running time of any algorithm for $\mathcal{C}$ is $T \approx 2^{k}$, which implies that this fraction cannot be much larger than $2^{-k}$. Since $\ell \gg k$ and $r \in \{0,1\}^\ell$ is chosen uniformly at random, this is even true with preprocessing that is allowed to depend on $H$ and $\mathcal{C}$ (but not $r$), and in particular it is true even if we know a solution to $\mathcal{C}$ in advance.


What makes a language (and its type-system) capable of proving theorems about its own terms?

[Self-advertising follows, but I think that this is relevant.]

There are several possible approaches to this questions. One of the ways (that I explored during my PhD thesis in the context of an ML-like language) is to extend the type system with a first-order layer, so that terms of the language can be manipulated as objects of the underlying logic. Of course, you also need to include some predicates so that there is something to observe. In the case of my system, these predicates are term equivalences. In particular, if $t$ and $u$ are terms of the language, then the type $t \equiv u$ is only inhabited if $t$ and $u$ are indeed (observationally) equivalent. You can use first-order quantifiers to encode properties such as $\forall v, (\lambda x.x)\;v \equiv v$ in types, and they are proved by constructing programs inhabiting them.

Of course you can also assume equivalences, and there are several different forms of quantifiers (typed / untyped, universal / existential). This mechanism can be used to reason about any program (they do not have to be proved terminating or even typed). The only constraint is that programs that are used as proofs must be proved terminating by the system (arbitrary general recursion leads to inconsistency).

Here are a couple of references if you want to check this out:

https://lepigre.fr/files/docs/lepigre2017_pml2.pdf (recent paper with examples)
https://tel.archives-ouvertes.fr/tel-01590363 (PhD thesis in English)
https://github.com/rlepigre/pml (language implementation)


Is signing a message hash a valid replacement for blind signature?

Wouldn't this algorithm replace the blind signature implementation as described in Wikipedia in every case?

No, because hashing is a deterministic algorithm. Let M be Alice's message, and $H(\cdot)$ be the hash function.

In your algorithm, Alice passes H(M) to Bob, who can store H(M) for later reference. This way, Bob effectively creates a database of message hashes signed by him, as well as the ID of the user who asked for Bob's signature. Let $D = \{\langle H(M_1), ID_1 \rangle, \langle H(M_2), ID_2 \rangle, \ldots \}$ be this database.

On seeing a message-signature pair $(M, \sigma)$, Bob hashes M to H(M), and searches D for H(M). If H(m) is found, Bob can easily recover the ID of the user. Hence, this method does not blind the identity of the user.


possible bridge between group growth theory and complexity theory?

Maybe this is along the lines you are looking for: I wrote a blog post here explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are no more powerful than linear time Turing machines for deciding word problems of groups.

The basic idea is that groups with non-uniform read once automata necessarily have polynomial growth (i.e., the number of elements with a word of length at most $r$ is $O(r^k)$ for some fixed $k$). By Gromov's theorem, this implies that the group is virtually nilpotent. There is work giving linear time algorithms for the word problems of such groups, so that's that.


Determining if a word of specific length exists that is not accepted by a NFA

Your problem is NP-hard, by reduction from 3SAT.

Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$.  Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as follows.  The $n$-bit input to the NFA is treated as an assignment to $x_1,\dots,x_n$.  The NFA first nondeterministically selects one of the $m$ clauses.  Then, it checks whether the input satisfies that clause, and if so, rejects; otherwise accepts.  Note that if the input $x$ satisfies $\varphi$, then the NFA rejects; otherwise, the NFA accepts.

Now there exists an input to the NFA of length $n$ that causes the NFA to reject, if and only if there is a satisfying assignment for $\varphi$.  That means that your problem is at least as hard as 3SAT.


finding permutations which fulfills given conditions

Jukka's comment reminds me of the following reference.

If we look at such a function g as a matrix, the condition is equivalent to one in the definition of a permuted inverse Monge matrix.  There is a polynomial-time algorithm to determine if a given matrix is a permuted inverse Monge matrix (and if so, that gives corresponding permutations).

The result was found by Deineko and Filonenko (1979) in their Russian paper, and it is explained (in a more general form) in the following survey by Burkard et al.

Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics 70(2): 95-161 (1996) http://dx.doi.org/10.1016/0166-218X(95)00103-X


W[1]-hard problems with FPT time approximation algorithms

In the Directed Odd Cycle Transversal problem the input is a graph $G$ and the task is to find a smallest set $S$ of vertices such that $G-S$ has no (directed) cycles of odd length. In the parameterized version we are also given an integer $k$ and asked whether a solution of size at most $k$ exists.

In this paper we prove that (R1) the problem is W$[1]$-hard, (R2) that it admits a factor 2 approximation algorithm in time $2^{k^{O(1)}}n^{O(1)}$, and that (R3’) assuming a hypothesis somewhat stronger than $FPT \neq W[1]$ that there exists an $\epsilon > 0$ such that the problem does not admit a $(1+\epsilon)$ approximation algorithm in time $f(k)n^{O(1)}$.


$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.)

The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a polynomially long line of $\ac$-computable edges. By a further extension of the idea, one could simulate edges computable in poly time with a PPAD oracle, that is, PPAD is closed under Turing reducibility; this argument is given in Buss and Johnson.

There are many equivalent definition of PPAD in the literature that differ in various details, hence let me fix one here for definiteness. An NP search problem $S$ is in PPAD if there is a polynomial $p(n)$, and polynomial-time functions $f(x,u)$, $g(x,u)$, and $h(x,u)$ with the following properties. For each input $x$ of length $n$, $f$ and $g$ represent a directed graph $G_x=(V_x,E_x)$ without self-loops where $V_x=\{0,1\}^{p(n)}$, and every node has in-degree and out-degree at most $1$. The representation is such that if $(u,v)\in E_x$, then $f(x,u)=v$ and $g(x,v)=u$; if $u$ has out-degree $0$, $f(x,u)=u$; and if $u$ has in-degree $0$, $g(x,u)=u$.

The node $0^{p(n)}\in V_x$ is a source (i.e., it has in-degree $0$ and out-degree $1$). If $u\in V_x$ is any source or sink (in-degree $1$, out-degree $0$) other than $0^{p(n)}$, then $h(x,u)$ is a solution to $S(x)$.

We can define $\ac\mathrm{PAD}$ similarly, except we require $f,g,h$ to be in $\mathrm{FAC}^0$.

I will ignore $h$ in the construction for simplicity. (It is not hard to show that one can take it to be a projection, hence $\ac$-computable.)

So, consider a PPAD problem $S$ defined by $f$ and $g$, and fix Turing machines computing $f$ and $g$ in time $q(n)$. For any $x$, we define a directed graph $G'_x=(V'_x,E'_x)$ whose vertices are sequences of the following form:

$(0,u,c_1,\dots,c_k)$, where $u\in V_x$, $0\le k\le q(n)$, and $c_1,\dots,c_k$ are the first $k$ configurations in the computation of $f(x,u)$.
$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)$, where $u,v\in V_x$, $0\le k\le q(n)$, $f(x,u)=v$, $c_1,\dots,c_{q(n)}$ is the full computation of $f(x,u)$, and $d_1,\dots,d_k$ are the first $k$ steps in the computation of $g(x,v)$.
$(1,v,d_1,\dots,d_k)$, where $0^{p(n)}\ne v\in V_x$, $0\le k\le q(n)$, and $d_1,\dots,d_k$ are the first $k$ configurations in the computation of $g(x,v)$.
$(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$, where $u,v\in V_x$, $v\ne0^{p(n)}$, $0\le k\le q(n)$, $g(x,v)=u$, $d_1,\dots,d_{q(n)}$ is the computation of $g(x,v)$, and $c_1,\dots,c_k$ are the first $k$ steps in the computation of $f(x,u)$.

$E'_x$ consists of the edges in $V'_x\times V'_x$ of the following kinds:

$(0,u,c_1,\dots,c_k)\to(0,u,c_1,\dots,c_{k+1})$
$(0,u,c_1,\dots,c_{q(n)})\to(0,u,c_1,\dots,c_{q(n)},v)$
$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)\to(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{k+1})$
$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{q(n)})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{q(n)})$ if $f(u)=v$ and $g(v)=u$ (i.e., either $(u,v)\in E_x$, or $u=v$ is an isolated vertex)
$(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{k+1})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$
$(1,v,d_1,\dots,d_{q(n)},u)\to(1,v,d_1,\dots,d_{q(n)})$
$(1,v,d_1,\dots,d_{k+1})\to(1,v,d_1,\dots,d_k)$
$(1,u)\to(0,u)$

Formally, let $r(n)$ be a polynomial bounding the lengths of binary representations of all the sequences above (such that we can extend or shorten sequences, and extract their elements with $\ac$-functions); we actually put $V'_x=\{0,1\}^{r(n)}$, and we let all vertices except the above-mentioned sequences to be isolated.

It is easy to see that the functions $f'$, $g'$ representing $G'_x$ are $\ac$-computable: in particular, we can test in $\ac$ whether $c_1,\dots,c_k$ is a valid partial computation of $f(x,u)$, we can compute $c_{k+1}$ from $c_k$, and we can extract the value of $f(x,u)$ from $c_{q(n)}$.

The sinks in $G'_x$ are nodes of the form $(0,u,c_1,\dots,c_{q(n)},u,d_1,\dots,d_{q(n)})$ where $u$ is a sink in $G_x$. Likewise, sources are $(1,v,d_1,\dots,d_{q(n)},v,c_1,\dots,c_{q(n)})$ where $v$ is a source in $G_x$, except that in the special case $v=0^{p(n)}$, we have pruned the line early and the corresponding source in $G'_x$ is just $(0,0^{p(n)})$. We can assume the encoding of sequences is done in such a way that $(0,0^{p(n)})=0^{r(n)}$.

Thus, $f'$ and $g'$ define an $\ac\mathrm{PAD}$ problem $S'$, and we can extract a solution to $S(x)$ from a solution to $S'(x)$ by an $\ac$-function $h'$ which outputs the second component of a sequence.


This is a late response.

First, to correct what you wrote:
Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational complexity classes. In an old paper (beginning of 80s) Andrew Yao shows some subexponential time derandomization for RP etc using these objects (btw, this is immediate), but no stronger derandomization is known. Note, that in terms of fooling power cryptographic PRGs are stronger than what you need for derandomization but at the same time in terms of their stretch are weaker than their typical complexity-theoretic analogues (this follows by the order of quantification in the definition of the PRGs).

As Sasho Nikolov mentioned there are plenty of examples in PAC learning. Have a look at a very early paper by Kearns and Valiant on the impossibility of learning formulas and automata (follow in google scholar the references from there). Also, there are consequences in proof complexity through interpolation -- have a look in the also early works by Jan Krajicek and Pavel Pudlak. However, I am not sure if you consider these to be complexity-theoretic implications (but I do).

-- Periklis


Would an optimal sorting network ever have to swap two numbers the "wrong" way

How do you decide what the "wrong way" is?

Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit.

Now, you can keep doing this until you've gotten rid of all the wrong-way swap gates. At this point, you may have permuted the order of the output wires, but you will have a circuit which always outputs a fixed permutation of the sorted order. But since if you input the numbers in sorted order, the right-way swap gates never change the order, this fixed permutation must be sorted order.

So for any sorting network, there's an equivalent one with the same number of gates and the same depth which has no wrong-way gates.


Is P equal to the intersection of all superpolynomial time classes?

Yes.

In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of McCreight and Meyer, 1969, free version here) a result of that I believe is due to Manuel Blum, there is a single function $f$ such that $\mathsf{P} = \mathsf{DTIME}(f(n))$. This function is necessarily superpolynomial, but "just barely."

The theorem applies more generally to any Blum complexity measure $\Phi$ and any union class $\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$ where $S$ is a c.e., self bounded set of total computable functions. (A set of functions $S$ is c.e. if there is a single partial computable function $F(i,\vec{x})$ such that $S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$ where $f_i(\vec{x}) := F(i,\vec{x})$. Self-bounded means that for every finite subset $S_0 \subset S$, there is a function in $S$ that dominates all $g \in S_0$ almost everywhere. "$\mathsf{BLUM}_{\Phi}$" is a notation I haven't seen before, but I like it :) - I'm using it for the $\Phi$-bounded analog of a time-bounded complexity class.)


A similar hardness result is known for the inapproximability of chromatic number [1]. Independent set is hard to approximate as well, since it is $\mathsf{MAX\text{-}CLIQUE}$ on the complement graph. Some problems that are easier to approximate include vertex cover, (connected) dominating set, feedback vertex set, TSP and Steiner tree.

[1] Zuckerman, David. "Linear degree extractors and the inapproximability of max clique and chromatic number." Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. ACM, 2006.


You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.matching


Are there any public synchronous discussion forums (slack, discord, etc.) for TCS

CSTheory is now live at Zulip.

Thanks to everyone who participated in the above discussion and for sharing your opinion.


Optimal Self Balancing Trees with Canonical Form?

Andersson and Ottmann's "New tight bounds on uniquely represented dictionaries" has a good survey on the subject of of canonical (or "unique", as they call it) forms for dictionaries.

Before I describe it, I should note that their structure is actually stronger than you are looking for. Their structures are size-unique, so any two trees with $n$ elements will have the same shape, even if the sets of elements are unrelated. They leave the problem of set-unique data structures open, though see below about randomization.

Andersson and Ottmann invented a data structure (a graph, not a tree) where updates and lookups take $O(n^{1/3})$ time. By tuning a parameter, they can get $O(\sqrt{n})$ time for updates and $O(\lg n)$ time for lookups, matching an earlier structure of Sundar and Tarjan (which Ottmann claims in "Trees - A Personal View" is not strictly size-unique due to the way they use an auxiliary structure). Andersson and Ottmann also prove that either update or lookup operations must take $\Omega(n^{1/3})$ time in their particular model. An earlier paper by Snyder showed some $\Omega(\sqrt{n})$ lower bounds, but the model he used was too strict for Andersson and Ottmann's taste.

If you're willing to accept "canonical" meaning "taken from the same sample space of trees", then treaps might be exactly what you're looking for -- any set of elements in a tree has shape independent of the order in which they arrived. However, the shape is randomized.

For storing data in the leaves (by which I assume you mean that each key is stored in a leaf, or that value (in a map structure) are all stored in leaves), views of skip-lists as trees may have this property. I mentioned some tree-views of skip lists on another question at this site. Others that may deserve mention are

Daniel Golovin's The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
Michael Spiegel and Paul F. Reynolds's Lock-free multiway search trees and      The Dense Skip Tree: A Cache-Conscious Randomized Data Structure

I've also been recently thinking about a treap-like structure in which every key is stored in a leaf, as mentioned in the related question I posed here. I hope to post something there on the matter soon.


What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?

For constraint satisfaction problems, the property of having no better approximation algorithm than random assignment is known as approximation resistance.

This is has been studied by several works in the last few years, with some results based on $P\neq NP$ and other more general results based on the unique games conjecture. A good source for this is Per Austrin's thesis.


What you want is a good reference to understand the exponential lower bounds for $AC^0$ circuits computing the PARITY function.

Now you haven't stated whether you actually want to understand the proof, or just understand things at a high level, the way a survey article would explain things.

A survey article I recently read and liked is "The complexity of finite functions" by Boppana and Sipser.

If you really want to sit down and understand the proof, then you can either read proofs based on the Switching lemma (which appear in the papers you cited - [FSS], [Y] and [H1]), or the Razborov-Smolensky proof.

For proofs using the Switching Lemma, Håstad's Ph.D. thesis is a good read, if a bit hard to follow if you're new to the area. A better exposition of the proof is in "Introduction to circuit complexity and a guide to Håstad's proof" by Allan Heydon. The only problem with it is that I can't find it online, and I have a hard copy. I really recommend it if you're new to circuit complexity.

For the Razborov-Smolensky approach, just google for it and you'll get a bunch of lecture notes. I understood the lower bound from these three lecture notes: Sanjeev Arora, Madhu Sudan and Kristoﬀer Arnsfelt Hansen.


Cryptographic hashes
I don't think anything is known unconditionally.
We can analyze this question using a random oracle assumption.  MD5, SHA1, SHA256, etc., have a Merkle-Damgaard structure: they split the input $x$ up into blocks $x_1,\dots,x_n$, then compute
$$h_i = F(x_i,h_{i-1})$$
where $h_0$ is a constant and $h_n$ is used as the output of the hash function.  Now let's analyze this structure under the assumption that $F$ can be modelled as a random function (which is believed to be a good heuristic).
Suppose we want to construct a message $x_1,\dots,x_n$ that hashes to output $y$.  Pick $x_1,\dots,x_{n-2}$ arbitrarily; this determines $h_{n-2}$.  Now let's consider all possibilities for $x_{n-1},x_n$, and the derived values of $h_{n-1},h_n$.  If we focus on MD5, each $x_i$ is 512 bits and each $h_i$ is 128 bits.  Since $F$ is a random function, the chances that any particular value of $h_{n-1}$ is never reached by any choice of $x_{n-1}$ is $(1 - 1/2^{128})^{2^{512}} \approx 1-1/2^{384}$; therefore it is overwhelmingly likely that all $2^{128}$ possible values of $h_{n-1}$ are attainable.  Now consider all $2^{640}$ possible combinations of $(h_{n-1},x_n)$, and consider the resulting value of $h_n = F(x_n,h_{n-1})$.  Since $F$ is a random function, the chance that none of these combinations yields $h_n=y$ is $(1-1/2^{128})^{2^{640}} \approx 1/2^{512}$, i.e., vanishingly unlikely.  In conclusion: if you pick $x_1,\dots,x_{n-2}$ arbitrarily, it is overwhelmingly likely that there will exist a way to pick $x_{n-1},x_n$ so that the resulting hash function outputs the value $y$.
It follows that, for MD5, there are infinitely many $x$'s that yield the hash $y$, assuming that treating $F$ as a random function is a good model.  In other words, for MD5, we expect all fibers to be infinite.
You can do the same for other Merkle-Damgaard hashes, like SHA1 or SHA256, and you'll reach the same conclusion: for SHA1 and SHA256, we expect all fibers to be infinite.  If they're not, then there is likely some deeper structural problem with the hash ($F$ doesn't behave like a random function).
Of course none of this is a proof.  The random oracle model has well-known limitations.  But it is a heuristic that might help you form a conjecture about what we expect the answer to be.
xxHash64
For xxHash64, it is not a cryptographic hash, so it is more amenable to analysis.  The answer is yes, all fibers are infinite.  In particular, xxHash64 works with four 64-bit "accumulators".  If we are given the value of an accumulator before and after a single iteration, it is easy to find a value of the 64-bit message (input) that causes the accumulator to evolve in that way (and it is unique).  So, this makes it easy to prove that all fibers are unique: given $y$, we can choose the first $n-32$ bytes arbitrarily, then choose the last 32 bytes (using the previous observation) to force its output to be $y$, and that will give a $n$-byte message that hashes to $y$.  Since we can do that for all $n$ and all choices of the first $n-32$ bytes, all fibers are infinite.


Finding outer face in plane graph (embedded planar graph)

First, suppose that your arcs are embedded to the plane as straight lines.  Then, the following three step algorithm works.

First, compute the leftmost vertex (as David Eppstein suggested).  This vertex will be on the unbounded face.

Second, among the arcs from that vertex, find the one whose slope is largest. This arc will be a side of the unbounded face.  (You must consider the slope; taking the arc with the leftmost destination vertex wouldn't work.  You may have to handle the case when this vertex is isolated somehow.)

Thirdly, take the face on the left hand side of this arc.  That face is the outer face.

If the edges aren't embedded as straight lines, then you need some extra information about the embedding.  Indeed, in any plane graph (with at least one cycle), you could just take an edge of the outer face and lift it around the whole embedding.  This changes the outer face, but doesn't move the vertexes, and doesn't change the cyclical orientation of arcs from the vertexes.

In particular, if the edges are open polygons given with the coordinates of the list of inner vertexes, then divide each such edge to a path and run the previous algorithm in the subdivided graph.  This may choose such an internal vertex in the first step.


The meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.


Shortest path in a DAG consisting of multiple copies of a smaller DAG

Yes, you certainly can (based on the fact that any subpath of a minimal path must also be minimal). That is, any shortest path entering $H_i$ at $u$ and leaving at $v$ must follow the shortest path from $u$ to $v$ in $H_i$.

Basically, you can compute the shortest-path distance matrix $D$ for any $H_i$ (it would be the same for all of them, of course), and replace every subgraph $H_i$ by one consisting only of the in- and out-nodes (that is, the nodes connected to other subgraphs; presumably fewer than $|V_i|$), and use only direct edges from the in-nodes to the out-nodes, with weights given by $D$.

You don't need to explicitly construct this new graph, of course. If you have the macrostructure of $G$ available in implicit form, you can compute $D$, and use that together with the macrostructure of $G$ in a (slightly customized) DP algorithm for finding the shortest path.


To the best of your knowledge, does the paper make a significant, well-presented, and correct contribution to the state of the art?  If the paper fails any of the three criteria, it's fair to reject it for that reason alone, regardless of the other two.
Here's what I think a report should contain.  Everything should be visible to the author, except possibly for serious accusations of misconduct.

a. A quick summary of the paper, to help the editor judge the quality of the results, and to help convince both the author and the editor that you actually read and understood the paper.  Place the result in its larger context.  Include a history of prior versions, even if the authors include it in the submission.  Be respectful, but brutally honest.

b. A discussion of the strengths and weaknesses of the paper, in terms of correctness, novelty, clarity, importance, generality, potential impact, elegance, technical depth, robustness, etc.  If you suspect unethical behavior (plagiarism, parallel submission, cooked data), describe your suspicions.  Be respectful, but brutally honest.

c. A recommendation to the editor for further action — accept, accept with minor revision, ask for a second round of reviewing, or reject outright.  Keep in mind that you are making a recommendation, not a decision; if you can't make up your mind, just say so.  Be respectful, but brutally honest.

d. More detailed feedback to the author — more detailed justification for your recommendation, requests for clarification in the final version, missing references, bugs in the proofs, simplifications, generalizations, typos, etc.  Be respectful, but brutally honest.
Conference reports should be shorter; program committees have hundreds of papers to consider at once.  Whether there should be a difference between conference and journal papers is up to the journal (and indirectly, up to the community).  Most theoretical computer science journals do not insist on a significant difference; it is quite common for the conference and journal versions of a theory paper to be essentially identical.  When in doubt, ask the editor!
If you still don't understand the paper after making a good-faith effort, it's the author's fault, or possibly the editor's, but certainly not yours.  The author's primary responsibility is to effectively communicate their result to their audience, and a good editor will send you a paper to referee only if they think you're a good representative of the paper's intended audience.  But you do have to make a good-faith effort; do not expect to immediately understand everything (anything?) immediately on your first reading.
If there are a lot of errors, don't even read the paper; just recommend rejection on the grounds that the paper is not professionally written.  Otherwise, if you really want to be thorough, include a representative list of grammar, spelling, and punctuation mistakes, but don't knock yourself out finding every last bug.  Be respectful, but brutally honest.
Expect to spend about an hour per page, mostly on internalizing the paper's results and techniques.  Be pleasantly surprised when it doesn't actually take that long.  (If it takes significantly less time than that, either the paper is either exceedingly elegant and well-written, you know the area extremely well, or the paper is technically shallow.  Don't confuse these three possibilities.)
You should write at least as many referee reports as other people write for you.  If this takes more time than writing your own papers, you're not spending enough time on your own papers.


Algebraic account of Gaussian elimination?

You really should read Gowers' essay carefully - it cleanly details the reasons why you need a basis in general. So if there is going to be an algebraic account of Gauss-Jordan, it will necessarily involve some additional conditions.  You can get an idea of the kinds of conditions by reading the n-lab page on dual vector spaces.  There it shows that there are a lot of spaces which are isomorphic to their double duals.

As you mention, this is related to double-negation elimination.  But let's spell that out. The isomorphism is linear CPS transform, as it is the set of functions $\left(V\multimap R\right)\multimap R$. You are seeking `unCPS'. Which highlights how miraculous the structure of $V$ must be for this to be feasible at all.  The page on the n-lab gives some of these miracles. [Turns out that, syntactically, this works for the duality measure $\leftrightarrow$ linear functional on programs if you choose your programming language "just right"; if you're curious, see my work with Chung-chieh Shan at PADL 2016, where we implement $\texttt{unCPS}$].

Another way, more computational, to look at this is to look at more general versions of LU decomposition. For LU with full pivoting, you can decompose $A$ as $PAQ = LDU$ with $P$ and $Q$ as permutation matrices, $D$ diagonal, $L$ unit lower triangular and $U$ unit upper triangular. You can generalize even more to various kinds of rings (see Fraction free factors by Zhou and Jeffrey). The point is that $P$ and $Q$ are arbitrary, but $L,D,U$ depend on them -- another way to see the base dependence. Clever choices of $P$ and $Q$ allow you to deal with whatever defects the expression of $A$ in the original basis were, and 'rotate' things in better position -- be it for stability, sparsity, expression size blowup, etc.


Is Magic: the Gathering Turing complete?

Alex Churchill (@AlexC) has posted a solution that does not require cooperation between the players, but rather models the complete execution of a universal Turing machine with two states and 18 tape symbols.  For details, see  https://www.toothycat.net/~hologram/Turing/ [archive].


EDIT: This solves the version of the problem where f only outputs 0 or 1. But I think the solution can be adapted to make it work for the more general case.

Maybe I misunderstood the question, but this doesn't look too hard.

Instead of estimating, the average, let's think of estimating the number of 1s, and call that number k. Let $N = 2^n$. So the average is k/N. You want to estimate this within a polynomial multiplicative factor in time O(N polylog(N)/k).

I think this can be done to within any constant multiplicative factor too. For example, let's say you want to estimate this to within a factor of 2. So the output $k'$ of the algorithm will be between k/2 and 2k.

I'll sketch an algorithm, which should have the appropriate running time. First check if k is between N/2 and N. This is easy, just sample a few random values and if you get more than half 1s, then it's in this interval. So you have a 2-approximation. If not, then check if it is between N/4 and N/2. And so on. Every time you make the interval smaller, it is more costly to estimate whether k lies in that range. But the cost is inversely proportional to how small the interval is.

For example, if you are checking if k is between $N/2^q$ and $2N/2^q$, then you need to make about $O(2^q)$ queries. Anyway, after repeating this procedure enough times, you should get the interval in which k lies. Say k lies between $N/2^q$ and $2N/2^q$. Then k is approximately $N/2^q$. So $2^q$ is about k/N. So in this step we would spend O(k/N) queries. But getting to this step required q other steps, but that's just an extra polylog(N) factor. So the overall running time is O(N polylog(N)/k), for a 2-approximation.

(One would actually have to do error amplification to get decent precision in each step. But that's only an extra polylog factor.)

The reason I like to think of it in this several stage process is that it highlights the process as a guess and check precedure. If someone told you $k$ is between $N/2^q$ and $2n/2^q$, then you could estimate it to even better precision knowing this fact, in the promised time bound. So we need to eliminate the step of being given a guess for $k$. This is done by binary searching over all possible intervals of that type.

To make this work for the case of non-boolean outputs, instead of counting the number of 1s, just sum the values seen. I'll try to find a reference to show that this works rigorously.


What is the name of this partition-indexed key-value data structure?

Sounds like a hash table to me, with collision resolution by chaining.


Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

Koiran's paper Hilbert's Nullstellensatz is in the Polynomial Hierarchy provides a public-coin Arthur-Merlin protocol for establishing that a system of $m$ equations on $n$ unknowns has a solution in $\mathbb{C}^n$, contingent on the Generalized Riemann Hypothesis.  Here Merlin finds a prime $p$ with $H(p)=0$ for some random hash $H$, along with a solution $(a_0,a_1,\cdots, a_n)$ to each of the $m$ equations $\bmod p$.

If the system of equations has no solution $\bmod p$, then there will only be a finite number of $p$ modulo which a solution exists.  If the system does have a solution $\bmod p$, then unconditionally there will be an positive density of $p$ with a solution, and the GRH allows that the $p$ with a solution are "equidistributed" in some sense, such that Merlin gets a win.

Although Koiran gives an example of a solvable system where the density of $p$ is exponentially small, Koiran suggests that if the system is solvable in $\mathbb{C}^n$, then in most cases there will be a large number of $p$ (and a large number of $a$); indeed about $1-1/e$ primes should have a solution IIRCC.

Thus, in the above problem, not only does there exist a valid response that Merlin can issue to Arthur for each challenge, but in fact there could be a large number of valid responses.

Distinguishing the easy systems of equations with solutions modulo many $p$ from the hard systems of equations with a few or only one $p$ seems to require determining properties of a Galois group of the system of equations.


What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?

Assuming that $p$ and $q$ are fairly large, one would expect that the expected length would mainly depend on the density, with some correction term depending on the perimeter. So it would, to first order, be a function of the following form.

$$ L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$$

Now, you could use experiments on smaller-size problems to figure out what $f$ and $g$ are. First, to estimate $f$, you want to do experiments on a sample without a boundary: the easiest way to do this is to use a $p\times p$ grid with the left side connected to the right and the top to the bottom, forming a torus. To estimate $g$, you can use experiments on a $p \times q$ grid.

For estimation, you need to solve (exactly or approximately) relatively large TSPs, since the larger the ones you use for the estimation, the better your results will be. You could either use heuristics that come within a few percent, or exact TSP code. See here for some good heuristics. Bill Cook's Concorde TSP solver will find the exact optimum for reasonably large instances (it's the best TSP code available), and can be used without charge for academic research.


Is this behavior in a programming language inconsistent?

Yes, your type inference seems incomplete. This example can be dealt with fairly trivially, by computing the respective type equations, e.g. in the style Hindley/Milner does it.
Alpha-renaming the example makes it easier to follow:
((\x.x) (\y.y)) 10

For maximum clarity, let's start by assigning type variables to each sub expression:

x : A
(\x.x) : B
y : C
(\y.y) : D
(\x.x) (\y.y) : E
10 : F
((\x.x) (\y.y)) 10 : G

Now, the typing rules of the language impose certain equality constraints for each language construct:

From the typing rule for lambda, applied to (\x.x), it follows that B = A -> A
Likewise, D = C -> C
From the typing rule for application, applied to (\x.x) (\y.y), it follows that A = D and E = D
From the typing rule for integers it follows that F = Int
From the typing rule for application, applied to (...) 10, it follows that E = F -> G

In summary, this yields the following equations:

B = A -> A

D = C -> C

A = D

E = D

F = Int

E = F -> G
Now you just solve the equations using unification:

From (2) and (3) it follows that A = C -> C

From (2) and (4) it follows that E = C -> C

From (5) and (6) it follows that E = Int -> G

From (8) and (9) it follows that C -> C = Int -> G, and thus, C = Int and C = G, and thus, G = Int

From (7) and (10) it follows that A = Int -> Int

A and C are the types you are ultimately interested in, because they are the ones you have to assign to x and y, respectively. They yield the typed term
((\x:(Int->Int).x) (\y.Int.y)) 10

Its overall type is G = Int.


Your question itself is not naive but the type of answer you ask for is. It is rare for any line of work or intellectual enquiry to have an elevator pitch explanation. Not all would agree with your characterizations of mathematics and physics because they ignore the depth and nuances of those fields.

Theoretical computer scientists are concerned with studying and applying computation. The computational perspective is a deep and all encompassing one so the study of computation is also deep and has a bearing on many other areas of study. Every single process, whether arising in nature or synthetic, manipulates information. They compute. As in mathematics, there are different languages and types of structures involved in computation, as in physics, there are fundamental laws about computation that we are trying to discover, as in chemistry, fundamental elements of computation can be classified. Theoretical computer science is broad and robust enough to be amenable to any perspective you bring to it. Some of the questions studied are:

What is computation and how can it be characterized? (Turing machines, lambda calculi, tiling systems, register machines, DNA computers etc.)
What is the computational model underlying a process? (Biological, chemical, economic, sociological processes, etc.)
What is efficient computation? (complexity via time, space, communication, amortized, smoothed, etc.)
What are characterizations of efficient computation? (Turing machines, algebraic notions, logic, type systems, etc.)
What is the most efficient way to  compute a solution to a problem? (algorithms)
How efficient are existing algorithmic processes (analysis of algorithms, statistical phenomena, market equillibria, etc.)

These are a small and non-representative sample of the questions that one may ask. As in any field, answers to some questions generate new questions and drive enquiry about other questions. You can find a rather dated view of the field by browsing the articles in the Handbook of Theoretical Computer Science.

Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, 1990
Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics, 1990


Processor failures in distributed computing that are not crash or Byzantine

Copied from the comments on the question as per-request.

I have taken theory of distributed computing with Michel Raynal and he described a third model, where messages can be dropped randomly. In that model a message can fail silently to be delivered, but that doesn't necessarily mean that the node has failed. It is about link failures rather than node failures "fair lossy channel model", you can read more about it here : Quiescent Uniform Reliable Broadcast as an Introductory Survey to Failure Detector Oracles - Michel Raynal (ftp.irisa.fr/techreports/2000/PI-1356.ps.gz)


I think, your problem is NP-complete. It is a special case of a theorem
by Farrugia,
stating that it is NP-hard to test if the vertex set a graph can be partitioned into
two subsets $V_1,$ and $V_2$ such that $G(V_1)$ belongs to the graph class $\mathcal{P}$ and
$G(V_2)$ belongs to the graph class $\mathcal{Q}$, provided $\mathcal{P}$ and $\mathcal{Q}$
are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least
one of $\mathcal{P}$ and $\mathcal{Q}$ is non-trivial (meaning not all graphs in the class are
edgeless).


How well can we do with this variable assignment problem?

Assuming that the $c_{a,b}$ values appears in a nicely ordered way, you can use Horner's rule to evaluate the polynomial in $O(n^2)$ arithmetic operations. As mentioned by frogeyedpeas, you can't expect beating $n^2$ because it is the size of the input.

Note that if you are interested by the number of bit operations then you need to multiply this by the elementary cost of multiplication (for numbers of the size considered in your problem).

It you want to beat the $n^2$ bound, you need the $c_{a,b}$ to be represented in a more compact/structured way.


The obvious N2Exp problem is of course the word acceptance problem for 2exp time bounded nondeterministic Turing machines. Using this might be as hard/easy as 2exp tiling, because the simulation of such a Turing machine computation in essence also requires you to define a double-exponentially large grid (2exp many configurations of memory tapes of length 2exp each) that is then filled in a non-deterministic way. In practice, showing N2Exp lower bounds often boils down to constructing such a grid (and making sure that it is not a tree or something else of insufficient structure). The "N" (nondeterminism) is often an inherent part of the problem and not so difficult to get once you have a large enough grid (if not, one would maybe shoot for 2exp at first).

Another practical N2ExpTime-complete problem is reasoning in expressive description logics (DL). In particular, the DL $\mathcal{SROIQ}$ that is underlying the W3C OWL 2 Web Ontology Language standard is N2ExpTime-complete (Yevgeny Kazakov: RIQ and SROIQ Are Harder than SHOIQ. KR 2008: 274-284). Now this is probably not a problem you want to use in reductions, since the definition of the logic is a bit unwieldy because of its many features. The actual lower bound proof for $\mathcal{SROIQ}$ has also been done by reduction to 2-exp tiling. However, depending on your problem, the construction given for $\mathcal{SROIQ}$ could be inspiring to see how to craft such large grids.

The tiling also shows another general pattern: N2Exp really is like NP, you just need to find a way to encode even larger problem instances very efficiently. In principle, you could try to scale up any NP problem. The reason why tiling is nice is that you only need to scale the size of the grid in this case (which is rather uniform).

On the other hand, if your problem is possibly only 2ExpTime-complete, then you could get away with an exponentially space-bounded alternating Turing machine simulation. If you have troubles building a 2exp grid, but you can get to exponential sizes, then this might be worth a try.


Let's assume that your three-valued logic consists of the truth values Yes, No and "unknown". We can think of these truth values as the sets $\{\top\}, \{\bot\}, \{\top,\bot\}$, and then the logical operations result in all possible values. For example, Yes and Unknown is Unknown while No and Unknown is No.

A trick known as "double rail logic" uses two binary variables to represent each truth value: Yes is 1,1; No is 0,0; and Unknown is 1;0. The connectives And and Or are implemented using two matching gates, and Not by two negation gates followed by a swap.

More generally, $k$-valued logic can be implemented by encoding each truth value using $\lceil\log_2 k\rceil$ bits. The logical operations are implemented using constant-size Boolean circuits. The advantage of the encoding above is that the circuits are very simple, in particular they read each input only once.


How can I obtain famous articles which are not available online?

It seems that:

The first paper was published in Mathematical Morphology and Its Applications to Image Processing, J. Serra and P. Soille (Eds.), Kluwer 1994, ISBN 0-7923-3093-5 (a.k.a. Proc. 2nd International Symposium on Mathematical Morphology, ISMM 1994). Amazon link.
The second paper was published in Proc. DICTA 1999. Worldcat knows about the book. It seems that there are at least two Australian libraries that have it in their collections, so it should be possible to order copies of articles from them.

Fairly often, the interlibrary services of university libraries can provide copies of papers published in hard-to-find books and journals.

As Peter Shor suggested in comments, you can also try to contact the authors. Usually, authors will be happy to send you copies of their articles – after all, researchers write papers in order to make their results as widely known as possible.


How does one extend local checkability to quantum complexity classes?

A preliminary guess at what it is you're looking for

I will give a preliminary answer, in the hopes that it might prompt you to elaborate on what promises to be quite a good question. I will assume you're referring to an idea along the lines of page 4 of [Arora+Impagliazzo+Vazirani 1993], which introduces the concept of "local checkability"  as follows:

  [...] we identify a general principle, the principle of local checkability, which appears to us to be at the root of the above-mentioned non-relativizing results [e.g. IP = PSPACE and MIP = NEXPTIME]. While this principle can be formulated in several ways, all of them express the fact that computation is a very local process, and hence checking the correctness of a computation is simpler than performing the computation itself.1 We show that "local checkability" is a fact which does not relativize.

  [...]

  1 This fact is also at the root of the Cook-Levin Theorem, and a preliminary version of this paper identified "local checkability" with the term "Cook-Levin Theorem".

Without going further into depth (awaiting a more precise description of the property which interests you), quantum computation does admit a notion of local checkability.

In the standard discrete-time models of quantum computation, all transformations are performed on small sets of bits: in this sense, computations are certainly local. So quantum computation is not any more holistic in principle than classical computation in this specific sense.

Local checkability vs. local performability

One might fear that the ability to perform local checks is undermined by the phenomenon of superposition, and in particular entanglement. If we have an operation O, which acts on a system A, how can we verify that the state of A after the operation corresponds correctly to the effect of O on the state of A before the operation, if the state of A cannot be isolated in the first place?

If we bear in mind that randomized computation is also subject to this complication — of systems not being independent of their environments — we can realise that perhaps entanglement does not cause any necessary "holisticness" to quantum computation.
As usual, entanglement has in common with probabilistic correlations the fact that they are not product distributions; so merely failing to be a product distribution cannot be something which prevents local checkability of a quantum state, if it does not also prevent probability distributions from being locally checkable. Absent this particular spectre, we may hope that there could be pertinent techniques in the quantum regime.
Of course, entanglement is more than just correlation of randomized events, because checkable properties of random correlations can be tested (with imperfect soundness) simply by sampling from the distribution, whereas this is not true in general of quantum states. Other techniques must be necessary.

The hint is provided by Arora, Impagliazzo, and Vazirani themselves in their invoking the Cook-Levin Theorem. I would suggest that we make reference to the techniques used to prove the QMA-completeness of LOCAL-HAMILTONIAN, which is the quantum analogue of the Cook-Levin Theorem. One might conjecture that any model of computation which is limited to locally performed operations, and has an analogue of the Cook-Levin theorem (i.e. complete problems for the class of constraint satisfaction problems admitting efficiently checkable certificates), is similarly subject to local checkability in some sense. A formal exploration of this idea might be an interesting subject in its own right, in the theory of computation.

Quantum local checkability via LOCAL-HAMILTONIAN

Not at all unlike the reduction of CIRCUIT-SAT to SAT, the classic proof of the NP-completeness of LOCAL-HAMILTONIAN involves testing whether or not a state satisfies local constraints imposed by simulating the evolution of a circuit.

In quantum information theory, constraints are generally presented as positive semi-definite "observable" operators, and satisfaction of all constraints amounts to the state being a ground-state for all such operators simultaneously. These "observables" correspond to events which can be measured and sampled using standard techniques.
In quantum computation (as with probability distributions), constraint testing has imperfect soundness error, but soundness can at least be tested statistically provided many copies of the distribution.

I'll elaborate later; but the specific constraints which are tested for in the proof of QMA-completeness of LOCAL-HAMILTONIAN correspond precisely to whether the state of a system A before some unitary operation, corresponds to the state of the system A after the unitary operation, this being exactly what local checkability represents.

On this basis, provided that this is what you mean, I would say that quantum computation admits a notion of local checkability.


This assumption has been used in cryptographic constructions.  Both the computational and decisions are generally believed hard by the provable security community, but I doubt a reduction to, e.g., DH will be found.  See http://homepage.ruhr-uni-bochum.de/Eike.Kiltz/papers/dh_full.pdf for discussion and references.


This is a very popular heuristic method in machine learning, known as alternating minimization. You can easily find tons of papers using it. Often the setting in which it is used is when $f(x,y)$ is convex in $x$ and $y$ separately (so each minimization step can be done via some variant of gradient descent), but not jointly convex. In this case, as RB notes, it is not apriori clear that this method converges to an optimal solution at all. A classical paper by Csiszar and Tusnady gives a general "five point criterion" for convergance to the global optimum, and proves that it holds for $f$ equal to the KL-divergence. More recently, Jain, Nethrapalli and Singhavi, and Hardt have analyzed variants of this approach for the matrix completion problem.


Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?

I think that the answer is "no", although I'm not certain and would also be interested in other examples. One thing that is known is that agnostic learning is significantly harder from an information theoretic perspective in the SQ model. Agnostically learning monotone disjunctions to error epsilon requires only $d/\epsilon^2$ examples in the PAC setting (though the task of learning might then be computationally hard...). In the SQ model, there is no agnostic learning algorithm for monotone disjunctions that has a polynomial dependence on $1/\epsilon$ in terms of the number of queries it makes, even ignoring computational considerations.


Oracles which put integer factorization in P

(This is shameless self-promotion.) If you don’t mind either assuming the generalized Riemann hypothesis (for $L$-functions of quadratic Dirichlet characters) or using randomized polynomial time, then the following search problems work:

Given integers $n,a$ such that the Jacobi symbol $\left(\frac an\right)=1$, output either a square root of $a$ modulo $n$, or a nontrivial factor of $n$.
Any PPA-complete problem, such as: given a circuit $C\colon\{0,1\}^m\to\{0,1\}^m$ computing an involution (i.e., $C(C(x))=x$ for every $x\in\{0,1\}^m$) such that $C(1^m)=1^m$, output an $x\ne1^m$ such that $C(x)=x$.
The weak pigeonhole principle: given a circuit $C\colon\{0,1\}^{2m}\to\{0,1\}^m$, output $x\ne y\in\{0,1\}^{2m}$ such that $C(x)=C(y)$.


Is it possible to verify a typechecker for a total dependently-typed language in that language's logic?

As often in these matters, the encodings are important: you could have some silly encoding of Turing machines or Gallina terms or both where an input string $\langle n\rangle$ represents "the $n$-th well-typed term in Gallina". The TM that accepts this is trivial, and you'd be able to prove correctness and termination of the machine easily.

See e.g. this Mathoverflow question: https://mathoverflow.net/questions/223109/does-the-notion-of-provably-total-function-depend-on-the-chosen-representation

However, for any reasonable representation, any proof that the "usual" type checking algorithm terminates implies termination of reduction for well-typed terms, which in turn implies consistency of the underlying logic as suggested here. This is impossible if Coq/Gallina is actually consistent, per the second incompleteness theorem.

Two obvious fixes:

Add consistency of Coq (or some equivalent or stronger statement) to your list of axioms. One possible axiom is: consistency of ZFC + $\omega$-many inaccessible cardinals. If you want something more computational, you can add a strong enough form of induction-recursion. I don't think anyone's worked out the details for the CiC yet, but I imagine they're very similar to those for (for instance) Agda.
Add some constraints on the representation of well-typed terms to be checked. In Gallina, terms carry implicit computational content, to be executed as the usual type-checking algorithm runs. However one could imagine an explicit form of the language, where each term comes with a natural number representing the "gas" it is allowed to use, aka the number of steps it must not exceed during reduction. Then the correctness proof for the type-checking algorithm would be conditional on not exceeding this explicit limit of computation.

Note that talking about computability of these axioms doesn't make much sense: a single axiom on it's own is always computable in the sense of computable sets which is usually what we mean when we talk about computable theories.

However an axiom may or may not have computational content, for example an axiom $\exists x,\ P$ may cause a theory to lose the existence property, if there is no closed term $t$ which satisfies $P[t/x]$. However, an axiom that asserts that a Turing machine $T$ halts on all inputs is always correct from a computable (constructive) point of view if $T$ does indeed always halt in the "true" world.


Why is finding the ground state of a Hamiltonian in QMA?

There needs to be a gap between the eigenvalue of the groundspace and the first excited state that is inverse-polynomial in the system size, and indeed such a promise is required for the QMA-complete Local Hamiltonian problem. Please refer to the formal definition of the Local Hamiltonian problem and the QMA-completness proof, e.g. Definition 10 and Theorem 1 in Nagaj's thesis. If the gap is inverse-exponentially small, then the promise is not satisfied by that local Hamiltonian instance and the QMA-completness proof does not apply since a key assumption is not satisfied.


How can we know that formal methods work?

Regarding 4: There's plenty of work combining formal methods and testing. Googling "formal methods testing" reveals quite a large amount of work. Although there are many different goals of such work, one of the key goals is to generate more effective test suites. This talk gives a nice introduction, based on model checking.

Also regarding the issue software security, which has been edited out of the question: formal methods need to work harder to deliver in that realm. Typically one writes a specification for a piece of software and verifies that the specification is satisfied, namely, that when the input satisfies the precondition that the output satisfies the postcondition. To ensure secure software one also needs to check also that the software behaves sensibly for input that does not satisfy the precondition. (This is of course equivalent to setting the precondition to true for all input.) The space of all inputs is typically much larger than just well-formed input, but typically this is one place where even functionally correct software can be violated, simply by violating its assumptions.

Regarding point 3: Some work has been done for verifying systems in settings where faults are explicitly modelled, including Faulty Logic:  Reasoning About Fault-tolerant Programs. Matthew Meola and David Walker. European Symposium on Programming, 2010. Work on probabilistic model checking and probabilistic verification certainly both also address the issue of faults to some degree.


polytime transformation from a graph to a set of binary strings

Yes. If the graph is regular there is a trivial scheme. Fix some ordering of the edges, and define $f(v)$ to be $0$ at the corresponding position of a particular edge if $v$ is not incident to that edge, and $1$ is $v$ is incident to the edge.

If the graph is $k$-regular, then $d_H(f(v),f(u))$ is $2k-2$ if $u$ and $v$ are adjacent, and $2k$ if they are not.

If the graph is not regular, then we may pad the graph with additional degree $1$ vertices such that all of the original vertices have the same degree. Then the above scheme will work.


Consequences of Unique Games being a NPI problem

To address your revised question:

  If UGC is false, is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover?

If it were known that it is NP-hard to approximate VC better than a factor of 2, even if the UGC is false, then we would unconditionally know that approximating VC to a factor better than 2 is NP-hard. This also works with a factor smaller than 2. If it were known that if UGC is false, then VC is NP-hard to approximate better than a factor of (say) 1.5, then we would know that it is (unconditionally) NP-hard to approximate it better than a factor of 1.5.

Since we don't know that, I guess the best we can say if the UGC is false is that it's NP-hard to approximate it to within a factor of 1.3606 by the result of Dinur and Safra (2005). (I think that's the current best-known inapproximability result.)


Efficient Algorithm for bilinear pairing on ECC

I realize this does not do justice to the breadth of your questions but as a starting reference, you may be interested in the benchmark times for various pairings implemented in the pairing-based cryptography (PBC) library:

http://crypto.stanford.edu/pbc/times.html

They reference RSA decryption to give a sense of time relative to a standard operation (although it isn't as useful as knowing a DL or ECC-DL operation). The main developer, Ben Lynn, also did his PhD on PBC implementations—the dissertation may answer some of your questions.


Alternate proofs of Immerman-Szelepcsenyi theorem

Since we don't seem to have any answers, can I make a comment?

Suppose we are given $n$ bits, $X=x_1,\cdots,x_n$ and we have to complement each bit to get $\neg x_1,\cdots, \neg x_n.$ The only constraint is that the circuit that does so should be monotone. We obviously need some additional information to do this and here is one such.

Suppose $k$ is the number of ones in the input and somehow we have this as advice. Then it is easy to see that $\neg x_i = Th^{n-1}_{k}(X-x_i)$ (i.e., on all inputs except $x_i$). Of course, the construction is monotone.

With this construction, the motivation for inductive counting is clear (at least to me). It is worth asking what other advice would work? I don't know of any other. But this may hold the key to your question.


The basic sum-of-squares proof system, introduced under the name of Positivstellensatz refutations by Grigoriev and Vorobjov, is a “static” proof system for showing that a set of polynomial equations and inequations
$$S=\{f_1=0,\dots,f_k=0,h_1\ge0,\dots,h_m\ge0\},$$
where $f_1,\dots,f_k,h_1,\dots,h_m\in\mathbb R[x_1,\dots,x_n]$, has no common solution in $\mathbb R^n$: a refutation of $S$ is given by polynomials $g_i$ and $e_{I,j}$ such that
$$\tag{$*$}-1=\sum_{i=1}^kg_if_i+\sum_{I\subseteq\{1,\dots,m\}}\sum_je_{I,j}^2\prod_{i\in I}h_i.$$
(One could work with any real-closed field in place of $\mathbb R$.) Stengle’s Positivstellensatz guarantees that $S$ has a refutation if and only if it has no solution. The main complexity measure here is the degree of the refutation, which is the maximum of total degrees of the polynomials that appear under the sum signs in $(*)$, that is, $g_if_i$ and $e_{I,j}^2\prod_{i\in I}h_i$.

As usual with algebraic proof systems, one can also consider it as a refutation system for unsatisfiable Boolean formulas $\phi$ by including in $S$ the axioms $x_i^2-x_i$ for each variable $x_i$, and a translation of $\phi$ by polynomial inequalities.

More on the history and development of SOS systems can be found in http://arxiv.org/abs/1211.1958 .


Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

It seems not.  Ian Parberry makes reference to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further deduce that the problem of verifying a sorting network is $co$-$NP$ complete.  I can't find the original paper right away, but certainly it matches (my) intuition.

Edit to add: It is actually very easy to find such a network that misses exactly one string.  The string to be missed will be $(1,0,\ldots,0)$.  Now you just want a circuit that sorts the last $n-1$ bits, then sorts the first $n-1$ bits.  This circuit will sort anything with at least two $1$s, will obviously sort the all-zero string, and will sort any string starting with $0$.


What notable automaton models have polynomially-decidable containment?

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can be solved in polynomial time. For more details, see the paper by Alur and Madhusudan, especially Chapter 6.

By the way, the nondeterministic variant of visibly pushdown automata is exponentially more succinct than the deterministic variant, but there the language inclusion problem is EXPTIME-complete and thus intractable.

Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words". Journal of the ACM 56(3): 1–43.


On the realisation of monoids as syntactic monoids of languages

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without paywall it would be great. I requested the full-text on ResearchGate.

Title: Which Finite Monoids are Syntactic Monoids of Rational omega-Languages.

Authors: Phan Trung Huy, Igor Litovsky, Do Long Van

Abstract: A notion of ω-rigid sets for a finite monoid is introduced. We prove that a finite monoid M is the Arnold's syntactic monoid of some rational ω-language (ω-syntactic for short) if and only if there exists an ω-rigid set for M. This property is shown to be decidable for the finite monoids. Relationship between the family of ω-syntactic monoids and that of ∗-syntactic monoids (i.e. the syntactic monoids of rational languages of finite words) is established.

Additionally, the wikipedia page on syntactic monoids states:

Every finite monoid is homomorphic to the syntactic monoid of some non-trivial language,[1] but not every finite monoid is isomorphic to a syntactic monoid.[2]
Every finite group is isomorphic to the syntactic monoid of some non-trivial language.[1]

[1] McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004) p.233


Document references describing weaknesses for cutting planes and algebraic proof system?

For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the pigeonhole principle in polynomial calculus (Razborov '98, IPS '99), and an exponential lower bound for the clique-colouring formula in cutting planes (Pudlák '99). Nowadays there are a few more examples to choose from.


This question may not have been phrased to make it look research-level, but trying to compute the minimum number of crossings in a layout of a given graph is definitely a research-level problem.

One complication is that there is more than one definition of the number of crossings: see Pach, "Which crossing number is it, anyway?", FOCS 1998.

If you allow a drawing with curved edges, and count the number of intersection points of edges, then the problem is fixed-parameter tractable: it can be solved in time linear in the number of vertices in the graph, but exponential or worse in the number of crossings. See Kawarabayashi and Reed, "Computing crossing number in linear time", STOC 2007, as well as several previous related papers cited by them.

I don't think the Kawarabayashi-Reed algorithm is practical, but if you restrict attention to drawings with straight line segment edges (giving a different crossing number) there are more practical (though still exponential) approaches based on integer programming. See e.g. Jünger et al, "A polyhedral approach to the multi-layer crossing minimization problem", Graph Drawing 1997, and Buchheim et al, "A branch-and-cut approach to the crossingnumber problem", Discrete Optimization 2008.

If you want to test if there are no crossings at all (i.e. is the graph planar), then theoretically it has been known for decades that it can be solved in linear time, so this is no longer research-level. But finding a linear time algorithm that is also easy to implement and run in practice is not entirely a solved problem.


Finding $x_1,x_2,...,x_k$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is minimal

Your algorithm is correct and its running time is in $\Theta(n)$ which is exponential to the input size. But we can use simple greedy algorithm to achive $O(\log n)$. Find largest number $i$ such that $i! \le n$. To do so just simply iterate through numbers in $1,\cdots, \log n +1$. And do the same for $n -i!$.


Permuting the columns of a 0/1-matrix to avoid short segments

The algorithm below runs in time $O(n\log n)$, but not $O(n)$. On the other hand, it permutes the columns in such a way that there are only $O(\log^2n \cdot\log\log n)$ short segments in the end.

Let us at first describe $O(n\log n)$-time algorithm for the case when $n + 1$ is prime. Then we may identify columns $\{1, 2, \ldots, n\}$ with elements of $(\mathbb{F}_{n + 1})^*$. The idea is to consider permutations of the form $x\mapsto \gamma x$ for $\gamma\in(\mathbb{F}_{n + 1})^*$. We will show that at least one $\gamma$ is good for us and how to find such $\gamma$ in $O(n\log n)$ time.

We start by finding $x^{-1}$ for every $x\in(\mathbb{F}_{n + 1})^*$. For each $x$ this takes $O(\log n)$ time by Euclidean algorithm, in total $O(n\log n)$.

Then assume that positions of stars are
$$(a_1, b_1), \ldots, (a_n, b_n).$$
Let $L$ be the list of all $(i, j)$ such that $i\neq j$ and $a_i = a_j$ (pairs of stars which are from the same row). The size of $L$ is $O(t_1^2 + \ldots + t_n^2)$, where $t_i$ is the number of stars from the $i^{th}$ row. Since $t_i\le\log n$, we have
$$|L| = O(t_1^2 + \ldots + t_n^2) = O((t_1 + \ldots + t_n)\cdot \log n) = O(n\log n).$$

We then create an array $M$ of size $n$, where $M[\rho]$ is equal to the number of $(i, j)\in L$ s.t. $\rho = b_i - b_j \pmod{n + 1}$. Clearly, computing $M$ takes $O(|L|) =O(n\log n)$ time.

Then we define another array $W$ of size $n$. Namely, $W[\gamma]$ is defined as follows
$$W[\gamma] = \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho].$$

Now let us prove that $W[\gamma]$ is an upper bound on the number of short segments after permuting columns according to $x\mapsto \gamma x$. Indeed, the number of short segments is at most the number of $(i, j)\in L$ such that for some $u, v\in\{1, 2, \ldots, n\}, u\neq v, |u - v| \le \log n$ it holds that $\gamma b_i = u\pmod{n + 1}, \gamma b_j = v\pmod{n + 1}$. In turn, this is at most the number of $(i, j) \in L$ s.t. for some $k\in [-\log n, \log n], k\neq 0$ it holds that $\gamma(b_i - b_j) = k \pmod{n + 1}$. This is exactly $\sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho]$.

Now it only remains to note that
$$W[\gamma] =  \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} M[\gamma^{-1} k]$$
Here we use the fact  that $n + 1$ is prime. Since we have all $\gamma^{-1}$ precomputed, it takes only $O(n\log n)$ time to compute $W$.  On the other hand for fixed $k$ all $\gamma^{-1} k$ are different, i.e. $\sum\limits_{\gamma} W[\gamma] \le 2\log n \sum\limits_{\rho} M[\rho] = 2\log n \cdot |L| = O(n\log^2 n)$.   Hence there exists $\gamma$ such that $W[\gamma] = O(n\log^2 n/n) = O(\log^2 n)$. We find any such $\gamma$ and permute columns according to $x\mapsto \gamma x$.

The problem in general case is that now not all $\gamma$'s from $\mathbb{Z}_{n + 1}\setminus \{0\}$ are reversible. However, there are $\Omega(n/\log\log n)$ of them, so we start our algorithm by finding all reversible $\gamma\in\mathbb{Z}_{n + 1}\setminus \{0\}$  in $O(n\log n)$ time (once again, Euclidean algorithm helps). We then do exactly the same thing but only for reversible $\gamma$'s. In the end we will have a slightly worse upper bound on the smallest $W[\gamma]$, namely $O(\log^2(n)\log\log n)$ (because we take into account only $\Omega(n/\log\log n)$ of $\gamma$'s).


Niel de Beausdrap found this article. The authors (Schumacher and Werner) propose a definition of quantum cellular automata and prove they are always invertible (Corrolary 7 on p. 10). Nominally their definition is different since they use the norm-completion of the algebra $A_\Gamma$ and impose a locality condition. However, it is actually equivalent.

Their locality condition states that the image of $A_x$ has to be contained in $A_S$ for some finite S. However, if we avoid the norm completion it holds automatically since any element of the direct limit is in $A_S$ for some finite S and $A_x$ is finite dimensional.

Moreover, an endomorphism of $A_\Gamma$ is always continuous hence extends to the completion. This is because the matrix norm can be defined algebrically as the maximal |lambda| for which a*a - lambda is non-invertible.

Representability follows from their Theorem 6 on p. 10 which gives a rather explicit (modulo some complicated constraints) description of all nearest-neighbour quantum cellular automata. As discussed on p. 9 this description encodes two finite-dimensional unitary operators. These operators can be easily used to construct the operator $U$ I seek.

As discussed on p. 8 the case of non-nearest-neighbour can be easily reduced to this case


Assignment problem with multiple workers for each job

This problem is a special case of the b-matching problem, and hence can be solved in polynomial time. Extensive information on b-matchings can be found for instance in the book:

László Lovász and Michael D. Plummer:
Matching Theory
ISBN-10: 0-8218-4759-7
ISBN-13: 978-0-8218-4759-6


Hardness when restricted to an infinite number of far apart instance sizes

The algorithmic problem is to tell if two finite groups (given by their multiplication tables) are isomorphic.
It is not known if this can be solved in polynomial time in the cardinality of the group. But for groups of prime order this can be solved in constant time.


The cozy neighborhoods of "P" and of "NP-hard"

The very terms "on the P-side" and "on the NP-side," and of course the question title, encourage us to imagine a "cozy neighborhood" surrounding P and another "cozy neighborhood" surrounding the NP-hard problems.  However, I'd like to argue that these two neighborhoods are not so "cozy" at all!

As a first observation, there are problems "on the P-side" that seem "morally" much closer to NP-hard than to P.  One example, anticipated by Gil of course, is the general problem of inverting one-way functions (depending on exactly what type of reductions are allowed; see Bogdanov-Trevisan or Akavia et al.).

Conversely, there are also problems "on the NP-side" that seem "arbitrarily far" from being NP-hard.  One silly example is a random language L, with probability 1 over L!  For if such an L is in P, then 0=1 and math is inconsistent, and therefore PH collapses also. ;-D

(Note that a random language L is also "on the P-side," with probability 1 over L.  For almost all such L's have the property that if they're NP-hard, then NP⊆BPP and PH collapses.  And this gives a proof, much simpler than the appeal to Ladner's Theorem, that there exist languages on both "sides."  Indeed, it shows that of the uncountable infinity of languages, "almost all" of them -- in fact, 100% -- are on both sides!)

This sounds like juvenile game-playing, but there's a serious lesson I'd like to draw from it.  I'd argue that, even though QUANTUM SAMPLING is formally "on the NP-side," that problem is barely any closer to being "morally NP-hard" than the random language L was.  Arkhipov and I (and independently, Bremner-Jozsa-Shepherd) showed that, if QUANTUM SAMPLING is in P (or rather, in SampBPP, the class of polynomially-solvable sampling problems), then P#P = BPPNP, and therefore the polynomial hierarchy collapses.  Yet if you're a BPP machine, an oracle for BosonSampling would, as far as we know, bring you no closer to solving NP-complete problems than a random oracle would.  Only if you already have the ability to solve NP-complete problems -- say, if you're a BPPNP machine -- do you "notice" that the BosonSampling oracle boosts your capabilities even further, to #P.  But the property of boosting NP up to #P seems different than, and maybe even "orthogonal to," the property of being NP-hard on one's own.

Incidentally, a wonderful open problem suggested by Gil's question is whether BosonSampling is also "on the P-side."  That is, can we show that if NP reduces to BosonSampling then PH collapses?  While I might be missing something obvious, at first glance I have no clue how to prove such a thing, any more than I know how to prove the stronger implication that if NP ⊆ BQP then PH collapses.


The problem for an arbitrary binary code is NP-hard.

Reference: Alexander Vardy, “The Intractability of Computing
the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757--1766.


Complexity of counting products of commuting operators drawn from a specific set.

For $D$ unrestricted, computing $N_D$ exactly is equivalent to evaluating the Tutte polynomial of a graph: the values $N_D$ determine the weight enumerator of a linear code, also known as the Tutte polynomial of a binary matroid, and your restriction on the $\lambda^i$ corresponds to the linear code being given by a basis of vectors of Hamming weight 2, which is the just the usual cycle matroid of a graph.

On the other hand, we can calculate $N_{n-2k}$ if $k$ is constant in polynomial time as follows. There are $O(n^k)$ diagonal matrices $C$ with $n-k$ ones and $k$ minus-ones. These can be enumerated in polynomial time for fixed $k$. $C$ can be considered as a point in $\mathbb{F}_2^n$ and each $b$ can be considered as a point in $\mathbb{F}_2^m$ where $m$ is the number of $\lambda^i$s. This turns multiplication into addition, so the definition of $C_b$ becomes $C_{b_j}=\sum \lambda^i_{jj} b_i$. In Diestel's book on graph theory the values $b$ such that $\sum \lambda^i_{jj} b_i=0$ are called the cycle space of the graph.


Kolmogorov Complexity of the composition of two computable functions

Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.

Edit: You might need to pay additional bits for the composition, as for ordered pairings -- as observed by  Emil Jeřábek in the comments.


The connections between neurons do not form scale-free networks, I think. See e.g. Figure 1 on p.181 of http://www.indiana.edu/~cortex/Koetter_chapter_modified.pdf and observe that the vertex degrees only span a single order of magnitude.


Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We can get a $(2,2)$ bi-criteria approximation as follows (or more generally $(1+\varepsilon, 1 + 1/\varepsilon)$ bi-criteria approximation).

We may assume that we know the cost of the optimal solution. Denote it by $OPT$. Let
$$w'(u,v) = \frac{w(u,v)}{OPT} + \frac{1}{k}.$$
Consider the optimal solution $(V_1, V_2)$. Then
$$\sum_{(u,v) \in E(V_1, V_2)} w'(u,v) = \sum_{(u,v) \in E(V_1, V_2)} \left(\frac{w(u,v)}{OPT} + \frac{1}{k}\right) = 1 + \frac{|E(V_1,V_2)|}{k} \leq 2.$$

Our algorithm finds the minimum directed $s$-$t$ cut $(V_1', V_2')$ in $G$ with edge weights $w'$. The cost of this cut is at most $2$. Therefore, the cut $(V_1', V_2')$ cuts at most
$$E(V_1', V_2') = \sum_{(u,v)\in E(V_1',V_2') } 1 \leq k \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2k$$
edges. The cost of the cut is at most
$$\sum_{(u,v)\in E(V_1',V_2')} w(u,v) \leq OPT \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2OPT.$$


Optimal evaluation of polynomials / rational functions

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic polynomials. The algorithm requires factoring polynomials. There is another algorithm from Rabin & Winograd that only requires division, but runs in $\frac{n}{2} + \log n$.

Your question is about automatically identifying special structure that can be exploited to optimize further, which these algorithms do not do.

Square-free factorization can be used to efficiently find repeated terms like $p(x)\cdot (q(x))^7$. It won't find your sum example.

If $n$ is not too big, it might actually be feasible to iterate through all circuits with $\frac{n}{2} + 1$ multiplication gates and arbitrary addition/subtraction gates. Reduce them symbolically to coefficient form and try to solve the resulting set of polynomial equations. I guess this last step would the hardest.


Concerning 3, I believe $\mathrm{PP\subseteq\oplus P^{C_=P}}$, as there are at least $a$ numbers $x<2^n$ satisfying $P(x)$ if and only if the number of $y<2^n$ such that $P(y)\land|\{x\le y:P(x)\}|=a$ is odd. (Note that there is always at most one such $y$. That is, the argument actually shows $\mathrm{PP\subseteq UP^{C_=P}}$. (In fact, it even shows $\mathrm{UP^{PP}=UP^{C_=P}=UP^{C_=P[1]}}$.))


Time/Space Requirements of Verifying or Falsifying a First-Order Statement

The theory of real closed fields (RCF) is complete for the first order theory of real numbers in the language you described. Therefore it is equivalent to checking if RCF proves the formula.

By Tarski's quantifier elimination for RCF this can be computed. Tarski's algorithms complexity is non-elementary and there is a doubly exponential lowerbound for the problem.

A more efficient algorithm than Tarski's algorithm is given by Saugata Basu "An Improved Algorithm for Quantifier Elimination Over Real Closed Fields", FOCS 1997 (which seems to be almost optimal, see Theorem 1) (a draft of the paper is available here).

Also check Saugata Basu, "New Results on Quantifier Elimination Over Real Closed Fields and Applications to Constraint Databases", Journal of the ACM, 1999.


Re your question 1: Guillemot and Marx, "Finding small patterns in permutations in linear time", SODA 2014 solves these problems in linear time, and more generally gives a linear time recognition algorithm for every fixed permutation class with a finite basis.

I don't know of an answer for question 2 (when the subpattern may be variable in size).


Bellman-Ford with Non-edge-decomposable Path Weights

No, Bellman-Ford won't work because the problem you described is NP-hard.

This is pretty easy to prove. I've been able to come up with several reductions using the same strategy. The general idea is to make it so that in the path you have several sections that can be chosen independently; then the overall question becomes whether you can coordinate all those choices so as to minimize the sum of the weights of the items in the chosen subpaths. You can easily set up the independent choices by using a sequence of "bottleneck" vertices $S = v_0, v_1, \ldots, v_{n-1}, v_n=T$ and making several paths between each $v_i$ and $v_{i+1}$ (the choices of which path piece from $v_i$ to $v_{i+1}$ to take for each $i$ are the independent choices I was talking about earlier).

For example, you can reduce from 3SAT. For each variable $x$, make one of the subpath choices be between item $x$ and item $\neg x$. For each clause, make one of the choices be between the items corresponding to the literals in the clause. For each variable either the variable, the negation, or both must be in any path. The only way to get away with having only one version of each variable in the path is if there exists an assignment that makes every clause true. If each item has weight 1, then the overall weight of the items in the path will equal the number of variables iff the 3SAT instance is satisfiable.

As another example, you can reduce from set cover. For each set that you want to cover, make a piece of the path be a choice that lets you chose any of the items in that set. Then to minimize the number items chosen in all, you have to cover all the sets with as few items as possible.


Encoding of binary trees as a regular language?

As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C_n$. It is known that the Catalan numbers have generating function

$C(x) = \frac{1-\sqrt{1-4x}}{2x}$.

On the other hand, it is known (Chomsky, Schützenberger; 1963) that regular languages have rational generating functions.

Clearly, $C$ is not rational. This implies that there is no regular encoding of full binary trees where each tree has a unique representation.

(Note that the generating function of arbitrary binary trees is not rational, either.)