Is Locality preserving projections (LPP) method the same as Laplacian eigenmap method?

There is a subtle difference, which can be difficult to recognize. They both minimize the same objective:

$\sum_{i,j} w_{ij} || y_i - y_j ||^2_2$

However, they parametrize the predictor on y differently. Locality preserving projections is linear because the parameterization is linear: $y_i = x_iW$. Laplacian eigenmaps is non-linear because the parametrization uses a kernel: $y_i = k_iA$. Kernel LPP is equivalent to Laplacian eigenmaps.

For a good description and a summary showing the connections between all these different dimensionality reduction algorithms, see the paper:

TRACE OPTIMIZATION AND EIGENPROBLEMS IN DIMENSION REDUCTION METHODS, KOKIOPOULOU et al.

or the summary table in Section 2.7 in the thesis:

Regularized Factor Models, Martha White


(N)DFA with same initial/accepting state(s)

Finite automata in which the initial state is also the unique accepting state have the form $r^∗$, where $r$ is some regular expression. However, as J.-E. Pin points out below, the converse is not true: there are languages of the form $r^*$ which are not accepted by a DFA with a unique accepting state.

Intuitively, given a sequence of states $q_0, \ldots, q_n$ such that $q_0 = q_n$ either $n = 0$ or the underlying state diagram must have a cycle involving $q_0$. The latter case is captured algebraically by the Kleene star.


Finding the two shortest paths while minimizing the number of nearby/common edges

If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.

The algorithm for shortest pair edge disjoint paths is known as Suurballe's algorithm.

https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm

If the cost is some arbitrary function the problem can be NP-complete.
e.g assuming edge weights one, let the cost function be as $|P_1| + |P_2| + |P_1∩P_2| + 2\cdot |G-P_1\cup P_2|$.
Then the cost is always $ \ge |G|+2$ (if source and terminal are distinct vertices). The equality holds iff the graph has a Hamiltonian cycle.


The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky.

For any fixed $\varepsilon>0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard.
There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{4g, g+4n\}$: Assign an arbitrary cyclic order to the edges leaving each vertex (keeping loops and parallel edges together).  In other words, when the genus is large, every embedding is a good approximation of the best embedding.
There is a polynomial-time $O(\sqrt{n})$-approximation algorithm for bounded-degree graphs.

It is an open question whether there is an efficient constant-factor approximation algorithm.


[I'm posting this as an answer despite being in $\mathsf{PromiseMA}$ because a) it exhibits a different kind of $\mathsf{MA}$-style algorithm, and b) @PeterShor asked  and it was too long for a comment.]
Over any finite field $\mathbb{F}$, the following problem is in $\mathsf{PromiseMA}$:

Input: A set of $\mathbb{F}$-polynomials $F_1(\vec{x}), \dotsc, F_m(\vec{x})$
Decide: Is there no solution to $F_1(\vec{x}) = \dotsb = F_m(\vec{x}) = 0$ over the algebraic closure $\overline{\mathbb{F}}$
Promise: Either there is a solution over $\overline{\mathbb{F}}$, or there is a poly-size $\mathbb{F}$-algebraic circuit $C(\vec{x}, y_1, \dotsc, y_m)$ such that $C(\vec{x}, \vec{0}) = 0$ and $C(\vec{x}, \vec{F}(\vec{x})) = 1$ (identically as polynomials)

The $\mathsf{MA}$-style algorithm guesses the circuit $C$, and then verifies the two conditions using polynomial identity testing, which is in $\mathsf{coRP}$ by Schwarz-Zippell-DeMillo-Lipton.
Note that, without the restriction of poly-size, Hilbert's Nullstellensatz guarantees that there is no solution if and only if there is some circuit $C$ satisfying the above two conditions. (On the other hand, assuming $\mathsf{NP} \not\subseteq \mathsf{coMA}$, there are systems of equations coming from algebrizations of 3SAT for which the above poly-size promise is violated.)
(This is the basis of an algebraic proof system from recent joint work with Toniann Pitassi, but for the purposes of this answer similar ideas go back to an earlier paper of Pitassi's as well as her 1998 ICM talk, and to the so-called Nullstellensatz and Polynomial Calculus proof systems.)


Is there a characteristic function of a tree?

First, Yixin Cao's comment that similarity is problem-specific is entirely correct. It doesn't make sense to talk about trees being similar or not, without having an idea of what you are trying to compute.

That caveat aside, it is indeed very common to equip trees with metrics. One of the most common is to equip them with an ultrametric, where we define a distance function on trees:

$$d(t_1, t_2) = 2^{-n}$$

where $n$ is the first level at which the branching structure of $t_1$ and $t_2$  differ. This is a generalization of the Cantor metric for sequences, where two strings have a distance of $2^-n$ where $n$ is the first position at which they differ.

The intuition behind this is a temporal one -- we think of a sequence as representing a series of events, and we want to say that two series are more similar the longer we have to wait to distinguish them. When we move from sequences to trees, it's a bit like moving from a linear model of time to a branching model of time. Trees with this kind of ultrametric are, IIRC, used a lot in phylogenetics, where they are called dendrograms, and used to work out possible lineages for species.

Another important metric on sequences is the Levenshtein distance, or edit distance. This measures the number of edits you have to make to change one string into another one. Generalizing this to trees gives you what is unsurprisingly called a "tree edit distance". Here's a survey by Phillip Bille on tree edit distances:

A survey on tree edit distance and related problems, Philip Bille. Theoretical Computer Science, 2004.

These tree edit distances are used for problems like detecting plagiarism in student source code, or diff algorithms for HTML and XML.


Is there a randomized algorithm for set-cover?

Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover.

input: collection of sets over $n$ elements, upper bound $U$ on opt

output: w/probability $\ge 1/2$, a set cover of size $O(U \ln n)$.

Let $K=\lceil \ln(2n)U/0.99\rceil$.  Let $T=\ln(100)$.
Create $K$ tokens, each with an associated unit-rate Poisson process.
As time $t$ increases continuously from $0$ to $T$, do the following:
When a Poisson process fires at time $t$,
remove its token from its current set (if any),
then place it on a set $s$ chosen to maximize
$$
\sum_{e\in s}
\Big(
\frac{1-1/U}{1/f(t) - 1/U}
\Big)^{C^{(t)}_e},
$$
where $C^{(t)}_e$ denotes the number of tokens (other than the firing token)
currently covering element $e$, and $f(t) \doteq 1-\exp(-(T-t))$.
Return the sets that have tokens on them.

When a token fires, it moves
to a set whose elements have largest total ``weight''.
Initially, when $t\approx 0$, the weight of element $e$
is about $.99^{C_e} \approx 1$,
so the algorithm essentially moves tokens onto the largest sets.
When $t\approx T-\ln 2$, the weight of an element $e$ is about $.5^{C_e}$.
Thus, each token on a set covering $e$ cuts $e$'s weight by a factor of $1/2$.
Finally, when $t\approx T-\epsilon$, an element $e$ has weight about
$\epsilon^{C_e}$, so only uncovered (or minimally covered) elements contribute significant weight.

If $U$ is unknown,
then binary search can be used
to find the smallest integer $U$
between $1$ and $n$
for which the algorithm works.

Here is the approximation guarantee:

Theorem.
If there exists a fractional set cover of size $U$,
then, with probability at least 1/2,  the algorithm returns
a set cover of size at most $\lceil \ln(2n)U/0.99\rceil$.

For the derivation and proof see https://algnotes.info/on/obliv/greedy/set-cover-grasp/.

One more

Oh, and there is a well-known randomized parallel algorithm for set cover, namely Primal-dual RNC approximation algorithms for set cover and covering integer programs by Rajagopalan and Vazirani.


Lower bound on the element distinctness problem

Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals:

  A. C.-C. Yao, Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains, SIAM J. Comput., 20(4), 655–668.

Rather, Yao has to re-prove the Milnor-Thom-Oleinik-Petrovski bound on the number of connected components of a semi-algebraic variety over $\mathbb{R}$ more or less from scratch to get it to work over $\mathbb{Q}$, where the notion of connectedness is a bit thornier. He also needs to assume that the problem is scale-invariant and "rationally dispersed" (see the paper), and only counts connected components of nonzero measure. These technical conditions already hint that it is not a simple consequence of the result over the reals.


Using Kolmogorov complexity as input "size"

Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So
$$f_n = \Theta(n).$$
On the other hand,
$$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Note that $K(2^{2^n}) = O(n)$. Thus $$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ and $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$. Similarly, $K(2^{\dots^{2^{2^n}}}) = O(n)$; thus $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$ “grows very rapidly”. Moreover, it's not hard to see that there is no computable upper bound for $f_n^K$.


Is there an algorithm which gets incrementally "smarter" as it runs?

Let's assume you're working on a toy programming language Flarp late at night and someone whispers in your ear a great deal of its particular Chaitin's Omega and you're clever enough to realize what you've got and type it down.

You could then write a special interpreter function F and a little script that enumerates Flarp programs and runs them as follows (from the wikipedia page):

  Given the first n digits of Ω and a k≤n, the algorithm enumerates the
  domain of F until enough elements of the domain have been found so
  that the probability they represent is within 2−(k+1) of Ω. After this
  point, no additional program of length k can be in the domain, because
  each of these would add 2−k to the measure, which is impossible. Thus
  the set of strings of length k in the domain is exactly the set of
  such strings already enumerated.

As your algorithm ran and enumerated more and more programs, the size of programs for which you can solve the halting problem will grow as well, allowing you answer many interesting questions like Goldbach's conjecture, etc.

(obviously this answer is a bit of a joke. I'm also not an expert on any of the above and may have misrepresented things)


how to achieve a topological sort of an given sequence with minimum swaps

This problem is NP-complete. I will prove NP-hardness below

Source Problem

Colored Token Swapping on Cliques:

In the colored token swapping problem, we are given a graph with a colored token placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on two adjacent vertices switch places. We are given a number $k$ and asked whether a sequence of at most $k$ swaps can result in each vertex having a token of the target color for that vertex.

In the colored token swapping on cliques problem, the graph is a clique (and so a swap can occur between any two tokens). Also, we can assume without loss of generality that the target coloring is reasonable; that is, we assume that for each color, the number of tokens of that color equals the number of vertices with that color as the target color.

This problem is shown NP-hard in Lemma 18 of http://www.lamsade.dauphine.fr/~bonnet/publi/token-swapping.pdf.

Reduction

We are given a colored token swapping on cliques instance. In other words, we are given

$n$, the size of the clique. WLOG we can assume that the vertices of the clique are $1, 2, \ldots, n$.
A function $t$ assigning a target color to each vertex. Since there are at most $n$ colors, we will also number the colors $1, 2, \ldots, n$ (some colors may be left unused).
A function $s$ assigning a starting token color to each vertex.
A number $k$.

Since we can reorder the vertices without changing the problem, we can assume WLOG that in $t$, all vertices with the same target color are numerically contiguous (if vertices $i$ and $j$ have the same target color then every vertex numerically between them also has that same target color). Furthermore, assume WLOG that the color values are chosen so that $t$ is increasing (which we can do since we can permute color names without changing the problem).

Now we will construct an instance of your problem (given a set of constraints, a sequence, and a value $k$, can the sequence be reordered in at most $k$ swaps so that the result is a topological sort of the DAG implied by the constraints.)

The value of $k$ we will use for your problem will equal the value $k$ from the token swapping instance.

The sequence we will use for the instance of your problem is $[1, 2, \ldots, n]$.

Next, construct a permutation $p$ on $\{1, 2, \ldots, n\}$ such that $t(x) = s(p(x))$. Notice that this is just a matching between $\{1, \ldots, n\}$ and $\{1, \ldots, n\}$ such that $i$ can be matched to $j$ only if the target color at vertex $i$ matches the color of the token initially at $j$.

Define $C_x$ to equal $\{p(i)~|~t(i) = x\}= p(\{i~|~t(i) = x\}) = p(t^{-1}(x))$. Notice that $C_1, C_2, \ldots, C_n$ partition $\{1, \ldots, n\}$. We add constraints so that if $i < j$, all the elements of $C_i$ must come before all the elements of $C_j$. This set of constraints is satisfied if and only if the elements of $C_1$ in any order occur before the elements of $C_2$ in any order, which themselves occur before the elements of $C_3$ in any order, etc...

Correctness

There is a correspondence between a token swapping instance and the instance of your problem produced by this reduction. Assign each token a number from $1$ to $n$. In particular, assign the token initially at vertex $i$ (according to $s$) the value $i$.

Now the correspondence is that at all times, token $i$ is at vertex $j$ if and only if the value $i$ is at position $j$ of the sequence.

Certainly this correspondence holds at the beginning: each vertex $i$ contains token $i$ and the initial sequence is $[1, 2, \ldots, n]$, which if 1-indexed has value $i$ at position $i$.

Under this correspondence, a swap in the token swapping instance corresponds to a swap in the sequence. If we have tokens $x_1$ and $x_2$ at vertices $y_1$ and $y_2$, then swapping those two tokens results in $x_1$ at $y_2$ and $x_2$ at $y_1$. Similarly, if we have values $x_1$ and $x_2$ at positions $y_1$ and $y_2$ of the sequence, then swapping those two values results in $x_1$ at position $y_2$ and $x_2$ at position $y_1$. Clearly, if we correspond swaps in this way, the invariant given by the correspondence is maintained.

Finally, under this correspondence, a solved token swapping instance (each token at a vertex whose target color matches the token's color) corresponds to a sequence that satisfies all constraints. This is not obvious, so here's a proof:

A sequence satisfies all the constraints if and only if the elements are in the order of $C_1$ elements first, then $C_2$ elements, etc... But the number of $C_1$ elements is $|C_1| = |p(t^{-1}(1))| = |t^{-1}(1)|$, which is the number of vertices with target color $1$. Since $t$ is increasing, these are the lowest-indexed vertices. Notice that the elements of $C_1$ have the lowest-indexed positions. Thus, the indices of the positions of $C_1$ elements exactly correspond to the indices of vertices with target color $1$. Next, $|C_2| = |t^{-1}(2)|$, so the next $|C_2|$ lowest indices belong to the positions of elements of $C_2$ and to the vertices with target color $2$.

We can continue applying the same logic. This shows that a sequence satisfies all the constraints if and only if for each $i$, each element $x$ of $C_i$ has a position $y$ whose corresponding vertex has target color $i$. Under the correspondence, element $x$ has position $y$ if and only if token $x$ is at vertex $y$. This shows that a sequence satisfies all the constraints if and only if for each $i$, for $x \in C_i$, the vertex containing token $x$ has target color $i$. Remember, however, that $C_i = p(t^{-1}(i))$ and therefore that $s(C_i) = s(p(t^{-1}(i)))$. Then by the definition of $p$ (that $t(x) = s(p(x))$), we have that $s(C_i) = t(t^{-1}(i) = i$. Thus, for every element $x$ of $C_i$, $s(x) = i$. Substituting this fact, we see that a sequence satisfies all the constraints if and only if for each $i$, for $x \in C_i$, the vertex containing token $x$ has target color $s(x)$. But token $x$ has color $s(x)$, so a sequence satisfies all the constraints if and only if every token is at a vertex whose target color matches that token.

Thus we have shown that the correspondence holds: a swap corresponds to a swap, the initial situations correspond, and situations that match the "victory conditions" also correspond. Thus, since the target number of swaps $k$ is the same, the two instances are equivalent.


3-color a cubic graph such that a MIS receives only two colors

It at least doesn't work out that for every maximum independent set there is a 3-coloring of the graph which 2-colors the independent set. Here is a counterexample to that stronger version of your question:

The circles represent vertices. You can also easily check that the graph is 3-regular and isn't $K_4$. Open circles define the maximum independent set which gives the counterexample. (Unfortunately, there are many other non-isomorphic maximum independent sets in this graph, and at least one of them does get 2-colored by some 3-coloring of the graph.) It's not too hard to see that each of the two "halves" that make up this graph can have an independent set of size at most three, and hence the graph as a whole has all independent sets having size at most six. Thus the independent set given here is indeed maximum.

It's fairly straightforward to show that there's no 3-coloring that 2-colors the independent set. Let's try to color the vertices in the independent set Red or Blue, leaving Green as the third color, and derive a contradiction. We'll start at the bottom: the triangle there (with the red edge) needs to have one vertex of each color. Since the top vertex in the triangle can't be Green, then, by symmetry, we can assume wlog that the bottom left vertex is assigned Green. This forces the top of that same triangle to be Red-or-Blue, and the other vertex of the triangle to be Blue-or-Red (the opposite). The bottom right vertex being Blue-or-Red then forces the vertex above it to be Red-or-Blue. The two white vertices both being Red-or-Blue force the left vertex of the inner triangle (with all black edges) to be Red-or-Blue. This in turn forces the remaining white vertex in the bottom half to be assigned Blue-or-Red. The top two white vertices in the bottom half are then Red-or-Blue and Blue-or-Red, which forces the top-most black vertex in the bottom half to be Green. Repeating this argument for the top half, we eventually get that the edge that bridge the two halves is Green on both sides, a contradiction.


In general the determinism of the transducer seems to be no real restrition. The choices that can be made by a transducer can be moved into the input language. If that is OK for you, the objects sometimes denoted ${\cal M}(L)$ are called principal trio's. Examples include families of linear, blind counter and one turn counter languages (fixed number of counters).
The Habilitation-thesis of Kluas Reinhardt (Counting as Method, Model and Task in Theoretical Computer Science, available on-line) contains a nice inclusion diagram of several families (page 64).


Finding the distance between two polynomials (represented as trees)

Tree Edit Distance is a generalization of string edit distance. The distance between two trees is the minimum number of node insertions \ deletions \ and relabels required to turn one tree into the other. (when we delete node v, v's children become children of parent(v)).
The problem is NP-hard when the trees are unordered, but when they are ordered (i.e., there is a left-to-right order among siblings) the problem is solvable in O(n^3) time (as in the paper that Sadeq mentioned). A good survey that describes this: http://portal.acm.org/citation.cfm?id=1085283


Does this variant of Multiplicative Linear Logic with mix rule enjoy cut elimination?

For question 1, if by "deadlock" you mean "non-trivial vicious circle", then the answer is obviously yes, simply because a non-trivial vicious circle cannot be typed: you will have a cut between a formula $A$ and a formula $F$ containing $A^\bot$ as strict subformula, so it is impossible that $F=A^\bot$. But this is kind of trivial: by refusing a priori to consider cyclic wires as deadlocks, you are eliminating the only possible typed deadlock, so of course you are deadlock-free...

For question 2, there are definitely problems with your sequent calculus.  First, I assume that you are working with orthogonality defined by $(A\cdot B)^\bot=A^\bot\cdot B^\bot$.  Then, you have that the formula $A^\bot\cdot A$ is essentially self-dual and, since it is provable, you have a proof of the empty sequent. But your inference rules (except cut) still verify the subformula property, which means that there is no cut-free proof of the empty sequent. In other words, you are forgetting the rule
$$\frac{}{\vdash}$$
Without this rule, cut-elimination does not hold. There is a further problem though, namely that you cannot represent the cut-elimination steps inside the sequent calculus: in other words, as a type system, you do not have subject reduction.  For that, you need to consider a unary cut rule:
$$\frac{\vdash\Gamma,A^\bot,A}{\vdash\Gamma}$$
Note that, like the tensor rule, the binary cut rule is derivable from this one (and mix).

For question 3, I assume that you are asking whether the system captures your notion of deadlock-freedom.  Since you are excluding cyclic wires a priori (i.e., you are artifically adding a cut-elimination rule that makes them disappear) the the answer is, again, trivially yes: a net normalizes (with your additional reduction rule) to what Lafont calls a reduced net (no vicious circle, no active pair) iff it is typable in the above system. This is provable by standard arguments: subject reduction/subject expansion and typability of reduced nets.

For question 4, I doubt anyone has published anything because this system is so degenerate that I honestly do not see what its interest may be.  In fact, one may further simplify the types by eliminating duality altogether: there is no negation, formulas are just
$$A,B::=\alpha\mathrel |A\cdot B$$
and axioms/cuts introduce/eliminate pairs of equal formulas. This system, albeit logically trivial (because of self-duality), has the same normalization property as above. It boils down to the so-called relational semantics of MLL, which is applicable to untyped structures too, in which tensor equals par.

Regarding your search for a Danos-Regnier correctness criterion for single-agent nets, there is not much to be said: if you make cyclic wires disappear "by fiat", then the self-dual "typing" above suffices and correctness criteria play no role; if you stick to the standard definitions, then there can be no meaningful correctness criterion: every one-conclusion net cut with itself generates cyclic wires.


There seems to be a typo; I assume you mean to find $u \in \{0,1\}^n$ which is not the sum of $(\log
    n)^{O(1)}$ vectors among $v_1,\dots, v_m$ (not $n$).

It's not clear to me if any constant in $(\log n)^{O(1)}$ works for you.  If you can settle for sums of less than $\log m$ vectors maybe there's something to be done. But If you want this quantity to be $(\log m)^{1+\delta}$, then I think it is quite hard (I have been working on this problem for a long time).

Still you may be interested to know that this is an instance of the Remote Point Problem of Alon, Panigrahy and Yekhanin ("Deterministic Approximation Algorithms for the Nearest Codeword Problem ") for certain parameters.  Let $m > n$ and $v_1,\dots,v_m$ be the columns of the parity check matrix of a linear code in $\{0,1\}^m$ of dimension $d = m - n$ (if this matrix didn't have full rank, the problem would be trivial). Then your problem is equivalent to finding $u \in \{0,1\}^n$ that is $(\log n)^{O(1)}$-far from the code.  This setting of parameters, where the dimension is very close to m, is not studied in the paper.  However, they can only achive remoteness $\log m$ up to dimension $d = cm$ for some constant $c$.  In fact, I don't think we know of any polynomial-sized certificate that allows us to prove that some vector is more than $\omega(\log m)$-far from a space of dimension $\Omega(m)$, let alone find it.

Another connection is with learning parities in the mistake-bound model. If one can efficiently learn $(\log n)^{O(1)}$-parities (defined on ${0,1}^m$) with mistake bound strictly less than $n$, then one can set arbitrary values to the first $n - 1$ bits of $u$ and ``force a mistake'' on the last bit by setting it to the opposite value to that predicted by the learner. This seems much stronger though.

The problem is also related to separating EXP from certain reductions to sparse sets.


Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments.  As a result, the question is still open.
Please let me know if you have any ideas.  :)

Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2.  Then, you check if there is an edge between any of these pairs.
A standard way to compute all pairs of vertices that are connected by a path of length 2 is to square the adjacency matrix of the graph.  We can perform Boolean matrix multiplication for the squaring.  All of the 1's in the result will represent pairs of vertices that are connected by a path of length 2.
With nondeterminism, we can compute Boolean matrix multiplication of two n by n matrices in $\tilde{O}(n^2)$ time by guessing the witness for Boolean matrix multiplication (the concept of witness for Boolean matrix multiplication has been discussed in [1] https://doi.org/10.1007/s00453-012-9742-3 and [2] https://doi.org/10.1109/SFCS.1992.267748).  Finally, we check in $O(n^2)$ time if all of the pairs of vertices do not form edges.  <- This paragraph doesn't quite work.


Testing isomorphism of asymmetric graphs

Upon request of Marzio De Biasi I'm converting my comment into an answer.

A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open:

1) Is isomorphism of asymmetric graphs in P?

2) Can isomorphism of general graphs be reduced to isomorphism of asymmetric graphs?

Question 1) has received a lot of attention in quantum computing due to the fact that the isomorphism of asymetric graphs can be reduced to the nonabelian hidden subgroup problem  and to the non abelian hidden shift problem. However the results are negative, showing that one needs to prepare at least $\Omega(n\log n)$ hidden subgroup states or hidden shift states to have enough information to solve the isomorphism problem.


Design of exact algorithms for non-local hard problems

Well, Hamiltonicity was $\Omega(2^n)$ problem till recently, when it was shown that simple k-path can be solved in $O^*(1.657^k)$, which means $O(1.657^n \cdot poly(n))$ for the classical Hamiltonicity.


Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?

The $k$-means algorithm for clustering is provably exponential even in the plane, but it works very well in practice.


Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

No. Consider the following function on $\{0,1\}^n$:
$$ f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}). $$
Clearly this function is hard for AC0. On the other hand, the function is almost constant, so almost all of its Fourier spectrum is on the first level.

If you want a balanced counterexample, consider
$$ g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus
\cdots \oplus x_{n-1})\right]. $$
This function is almost always equal to $x_0$, so almost all of its Fourier spectrum is on the first two levels.


Measures of "correlation" between two orderings

The standard approach to computing the correlation between two total orders is Kendall's $\tau$, defined as the difference between the number of agreeing pairs and disagreeing pairs (in rank) divided by $\binom{n}{2}$.

If you only have partial orders, then things get a little trickier.


Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

Based on Sasho Nikolov's very helpful comment, it seems that both papers use similar models of complexity which lead to unreasonable conclusions, such as the implication that any problem in PSPACE or #P can be solved in polynomial time.

I welcome any comments which may lead to a modification of this tentative answer.


Brackets expression incremental parsing algorithm

Take a look at Tim Wagner and Susan Graham's 1998 TOPLAS paper, "Efficient and Flexible Incremental Parsing", which extends LR parsing to support incremental  update of the document.


Matching regular expressions using regular expressions

Even if we require that the expressions are "human-readable", and the conversion between the standard notation and the new notation is fairly easy to compute, the answer is "yes".

For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:

You are allowed to remove any prefix that consists of a sequence of ('s
You are allowed to remove any suffix that consists of a sequence of )'s

That is, ((a|b)*c)de(f|g) can be expressed in the "compressed" notation using, for example, any of the following forms: a|b)*c)de(f|g or ((a|b)*c)de(f|g or (a|b)*c)de(f|g).

The compressed notation is unambiguous in the sense that you can recover a semantically equivalent expression by simply adding a sufficient number of leading and trailing parentheses to make everything balanced. Of course, a|b)*c)de(f|g might represent ((a|b)*c)de(f|g) or (((a|b)*c)de(f|g)), but adding extra parentheses does not change the language defined by the expression.

The "compressed" notation is a regular language.

And yes, this is cheating.


Recent progress on the next-to-shortest-path problem for directed graphs?

My first intuition is certainly naive. What's wrong with it?

Since $p_2$ is different from $p_1$ on at least one edge, repeatedly remove one edge in $p_1$ from the graph and solve the shortest path problem, which would be at worst $n$ times the complexity of the shortest path problem.


First, your two criteria (that it is a quantum channel and that for all input states, the inverse channel gives the best approximation of the input state) aren't compatible. If they were, then the optimal inverse channel would be independent of whether you choose to optimize the worst-case fidelity or the average-case fidelity. It's not.

There are quite a few papers on this question. Here's one Andrew Fletcher, Moe Win, and I wrote. It shows you can use a semidefinite program to optimize the recovery channel when the criterion to be optimized is the entanglement fidelity, and you assume a specific entangled input state and a specific channel $\Phi$. You should be able to find other papers by looking at our bibliography and using some forward citation tool.


Complexity of finding minimal cover of FDs

It seems like this problem may be known as the dependency inference problem, as described in this extended abstract of the paper "Dependency Inference" by Mannila and Raiha in VLDB '87:

  Given a relation $r$, find a set of functional dependencies that logically determines all the functional dependencies holding in $r$.

Unfortunately, it seems that this problem is intractably super-polynomial. According to the same extended abstract:

  Theorem 1. For each $n$ there exists a relation over $R$ such that
  $n = |R|$, $|r| = O(n)$, and each cover of $dep(r)$ has $\Omega(2^{n/2})$ dependencies.

In other words, you cannot guarantee that the minimal cover is sub-exponential in the size of the input.

EDIT: However, the asker is asking whether or not an output-polynomial algorithm exists (i.e.: an algorithm that runs in time polynomial in the size of the input and output). The nearest reference I can find is in the paper "Identifying the Minimal Transversals of a Hypergraph and Related Problems", SIAM J. Computing, 1995 (24) by Eiter and Gottlob.
They first define problems AP1 and AP2 where AP2 is the dependency inference problem. Then, they state the following:

  Note that problems AP1 and AP2, which are search problems in terms of complexity theory, are solvable by algorithms in output-polynomial time only if the following decision problem, which we call FD-RELATION EQUIVALENCE, is in P:

  Problem: FD-RELATION EQUIVALENCE
  Instance: A relation $R$ and a set $F$ of FD.
  Question: Does $F_R = F^+$ hold ?

  FD-RELATION EQUIVALENCE is in co-NP, but there is neither a polynomial time algorithm known for this problem nor is it proved co-NP-complete.


Question on deduction that a certain problem requires exponential space

Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard Space Hierarchy Theorem. The standard version of the Space Hierarchy Theorem has the quantifiers rearranged:

  For every space-constructible $S_2(n)$, there exists $L \in \mathbf{DSPACE}(S_2(n))$ such that for every space constructible
  $S_1(n) \leq o(S_2(n))$, $L \not \in \mathbf{DSPACE}(S_1(n))$.


Why/when do we ever need transfinite loop variants?

You are correct when you observe that for any particular terminating loop $L$ we may simply define the invariant "we're getting one step closer to termination". But proving that this is indeed a valid invariant may require transfinite induction!

For instance, we could write a loop that computes the Goodstein sequence. This is particular sequence of numbers which starts with any given number $n$ and it eventually terminates, but proving that it terminates for every $n$ requires transfinite induction to the ordinal $\epsilon_0$ (which is the limit of ordinals $\omega$, $\omega^\omega$, $\omega^{\omega^\omega}$, ...)! So, in order to show that a loop computing the Goodstein sequence terminates for every inital term $n$ we need an appeal to transfinite induction.

At this point we have two choices:

Use transfinite induciton to show the loop terminates, then "forget" that you used transfinite induction to show that the silly invariant "we're one step closer to the end" does the job.
Use a loop invariant which requires ordinal numbers but is informative because it is an obviously decreasing sequence that dominates the Goodstein sequence.

Take your pick.

In summary, it's not just about whether we can avoid ordinal numbers (we cannot avoid them completely), it's also whether we want to. Avoiding them might just complicate your life and lead to convoluted proofs of termination. Why would we do that?


Without looking at specifics, growing a tree using information gain is a greedy procedure and won't always get you to the smallest tree consistent with the data, even if one exists.  If there are ties among attributes, you break them arbitrarily.


The ODD EVEN DELTA problem is #P-hard, even on 3-regular bipartite planar graphs.

Let $\mathcal{C}$ be the set of vertex covers of a general graph $G$. Then, assuming $G$ has no isolated vertices, the following equation holds (refer to the above article for the proof):

$$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$$

Counting vertex covers is #P-complete even on 3-regular bipartite planar graphs, and it can be done with a linear number of calls to an ODD EVEN DELTA oracle.


What are different definitions of Universal Turing-machine?

I found some alternate definitions of Universal Turing Machine in papers related to the universality of small Turing machines and other models.

See for example the four definitions (the first 3 are equivalent and are similar to yours except that there there is also an explicit decoding function) in section 2 of Yurii Rogozhin, Small universal Turing machines, Theoretical Computer Science, Volume 168, Issue 2, 20 November 1996, Pages 215-240.

For example the Davis's definition in M. D. Davis, A Note on Universal Turing Machines ; Martin Davis, The Definition of Universal Turing Machine . Journal of Symbolic Logic 35 (1970), no. 4, 590; bypasses the encoding phase:

A generic machine (Turing machine, tag-system, ...) is universal if and only if its halting problem is r.e. complete.

Probably you're not interested in them (and you'll probably know them), but there are also  notions of semi-weakly universal  and weakly universal Turing machines (in which the initial tape has an infinite repeated string on the left/right/left+right of the input). For further details see the work of Neary and Woods on small TMs.


FWIW, your problem is hard to approximate within a multiplicative factor of $n^{1-\epsilon}$ for any $\epsilon>0$.

We show that below by giving an approximation-preserving reduction from Independent Set, for which the hardness of approximation is known.

Reduction from Independent Set

Let undirected graph $G=(V,E)$ be an instance of Independent Set.
Let $d_v$ denote the degree of vertex $v$ in $G$.
Let $n$ be the number of vertices in $G$.

Construct edge-weighted graph $G'=(V',E')$ from $G$ as follows.
Give each edge in $E$ weight 1.
For each non-isolated vertex $v\in V$,
add $d_v-1$ new edges, each with weight $-1$,
to $d_v-1$ new vertices.
For each isolated vertex $v\in V$,
add one new edge of weight 1 to a new vertex.

(Note: each new vertex (in $G'$ but not $G$) has exactly one neighbor,
which is in $G$.)

Lemma. $G$ has an independent set of size $k$ iff
$G'$ (as an instance of your problem) has a solution of value at least $k$.

Proof.  Let $S$ be any independent set in $G$.
Then, since the vertices in $S$ are independent in $G'$,
the value of $S$ in $G'$ (by your objective)
is
$$\sum_{v\in S} d_v - (d_v-1) ~=~ |S|.$$

Conversely, let $S$ be a solution for $G'$ of value at least $k$.
Without loss of generality, assume $S$ contains no new vertices.
(Each new vertex $v'$ is on a single edge $(v',v)$.
If $v$ was not isolated in $G$, then the weight of the edge
is $-1$, so removing $v'$ from $S$ increases the value of $S$.
If $v$ was isolated, then the weight of the edge is 1,
so removing $v'$ from $S$ and adding $v$ maintains the value of $S$.)

Without loss of generality, assume that $S$ is an independent set in $G$.
(Otherwise, let $(u,v)$ be an edge such that $u$ and $v$ are in $S$.
The total weight of $v$'s incident
edges in $G'$ is $d_v - (d_v-1) = 1$, so the total weight of $v$'s incident
edges other than $(u,v)$ is at most zero.
Thus, removing $v$ from $S$ would not increase the value of $S$.)

Now, by the same calculation as at the start of the proof,
the value of $S$ is $|S|$.  It follows that $|S| \ge k$. QED

As an aside, you might ask instead for an additive approximation,
of, say, $O(n)$ or $\epsilon m$.

It seems possible to me that for your problem even deciding whether
there is a positive-value solution could be NP-hard.


Various conjectures which is similar to Log Rank conjecture

The log-rank conjecture is equivalent to the following conjecture.

  For any graph $G$ with adjacency matrix $A$ and complement graph $\bar{G}$, the chromatic number of $\bar{G}$ is at most $(\log \mathsf{rank}(A))^{O(1)}$.

This is from Lovasz and Saks's original paper, which has more connections.

Nisan and Wigderson observed that to prove the log-rank conjecture it suffices to show that any $M \in \{0, 1\}^{N \times N}$ has a monochromatic rectangle of size at least $N 2^{-(\log \mathsf{rank} M)^{O(1)}}$.

More intuitively, the hardness in trying to disprove the conjecture comes from the fact that it's difficult to construct a non-trivial example of a binary matrix that has low rank over the reals. The trivial examples are matrices that can be decomposed into a small number of combinatorial rectangles, but we know that such a decomposition implies small communication complexity. So the conjecture asks, are all low rank binary matrices decomposable into a small number of rectangles.


Does Rabin/Yao exist (at least in a form that can be cited)?

After more than two years, I have to assume the answer is "no".  (Posting this stub answer so the question can be marked as answered.)


Counting subsets of given set with certain properties

If $S = \{2,2\}$ and $k=1$, the answer is $2$, the following dynamic program works.

Let $S = \{a_1,a_2,...,a_{|S|}\}$ where $a_i \leq a_{i+1}$. Consider the function $DP(i,n)$ as the number of satisfying subsets ending with element $i$ of length $n$. A satisfying set is a set $T = \{s_1,s_2,...,s_{k'}\}$ with the property $i \leq s_i \leq s_{i+1}$.

Hence, $DP(i,n) = 0$ if $a_i \leq n$, $1$ if $n = 1$. Otherwise, $DP(i,n) = \sum_{j=1}^{i-1} DP(j,n-1)$. The answer will then be $\sum_{j=1}^{|S|} DP(j,k)$.

If indeed for the case  $S = \{2,2\}$ and $k=1$, the answer is $1$. A small modification to the above recurrence is possible. Consider a representation of a multiset $S$ in the form $\{(a_1,b_1),(a_2,b_2),...,(a_n, b_n)\}$ where $a_i < a_{i+1}$ and $b_i$ is the number of copies of $a_i$ in $S$.


As far as I know, the state of the art is what is reported in

Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos (2012), "On exact algorithms for treewidth", ACM Transactions on Algorithms 9 (1): A12, doi:10.1145/2390176.2390188.

The methods described there include an implemented $O^*(2^n)$ algorithm with some heuristic optimizations to make it faster in practice.


Constructing uniquely satisfiable formulas

If I understand your question correctly, you're looking for ways to generate lots of non-trivial uniquely satisfiable 3SAT instances.
There's a tension between your desire to find a way to generate all uniquely satisfiable instances and your desire to find a way to generate hard uniquely satisfiable instances.  For the moment let's ignore your uniqueness condition. Then I know there has been some work on this problem, e.g., see Generating satisfiable problem instances by Achlioptas, Gomes, Kautz, and Selman.  You might think that they proceed by generating random clauses and discarding the clauses that are inconsistent with a randomly chosen but fixed assignment.  But although this method will in principle generate every satisfiable instance (with some probability), it tends to produce instances that are easy to solve.  To get hard instances, Achlioptas et al. adopt the approach of picking some known hard problem and generating instances based on that.
I suspect that a similar dilemma will arise for uniquely satisfiable instances.  My guess is that a randomized method that generates every uniquely satisfiable instance with some probability will tend to produce easily solved instances.  If you want hard instances, your best bet is probably to pick some cryptographic problem (where the unique solution is the cryptographic secret, e.g., a factorization) and generate instances based on that.


parameterized algorithms for geometric set cover

The paper D. Marx: Efficient approximation schemes for geometric problems?, in ESA 2005, gives W1-hardness for covering points with unit squares. A draft is here.


Decidability of parametric higher-order type unification

No, it's not decidable. The pure simply-typed lambda calculus is parametric in your sense (it has no case analysis) and higher-order unification is undecidable.

In general, permitting partial application of type synonyms is equivalent to adding lambda-abstraction to the language of type expressions. This is because type synonyms suffice to encode the SKI combinators, which are equivalent to the full lambda calculus.

 type I a     = a
 type K a b   = a
 type S a b c = a c (b c)

It would be very unnatural to write type annotations using such synonyms, but that doesn't matter for decidability results!

However, pattern unification and higher-order matching are both decidable, and may be useful for your purposes.

In higher-order unification, you have two lambda terms $s$ and $t$ containing unification variables, and a unifier is a substitution $\theta$ such that $\theta(s) =_{\beta\eta} \theta(t)$, with the goal finding a complete set of unifiers (ie, a set such that every unifier factors through this set).

In higher-order matching, we assume that only one of the two terms (say $t$) has unification variables, so we are looking for unifiers $\theta$ such that $s = \theta(t)$. This can be useful for type inference, because often we ask programmers to write type annotations (which obviously won't have unification variables in them).

Colin Stirling gives the algorithm for this in his paper Dependency Tree Automata.
In pattern unification, we assume that every unification variable $X$ only occurs with arguments that are a disjoint set of variables. That is, any application of $X$ must look like $X\;a\;b\;c$, where $a,b,$ and $c$ are variables distinct from one another. This effectively reduces the problem to first-order unification, since applying a variable to a lambda-term can never introduce a new redex. This procedure is the basis of type inference in most proof assistants like Coq and Agda.

Dale Miller originally made this observation, and many people have worked out different presentations of this algorithm. One I like is Gopalan Nadathur and Natalie Linnell's Practical Higher-Order Pattern Unification
With On-the-Fly Raising.


What's the correlation between treewidth and instance hardness for random 3-SAT?

Not really an answer but the closest references I am aware of. There are results available for branch-width. Also, there is at least one empirical study of treewidth of industrial instances.

Discovering treewidth, H. Bodlaender, 2005. Gives algorithms to compute bounds on treewidth.
Treewidth in Industrial SAT Benchmarks, R. Mateescu, 2011. Uses variations of above algorithms to estimate treewidth of SAT2009 competition benchmarks.
Algorithms and complexity results for #SAT and Bayesian inference, F. Bacchus S. Dalmao, T. Pitassi, 2003. Relates branch-width to complexity of #SAT, 2003.
Satisfiability, branch-width and tseitin tautologies, Alekhnovich, Razborov, 2002.


Algorithm for Longest Path in Undirected Weighted Graph

Two questions where I think you have remained unclear:

Are there any assumptions on the weight function?
What exactly holds if $(x, y) \in R$?

Ad 4: You break your desired invariant for $R$ here since the last node in $x$ does not necessarily occur in $w$ at all. Example: $x = abc, y=adc, z=adce, w=ae$

I believe a worst-case instance might be the complete graph with $w(i,k) = 1$ for $i$ the starting node and all $k\neq i$, and $w(j, k) = 0$ for all $j,k \neq i$. Paths with more nodes will never remove those from earlier iterations so the tree is never shrunk at all, growing up to having $n!$ nodes.


Examples of the value of proofs for algorithms

Here is a natural problem from graph theory where the proof and the algorithm are closely intertwined. In my view, one can discover this algorithm only via thinking about the proof and the algorithm "in parallel." The task is this:

Input: An undirected graph.

Task: Find a subgraph with maximum edge-connectivity.

Note: What makes the task non-trivial is that a subgraph can have larger edge-connectivity than the whole graph. Since there are exponentially many subgraphs, it would take exponential time to check all of them to find the most connected one, even though we can compute the edge-connectivity of any graph in polynomial time.

Below is a part of a lecture note about solving this problem. It shows that the task can be solved in polynomial time, using a subroutine that finds a minimum cut (which is well know to be doable in polynomial time). For short, edge-connectivity is just called connectivity, and is denoted by $\lambda(G)$.


Is there any equation-based method for transforming Büchi-automata to omega-regular language?

Sure. In fact, the translation from Büchi automata to $\omega$-regular expressions is only a small extension of the one for finite-word languages.

Recall that an $\omega$-regular expression is of the form $s_1\cdot t_1^\omega+\ldots+s_k \cdot t_k^\omega$, where all the $s_i$ and $t_i$ are regular expressions.

The translation of an NBW $A$ to such an expression is based on the following observation: let $A_{p,q}$ be the NFA obtained from $A$ by setting $p$ as the initial state, and $q$ as the single accepting state, then $L(A)=\bigcup_{q\in \alpha} L(A_{q_0,q})\cdot L(A_{q,q})^\omega$ where $\alpha$ is the set of accepting states of $A$.

Indeed, a word is accepted by $A$ iff there is a run on it that leads from $q_0$ to an accepting state $q$, that is then visited infinitely often.

So all you need to do is write the equations that correspond to this union. It'll be slightly uglier than those for an NFA, but not much.


When to apply soft constraints evaluation functions in genetic algorithms?

Experiment.  It depends on the topology of your problem domain. If you knew how to optimize more efficiently you wouldn't be throwing a GA at it.


Difference between NP-Hard and NP-Complete

A NP-complete problem is an NP-hard problem which is in NP.


What are the consequences of $L = \oplus L$?

Wigderson proved that $NL/poly \subseteq \oplus L/poly$. By standard arguments, $L = \oplus L$ would imply $L/poly = NL/poly$. (Take a machine $M$ in $NL/poly$. It has an equivalent machine $M'$ in $\oplus L/poly$. Take the $\oplus L$ language of instance-advice pairs $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$. If this language is in $L$, then by hardcoding the appropriate advice $a$ we get an $L/poly$ machine equivalent to $M$.)

I think that would be surprising: nondeterministic branching programs would be equivalent to deterministic branching programs (up to polynomial factors).


Exponential gap on neural network layers

The paper that people usually cite is Almost Optimal Lower Bounds for Small Depth Circuits, which appears in STOC 1986. The main result pertaining to your question is:

  There exists a family of functions admitting linear size, depth $k$ circuits (of unbounded fan-in AND/OR and NOT) that requires exponential size at depth $k-1$.

What's possible even more relevant is the fact that $\mathsf{TC}^0$ admits an exponential separation between depth 3 and depth 2. This is relevant because threshold gates are commonly used in deep networks.


Complexity of checking if two words have an interleaving in a language

For a word $w=w_1\ldots w_{\ell}$ and for two integers $i,j$ with $1\le i\le j\le \ell$ we denote by $w(i,j)$ the subword $w_iw_{i+1}\ldots w_j$ of $w$.
Furthermore we let $w(0,0)$ denote the empty word.

Let $u=u_1\ldots u_m$ and $v=v_1\ldots v_n$ be the two words under consideration.
Assume that the context-free language $L$ is specified by a context-free grammar in Chomsky normal form.

Construct a dynamic program, where a state $[i,j,r,s,A]$ is specified by

two integers $i,j$ with $1\le i\le j\le m$ or $i=j=0$
two integers $r,s$ with $1\le r\le s\le n$ or $r=s=0$
a non-terminal symbol $A$ in the context-free grammar

For every state, decide whether in the context-free grammar there exists some derivation that starts with the non-terminal $A$ and that ends with some interleaving of the two words $u(i,j)$ and $w(r,s)$.
This decision can easily be made, if the states are handled in the right order (short subwords before longer subwords).

All in all, this yields a polynomial time algorithm for the $L$-interleaving problem of any context-free language $L$.


Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]?

There was a subsequent extension by Grigoriev and Razborov (PS) that has a shorter exposition of proof.


Here is an excerpt from the call for papers that explains the procedure:

As soon as a submission arrives, several board members with expertise in its declared area are notified, and once a week all board members are sent the list of pending submissions. Board members may screen a submission at their own discretion, and make the decision whether or not to accept it. An accepted submission is posted as a report immediately. A submission is automatically rejected after two months if no board member accepted it.

The call for papers also lists the members of the board.


Stable Marriage with incomplete lists and ties - NP-hardness

The stable marriage instance with ties is solvable in polynomial time, whereas the stable marriage instance with incomplete lists and ties is NP-hard.

The same holds for the Hospitals/Residents problem.  So there is no conflict between [1] and [2].


Is there any hidden subgroup of a symmetric group which can be efficiently determined?

From what I understand, it is partially because we don't have any techniques currently that take advantage of structure of the hidden subgroup itself. Weak Fourier sampling solves the problem whenever the hidden subgroup is normal (but this is not a property of the subgroup itself - analogous to being a direct product etc - but rather how the subgroup sits within the larger group), but that's no help for the symmetric group because its only normal subgroup is the alternating group (for $n \geq 5$).

From the examples of [1] - which shows that in the symmetric group strong Fourier sampling produces distributions for the hidden trivial group vs a hidden random involution that are exponentially close - and [2], it would seem that there may be some hope if the hidden subgroup is promised to be relatively large. But you would need to either be able to show that Fourier sampling succeeds in this case, or to come up with a different method that (likely) really took advantage of the largeness of the hidden subgroup.

Moore, Russell, and Sniady [3] also showed that the other relatively successful method - a Kuperberg-style sieve - doesn't work efficiently in a group very close to the symmetric group (namely, $S_n \wr S_2 = (S_n \times S_n) \rtimes S_2$), to distinguish a hidden trivial group from a hidden involution.

[1] Moore, C., A. Russell, and L. J. Schulman. The Symmetric Group Defies Strong Fourier Sampling. SIAM J. Comput. 37, p. 1842, 2008. Preliminary version in FOCS 2005. (arXiv version)

[2] Grigni, M., L. J. Schulman, M. Vazirani, and U. Vazirani. Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem.
Combinatorica 24, p. 137, 2004. Preliminary version in STOC 2001.

[3] Moore, Russell, and Sniady. On the impossibility of a quantum sieve algorithm for graph isomorphism. SIAM J. Comput. 39 (2010), no. 6, 2377–2396. Preliminary version in STOC 2007.


How to calculate the cost of factoring a large integer?

To turn the question around, one could equivalently ask: "How large must my prime be in order to be secure until year X against the resource plausibly available to a potent (e.g. government-funded) attacker?" This question is being regularly reassessed in various studies yielding recommended key lengths for crypto systems. A regularly updated web page summarizing these reports can be found here.


Is the complexity of this covering problem known?

The problem is known as the propagation problem. Aazami has proved in his PhD thesis that the weighted version is NP-complete even when the graph is planar and the node weights are in $\{0,1\}$. The complexity for the unweighted version seems to be an open problem.


Cleaning images in order to perform feature detection

A common preprocessing tactic is to smooth the image prior to feature extraction using for instance a Gaussian kernel or a low pass filter. This allows for the high frequency spurious details to be removed.


Which monotone Boolean functions are representable as thresholds on sums?

It was mentioned in the comments that these are the positive threshold functions.

As for other characterizations, I found the following to be interesting. Suppose we have a positive threshold function with decreasing weights $w_1\ge w_2\ge\dots w_n$:
$$f(v_1,\dots,v_n)=1 \iff \sum_i w_iv_i\ge 1.$$
Then in particular the set of inputs $(v_1,\dots,v_n)$ for which $f(\vec v)=1$ is an order ideal of the binary majorization lattice with $2^n$ points, which is studied in

  Donald Knuth, "The Art of Computer Programming", Exercise 109 of Section 7.1.1.

To put it informally, $f$ is the kind of function where making earlier bits 1 makes $f$ more likely to be 1: so e.g. $f(0,1,1)\le f(1,0,1)\le f(1,1,0)$. That is, "some bits matter more", and to remove redundant isomorphic cases we assume earlier bits matter more.

However, not all such functions are positive threshold functions! That is, just because you've ordered the exam questions from most important to least doesn't mean your pass/fail rule is based on just adding up some scores.

Indeed, the number of positive threshold functions (with decreasing weights) on $n$ variables is given by the sequence
$$2,3,5,10,27,119,\mathbf{1113},\dots$$
(oeis.org sequence A000617)
whereas the number of such order ideals is
$$2,3,5,10,27,119,\mathbf{1173},\dots$$
(oeis.org sequence A132183)


Yes, a polynomial time algorithm was first given in:

Neil Robertson, P. D. Seymour, Robin Thomas. "Permanents, Pfaffian orientations, and even directed circuits." Annals of Mathematics 150.3 (1999): 929-975. arXiv

edit: Actually, according to the acknowledgements section of the above paper, the result was first obtained by McCuaig who later published it as:

William McCuaig. "Pólya's Permanent Problem." Electr. J. Comb. 11(1) (2004) http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r79


Is graph connectivity definable in existential MSO with vertices and edges?

You can express that $s$ is connected to $t\ne s$ in $G=(V,E)$ by the $\exists\mathrm{MSO}_2$ formula

  “there exists $E'\subseteq E$ such that in the graph $(V,E')$, $s$ and $t$ have degree $1$, and all other vertices have degree $0$ or $2$.”

Note that the formula after the initial $\exists E'$ quantifier is first-order.

A graph of degree $\le2$ is a disjoint union of lines and cycles; since end-points of lines are exactly the vertices of degree $1$, the only way to satisfy the formula is that $E'$ consists of a line connecting $s$ to $t$, and possibly some disjoint cycles.

Likewise, directed connectivity can also be defined by an $\exists\mathrm{MSO}_2$ formula (we replace “degree $2$” with “in-degree and out-degree $1$”, and similarly for the end-points).


What does it mean that there are differing views on how computations are represented on the Turing Machine?

It is not the algorithms that are represented in different ways, but input and output. Depending on how the input is encoded, a given problem might be hard or easy. To take a trivial example, consider the following encoding of Turing machines:

  A turing machine $T$ is represented by a number of the form $2 n + b$ where $n$ such
  that the binary digit expansion of $n$ gives a description of $T$'s program (encoded in a reasonable way). The number $b$ is $1$ if $T$ halts when run on empty input and $0$ otherwise.

With this encoding of Turing machines the halting problem becomes very easily computable. Given a description of Turing machine, just look at the lowest bit to determine whether the machine stops.

The moral of the story is that encoding of data is meaningless until we also specify what sort of structure we are trying to encode, i.e., which operations on data are supposed to be computable. (In the case of Turing machines it is known that the relevant operations are those of the s-m-n and u-t-m theorems, which fail for the silly encoding above.)

In case we worry about computational complexity we also need to require that the data are suitably "compressed", for example, if the input to an algorithm is a number $n$, it should be written with input of size $O(\log n)$, otherwise we can artificially "boost" the efficiency of the algorithm by writing down input in a very inefficient way.

If we work with the usual Turing machines then all reasonable ways of representing data will be equivalent (even polynomial-time convertible). But with very small Turing machines one might be forced to represent inputs in very strange ways because the machine will lack the power to recode its input in whatever form is needed. Under such circumstances people might disagree what is a reasonable way of encoding input. For example, may the input be repeated twice (suppose the machine lacks the ability to go backwards but it needs to read the input twice to do its job)? May the input be repeated infinitely many times? If we impose no restrictions on how the input is presented to the machine, then the input itself might already contain the answer that the machine is supposedly computing (witness the example of the Halting problem above). Sometimes it is hard to tell whether a given representation is "hiding" extra information. An infamous example of this was the solution to the Wolfram 2,3 Turing machine research prize where the input tape had to contain an infinite repeating pattern in order for the machine to work correctly. I suggest you look at the archives of the Foundations of mathematics mailing list for a detailed discussion about the 2,3 prize and about how even minor changes in input representations can cause big jumps in the computational power of a machine. The relevant threads are:

Wolfram 2,3 Turing Machine Prize
Smallest universal machine
Definition of universal Turing machine
Simple Turing machines, Universality, Encodings, etc.


Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?

Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Röglin and Vöcking is that, provided that the range of integers that the variables can assume is polynomially bounded, (randomized) pseudo-polynomial solvability is equivalent to polynomial smoothed complexity. Thus, general integer programs do not have polynomial smoothed complexity.

The statement "randomized pseudo-polynomial complexity = polynomial smoothed complexity" is not known to be true in general. For instance, the flip heuristic for Max-Cut runs in pseudo-polynomial time, but it is unknown if a local optimum w.r.t. the flip heuristic can be found with polynomial smoothed complexity (cf. Etscheid and Röglin, SODA 2014).


(transferred from a comment above)

The problem you want to solve is called Graph Bisection and is NP-hard. A simple heuristic that might work well in your case is to find two nodes that are as far apart as possible, and then grow out their neighborhoods till you get roughly equal sizes on both. Another local improvement heuristic is to take a candidate solution, and find two vertices to swap that will reduce the cut size.


Computational complexity of counting induced subgraphs which admit perfect matchings

The problem is #P-complete. It follows from the last paragraph of page 2 of the following paper:

C. J. Colbourn, J. S. Provan, and D. Vertigan, The complexity of computing the Tutte
polynomial on transversal matroids, Combinatorica 15 (1995), no. 1, 1–10.

http://www.springerlink.com/content/wk55t6873054232q/


Are there any counterintuitive results in theoretical computer science?

I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where the running time to solve them is way better than what you would expect it to be.


Integer linear programming in logarithmic number of variables

I can only give a partial answer to this question.

A result by Lenstra (later improved by Kannan, and Frank and Tardos) states that ILP with $k$ variables can be solved in time $k^{O(k)}$ (times a polynomial in the size of the ILP). Therefore, ILP is in P when the number of variables is $O(\log n/\log\log n)$. I am not sure if a $2^{O(k)}$ algorithm is known, or if such an algorithm would contradict the ETH.

I found this information in Daniel Lokshtanov's dissertation. Here are the relevant references.

H.W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538–548, 1983.
R. Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12:415–440, 1987.
Andras Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7:49–65, 1987.


Function with space-depending computation time

By the Space Hierarchy Theorem, for every space-constructible space bound $s>\log(n)$, there is a problem $L \in \mathsf{SPACE}(s)\setminus \mathsf{SPACE}(o(s))$.

In other words, $L$ can be solved in space $s$, and thus in time $c^{s(n)}$, but not in space $o(s)$, regardless of how much extra time you allow.


NP-Hardness of a special case of orthogonal packing problem

I think that the paper by Klaus Jansen and Roberto Solis-Oba "An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths" has a partial answer to your question. They consider a special case of your problem known as Cutting Stock problem when the number of diﬀerent object types is constant and defined as follows:

  In the cutting stock problem we are given a set $T = \{T_1,T_2,\dots,T_d\}$ of object types, where objects of type $T_i$ have positive integer length $p_i$. Given an inﬁnite set of bins, each of integer capacity $\beta$, the problem is to pack a set $\mathcal{O}$ of $n$ objects into the minimum possible number of bins in such a way that the capacity of the bins is not exceeded; in set $\mathcal{O}$ there are $n_i$ objects of type $T_i$, for all $i =1,\dots,d$.

The authors claim that

  it is not known whether the cutting stock problem can be solved in polynomial time for every ﬁxed value $d$.

And they propose $OPT+1$ approximation polynomial-time algorithm when $d$ is fixed.

Since it's not proved that this special case is in $P$, this is the evidence that your problem is $NP$-hard.

Addendum: it's known that the case with two object types ($d=2$) is polynomially solvable, but for $d=3$ there is known only $OPT+1$-approximation.


In fact it is possible to show that, for every $f$ sufficiently small (less than $2^n/n$), there are functions computable by circuits of size $f(n)$ but not by circuits of size $f(n)-O(1)$, or even $f(n)-1$, depending on the type of gates that you allow.

Here is a simple argument that shows that there are functions computable in size $f(n)$ but not size$ f(n)-O(n)$.

We know that:

there is a function $g$ that requires circuit complexity at least $2^n/O(n)$, and, in particular, circuit complexity more than $f(n)$.
the function $z$ such that $z(x)=0$ for every input $x$ is computable by a constant-size circuit.
if two functions $g_1$ and $g_2$ differ only in one input, then their circuit complexity differs by at most $O(n)$

Suppose that $g$ is nonzero on $N$ inputs. Call such inputs $x_1,\ldots,x_N$. We can consider, for each $i$, the function $g_i(x)$ which is the indicator function of the set $\{ x_1,\ldots,x_i \}$; thus $g_0=0$ and $g_N=g$.

Clearly there is some $i$ such that $g_{i+1}$ has circuit complexity more than $f(n)$ and $g_i$ has circuit complexity less than $f(n)$. But then $g_{i}$ has circuit complexity less than $f(n)$ but more than $f(n) - O(n)$.


Why are linear bounded automata not as popular as other automata?

With "appropriate" modifications we can turn these classes into complexity classes; Finite Automata into $NC^1$, CFL into LogCFL, and LBA into PSPACE.

It should now be quite clear why we are interested in the first two more than LBA. The first two naturally fit into the usual definition of feasible computation. But PSPACE does not.


Pair of vertex disjoint cycles in a directed graph

According to Grohe and Grüber "Parameterized approximability of the disjoint cycle problem" (ICALP 2007) there is an algorithm for finding $k$ vertex-disjoint cycles in a digraph, in time $n^{f(k)}$ for some function $f$ (polynomial for fixed $k$ but not FPT) in the section 5 of Reed, Robertson, Seymour and Thomas, "Packing directed circuits" (Combinatorica 1996) (which in turn uses theorem 3 of "The directed subgraph hemeomorphism problem" of Fortune, Hopcroft, and Wyllie.)


Numerical accuracy of superpositions in quantum computers

It appears that my question about "numerical accuracy" / error correction for qubits is nicely answered in the bible of quantum computation, M.A. Nielsen and I.L. Chuang, "Quantum Computation and Quantum Information", Oxford Univ. Press, 2010, chapter 10, in particular section 10.3.1. This book is great, I think that it is both very readable and very thorough!

The key point is the following: Yes, errors may be introduced during the calculation so that the superpositions becomes more and more "inaccurate" in small ways. Then, it may seem very strange that in many papers on error correction in quantum computation, authors often only correct for a few types of errors, in particular bit flip errors ($|0\rangle\leftrightarrow|1\rangle$) and sign flip errors ($|1\rangle\to -|1\rangle$). What about small deviations in superposition coefficients? The answer is: If you correct for the former kind of error, then the latter ones are accounted for as well! (Theorem 10.2 in the book.) The reason is that if you account for bit and sign flip errors, then you automatically account for any linear combination of these errors, which now includes small deviations in the coefficients as well. Hurray!

In general, when thinking about qubits, it is not a good idea focus on the fact that the superposition coefficients can be arbitrary real numbers. Sure, Shor's algorithm requires a fairly precise cancellation of these coefficients. But a better point of view is to think of a qubit as something much closer to a classical bit, which has only two discretes states $0$ and $1$, than to a high precision real number from the interval $[0,1]$. The point is that when we try to physically measure a qubit, we only ever get one of two discrete answers (albeit with interesting probabilities), so it's pretty much discrete.

If we compare analog and quantum computers, then it is fair to say that an analog computer tries to encode as much information as possible in high precisions real numbers, whereas a quantum computer has essentially just discrete bits with a little bit of "quantum extra". Then the key point to the computational power of quantum computers is not that a qubit contains real numbers, but that qubits combine by taking the tensor product of Hilbert spaces ($H_1 \otimes H_2$) whereas analog computers combine by just adding more real numbers, corresponding to the direct sum of vector spaces ($V_1 \oplus V_2$). The "little quantum extras" combine into something useful if we add many of them.

Also note that at the time of this writing, it is totally unclear whether quantum computers are really more powerful than classical computers. As far as I am aware of, there is no "genuine" (no oracles) problem that can be solved efficiently only with a quantum computer, i.e. where we have proof that a classical computer can't do it efficiently. Quantum computers certainly don't solve the $NP = P$ problem.


Has anyone studied "polynomially compact" metric spaces?

The notion of bounded doubling dimension appears to be related. Specifically, assume your region S is a ball of radius \rho in the metric space. Then the space is said to have bounded doubling dimension $k$ if any such S can be covered by at most $(1/\epsilon)^k$ balls of radius $\epsilon \rho$. The difference between your definition and this one is the limitation of $S$ to be a ball though.

In essence, your parameter $k$ is acting like a kind of dimension of the space. A worthwhile reference is Ken Clarkson's review of different notions of metric space dimension.

Separately, I'm a little confused about your definition, since it appears to require a bound unrelated to the size of $S$. This is odd, because $S$ could grow arbitrarily large.


Here is an algorithm:
Choose a number from the sequence with probabilities proportional to their values, remove it and push_front it to the output sequence. Repeat the steps.

With your 1 2 3 example, consider the probability that 1 comes earlier than 3 ( so 1 is removed later than 3 in the input sequence ). Obviously the time 2 is removed is not relevant. So the probability is 1/(1+3)=1/4.

The algorithm can be implemented in time O(NlogN)


Optimization problems with good characterization, but no polynomial-time algorithm

In some technical sense you are asking whether $P = NP \cap coNP$.  Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$.  This can be recast as a minmax characterization by
$f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ and $g_x(y) = 1$
otherwise.  Now indeed we have $max_y f_x(y) = min_y g_x(y)$.

So in this sense, any problem known to be in $NP \cap coNP$ but not known to be in $P$ can be turned into an answer to your question.  E.g. Factoring (say, the decision version of whether the $i$'th bit of the largest factor is 1).


Protocol partition number and deterministic communication complexity

Ok, so let me try to prove that two is enough, that is $cc(R)\le 2\log_2(pp(R))$. Sorry but sometimes I write leaves instead of number of leaves/pp(R), whenever the number is smaller than 1, I obviously mean this. Also, I usually write < instead of $\le$ to enhance non-tex readability.

Indirect suppose that there is an R for which this is not true and let us take the R with the smallest possible pp(R) that violates the inequality. We basically have to show that using two bits, we can halve the number of leaves in all four outcomes of the protocol tree, then we are done using induction.

Denote the possible set of inputs of Alice by X and of Bob by Y.
Take the center of the protocol tree that achieves pp(R) leaves, i.e. the node deleting which the tree falls into three parts, each having at most 1/2 of the pp(R) leaves, and denote the corresponding inputs by X0 and Y0.
Without loss of generality we can suppose that Alice speaks at the center and she tells whether her input belongs to XL or XR, whose disjoint union is X0.
Denote the ratio of the leaves to pp(R) in XL $\times$ Y0 by L, in XR $\times$ Y0 by R and in the rest by D.
Now we divide the rest into three more parts, similarly to Doerr, denoting the leaves whose rectangle intersect Y0 $\times$ X by A, whose rectangle intersect X0 $\times$ Y by B and the rest by C.
Notice that A+B+C=D.

Now we know that L+R>1/2, L,R<1/2 and without loss of generality we can suppose that L is at most R. We also know D=A+B+C<1/2. It follows that 2L+A+B<1, from which we know that either L+A<1/2 or L+B<1/2, these will be our two cases.

Case L+A<1/2: First Bob tells whether his input belongs to Y0 or not. If not, we have at most D<1/2 leaves left. If it does, then Alice tells  whether her input belongs to XR or not. If not, we have at most L+A<1/2 leaves left. If it does, then we have R<1/2 leaves left.

Case L+B<1/2: First Alice tells whether her input belongs to XR or not. If it does, then Bob tells whether his belongs to Y0 or not, depending on this we have R or B leaves remaining. If the input of Alice is not in XR, then Alice tells whether her input is in XL or not. If it is, then we have L+B<1/2 leaves remaining. If not, we have at most D<1/2 leaves remaining.

In all cases we are done. Let me know what you think.


Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

Here is one way to prove the fact you are interested in.

Suppose $\rho_0$ and $\rho_1$ are density matrices.  Like every other Hermitian matrix, it is possible to express the difference $\rho_0-\rho_1$ as
$$\rho_0-\rho_1 = P_0-P_1$$ for $P_0$ and $P_1$ being positive semidefinite and having orthogonal images.  (Sometimes this is called a Jordan-Hahn decomposition; it is unique and easily obtained from a spectral decomposition of $\rho_0-\rho_1$.) Note that the fact that $P_0$ and $P_1$ have orthogonal images implies that they are simultaneously diagonalizable, which I interpret is the property you are interested in.

The trace norm of the difference $\rho_0-\rho_1$ (as you define it, with the multiplicative factor 1/2), is given by $$\|\rho_0-\rho_1\|_{\text{tr}} = \frac{1}{2}\operatorname{Tr}(P_0) + \frac{1}{2}\operatorname{Tr}(P_1).$$  Under the assumption that this quantity is 1, we will conclude that $P_0=\rho_0$ and $P_1=\rho_1$, which proves what you want to prove.

To draw this conclusion, note first that $\operatorname{Tr}(P_0)-\operatorname{Tr}(P_1)=0$ and $\operatorname{Tr}(P_0)+\operatorname{Tr}(P_1)=2$, so $\operatorname{Tr}(P_0)=\operatorname{Tr}(P_1)=1$.  Next, take $\Pi_0$ and $\Pi_1$ to be the orthogonal projections onto the images of $P_0$ and $P_1$, respectively.  We have $$\Pi_0 (\rho_0 - \rho_1) = \Pi_0 (P_0 - P_1) = P_0$$ so $$\operatorname{Tr}(\Pi_0 \rho_0) - \operatorname{Tr}(\Pi_0 \rho_1) = 1.$$ Both $\operatorname{Tr}(\Pi_0 \rho_0)$ and $\operatorname{Tr}(\Pi_0 \rho_1)$ must be contained in the interval [0,1], from which we conclude that $\operatorname{Tr}(\Pi_0\rho_0)=1$ and $\operatorname{Tr}(\Pi_0\rho_1) = 0$.  From these equations it is not difficult to conclude $\Pi_0\rho_0=\rho_0$ and $\Pi_0\rho_1=0$, and therefore $P_0=\rho_0$ by the equation above.  A similar argument shows $P_1=\rho_1$.


Are biases necessary to make neural networks universal approximators when using sigmoid activations?

No, you don't need a bias. You can have a "dummy" input (input(n+1) in your formualtion) which is always set to 1. Then the bias term is absorbed into the weights.


Are you aware of the work on positive LPs/SDPs? There are a bunch of results in the area, mostly along the lines of "if the constraints of the LP/SDP are positive, then the problem can be solved in NC."

Some important references in this line of work are Luby-Nisan 93 and Jain-Yao 11. Another excellent resource is this slide of Rahul Jain's talk at the "Recent Progress in Quantum Algorithms" conference at IQC. The entire talk is available on youtube.


The number of integral points in a polytope

Check out

https://www.math.ucdavis.edu/~latte/

and the corresponding paper

Effective lattice point counting in rational convex polytopes. Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, Ruriko Yoshida. Journal of Symbolic Computation 2004 38:4, 1273-1302.

The algorithm they implement was introduced in

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Alexander I. Barvinok. Mathematics of Operations Research 1994 19:4, 769-779.


Algorithms to synthesize optimal plans satisfying temporal logic constraints

Maybe take a look at http://www.syntcomp.org/

This is a competition of tools solving the LTL synthesis problem (and some related problems).


Lengths of "all-accepted" words in Context Free languages

The shortest word in $A_L$ is not bounded by a recursive function in the size of a given context-free grammar describing $L$. See here for more results in that direction:
https://doi.org/10.4230/LIPIcs.STACS.2020.16


On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures

The technique of "hopping" from one game to another, and proving the security through a "sequence of games" is not new. In particular, there are several papers which discuss these techniques, and exemplify them through various security proofs. The famous examples are:

Sequences of Games; A Tool for Taming Complexity in Security Proofs by Victor Shoup (2006)
Code-Based Game-Playing Proofs and the Security of Triple Encryption by Mihir Bellare and Phillip Rogaway (2008). Side note: This paper is a bit hard to grasp, so don't start with this one! The extended abstract of this paper is published in Eurocrypt 2006 under the name The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs.
A Note on Game-Hopping Proofs by Alexander W. Dent (2007). Side note: This paper introduces another famous technique which was omitted from the above two papers.

Regarding your question, I use a quote from the last paper cited above:

  In a game hopping proof, we observe that an attacker running in a particular attack environment has an unknown probability of success. We then slowly alter the attack environment until the attacker’s success probability can be computed. We also bound the increase in the attacker’s success probability caused by the changes to the attack
  environment. Thus, we can deduce a bound for the attacker’s success probability
  in the original environment.

Thus, the reason for using several games is that in each game, we simplify the computation of some unknown probability, without altering it in a significant way. This continues until we reach a game in which the computation of the probability is easy enough.


Reference for NP-hardness of 3-colouring?

László Lovász, Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973, pp. 3--12, proved that Chromatic number reduces to 3-colourability.

I think, that is the first proof for NP-completeness of 3-colourability.

Here is Lovász's paper; see also Vašek Chvátal's excellent explanation to Lovász's reduction.


Chromatic number of planar graph with girth at least k

This paper: http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf
gives an $O(n\log{n})$-time 3-colouring algorithm for triangle-free planar graphs, improving on Thomassen's $O(n^2)$-time constructive proof.

I'm not exactly sure, but does this answer your question?


Is there a computation class describing FOR-programs, what are the limitations?

Having just asked a very similar question:

The language of for programs can express exactly the primitive recursive functions -- see Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.  (I found a copy online here.)

The complexity class for the p.r. functions is called PR.


Understanding performance of QFBV SMT solvers

The short answer is no, we don't understand it.  The long answer is yes, we have some bounds, but those bounds aren't very helpful.  It's quite clear that the worst-case running time is exponential.  That's not very helpful, because we know that in some/many practical situations, it seems to run fairly rapidly -- and we don't really know why.

We don't know why that is true for SAT solvers, let alone for QFBV.  Understanding why QFBV solvers are often fast seems at least as hard as understanding why SAT solvers are often fast, which is already beyond our current level of understanding.  If you search more on this site you can find a summary of current attempts to understand the latter topic.


Not really an answer, but an extended comment on András's answer.

András's answer contains a nice intuition, though I do not believe it is a rigorous calculation of the expected number of steps. I think it is perhaps a good approximation to an answer, but it does not seem to properly deal with cases where the bin below the highest occupied bin becomes empty before that the upper bin is emptied downwards. Still, this might be a reasonable approximation to make (I'm not sure).

His calculation contains an error which affects the scaling. I'm going to take exactly the same starting point, and redo and expand the calculation.

It misses a factor of p inside the summation, as the probability of randomly choosing the correct bin is $\frac{p}{n}$ rather than $\frac{1}{n}$. As a result we have

$\begin{eqnarray*}
n + \sum_{p=1}^n \sum_{k=0}^{\infty} (k+1) \frac{p}{n} \left(\frac{n-p}{n}\right)^k
& = & n + \sum_{p=1}^{n} \frac{p}{n} \sum_{k=0}^{\infty} (k+1) \left(\frac{n-p}{n}\right)^k
\\\\& = & n + \sum_{p=1}^{n} \frac{p}{n} \cdot \frac{n^2}{p^2}
\\\\& = & n + n\sum_{p=1}^{n} 1/p
\\\\& = & n (1+H_n)
\end{eqnarray*}$

where $H_n = \sum_{p=1}^{n} 1/p$ is the nth Harmonic number. To approximate $H_n$ we can simply replace the summation with an integral: $H_n \approx \int_{1}^{n+1} \frac{1}{x} dx = \log(n+1)$. Thus the scaling is $n (1+\log(n+1))$ or approximately $n \log(n+1)$. While this scaling does not match the scaling of the problem exactly (see simulation below) it is out by almost exactly a factor of $\log(2)$.

Red circles: Data points from simulation of process averaged over 10k runs. Green: $n \log_2(n+1)$. Blue: $n \log(n+1)$.


Recap:

At this stage in the proof of Ladner's Theorem, it has already been shown that $H(n)$ tends towards $\infty$ as $n$ does. You are assuming that $\text{SAT}_H$is $\text{NP-complete}$ for the sake of contradiction. Equivalently: $\text{SAT} \le_p \text{SAT}_H$.

The mapping used in the reduction, $f(x)$, maps $\langle \varphi , pad \rangle$ to a $\langle \varphi' , pad \rangle$. Because of the polynomial time limitation, $\langle \varphi' , pad \rangle$ has to be, at most, of size $c\left|\langle \varphi , pad \rangle\right|^c$. If the size of $\varphi$ remains unchanged, then the length of the padding causes $\langle \varphi' , pad \rangle$ to be too large.

The only alternative is to assume that $f(x)$ somehow reduces the size of $\varphi$ to compensate for possible growth of the padding. It is pointed out that size of $\varphi'$ is less than or equal to $\left|\varphi\right|/2$.

The primary observation here is that $f(x)$ has significantly reduced the size of the $\varphi$ we need to consider in polynomial time.

Answer:

Take padding out of the picture completely and just consider instances of $\text{SAT}$ (with formula $\varphi$). Take a modification of $f$ to ignore padding and compose it $\text{log}_2(\left|\varphi\right|)$ times on our input $\varphi$. The result is a boolean formula, $\varphi^*$, of constant size that is satisfiable if and only if $\varphi$ is. The satisfiability of $\varphi^*$can trivially be determined in far less than polynomial time. So overall, this entire procedure must decide any $SAT$ instance in polynomial time.

Because this violates Ladner's assumption that $\text{P} \ne \text{NP}$, $\text{SAT}_H$ could not possibly be $\text{NP-complete}$.


Why is the Greedy Conjecture so difficult?

Let me first try to summarize what is known about the Greedy Conjecture.

Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem.
A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, Tromp, Yannakakis).
The Greedy Conjecture holds when all the input strings all of length at most $3$ (Tarhio, Ukkonen; Cazaux, Rivals) or $4$ (Kulikov, Savinov, Sluzhaev).
The Greedy Conjecture holds if the Greedy Algorithm happens to merge strings in some specific order (Weinard, Schnitger; Laube, Weinard).
The Greedy Algorithm gives a 2-approximation of the compression Tarhio, Ukkonen (which is defined as the total length of the input strings minus the length of the shortest common superstrting).
There is an extremely efficient implementation of the Greedy Algorithm Ukkonen.

I think that one of the reasons why it's hard to prove the Greedy Conjecture might be the following.
Most of the approaches to proving approximation guarantees of the Greedy Algorithm analyze the overlap graph (or, equivalently, the prefix graph) of the input set of strings. We know only some properties of these graphs (such as Monge and Triple inequalities), but these properties are provably not sufficient for proving the Greedy Conjecture (Weinard, Schnitger; Laube, Weinard).


Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious.
For the record, here's a sketch of a reduction that is parsimonious.
It is obtained by composing parsimonious reductions from 3-SAT to 1-in-3-SAT, from 1-in-3-SAT to a problem we call 1+3DM, and from 1+3DM to 3DM.  We sketch each of these next.
Lemma 1. There is a parsimonious poly-time reduction from 3-SAT to 1-in-3-SAT.
Note: This reduction comes originally from [1].  [2] points out that it is parsimonious.
[1] Schaefer, Thomas J. The complexity of satisfiability problems, 1978, Proceedings of the tenth annual ACM symposium on Theory of computing.
[2] V. Bura. A Kernel Method for Positive 1-in-3-SAT.  draft on arXiv.org.
Proof sketch.  Given any 3-SAT instance $\Phi$, obtain $\Phi'$ from $\Phi$ by replacing each clause $x \vee y \vee z$ by the clauses $(\lnot x \vee u_1 \vee u_2) \wedge (y \vee u_2 \vee u_3) \wedge (\lnot z \vee u_3 \vee u_4)$, where $u_1, u_2, u_3, u_4$ are new variables specific to this clause.  The satisfying assignments for $\Phi$ then correspond bijectively to assignments for the modified formula $\Phi'$ such that exactly one literal in each clause is true. $~~~\Box$
For example, in an assignment for $\Phi$ that makes $x$ and $y$ true and $z$ false, the corresponding assignment for $\Phi'$ would extend that assignment by taking $u_1$ to be true, and $u_2, u_3, u_4$ to be false.
Next define 1+3DM to be the following variant of 3DM.  The input $(X,Y,Z,T,S)$ consists of three pairwise-disjoint sets $X, Y, Z$ each containing $n$ elements, a collection of triples $T \subseteq X\times Y \times Z$, and a collection of singletons $S\subseteq X \cup Y \cup Z$. The problem is to choose some of the triples and singletons so that each element is in exactly one of the chosen triples or singletons.  For technical reasons, we restrict to instances where, for every valid matching (solution), the set of chosen singletons distinctly determines the solution.
Lemma 2. There is a parsimonious reduction from 1-in-3-SAT to 1+3DM.
Proof sketch.  Given a 1-in-3-SAT formula $\Phi$, the reduction produces the following instance of 1+3DM.
For every variable $a$ in $\Phi$, let $k$ be the number of occurrences of $a$ in $\Phi$.  Build a variable gadget of "size" $k$ as follows.  First, create $4k$ new elements $a_1, a_2, \ldots, a_k$, and $\overline a_1, \overline a_2, \ldots, \overline a_k$, and $y_1, y_2, \ldots, y_k$ and $z_1, z_2, \ldots, z_k$.  For each $i\in\{1,2,\ldots, k\}$ add triples $(a_i, y_i, z_i)$ and $(\overline a_i, y_i, z_{i-1})$, interpreting $z_0$ as $z_k$.  Here's an illustration for $k=3$:
$~~~$
Note that in any solution either the $k$ triples of the form $(a_i, y_i, z_i)$ must be chosen, or the $k$ triples of the form $(\overline a_i, y_i, z_{i-1})$ must be chosen.  Hence, either all $k$ $a_i$'s are left uncovered, or all $k$ $\overline a_i$'s are left uncovered.
For every clause create a "clause gadget" as follows.  We'll illustrate the construction by example.  For the clause $a\vee \overline b \vee c$ in $\Phi$, select elements $a_h$, $\overline b_i$, $c_j$ (one for each literal in the clause), from the previously created variable gadgets, where the indices are chosen so that the clause contains the $h$th, $i$th, and $j$th occurrences of the variables $a$, $b$, and $c$, respectively, in $\Phi$.
Create two new nodes $y,z$.
Add three triples $(a_h, y, z)$, $(\overline b_i, y, z)$, and $(c_j, y, z)$:
$~~~$
Finally add three elements $\overline a_h$, $b_i$, and $\overline c_j$ (for the complements of the literals in the clause) to the set of singletons $S$.  These "singleton" elements do not occur in any triple in any clause gadget, although they do occur in triples in their respective variable gadgets.
Note that, for each variable $a$, among each pair of elements $a_i$ and $\overline a_i$ in the variable gadget, one of $a_i$ or $\overline a_i$ occurs in a triple in any clause gadget, while the other does not and is an allowed singleton.
Note that any solution must choose one of the triples in each clause gadget, thereby covering one of the three elements for the literals in the clause.
This completes the reduction.
To verify that it is correct, consider any 1-in-3 satisfying assignment $A$ for $\Phi$.  The corresponding matching uses the following triples.  For each variable $a$ that is true, use the triples of the form $(\overline a_i, y_i, z_{i-1})$ to cover all elements in the variable gadget except the $a_i$'s; also, for each element $a_i$ that is not used in any clause gadget, choose $a_i$ as a singleton.
For each variable $a$ that is false, use the triples of the form $(a_i, y_i, z_i)$ to cover all the elements of the variable gadget except the $\overline a_i$'s; also, for each element $\overline a_i$ that is not used in any clause gadget, choose $\overline a_i$ as a singleton.
For each clause, e.g., $a\vee \overline b \vee c$, select the true literal, and use the triple from the clause gadget that contains that literal.  E.g. if $a$ is true, use the triple $(a_i, y, z)$ from the clause gadget.
The above correspondence is a bijection between 1-in-3 assignments to $A$ and valid matchings, so the reduction is correct.
The instance meets the technical requirement that, for every valid matching, the set of chosen singletons is distinct.  This is because, for each variable, for each occurrence of that variable, the singleton is used iff the corresponding assignment sets the variable so that the literal does not satisfy the clause, so the presence or absence of the singleton determines the value assigned to the variable.  So the set of chosen singletons determines the corresponding assignment, which in turn determines the entire matching. $~~~\Box$
Lemma 3. There is a parsimonious reduction from 1+3DM to 3DM.
Proof idea. Given any instance $(X, Y, Z, T, S)$ of 1+3DM, the reduction outputs the instance $(X', Y', T')$ of 3DM obtained as follows.
Create three copies of each of $(X, Y, Z, T)$, with all copied elements distinct.
Label them $(X_1, Y_1, Z_1, T_1)$, $(X_2, Y_2, Z_2, T_2)$, and $(X_3, Y_3, Z_3, T_3)$.
Let $X'=X_1 \cup Y_2 \cup Z_3$, and $Y'= X_2 \cup Y_3 \cup Z_1$, and $Z'=X_3\cup Y_1 \cup Z_2$.
Let $T' = T_1 \cup T_2 \cup T_3 \cup S'$ where
$$S' = \big\{\{s_1, s_2, s_3\} : s \in S\big\},$$
where $s_1$, $s_2$, and $s_3$ are the three copies of element $s$
(that is, $s_i$ is the copy of $s$ that occurs in $X_i \cup Y_i \cup Z_i$).
Given any (1+3D) matching $M$ for $(X, Y, Z, T, S)$, the corresponding matching for $(X', Y', Z', T')$ is obtained by choosing, for every triple $(x, y, z)$ in $M$, the three corresponding triples in $T'$,
namely $(x_1, y_1, z_1)$, $(y_2, x_2, z_2)$,  and $(z_3, y_3, x_3)$,
along with a triple $(s_1, s_2, s_3)$ for each singleton $s$ in $M$.
This correspondence is bijective because of the technical assumption that the chosen singletons determine the matching $M$. $~~~~\Box$


L-systems, are more about general : Abstract rewriting systems rather then to concrete application.

Agree, a wide range of L-systems applications is in computer graphics (generating nature, textures etc), while from mathematical point of view, they are still, the same model.

As stated in referred by you L-systems definition :

  Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen.

Coming back to your question

  Yet in (...) implementation, even where a symbol is not defined, it will still be rendered as a full length. The question is, why?

Answer: Because that's the way, how those implementations' authors decided to map symbols into rendering commands.

You can do in your implementation any other mapping... and still both of them can be same type of system - L-system.

It's all about defining isomorphism between systems behind implementations, or homomorphism between those systems and graphics they generate. If you will make your own implementation, that will draw symbols differently - you will indirectly define your own homomorphism.


For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

Thanks to my colleague Maxim Zhukovskii for suggesting this answer.

It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and $H=K_{m+1}\sqcup \overline{K_{m-1}}$ for $n=2m$ and $G=K_m\sqcup \overline{K_{m+1}}$ and $H=K_{m+1}\sqcup \overline{K_m}$ for $n=2m+1$. (Here $K_s$ is an $s$-clique and $\overline{K_s}$ is a set of $s$ isolated vertices). By considering the Ehrenfeucht game one can show that in the first case the minimal possible depth is $m$ and in the second case it is $m+1$.

It was shown in the paper "The first order definability of graphs: Upper bounds for quantifier depth" by Oleg Pikhurko, Helmut Veith and Oleg Verbitsky that this bound is almost tight and any two $n$-vertex graphs are distinguishable by a formula of depth $\frac{n+3}{2}$.