Trivial upper bound for distribution testing

You might find this short note helpful ($\LaTeX$ code available [1]
 if the binary link breaks). I am reproducing the relevant part below:

  Theorem. (Folklore)  Learning an unknown distribution over a known domain of size $n$, up to total variation $\varepsilon\in(0,1]$, and with error probability $\delta\in(0,1]$, has sample complexity $O\!\left(\frac{n+\log(1/\delta)}{\varepsilon^2}\right)$. (Moreover, this can be done efficiently.)

Proof. Consider the empirical distribution $\tilde{p}$ obtained by drawing $m$ independent samples $s_1,\dots,s_m$ from the underlying distribution $p\in\Delta([n])$:
\begin{equation}\label{def:empirical}
\tilde{p}(i) = \frac{1}{m} \sum_{j=1}^m \mathbb{1}_{\{s_j=i\}}, \qquad i\in [n]
\end{equation}

First, we bound the expected total variation distance between $\tilde{p}$ and $p$, by using $\ell_2$ distance as a proxy:
$$
    \mathbb{E}{ d_{\rm TV}(p,\tilde{p}) }
    =\frac{1}{2}\mathbb{E}{ \lVert{p-\tilde{p}}\rVert_1}
    =\frac{1}{2}\sum_{i=1}^n\mathbb{E}{ \lvert{p(i)-\tilde{p}(i)}\rvert }
    \leq\frac{1}{2}\sum_{i=1}^n\sqrt{\mathbb{E}{ (p(i)-\tilde{p}(i))^2} }
$$
the last inequality by Jensen. But since, for every $i\in[n]$, $m\tilde{p}(i)$ follows a $\operatorname{Bin}({m},{p(i)})$ distribution, we have
$\mathbb{E}{ (p(i)-\tilde{p}(i))^2} = \frac{1}{m^2}\operatorname{Var}[m\tilde{p}(i)] = \frac{1}{m}p(i)(1-p(i))$, from which
$$
    \mathbb{E}{ d_{\rm TV}(p,\tilde{p}) } \leq\frac{1}{2\sqrt{m}}\sum_{i=1}^n\sqrt{p(i)} \leq \frac{1}{2}\sqrt{\frac{n}{m}}
$$
the last inequality this time by Cauchy—Schwarz. Therefore, for $m\geq \frac{n}{\varepsilon^2}$ we have $\mathbb{E}{ d_{\rm TV}(p,\tilde{p}) }\leq \frac{\varepsilon}{2}$.
Next, to convert this expected result to a high probability guarantee, we apply McDiarmid's inequality to the random variable $f(s_1,\dots,s_m) \stackrel{\rm def}{=} d_{\rm TV}(p,\tilde{p})$, noting that changing any single sample cannot change its value by more than $c\stackrel{\rm def}{=} 1/m$:
$$
    \mathbb{P}\left\{ \lvert{f(s_1,\dots,s_m) - \mathbb{E}{f(s_1,\dots,s_m)}\rvert} \geq \frac{\varepsilon}{2} \right\} \leq 2e^{-\frac{2\left(\frac{\varepsilon}{2}\right)^2}{mc^2}} = 2e^{-\frac{1}{2}m\varepsilon^2}
$$
and therefore as long as $m\geq \frac{2}{\varepsilon^2}\ln\frac{2}{\delta}$, we have $\lvert{f(s_1,\dots,s_m) - \mathbb{E}{f(s_1,\dots,s_m)}\rvert} \leq \frac{\varepsilon}{2}$ with probability at least $1-\delta$. $\square$

There is a second proof, somewhat more fun, given in that short note (credit to John Wright for pointing it out, and emphasizing it's the "fun" one). Here it is:

Proof. Again, we will analyze the behavior of the empirical distribution $\tilde{p}$ over $m$ i.i.d. samples from the unknown $p$.  Recalling the definition of total variation distance, note that $d_{\rm TV}({p,\tilde{p}}) > \varepsilon$ literally means there exists a subset $S\subseteq [n]$ such that $\tilde{p}(S) > p(S) + \varepsilon$. There are $2^n$ such subsets, so we can do a union bound.

Fix any $S\subseteq[n]$. We have
$$
\tilde{p}(S) = \tilde{p}(i) = \frac{1}{m} \sum_{i\in S} \sum_{j=1}^m \mathbb{1}_{\{s_j=i\}}
$$
and so, letting $X_j \stackrel{\rm def}{=} \sum_{i\in S}\mathbb{1}_{\{s_j=i\}}$ for $j\in [m]$, we have
$
\tilde{p}(S) = \frac{1}{m}\sum_{j=1}^m X_j
$ where the $X_j$'s are i.i.d. Bernoulli random variable with parameter $p(S)$. Then, by a Chernoff bound (actually, Hoeffding):
$$
    \mathbb{P}\left\{ \tilde{p}(S) > p(S) + \varepsilon \right\} = \mathbb{P}\left\{ \frac{1}{m}\sum_{j=1}^m X_j > \mathbb{E}\left[\frac{1}{m}\sum_{j=1}^m X_j\right] + \varepsilon \right\} \leq e^{-2\varepsilon^2 m}
$$
and therefore $\mathbb{P}\left\{ \tilde{p}(S) > p(S) + \varepsilon \right\} \leq \frac{\delta}{2^n}$ for any $m\geq \frac{n\ln 2+\log(1/\delta)}{2\varepsilon^2}$. A union bound over these $2^n$ possible sets $S$ concludes the proof:
$$
    \mathbb{P}\left\{ \exists S\subseteq [n] \text{ s.t. }\tilde{p}(S) > p(S) + \varepsilon \right\} \leq 2^n\cdot \frac{\delta}{2^n} = \delta
$$
and we are done. $\square$

Note: a lower bound of $\Omega(\frac{n}{\varepsilon^2})$ (also folklore) is easy to derive from Assouad's lemma, by considering the family of distributions over $[n]$ where each pair of consecutive elements $(2i,2i+1)$ has either probabilities $(\frac{1+c\varepsilon}{n},\frac{1-c\varepsilon}{n})$  or $(\frac{1-c\varepsilon}{n},\frac{1+c\varepsilon}{n})$ for some suitable constant $c>0$. (Intuitively and a bit misleadingly: any learning algorithm has to "figure out" at least $\Omega(n)$ of these independent choices, but each of them requires $\Omega(1/\varepsilon^2)$ samples.)

[1] Public GitHub: https://github.com/ccanonne/probabilitydistributiontoolbox (includes the source for the note on Assouad's lemma as well).


Shor's quantum error correction code with unknown basis

Q1 : Fate of the 9 qubits
There is no (or 2) answer to your question, since it is implementation dependent :

If your implementation of the code is ideal, and you have a way to directly measure the syndromes, the 9 qubits are projected on the global 9 entangled qubits state. It is the case, for example, if the code is used in a fault-tolerant implementation of quantum computing.
If the implementation is more realistic, the measurement of the 8 syndromes is performed in 2 steps : 1st you apply a global unitary (through a quantum circuit) on the 9 qubits, then you measure 8 qubits, destroying them in the problem. You have then a single qubit, to which you can apply a unitary(depending on the measurement result) to get the single original qubit.

Q2: Effect of misalignment
The misalignment behaves like an error, whether $x$ is small or $π/4$ (as in your $\lvert±\rangle$ example). What you describe correspond to applying the operator $\cos x I +\sin x XZ$ to each qubit. Measuring the syndrome projects the state to one with a given number of errors, but as long as there is less than 1 X error and 1 Z error, the code is enough to correct it.
This condition happens with probability
$$(\cos^2 x)^9 + 9 (\cos^2 x)^8\sin^2 x=\cos^{16}x(1+8\sin^2x)\simeq 1-64x^4$$
the last approximation being valid for small $x$.
If the rotation is by $\pi/4$, the error rate is 50% and your code will not be able to correct it.


Asymmetry in Property Testing Definition

There is a notion of property testing in which 1) is indeed "x is epsilon'-close to some y in L" (where epsilon' < epsilon), which is called tolerant property testing. In general, tolerant testers are harder to design than property tester (since property testing is a special case).

In many cases, one can actually construct a one-sided error property tester which accepts all x in L with probability 1. These constructions rely on locally testing some sort of condition which things in L satisfy globally (and hence anything in L always passes) whereas inputs that are far away from L are unlikely to pass. For example, say you want to test whether a boolean function is linear, i.e. f(x) + f(y) = f(x+y). A natural test would be to randomly pick two points x,y and verify that f(x) + f(y) = f(x+y). Any f that is already linear always passes this test, and one can easily show that those f which are far from being linear fail this test with high constant probability. The problem with detecting if f is close to being linear comes from the fact that the probability of detecting this is too small.


An example where smallest normal lambda term is not fastest

Blum’s speedup theorem is usually stated in the language of partially recursive functions, but up to trivial differences in notation, it works just the same in the language of $\lambda$-calculus.

It says that given any reasonable complexity measure $M$ (for example, the optimal number of reductions as in the question) and a recursive function $f(x,y)$ (for example, $2^y$), we can find a recursive predicate $P(x)$ such that:

  For every algorithm (i.e., $\lambda$-term in normal form here) $g$ computing $P$, there is another algorithm $h$ for $P$ that has $f$-speedup over $g$:
  $$f(x,M(h,x))\le M(g,x)\text{ for all large enough inputs }x,$$

where $M(g,x)$ denotes the complexity of the computation of $g$ on input $x$ according to measure $M$.

Consequently:

$P$ has no asymptotically optimal algorithm in the given measure
in particular, the shortest algorithm for $P$ is not asymptotically optimal
for any algorithm for $P$, there is an asymptotically faster algorithm whose normal form is longer (because up to renaming of variables, there are only finitely many normal terms of a given length)


The Complexity of Advice in Computational Indistinguishability

Case 1. The distributions $U_n$ and $V_n$ are computable in the sense that we can eventually tell if your displayed inequality is violated, for fixed $n$ and $z$.

It seems the answer to the first question (following "The question is") is No in this case. Suppose there is a $D$ and a $p$ such that for infinitely many $n$, there is a $z$ violating the inequality. I claim we can find a computable function $f$ such that $f(1^n)$ is infinitely often such a $z$. What $f$ does is run all searches for $z$ for various values of $n$ in parallel. When one is found for some $n$, we define $f(1^n)=z$ and the searches for undefined values $m<n$ are called off and $f(1^m)$ is defined arbitrarily. Then another parallel search is instituted for a larger value of $n$.

Case 2, we do not make any assumption about $U$ and $V$. Then Yes. Both $U_n$ and $V_n$ will be deterministic in the following construction.

Let $D(1^n,w,z)$ simply compute whether $w=z$ and output 1 if this is the case. But $U_n$ and $V_n$ will output the $n$th element $s_n$, $t_n$, of sets $S$ and $T$, respectively. Then such a function $f$ would have the property that infinitely often $f(1^n)=s_n\ne t_n$ or vice versa. Now suppose that $n\mapsto s_n$ and $n\mapsto t_n$ both dominate all computable functions, and $\{n: s_n\ne t_n\}$ is infinite (such sets $S$ and $T$ clearly exist). Then a function $f$ exists with the required property, but cannot be computable.


Graphs-like data structure with weighted vertices

Your description of an example of your question #2 of having vertex weights and distributing the weight on some $v$ to its neighbours sounds reminiscent of the discharging method famously used in proofs towards the 4-colour theorem. That method, though, had weights assigned to vertices and to the faces of the (planar) graph. But I believe the discharging method has found other applications. Here is a thesis on discharging methods: https://tel.archives-ouvertes.fr/tel-02083632/document
As for your general question #2 of example problems studied with vertex weights, consider looking up

graceful labelings (e.g. https://en.wikipedia.org/wiki/Graceful_labeling)
channel assignment problems (e.g. https://www.sciencedirect.com/science/article/pii/S0166218X04002562)
any vertex selection problem (like max clique, min vertex cover, etc) has a vertex-weighted analogue
problems that choose orderings of vertices (i.e. assign a timestamp to vertices) like in fire-fighter problems (https://www.sciencedirect.com/science/article/pii/S0012365X0600776X)  or graph burning problems (https://arxiv.org/abs/1507.06524)
the definition of threshold graphs involves looking at a vertex-weighted graph and adding an edge between any two vertices whose sum of vertex weights exceeds some threshold value: https://en.wikipedia.org/wiki/Threshold_graph

Here is a paper talking about more application problems of vertex-weighted graphs: https://www.researchgate.net/publication/268065544_Vertex-weighted_graphs_and_their_applications


Example of a function that you can write in Calculus of Constructions but not in System-F

Since the CoC has dependent types and system $F$ does not, I'll assume you mean a function whose types is in system $F$, but whose definition can only be written in CoC. Luckily in this case we can restrict to system $F_\omega$, which can express the same non-dependent functions as CoC, by some erasure argument.

In general, a rule of thumb to construct such functions is to consider systems $F$ and $F_\omega$ as the language of realizers of theorems of 2-nd and higher-order arithmetic, respectively, and to prove a theorem of the form $\forall x, \exists y, P$ in one not provable in the other, which by extraction should be a function definable in one and not the other.

One such theorem is the proof of normalization of system $F$ itself, which is provable in higher-order arithmetic using the "standard" proof, and not in 2nd order arithmetic by a simple diagonalization argument (though it is instructive to see where the standard proof fails).

Extracting this gives a normalization function for encodings of system $F$ terms, definable in system $F_\omega$, but not in system $F$.

I've explained this a bit in a related answer.


Hardness of constrained star system problem?

You may take a look at The Star System Problem revived. Among other things, the authors prove that:

  if the graph $G$ is required to be $C_k$-free, i.e. not allowed to have an induced cycle of length $k$, then the problem is solvable in polynomial time for each $k \le 4$, and is NP-complete for each $k>5$.

In addition, you may find the papers in this list useful.


Algorithm whose running time depends on P vs. NP

If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:

Input: N   (integer in binary format)
For I = 1 to N do
begin
  if I is a valid encoding of a proof of P = NP in PA (or ZFC)
    then halt and accept
End
Reject

Another - less trivial - example that relies on no assumption is the following:

Input: x   (boolean formula)
Find the minimum i such that
  1) |M_i| < log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration]
  2) and  M_i solves SAT correctly
       on all formulas |y| < log(log(|x|))
          halting in no more than |y|^|M_i| steps
          [ checkable in polynomial time w.r.t. |x| ]
  if such i exists simulate M_i on input x
      until it stops and accept/reject according to its output
      or until it reaches 2^|x| steps and in this case reject;
  if such i doesn't exist loop for 2^|x| steps and reject.

If $P =NP$ the algorithm will soon or later - suppose on input $x_0$ - find the index of the polynomial time Turing machine (or a padded version of it) $M_{SAT}$ that solves SAT in $O( |x| ^ { |M_{SAT}| })$ and for all inputs greater than $x_0$ will continue to simulate it and halt in polynomial time (note that step 2 can also be checked in polynomial time). In other words if $P = NP$ the algorithm solves SAT in polynomial time on all but a finite number of instances.

If $P \neq NP$ the algorithm runs in exponential time.


Time complexity of Held-Karp algorithm for TSP

Addendum to below, clarifying the $k(k-1)$ terms:

So, if you examine the terms in the expression, you can envision (as analogy) the $n-1 \choose k$ term is an enumeration of all binary strings containing $k$ 1's that have a 1 in the first position. In other words, we let each position in the binary string represent the choice of whether a given one of the $n$ cities in the problem are in the exact subset we are considering at the time. So, for 5 cities, 10101 corresponds to the subset {1,3,5}.

Thus, to compute across all subsets of {1,...,$n$}, we simply count through each binary subset (i.e. count through binary strings) of size=2 (i.e. binary strings of size $n$ that contain two 1's), then size=3, then size=4, ...then size=n. (Note that the size=1 subset must contain only the first city, and thus it's irrelevant to compute its partial distance, since the distance from 1 -> all other cities in the subset -> 1 is exactly 0.)

At each subset with $k$ cities, we have to consider up to $k-1$ candidate-optimal, partial paths. Specifically, the optimal, total path could conceivably traverse through the given subset and end up on any of the $k-1$ cities, excluding the first city. Then, for each such candidate sub-path, we compute the optimal tour up to that point as the minimum of any of the previous, size=$k-1$ sub-paths plus the distance from the terminal city for that sub-path to the terminal city for the current candidate sub-path. This gives $(k-1)(k-2)$ such comparisons that we must make. The discrepancy between my $(k-1)(k-2)$ term, and the $k(k-1)$ term in the analysis linked is a notational difference (I would sum over a different range, given my definition of $k$ than they did). At the very least, however, it should illustrate the quadratic-order complexity of that term.

How interesting -- I just finished coding this exact algorithm up in C++ a few minutes ago. (So forgive the tangent from pure theory into a little practical discussion. :))

It costs $O(2^n n^2)$ time and $O(2^n n)$ space -- at least under my implementation. Practically speaking though, when your space requirements grow that fast, they become way more painful than the time requirements. For instance, on my PC (with 4 GB of RAM), I can solve instances with up to 24 cities -- any more than that, and I run out of memory.

Of course, I could just be a bad programmer, and you might be able to do better than me in practice. :)

Edit: A little more specifics on one detail of your question: The $k(k-1)$ term comes from the fact that you have to, in the worst case, calculate the partial, optimal distance from the previous subsets (there are at most $n$ of them; note that $k$ is summed over $n$ in the analysis you linked) to the current one. This requires, again in the worst case, $O(k)$ comparisons with subsets of size $k-1$ for a total of $O(k^2)$.

Also, if my explanation wasn't clear enough, here are some nice lecture notes of Vazirani's (PDF). Scroll down to P. 188 for a discussion of TSP, including an analysis of Held-Karp.


Unfortunately, there are many possible levels of description for a problem; choosing one among them is strictly dependent on your aims and on the tools available to you. In general, there are three possible approaches: analytical, numerical and observational. Each one is characterized by pro and cons. When you need to build a model, there are many possible decisions that must be made. For instance, you may decide among:

specific - general
model estimation - first-principles models
numerical - analytical
stochastic -deterministic
microscopic - macroscopic
discrete - continuous
qualitative - quantitative

and so on. You must understand that, in general, there are no rigorous rules of thumb when making these choices. As pointed out by @Suresh, this a matter of experience, requires a careful understanding of the domain, and some inspired guessing as well. The good news is that once you have made your choices, then there are rigorous ways to proceed. Probably, the best model overall for a given problem is the one given by the Minimum Description Length Principle (essentially the Occam's razor): the best model is the smallest one. But determining it is beyond hope. So, the best model is almost always, the one that works best for you, given your explicit and even implicit assumptions.

That said, analytical and numerical approaches allows you to explore the behavior of a model, but the assumption here is that the underlying model is known. It's up to you to derive this model. Observational approaches allows you to derive a model from the experimentally observed data.

Analytical models may lead to a closed-form solution; they are of great importance, given their power: if and when an analytical model may be successfully applied, then you will be able to deduce almost everything there is to know about a system. Their major drawback is limited applicability, since much of the world is simply too complicated to be described this way. Examples include ODE, PDE, difference equations, variational calculus and stochastic processes.

Numerical models are required when the equations in an analytical model are too complex to be solved exactly in closed-form. This usually happens as soon as we move too far from linearity to nonlinearity. It's important to remember that numerical and analytical solutions are complementary approaches rather than exclusive alternatives. Examples include Runge-Kutta methods, finite element methods, cellular automata and lattice gases.

Observational models can come from introspection or observation (or both).In some cases you may want to infer a model from experimentally measured data.This model may then be used to characterize and classify the data at hand, or to generalize from the measurements to predict the outcome of new observations etc. Examples include function fitting, SVD, Fourier and Wavelets transforms, neural networks, genetic algorithms, Expectation-Maximization algorithms, Wiener and Kalman filters, HMM, and time series.

A very good introductory book you may want to read is The nature of mathematical modeling. Of course, given the huge amount of topics covered, do not expect a detailed treatment.


Are there NP-complete problems with polynomial expected time solutions?

There is a polynomial time algorithm for finding Hamiltonian cycles on random graphs, that succeeds asymptotically with the same probability that a Hamiltonian cycle exists. Of course, this problem is NP-hard in the worst case.

They also show that a dynamic programming algorithm which is always guaranteed to find a Hamiltonian cycle, if it exists, has polynomial expected running time, if the input distribution is uniformly random over the set of all $n$ vertex graphs.

Reference: "An algorithm for finding Hamilton cycles in random graphs"

Bollobas, Fenner, Frieze

http://portal.acm.org/citation.cfm?id=22145.22193


Densest k subgraph problem for outerplanar graphs?

It can be solved in linear time in an even more general class of graphs: As shown in

N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V.T. Paschos
Exact and approximation algorithms for densest $k$-subgraph
WALCOM’13, LNCS, vol. 7748, Springer-Verlag (2013), pp. 114-125

the Densest-$k$-Subgraph problem can be solved in $O(2^{\mathrm{tw}(G)}\cdot k \cdot ((\mathrm{tw}(G)^2)+k)\cdot |X|)$ time when a tree decomposition $(X,T)$ of the input graph $G$ is given. Since outerplanar graphs have treewidth at most two, the Densest-$k$-Subgraph can be solved in $O(k^2 n)$ time on outerplanar graphs with $n$ vertices.


What is "Synthetic Network" in Network Science?

It's difficult to answer if you don't explain more precisely the context, but I think it would be networks generated using some random model such as Watts-Strogatz's, Barabasi-Albert's, etc.


Since your question is: "What is known?" Here's something:

http://arxiv.org/abs/1307.3033

This gives an average case analysis of the Ford-Johnson Algorithm. The expected number of comparisons is $\log n! +cn$ for a surprisingly small constant $c$ (about .05).


The usual terms I know from the theory of posets and lattices are downset and upset (or upper set). Also as the empty set is a subset of every set, I think your first condition is vacuous as long as the system is not empty. Same for the first condition in the second definition.

If a downset is closed under joins (in your case set unions), it is called an ideal. If an upset is closed under meets (in your case set intersections), it is called a filter.


The minimum number of arithmetic operations to compute the determinant

It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant.  See for example this table on Wikipedia, as well as its footnotes and references.  Note that the asymptotic complexity of matrix inversion is also the same as matrix multiplication in this same sense.

The equivalence is quite effective.  In particular, you can recursively compute the determinant of a $n\times n$ matrix by working on $(n/2) \times (n/2)$ blocks using the Schur complement:

$$ \text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C). $$

Thus, you can compute an $n\times n$ determinant by computing two $(n/2)\times (n/2)$ determinants, inverting one $(n/2)\times (n/2)$ matrix, multiplying two pairs of $(n/2)\times (n/2)$ matrices, and some simpler operations.  Expanding the determinant calls recursively, the complexity ends up being dominated by the matrix multiplication and inversion.

This works well even for small $n$ and even without using sub-cubic matrix multiplication algorithms.  (Of course, it ends up being more-or-less equivalent to Gaussian elimination.)  For example, for $n=4$, we can compute $\det(D)$ with two multiplications, $D^{-1}$ with four divisions, $BD^{-1}C$ with $2\times 8=16$ multiplications, $\det(A-BD^{-1}C)$ with two multiplications, and the final answer with one multiplication.  The total number is $2+4+16+2+1=25$ multiplications plus divisions, which is less than the $40$ from cofactor expansion.  Using Strassen's algorithm saves two multiplications here, but more asymptotically.

You may notice that this expansion crucially uses division.  If you wish to avoid division, then one can do so in $O(n^4)$ operations by working with Clow sequences and dynamic programming.  It is also known how to achieve $n^{2+\omega/2+o(1)}$ multiplications and no divisions.


The described concept is known as graph grammars and dates back into the 1970ies. Searching for this yields a sufficient amount of references. The terms "Graph Transformation" and "Graph Rewriting" are also used. See e.g. Wikipedia on Graph Rewriting.


Proof for Kolmogorov complexity is uncomputable using reductions

You can find two different proofs in:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)

In Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications it is presented as an exercise (with a hint on how to solve it that is credited to P. Gács by W. Gasarch in a personal communication Feb 13, 1992).

** I decided to publish an extended version of it on my blog.


Finding the closest pair between two sets of points on the hypercube

Just realized that you are asking for the case that $|M|=|N|=d$. Then you can do matrix multiplication, right? Write $M$ is a row matrix $X$, $N$ as a column matrix $Y$, negate the entries of $Y$, and compute the matrix $Z=XY$. Clearly, the $z_{i,j}$ is the Hamming distance between the $i$th point of $M$ and the $j$th point of $N$. According to the last breakthroughs this has running time $O(d^{2.3727})$ (but I have a 50,000 pages manuscript that shows how to do this matrix multiplication in $O(d^{2.3726999999})$ time by a really simple algorithm).

You can get similar effect if the matrices are not squares. I think Uri Zwick has a paper about fast matrix multiplication in this case.

In some sense, this is not too interesting - we want to avoid the $O(|M| * |N|)$  term. The improvements in the $d$ term are kind of meh, meh...


NBE for MiniTT: Why is labelled sum eliminator both a normal form and a neutral value?

They are different things. SClos is a case-split function, which is a function that pattern match on its parameter. Think of it as a lambda (if you know Haskell, you can think of it as a LambdaCase \case, which is a sugared lambda). This is definitely a canonical value in Mini-TT.
The neutral value, OTOH, is an application on a case-split function, where the argument supplied is neutral. If an instance of a sum type is neutral, you don't know which constructor it belongs to, so you don't know which clause in the pattern matching should be selected, so this is a neutral value.
Summary: pattern matching itself is canonical, while application on pattern matching is not. If this application stucks, it becomes a neutral value.


What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices

The best way to do it, if you want to generate billions of graphs is to read up on enumeration algorithms such as:

[Yasuko Matsui, Ryuhei Uehara and Takeaki Uno, Enumeration of Perfect Sequences of Chordal Graph (2008)]

However for many this may be more than what is needed.
An easier algorithm is:

Enumerate all chordal graphs on n-1 vertices.
For each chordal graph G on n-1 vertices and each clique C in G.
Create a graph G' by adding a vertex v with neighbours C.
If G' has not already been found, add G to the list of chordal graphs on n vertices.

By this algorithm you should be able to generate the chordal graphs on at most 11 vertices which means over a million graphs.


A simple approximation algorithm for the TSP

This is called an insertion heuristic. The general TSP cannot be approximated unless $P=NP$. The question is more interesting for the metric TSP. In that case, Rosenkrantz et al. (1974) show that your heuristic gives an $O(\log n)$ approximation.

You can also try to choose a good vertex $v$ to be inserted in each step, instead of just taking an arbitrary one. One variant is farthest insertion in which $v$ is chosen such that is has maximum distance from the current $H$. Another variant is nearest insertion in which $v$ is chosen such that it has minimum distance from the current $H$. Yet another possibility is cheapest insertion in which $v$ is chosen such that the new $H$ has minimum length. Rosenkrantz et al. show that both nearest and cheapest insertion give a $2-2/n$ approximation and this is tight.

The full reference is:
D. Rosenkrantz, R. Stearns, and P. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563-581, 1977.


reference for lexicographic path ordering

Some information at the right level of abstraction can be found in:

Nachum Dershowitz's A Taste of Rewrite Systems

If you are near a library or bookshop, this book has even more details:

Baader and Nipkov's Term Rewriting and All That


Lowerbound for the minimum distance between points in a "nice" triangulation

The short answer is: no, there is no such lower bound.

Let $p$ be a positive integer.
Let $\epsilon = \frac{1}{p}$.

Put points at coordinates $(i \epsilon, j \epsilon)$ for $i,j \in \{ 0 \dots p \}$, and at coordinates $(i \epsilon + \frac{\epsilon}{2}, j \epsilon + \frac{\epsilon}{2})$ for $i,j \in \{ 1 \dots p \}$.
You end up with $n = (p+1)^2 + p^2$ points, and a triangulation in which all triangles are both right and isosceles. So all angles are either $\frac{\pi}{2}$ or $\frac{\pi}{4}$, and the minimal distance between two points is $\frac{\epsilon}{\sqrt{2}}$.


How can I construct sorting network for $k$ numbers

there is some research angle here dating at least to Knuth's Art of Computer Programming and presumably earlier in finding optimal sorting networks for low $n$. its intractable to find optimal sorting networks for small $n$ but it has been done up to about $n=10$ eg as in this recent notable paper, also using SAT. details about how to reduce the problem to SAT are in the paper. basically a large SAT formula encoding is built that asserts "these boolean variables configure a circuit that sorts all inputs for size $n$". (the more nonresearch angle is to use existing sort algorithms or sorting network configurations as mentioned in the paper by Har-Peled you cite to generate the (nonoptimal) circuits, this is more like a CS/EE exercise.)

Optimal Sorting Networks Daniel Bundala, Jakub Závodný

  This paper settles the optimality of sorting networks given in The Art of Computer Programming vol. 3 more than 40 years ago. The book lists efficient sorting networks with n <= 16 inputs. In this paper we give general combinatorial arguments showing that if a sorting network with a given depth exists then there exists one with a special form. We then construct propositional formulas whose satisfiability is necessary for the existence of such a network. Using a SAT solver we conclude that the listed networks have optimal depth. For n <= 10 inputs where optimality was known previously, our algorithm is four orders of magnitude faster than those in prior work.


Encoding quadratic constraints in a constraint satisfaction problem into SAT

This of course depends on the type of satisfaction problems you are trying you encode in SAT. Assuming the general case, where your problem falls into the class of problems that can be handled by some existing encoding techniques (a review of some techniques can be found in [1]), some techniques are specific to support encoding quadratic constraints (and arithmetic operations such as multiplication, in general):

1) Some of the approaches for encoding quadratic constraints, as well as other form of constraints that involve arithmetic operations, into SAT include encoding techniques often referred to as 'bit blasting' or such as the ones based on sparse encoding:

Bit blasting is a commonly used decision procedure for bit-vector arithmetic. Essentially, the idea is to represent bit-vector terms with vector of Boolean variables and emit constraints on the bits of those vectors depending on the constants and operations used in the formula, where arithmetic operations are encoded as "circuits", which effectively put constraints for every bit of the resulting vector. (More information about this technique can be found e.g. in [2]).
Sparse encoding (of integers) is an approach, interestingly different from bit blasting, which avoids using circuits by trying to precompute possible integer values and using guards in the encoding to designate when can a term hold a specific value (depending on the structure of the constraint and possible starting values). Such a technique might be superior to bit blasting for cases of considering smaller integer domains. (More details and the discussion about benefits of using this approach is presented in [3].)

2) There exist different ways of leveraging techniques such as bit blasting and sparse encoding for the purpose of encoding different (CSP) problems into SAT, while some of the mentioned literature directly suggests plausible algorithms: a standard approach for a translating algorithm is described in [2], while the algorithm that relies on sparse encoding is implemented in a software synthesizer Sketch, and described in detail through examples in [4].

[1] Walsh, Toby. "Sat v csp." International Conference on Principles and Practice of Constraint Programming. Springer Berlin Heidelberg, 2000.

[2] Kroening, Daniel, and Ofer Strichman. Decision procedures: an algorithmic point of view. Springer Science & Business Media, 2008.

[3] Solar-Lezama, Armando. Program synthesis by sketching.

[4] Solar-Lezama, Armando. "Program sketching." International Journal on Software Tools for Technology Transfer 15.5-6 (2013): 475-495.


The argument is the same, there are only $1 + 2 + 4 + ... + 2^{\delta n - 1}$ programs shorter than $\delta n$ so there are at least $2^n - (2^{\delta n} - 1)$ integers with $K(x) \geq \delta n$.


Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?

I think the answer to your first question is "no".

In particular, if you take a random bipartite graph $G=([n],[n],E)$
where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$,
the answer is no with probability close to 1.

I am interpreting your first question as follow:

Given any graph $G$, is it always possible to find a collection of subgraphs such that

each subgraph is a complete $k$-partite graph for some $k$,
each edge in $G$ occurs in at least one of the subgraphs, and
each vertex in $G$ occurs in at most a constant number of the subgraphs?

Proof.
Fix $n$.  Let $G$ be the random graph described above.

Since $G$ is bipartite any complete $k$-partite subgraph has to be bipartite.

First, I claim that with probability $1-o(1)$, every complete bipartite subgraph of $G$ has at most $4n$ edges.

(Here's why.
For any pair of subsets $L\subseteq [n]$ and $R\subseteq [n]$ with $|L\times R| \ge 4n$,
the probability that the complete bipartite subgraph with edge set $L\times R$
is in $G$ is $2^{-|L\times R|} \le 2^{-4n}$.
There are fewer than $2^n\times 2^n = 4^n$ such pairs $L$ and $R$,
Thus, by the naive union bound, the probability that any of
the corresponding subgraphs is present in $G$ is at most $4^n 2^{-4n} \le 2^{-2n}$.)

Also, with probability $1-o(1)$, the graph $G$ has at least $n^2/4$ edges.

Thus, with probability $1-o(1)$, every complete bipartite subgraph in $G$
has at most $4n$ edges, and $G$ has at least $n^2/4$ edges.
Assume this happens.

Now suppose for contradiction that a collection of subgraphs with the desired properties exists.
Each of the subgraphs has edge set $L\times R$ for some pair of subsets $L$ and $R$.
In $G$, direct all the edges in $L\times R$ from the larger side to the smaller side
(to the left if $|L|\le |R|$, and to the right otherwise).
Since $|L\times R|\le 4n$, the smaller of $L$ or $R$ must have size at most $2\sqrt n$.

Since each vertex is in $O(1)$ of the subgraphs, each vertex now has $O(\sqrt n)$
edges directed out of it.  But all edges are directed one way or the other,
so the number of edges in $G$ is at most the number of vertices
times the maximum out-degree of any vertex, that is, at most $O(n\sqrt n)$.
This contradicts the graph having at least $n^2/4$ edges.


Smallest known formula for the determinant

One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is described in Hrubeš and Tzameret, Short proofs for the determinant identities.


Number of vertices present in all maximum matchings

Is your graph bipartite? Because, if it is: suppose that one side of the bipartition is left and the other is right. Find a maximum matching, and orient all matched edges left-to-right and all unmatched edges right-to-left. Then a vertex $v$ can be omitted from a maximum matching if and only if one of the three following (mutually exclusive) conditions holds:

$v$ is already unmatched
$v$ can be reached from an unmatched vertex on its side of the bipartition in the resulting digraph
$v$ can reach an unmatched vertex on its side of the bipartition in the resulting digraph.

By doing two breadth-first or depth-first searches, one to find the parts of the graph that can be reached from unmatched vertices and one to find the parts that can reach unmatched vertices, you can find the essential vertices in linear time once you already have the matching.

Probably something like this will also work for the non-bipartite case, using a blossom-contracting alternating path search, but the details will be more complicated.


Examples of #P problems which are in FP ?

$SAT$ and $\#SAT$ for CNF formulas of bounded rank are tractable. See $[1]$.

Andrei S. et al. A hierarchy of tractable subclasses for SAT and counting
SAT problems. 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing.


I believe that these are exactly the ($C_4$, $P_4$, $2P_3$)-free graphs — that is, the graphs whose induced subgraphs do not include 4-cycles, 4-vertex paths, or the graphs formed from the disjoint union of two 3-vertex paths. This class seems to lie between the threshold graphs themselves, which may be characterized as the ($C_4$, $P_4$, $2K_2$)-free graphs, and the trivially perfect graphs (intersections of nested intervals), which may be characterized as the ($C_4$, $P_4$)-free graphs. I don't think it has a name; at least, it doesn't seem to be listed at graphclasses.org.

To see that this is the correct characterization, consider the representation of trivially perfect graphs as the transitive closures of rooted forests. A forest gives rise to a (connected) threshold graph if and only if it has a directed path that contains all non-leaf nodes: adding a new isolated vertex corresponds, in the forest, to adding a new single-node tree, which doesn't change this property, and adding a new vertex connected to all of the others corresponds to adding a new root connected to all the previous tree roots, which again doesn't change this property (the new root can be part of the path).

Now your clique-replacement operation corresponds, in the tree view of a trivially perfect graph, to subdividing tree edges into paths (or replacing a one-vertex tree by a path). The forests that you can get from this operation are the ones in which there is a single directed path that contains all nodes with two or more children. A forest has such a path if and only if it does not have two unrelated forks (nodes with two or more children, neither of which can reach each other). And the subgraph you get in your trivially perfect graph when there are two forks is exactly $2P_3$.

The graphs whose complements are in the class you ask about — that is, the ($2K_2$,$P_4$,co-$2P_3$)-free graphs — were studied by Gurski, who showed that they are the same as the graphs of linear clique-width at most two. See theorem 10 of Gurski, Frank, "Characterizations for co-graphs defined by restricted NLC-width or clique-width operations", Discrete Math. 306 (2006), no. 2, 271–277.


What evidence is there that $coRP \neq NP$?

When considering the power of non-determinism (P vs NP), randomization seems like a 2nd order issue.  In particular when we think about "P=NP?" we are really interested in the question "are all NP problems tractable", where randomization could be allowed, so tractability really means "in BPP".  So "NP contained in BPP" seems essentially as unlikely as "P=NP", and in fact if these were considered different then people would care about the former rather than the latter.  (The peculiar variant "NP in coRP" is formally somewhere in the middle between these two, but conceptually essentially the same).    If good enough pseudo random generators exist then the two questions are formally the same.  Similarly, in "non-uniform settings" randomization is known not to help and thus "NP in BPP" implies that NP has poly-size circuits.


I'm no expert on Kolmogorov complexity, but I think it could happen; here is some intuition. The $D$ and $D + d$ are represented by two strings $S(D)$ and $S(D + d)$, and $S(D)$ is a prefix of $S(D + d)$. So you're asking whether a prefix of a string can have higher Kolmogorov complexity than the string itself. I think this is the case:

Let $P$ be some randomly generated string of high complexity. Now let $X$ be the result of repeating $P$ a number of times, say 10 times. Let $Y$ a prefix of $X$ that is some characters shorter. Then a program to output $X$ would just say "repeat string $P$ 10 times", whereas the program to output $Y$ would have to say: "repeat string $P$ 10 times, and then subtract a couple of characters from the end". If $P$ is sufficiently complex then the intuition is that indeed the shortest way to generate $Y$ would be in this way, hence the program that generates $X$ is shorter than the one which generates $Y$, and the Kolmogorov complexity of $X$ would be lower than of its prefix $Y$.


Given a partition and an element, find the subset that includes this element

It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.


Translation of context-free parsing into SAT

(I guess the important word in the original question is ``published''.)  There is such an encoding of context-free parsing (more exactly of CYK-style parsing) in  Roland Axelsson, Keijo Heljanko, and Martin Lange, Analyzing Context-Free Grammars Using an Incremental SAT Solver, ICALP 2008, Lecture Notes in Computer Science vol. 5126, pp. 410--422, doi:10.1007/978-3-540-70583-3_34.  They use it in particular to detect ambiguity of words $w$ in context-free grammars for growing word lengths.


Theoretical computer scientists both design algorithms and prove their correctness and running time. For some algorithms, the correctness and running time are evident, while others require proof.
For the latter, without a proof it's hard to know whether the algorithm actually does what it should.
There are countless examples of small subtleties in algorithms that make enormous differences for performance (e.g., take a look at union-find data structures in CLRS).

An alternative could be running the algorithm and experimenting with it.
This is often an excellent first step when you try to figure out if you actually have a good algorithm or not.
Experimenting is especially useful when a rigorous analysis seems hard, or when you're still trying to figure out the exact formulation of the algorithm's task (e.g., think of the Netflix challenge, where you want to recommend movies to users given data about their history. It's not even clear what it is exactly that you want your algorithm to do).

Ultimately, though, a clear understanding of what the algorithm guarantees is sought after, and for the most part, you need a proof for that.


How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?

Answer from the other SE site

The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language in Rosser's 1939 expository paper about provability and computability is biased towards deterministic algorithms. There is an important simplifying theorem here: If you only care about what is ever computable, then you don't need randomness or quantum randomness, because you can simulate them using exponentially more time. Like many simplifying results, it can be taken in the wrong way. It meant that in the 1930s, back when mainly logicians were defining what was computable at all, randomized algorithms were not yet on their radar.

If you extend your thinking to the Extended Church-Turing thesis, then you should also extend your scope to randomized computation. You have no choice, because even if an algorithm answers a deterministic question (like whether a number is prime), the method of calculation could be randomized (like Miller-Rabin or ECPP). And then it's not very natural to demand that the answer be deterministic even if the solution doesn't have to be.

On the other hand, you're free to be a stickler in your personal interpretation of ECT, because it's not a rigorous concept. You're free to say that Google's quantum supremacy gets a bronze medal in its fight against ECT, but not a gold medal, because it doesn't answer a deterministic question.

Or you could be even more of a stickler and say that none of this counts because quantum computing isn't deterministic. Then I would say that I believe this reactionary version ECT after all --- a TM with a linear tape is polynomially equivalent to one with a 2D tape, etc. But I would also say that that's not the right question.


Is a turing machine with random number generator more powerful?


Heuristics for the minimum-weight $k$-clique problem

Your problem appears to be the minimization variant (flip the edge weight signs?) of the edge-weighted maximal clique problem. Check out this reference:

  @article{park1996extended,
  title={{An extended formulation
  approach to the edge-weighted maximal
  clique problem}},
  author={Park, K.
  and Lee, K. and Park, S.},
  journal={European Journal of
  Operational Research},
  volume={95},
  number={3},
  pages={671--682},
  year={1996},
  publisher={Elsevier} }

where they discuss various LP-based heuristics.


If you measure approximation as a ratio between the number of constraints satisfied by your algorithm divided by the total number of constraints, then trivially all constraint satisfaction problems are unconditionally approximation-resistant.

By definition, a problem is approximation resistant if the (worst-case) approximation ratio of a random solution is (up to an additive $o(1)$ term) best possible among the (worst-case) approximation ratios achieved by all polynomial time algorithms.

With your definition of approximation ratio, you get approximation resistance of Max Cut (and all constraint satisfaction problems)  just because you can always construct instances for which the ratio given (on average) by a random assignment is more or less (up to a $o(1)$ term) the same as the ratio given by an optimal assignment.

For example, in the Max Cut problem, a clique on $n$ vertices is a graph that has ${n \choose 2} = n\cdot (n-1)/2$ edges, and in which an optimal cut cuts $n^2/4$ edges. This means that every algorithm, and in particular every polynomial time algorithm, has a worst-case approximation ratio (according to your definition) that is at most $1/2 + O(1/n)$ on $n$-vertex graphs. The random assignment has ratio $1/2$ on all instances, and so no algorithm can do better than the random algorithm, and the problem is approximation-resistant.


NP-complete graph property that is hereditary, but not additive?

I think the $k$-clique cover problem, which asks whether there exists a partition of the vertices in $k$ sets such that each set induces a clique, has the desired properties.

Clearly, taking induced subgraphs can't make the minimum size of such partition increase. On the other hand, when you take the disjoint union of two graphs, you have to take the union of the partition into cliques of each one.


There are probably few or no "interesting" and "natural" closure properties for the class of languages that are not context-free. In fact that's probably true of:

any class of languages that is defined by a specific automaton, grammar or computational model -- the regular languages, the cfl's, various subclasses of the cfls such as the linear languages and the deterministic cfl's, the context-sensitive languages, bounded languages, and so on.
classes actually defined by closure properties, like the least family containing, say, {$a^n b^n$} and closed under the regular operations and transduction. In fact, AFL theory was all about things like that.

The reason is that many if not most or all "interesting" closure properties have the ability to drastically simplify a language, for example map it down to finite sets or something equally simple. For example, you can always apply a constant homomorphism (h(a) = 0) to a non-context-free language and get the language of all strings of zeros, which is context-free (in fact regular). So if the very definition of the class entails that it is not very "simple" (like non-context-free), then closure takes you down to "simple" languages, that is, outside the class.

This might actually make an interesting research project, part of which, I would hazard a guess, would be to define "simple", "interesting" and "natural" in some suitable way, and also to find formal ways to deal with trivial and degenerate cases like the one I gave.

The union and concatenation operations would be one test of such a theory.  I'll conjecture that there are two non-cfl's which concatenate to $ \Sigma^*$ and others which union to that. I'd start with non-cfl's over a single letter, so you are really talking number theory and linear algebra.

Adendum -- here are two languages that definitely concatenate to $a^*$ and are almost certainly not context-free:

$\{a^{n-i}:i = \lfloor \sqrt n \rfloor\}$

$\{a^{n+i}:i = \lfloor \sqrt n \rfloor\}$

If for some reason, those turn out CF, use an even stranger function than $ \sqrt x $


If integer multiplication is in linear time, then the Hartmanis-Stearns conjecture on real-time computation is false. See this post by Richard Lipton (and Ken Regan?).


This is of course a very subjective matter, but here is something that might be interpreted as saying that $\mathbf{MA}$ is a closer fit: The same assumptions that imply that $\mathbf{P} = \mathbf{BPP}$ also imply that $\mathbf{NP} = \mathbf{MA}$, but those assumptions are not known to imply $\mathbf{NP} = \mathbf{AM}$.
In addition, the assumption that $\mathrm{promise}\mathbf{P} = \mathrm{promise}\mathbf{BPP}$ implies that $\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{MA}$, but is not known to imply $\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{AM}$.

However, there is an alternative view saying that $\mathbf{MA}$ is the non-deterministic variant of $\mathbf{BPP}$ while $\mathbf{AM}$ is the probabilistic variant of $\mathbf{NP}$. The foregoing facts can also be interpreted as evidence for this view.


Best method of Error Correction in Quantum Key Distribution

Actually, there is a lot going on in the research of better and faster error correction codes for QKD. The biggest bottleneck of the CASCADE protocol is that it requires a lot of classical communication between Alice and Bob.

A lot of work has been done on LDPC codes. You can have a look to the following papers:

-Efficient reconciliation protocol for discrete-variable quantum key distribution (arXiv:0901.2140v1)

-Rate Compatible Protocol for Information Reconciliation: An application to QKD (arXiv:1006.2660v1).

Moreover, I suggest to look at the slides at https://sqt.ait.ac.at/software/projects/hipanq/wiki/Schedule where there are many talks about error correction in QKD.

Finally, regarding the applications, I would like to point out that the demostration that has been done in Tokyo was also implemented using LDPC codes (see arXiv:1103.3566v1 on page 13 for a reference).


In terms of related work, Marek Zaionc and collaborators have been studying similar kinds of questions for some time.  The following paper includes many results:

René David, Katarzyna Grygiel, Jakub Kozic, Christophe Raffalli, Guillaume Theyssier, Marek Zaionc.  Asymptotically almost all λ-terms are strongly normalizing.  Logical Methods in Computer Science, Volume 9, Issue 1 (February 15, 2013). arXiv

The result stated in the title is not exactly the same as the one you are asking about, but related: they prove that the asymptotic density of strongly normalizing terms among all terms of $\lambda$-calculus is 1.  Surprisingly, they also prove that the asymptotic density of strongly normalizing SKI combinator terms among all SKI combinator terms is 0.
As suggested by Gabriel Scherer's response, the specific formulation of density you are asking about is related to the density of normal terms among all terms, or in other words the probability that a uniformly random term of a given size is already normalized.  For subsystems of $\lambda$-calculus the probability that a term is normal typically decreases exponentially with size, and I believe it should be a small step from there to proving that the asymptotic density you are interested in is 0.  Certainly this is true for linear $\lambda$-terms: since normalization cannot increase the size of a term, the number of equivalence classes of terms of size $n$ is at most $n$ times the number of normal terms of size $n$, hence the ratio of equivalence classes to terms is asymptotically 0.


Integer priority queue with distribution-sensitive deleteMin

This paper[1] additionally introduced the "time-finger" property, a unified property encapsulating both the working-set and the queueish properties:

  We present a priority queue that supports the operations: insert in worst-case constant time, and delete, delete-min, find-min and decrease-key on an element $x$ in worst-case $O(lg(min\{w_x,q_x\}+2))$ time, where $w_x$ (respectively, $q_x$) is the number of elements that were accessed after (respectively, before) the last access of $x$ and are still in the priority queue at the time when the corresponding operation is performed.

[1] A. Elmasry, A. Farzan, and J. Iacono, ‘A Unifying Property for Distribution-Sensitive Priority Queues’, in Combinatorial Algorithms, vol. 7056, C. Iliopoulos and W. Smyth, Eds. Springer Berlin Heidelberg, 2011, pp. 209–222.


What's the status of Babai's Graph isomorphism result?

Aggregating comments by  Thomas Klimpel, Sasho Nikolov and  Mohammad Al-Turkistany into a community answer:

The correction (and hence the quasi-polynomial result) was immediately supported by Harald Andrés Helfgott. His expository paper (https://arxiv.org/abs/1701.04372) and its translation (https://arxiv.org/abs/1710.04574) are all the support that is needed for the quasi-polynomial results. Helfgott’s exposition appeared as Exposé 1125 in Astérisque 407 (2019), Séminaire Bourbaki 2016/2017, pp. 135–182.

There are no current known issues with Babai’s proof, and it has gone through extensive peer review. That said, even published peer-reviewed papers have later been withdrawn as incorrect.

The support by Harald Andrés Helfgott along with the lack of other issues should be sufficient for us to accept that graph isomorphism is indeed solvable in quasi-polynomial time.


What is the current state of the art in black-box grammar induction?

de la Higuera's book focuses mostly on the classical theory of Angluin style learning of finite state automata and related results. This theory has been lifted to the class of context free grammars and beyond to multiple context free grammars etc. using what is called "distributional learning" which in its modern form started with Clark & Eyraud paper in JMLR 2007 (I was the first author). The most recent papers in this line of research are  Chihiro Shibata, Ryo Yoshinaka:
Probabilistic learnability of context-free grammars with basic distributional properties from positive examples. Theor. Comput. Sci. 620: 46-72 (2016) which looks at learning when the samples are generated by a PCFG.
There are analogues of the basic Angluin results using membership queries etc as well, and results for strong learning where you want to recover a CFG which generates the same trees as the target grammar (Learning Trees from Strings, Clark JMLR 2013).
(Apologies for the self citations)

I wasn't familiar with the Bastani paper, but it seems to be a heuristic paper with no theoretical guarantees.


I'm not sure that the statement you want is known to hold in full generality (if you look at O'Donnell's website, he remarks that what he stated in that survey is not in fact known to be true in full generality). That said, it does hold for $q\geq 2\geq p\geq 1$. Let's suppose the Hypercontractivity Theorem holds as you have stated, i.e. for $q\geq p\geq 1$, suppose for $\rho=\sqrt{\frac{p-1}{q-1}}$, we have
\begin{equation}
\|T_{\rho}f\|_q\leq \|f\|_p.
\end{equation}

To use this statement to get this revised version (or almost, you forgot to take the reciprocal of $\rho$), suppose $q\geq 2$ and first take $p=2$, so $\rho^{-1}=\sqrt{q-1}$. As you seem to have figured out, hypercontractivity gives
\begin{align}
\|f\|_q^2&=\|T_{\rho}T_{\rho^{-1}}f\|_q^2\\
&\leq \|T_{\rho^{-1}}f\|_2^2\\
&=\sum_{k=0}^d \rho^{-2k}W_k(f)\\
&\leq \rho^{-2d}\sum_{k=0}^dW_k(f)\\
&=\rho^{-2d}\|f\|_2^2\\
&=\sqrt{q-1}^{2d} \|f\|_2^2,
\end{align}
where $W_k(f)$ is the level-k Fourier weight of $f$, and we use Parseval and the degree assumption. Taking squareroots yields $\|f\|_q\leq \sqrt{q-1}^d\|f\|_2$ in this simple case.

We also have for $1\leq p\leq 2$
\begin{align}
\|f\|_2^2&=\langle f,f\rangle\\
&\leq \|f\|_p\|f\|_{p/(p-1)}\\
&\leq \|f\|_p\sqrt{p/(p-1)-1}^d \|f\|_2\\
&=\sqrt{\frac{1}{p-1}}^{d}\|f\|_p\|f\|_2,
\end{align}
where we use Holder's inequality and then the case we just proved with $q=p'=p/(p-1)$. Putting this together with the previous case, we conclude for all $q\geq 2\geq p\geq 1$, that
\begin{equation}
\|f\|_q\leq \sqrt{q-1}^d \|f\|_2\leq \sqrt{\frac{q-1}{p-1}}^d \|f\|_p,
\end{equation}
as claimed.

According to O'Donnell's website, this paper gives the state of the art on this problem (though I haven't looked through it).


What is known about the complexity of finding minimum circuits for SAT?

Let's assume that one cannot solve SAT much faster non-uniformly than uniformly. That is, there is a TM M solving SAT in time T(n), and the smallest circuit for SAT has size T'(n) that's not much smaller than T(n) (say, $T(n) = poly(T'(n))$ - in particular this holds if the smallest circuit for solving SAT has size $2^{\Omega(n)}$ which may very well be true).

So, you could get an "almost" minimal circuit by just running some canonical simulation of M by a circuit, in time that's basically optimal (as much time as it takes you to write the output). Just for this reason, am guessing there will be no lower bound for this question based on any "nice" assumption. However, I don't know how to go from an "almost minimal" to actually minimal. One way to do so will be to use the fact that finding the circuit up to size $S$ is a question in the polynomial hierarchy, and so you should be able to solve it in roughly $T(T(n))$ time which will be $2^{o(M)}$ if $T(n)=2^{n^{o(1)}}$.


A quick bit of googling gives this for the RSA paper:

Rivest stayed up all night, preparing the manuscript describing the code before he handed it to Adleman. He had listed the paper's authors in alphabetical order - Adleman, Rivest, Shamir. Adleman demurred:
I told Ron, 'Take my name off the paper. It's your work'.
But Rivest insisted and eventually prevailed upon him.
I thought, 'Well, it's going to be the least important paper I've ever been on, but in a few years I will need so many lines on my vita to get tenure, ... on the other hand, I did do a substantial amount of intellectual work breaking the codes 1 through 42. So the reasonable thing to do is be the third author'.


From the information I could find online, I assume that the purpose of "Physics Today" is to summarize the incredibly vast field of physics and promote results that are considered important enough to be known from researchers with a different specialization from the subject matter. The focus is also on newly published results, rather than re-examining classical ones or establishing a "must-know" basis.

With this assumption, I believe the answer is no. The field has embraced Web technologies to a degree where results are usually known months before their official publishing in conferences and years before the journal version is out, with preprints being available typically via arxiv and rigorous discussions being held in popular blogs (for example Lipton&Regan, Fortnow&Gasarch , Aaronson ), TCS+ and questions appearing on this site as well.

Perhaps the one that comes the closest is Journal of the ACM (JACM).

See also this question.


Correction:

I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods.

In fact, "Exact Cover" is contained in W[1].
It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]:

In the preprocessing phase, construct and store a 2-dimensional table
that states for every two subsets $S_i$ and $S_j$ in $S^*$ whether they overlap.
Furthermore, construct a second table that stores for every subset $S_i$ in $S^*$ its cardinality. This clearly can be done in polynomial time.
In the guessing phase, guess a system of $k$ (indices of) subsets in $S^*$. This clearly can be done in $O(f(k))$ time on a RAM.
In the verification phase, first check whether any two guessed subsets overlap, by looking up the 2-dimensional table. Then check whether the total size of all guessed subsets equals $|U|$. (The first check guarantees that every element of $U$ is covered at most once, and the second check guarantees that it is covered at least once.) All this can be done in $O(g(k))$ time on a RAM.

Correct answer:

ExactCover is W[1]-complete. The above discussion shows containment in W[1].
Furthermore, ExactCover contains the W[1]-complete PerfectCode problem as a special case. (Given a graph $G$ and an integer $k$. Does $G$ contain a subset $C$ of $k$ vertices, such that every vertex in $G$ is contained in the closed neighborhood of exactly one vertex in $C$?)

R.G. Downey, M.R. Fellows
Fixed-parameter tractability and completeness. II. On completeness for W[1]
Theoretical Computer Science 141 (1995), pp. 109–131

Old (wrong) answer, left for reference:

"Independent Dominating Set" is W[2]-complete, and a special case
of your ExactCover problem:

R.G. Downey and M.R. Fellows.
Fixed-parameter tractability and completeness.
Congressus Numerantium 87:161–178, 1992.


Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences

So if I understand it correctly you want the neighbors of each vertex to form a small number of contiguous blocks of the ordering? Then no, you need a larger number of blocks than that.

Let's suppose we have a bipartite graph with a small number $k$ of (labeled) vertices on one side and $n$ on the other. Each edge from one side to the other can be present or absent independently of the others, so there are $kn$ bits of information required to specify the whole graph.

On the other hand, suppose you could find an ordering with the neighbors of each vertex forming at most $b$ blocks. Then you could specify the same graph by listing the ordering of the big side of the bipartition (representable in $\le n\log_2 n$ bits of information) and the positions and lengths of the blocks for each of the $k$ vertices on the small side of the bipartition ($\le 2bk\log_2 n$ bits). So to have enough information to specify the whole graph we need
$$
n\log_2 n+2bk\log_2 n\ge kn
$$
or equivalently
$$
b\ge\frac{kn-n\log_2 n}{2k\log_2 n}
$$
Setting $k=2\log_2 n$ gives $b=\Omega(n/\log n)$, significantly greater than $\sqrt m=\Theta((n\log n)^{1/2})$.


Implications of a recent negative result to geometric complexity

It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit closure of the determinant, and not merely use those on the orbit of the determinant as an upper bound. In using (a), one might at least still hope for a significant difference in the magnitude of the multiplicities, rather than small differences in their exact values - this should make such differences easier to detect.

The possibilities to use both (a) and (b) have been known for several years, though perhaps not everyone agreed regarding their necessity. (I personally have always thought that at the very least we'd need to do (b); it is very nice that their paper actually proves this.)

(Both (a) and (b) are clearly spelled out in Section 5 of the paper, entitled "Consequences for geometric complexity theory." Although my answer duplicates the points from the paper, I am posting it here both to give what I think is needed for a complete answer, and to assert that I agree with the authors that these are the ways forward.)


Higher-rank polymorphism over unboxed types

I've thought a bit about this. The main issue is that in general, we
don't know how big a value of polymorphic type is. If you don't have
this information, you have have to get it somehow. Monomorphisation
gets this information for you by specializing away the
polymorphism. Boxing gets this information for you by putting
everything into a representation of known size.

A third alternative is to keep track of this information in the
kinds. Basically, what you can do is to introduce a different kind for
each data size, and then polymorphic functions can be defined over all
types of a particular size. I'll sketch such a system below.

$$
\newcommand{\bnfalt}{\;\;|\;\;}
\newcommand{\rule}[2]{{\mathord{\array{#1}} \over {\mathord{#2}}}}
\newcommand{\judge}[3]{{#1} \vdash {#2} : {#3}}
$$
$$
\begin{array}{llcl}
\mbox{Kinds} & \kappa & ::= n \\
\mbox{Type constructors} & A & ::= & \forall a:\kappa.\; A \bnfalt \alpha \bnfalt A \times B \bnfalt A + B \bnfalt A \to B \\
                         &   & |   & \mathsf{ref}\;A \bnfalt \mathsf{Pad}(k) \bnfalt \mu \alpha:\kappa.\; A\\
\end{array}
$$

Here, the high level idea is that the kind of a type tells you how
many words it takes to lay out an object in memory. For any given
size, it's easy to be polymorphic over all types of that particular
size. Since every type -- even polymorphic ones -- still has a known
size, compilation isn't any harder than it is for C.

The kinding rules turn this English into math, and should look something like this:
$$
  \rule{ \alpha:n \in \Gamma}
       { \judge{\Gamma}{\alpha}{n} }
  \qquad
  \rule{ \judge{\Gamma, \alpha:n}{A}{m} }
       { \judge{\Gamma}{\forall \alpha:n.\; A}{m} }
$$
$$
  \rule{ \judge{\Gamma}{A}{n} &
         \judge{\Gamma}{B}{m} }
       { \judge{\Gamma}{A \times B}{n + m} }
  \qquad
  \rule{ \judge{\Gamma}{A}{n} &
         \judge{\Gamma}{B}{n} }
       { \judge{\Gamma}{A + B}{n + 1} }
$$
$$
  \rule{ \judge{\Gamma}{A}{m} &
         \judge{\Gamma}{B}{n} }
       { \judge{\Gamma}{A \to B}{1} }
  \qquad
  \rule{ \judge{\Gamma}{A}{n} }
       { \judge{\Gamma}{\mathsf{ref}\;A}{1} }
$$
$$
  \rule{  }
       { \judge{\Gamma}{\mathsf{Pad}(k)}{k} }
  \qquad
  \rule{ \judge{\Gamma, \alpha:n}{A}{n} }
       { \judge{\Gamma}{\mu \alpha:n.\; A}{n}
       }
$$

So the forall quantifier requires you to give the kind you are ranging
over. Likewise, pairing $A \times B$ is an unboxed pair type, which
just lays out an $A$ next to a $B$ in memory (like a C struct
type). Disjoint unions take two values of the same size, and then add
a word for a discriminator tag. Functions are closures, represented as
usual by a pointer to a record of the environment and the
code.

References are interesting -- pointers are always one word, but they
can point to values of any size. This lets programmers implement
polymorphism to arbitrary objects by boxing, but doesn't require
them to do so. Finally, once explicit sizes are in play, it's often
useful to introduce a padding type, which uses space but doesn't do
anything. (So if you want to take the disjoint union of an int and a
pair of ints, you'll need to add padding the first int, so that the
object layout is uniform.)

Recursive types have the standard formation rule, but note that
recursive occurences have to be the same size, which means you usually
have to stick them in a pointer to make the kinding work out. Eg, the
list datatype could be represented as

$$
   \mu \alpha:1.\; \mathsf{ref}\;(\mathsf{Pad}(2) + \mathsf{int} \times \alpha)
$$

So this points to an empty list value, or a pair of an int and a pointer
to another linked list.

Type checking for systems like this is also not very hard; the
algorithm in my ICFP paper with Joshua Dunfield, Complete and Easy
Bidirectional Typechecking for Higher Rank
Polymorphism applies to this case
with almost no changes.


Translating pure literal elimination into rup

Pure literal elimination over base clauses is effectively deleting those clauses from the formula, an action which cannot be encoded in a RUP proof since such proofs only encode clause additions.  But since an unsatisfiable formula will be unsatisfiable even without the clauses that contain pure literals you can treat the formula as if those clauses were not present.  Any RUP proof of the unsatisfiability of the formula with those clauses missing will also be a RUP proof of the unsatisfiability of the original formula.
As for the second example, you can't validly add $(\lnot A \lor \lnot B)$ to the proof because that clause isn't an actual requirement to satisfy the formula.  $A$ dominating $B$ after a partial assignment doesn't indicate that $\lnot B$ is mandatory, rather it means that asserting $B$ isn't helpful.  In fact, it might be a bad thing to do if $\lnot B$ is needed to satisfy some clauses later.  If you assert $\lnot B$ to satisfy all clauses containing $\lnot B$ you can be confident that $B$ will never appear in a downstream conflict clause and thus will never be part of a RUP clause generated by this partial assignment.  So asserting $\lnot B$ can't hurt but you can't be sure that it is necessary.  RUP proof clauses state only what is necessary.


Reconstructing a tree from separator queries

No.  The following simple adversary strategy implies that any algorithm to reconstruct an $n$-node tree requires at least $\binom{n-1}{2} = n(n-1)/2$ "betweenness" queries.

Arbitrarily label the nodes $0,1,2,\dots,n-1$.  The adversary answers all queries as though the tree is a star with vertex $0$ in the center; think of $0$ as the root and the other nodes as its children.

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Now suppose the algorithm halts after performing less than $n(n-1)/2$ queries.  Then there must be two vertices $y$ and $z$, neither equal to zero, such that the algorithm has not queried any permutation of the triple $(0,y,z)$.  If the algorithm claims that the tree is not a star with center $0$, the adversary reveals its input, proving the algorithm wrong.  The adversary then reveals that $x$ is actually the only child of $y$, proving the algorithm wrong again.

Update: Oops, just noticed the degree constraint.  Fortunately, this is not a major hurdle.  Replace node $0$ with your favorite binary tree, with the other $n-1$ nodes as leaves in some unknown order, and then reveal this subtree to the reconstruction algorithm.  Reconstructing the resulting $(2n-3)$-node binary tree still requires at least $n(n-1)/2$ queries.  Equivalently, reconstructing an $m$-node binary tree requires at least $(m+3)(m+2)/8$ queries.  (I'm sure a more subtle construction would improve the constant.)  As Jagadish points out, this generalization doesn't work; queries about internal nodes in the tree impose an ordering on the leaves, which reduced the number of necessary queries.


Regular expressions: Finding "negation" of regular expression?

As another answer already states, the standard approach is: converting to a DFA, complementing, and converting back to a regular expression takes two exponential steps in the worst case (one for obtaining the equivalent DFA, and one for converting its complement to a regular expression).

This is essentially optimal in the worst case: There are examples of regular expressions of length $n$ such that the shortest regular expression describing complement provably has length at least $2^{2^{c \cdot n}}$, where $c$ is some fixed constant; Such examples are known already for alphabets of size $2$. (Gelade & Neven 2008, and Gruber & Holzer 2008).

Wouter Gelade, Frank Neven: Succinctness of the Complement and Intersection of Regular Expressions. STACS 2008: 325-336
Hermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50


The SQ argument in Balazs Szorenyi's paper

This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these notes by Jeff Erickson.

The idea for the proof is that the SQ oracle is controlled by an adversary, and the adversary does not have to initially commit to a specific $f^*$. Instead, the adversary always makes sure that some $f^*$ is consistent with the oracle answers. In Szorenyi's paper, the adversary will make sure that there is always some $f_i$ which is consistent with all of the query answers. More precisely, let $\cal G$ be the set of all $f_i$ which are consistent with answering $0$ to all queries so far. If no queries have been answered yet, then $\mathcal{G} = \{f_1, \ldots, f_d\}$. Szorenyi shows that answering a new query by $0$ decreases $|\cal G|$ by at most $2d/(d\tau^2 - 1)$, so as long as $|\mathcal{G}| > 2d / (d\tau^2-1)$, the adversary can keep answering queries by $0$ and $\cal G$ will remain non-empty. Moreover, while this is true, the algorithm cannot stop and output an answer, because any possible concept it outputs will have correlation less than $\tau$ with $|\mathcal{G}| - d / (d\tau^2-1)> 0$ many concepts in $\mathcal{G}$. But any concept in $\mathcal{G}$ could be $f^*$, and the algorithm would output the wrong answer for at least one such possible $f^*$.

Another way to see the last point is the following. Suppose that the algorithm outputs something while $|\mathcal{G}| > 2d / (d\tau^2-1)$. Then take an element of $\cal G$ that has correlation less than $\tau$ with the algorithm's output, and call it $f^*$. Rerun the whole process again with the oracle always outputting $0$: all the oracle answers are consistent with $f^*$ (by the construction of $\cal G$) and the algorithm would produce the same output, but that output would be incorrect for $f^*$. Note that this assumes that the algorithm is deterministic.

One detail he doesn't mention is that once $|\mathcal{G}| \le 2d / (d\tau^2-1)$, the adversary can pick some $f^* \in \mathcal{G}$ and answer new queries in any way consistent with $f^*$. This doesn't matter much in the proof because it can only happen once $(d\tau^2 - 1)/2$ queries have been made.


What is the best place to get BibTeX entries for computer science articles ?

You don't get correct TCS Bibtex entries from anywhere.

CiteSeer, Google Scholar, etc.: the Bibtex entries are garbage, worse than useless.

Examples: Many conference papers in Google Scholar are exported as an @article, with (some version of) the title of the book in the journal field. Google Scholar abbreviates the first names of the authors. And then of course we have ridiculous things like author = {Submission, H.C.F.} – Google Scholar populates the fields by picking some words from the cover page of the paper.

Publishers: the entries are a bit better, but you cannot rely on them – you must check every single field manually anyway. IEEE tends to be worst, ACM and Springer are little bit better, but even with the latter, you need to do manual editing and cross-checking. Springer has a strange idea of what is the title of a proceedings book. ACM gives book titles in a strange mixture of upper-case and lower-case letters. And, as usual, if there are accents in the authors' names, or any math in the title, all bets are off.

Examples of booktitle fields for conference papers: Springer might produce something like booktitle = {Distributed Computing} for a proceedings volume – it requires a lot of imagination to figure out that it actually means "Proc. 23rd International Symposium on Distributed Computing (DISC 2009)". IEEE exports unreadable titles such as booktitle = {Sensor, Mesh and Ad Hoc Communications and Networks, 2007. SECON '07. 4th Annual IEEE Communications Society Conference on}. ACM is usually fairly good, but you need to fix the mixture of upper and lower case letters: booktitle = {Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures}.
Examples of titles with math: ACM might produce (\&\#948;+1) instead of {$(\Delta+1)$}. IEEE might produce Otilde(radic(log n)) instead of {$\tilde{O}(\sqrt{\log n})$}. I am not kidding you.

MathSciNet: high-quality Bibtex entries for journal articles, but the coverage of TCS is poor, and conference papers are not necessarily that well indexed.

"Core TCS" conferences such as FOCS, STOC, and SODA seem to be covered fairly well, but anything else is more patchy. For example, there seem to be few papers indexed from PODC or SPAA.
The entries of the conference papers are not perfect. You can find something like @incollection instead of @inproceedings, or proceeding books such as BOOKTITLE = {Distributed computing}.

DBLP: reasonably good, but once again, a lot of data comes from the publishers, and you need to double-check it anyway (beware of accents).

Examples of accents: Michal Hanckowiak instead of Micha{\l} Ha{\'n}{\'c}kowiak.

As JɛﬀE pointed out in the comments, the correct title of a conference volume is a matter of taste (and a matter of interpretation). For example, LNCS volumes may have useless main titles and ridiculously long subtitles; therefore even if you had pedantically correct bibliographic entries, you most likely would like to edit some of them slightly, for readability and for consistency.

But as soon as you start to tweak the titles of the conference volumes, it becomes obvious that even for your own purposes, there are many possible right answers. When you are running out of space, you might prefer "Proc. STOC 2010" to "Proceedings of the 42th ACM Symposium on Theory of Computing (STOC, Cambridge, MA, USA, June 2010)". This answer at the TeX site gives one example of how to deal with multiple versions of the titles, so that you can easily switch between different variants.


If you have a casual conversation with someone and it leads to a paper, what do you owe them?

The problem with this question is that it is way too vague. Suppose you have a casual conversation, and somebody says "I've been looking at Trudeau gadgets, and I think I can show that they all have a canonical commuting umbrella." If you then publish a paper showing that all Trudeau gadgets have a canonical commuting parasol, there is no question that this is unethical, even if you didn't hear all the details of his proof. (Things like this have happened occasionally, and sometimes the unethical author gets away with it, but I'm not sure doing this is good for your career ... people will probably hear about it).

However, suppose you are having a casual conversation about your research, and you explain to somebody what a Trudeau gadget is, and she says "That reminds me of Smith's umbrella theorem." You then look up Smith's umbrella theorem, and it is exactly what you need to prove your result. Here, it would be nice to thank her in the acknowledgments of your paper, but you certainly don't need to make her a coauthor.

So there is really no way to answer this question without knowing more details.


Natural candidates for the hierarchy inside NPI

Group Isomorphism $\leq_m$ Graph Isomorphism $\leq_m$ Ring Isomorphism. Also Integer Factoring $\leq_m$ Ring Isomorphism [Kayal and Saxena]. Also Graph Automorphism $\leq_m$ Graph Isomorphism.

Not only are there no known reductions the other way, but there is provably no
$\mathsf{AC}^0$-reduction from Graph Iso to Group Iso [Chattopadhyay, Toran, and Wagner].

Note that a reduction from Ring Isomorphism to Graph Isomorphism would also provide a reduction from Integer Factoring to Graph Isomorphism. To me, such a reduction would be surprising though perhaps not shocking.

(For Graph Automorphism vs Graph Isomorphism, their counting versions are known to be equivalent to one another and equivalent to deciding Graph Isomorphism. However, that's not necessarily saying much, as the counting version of bipartite matching is equivalent to the counting version of SAT.)

I don't think there is a real consensus as to which, if any, of these are actually in $\mathsf{P}$. If any of these problems is $\mathsf{NP}$-complete then $\mathsf{PH}$ collapses to the second level. If factoring is $\mathsf{NP}$-complete, then it collapses to the first level, i.e. $\mathsf{NP} = \mathsf{coNP}$.

Also, I seem to recall that using techniques similar to Ladner one can show that any countable partial ordering can be embedded in the ordering $\leq_{m}$ on the problems in $\mathsf{NP}$ (so it's not just a hierarchy, but an arbitrarily complicated countable partial order).


Why semi-gradient is used instead of the true gradient in Q-learning?

The problem does not come from the above equation but from the bootstrapping method. Sutton's reinforcement learning book (2nd) gave a pretty good explanation to the problem in Chapter 9.3.
The idea here is you cannot obtain the true value for $V_\pi$, but you want to approximate it. My understand is that when bootstrapping, like with the TD method, $V_\pi$ depends on $w$. This breaks the assumption that $V_\pi$ is independent of $w$ and thus the gradient is not the true gradient and we call it semi-gradient. However, if you are not bootstrapping, as with Monte Carlo methods, $V_\pi$ will be unbiased and the above will be guaranteed to converge to a local minimal.


Node-weighted steiner problem with few terminals

An algorithm with a run-time of $n^{poly(k)}$ should be easy where $n = |V|$ and $k = |T|$. Think of an optimum solution which is edge-minimal. It will be a tree and one can see that the number of nodes with degree $\ge 3$ in this tree will be $O(k)$. We can guess those nodes $A$. Once we guess those nodes we create a graph on $A \cup T$ with edge-lengths between two nodes $u,v$ equal to the shortest node-weighted path between $u$ and $v$ in $G$ (we do not include the end points in this calculation). Then find a min-cost spanning tree in the resulting graph.


What is the connection between moments of Gaussians and perfect matchings of graphs?

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$ be the covariance of $\gamma_i$ and $\gamma_j$. Consider the complete graph on $\{1, \dots, 2n\}$; assign weight $c_{ij}$ to edge $(i,j)$. Let the cost of a perfect matching $M$ (i.e. a matching of size $n$) be the product of weights of the edges in $M$:
$$\mathrm{cost}(M)=\prod_{(i,j)\in M} c_{ij}.$$
Then
$${\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}] = \sum_{M\text{ is a perfect matching}} \mathrm{cost(M)}.$$

We get the formula for the $2n$-th moment of a Gaussian random variable by letting $\gamma_1 = \dots = \gamma_{2n} = \gamma$, where $\gamma\sim{\cal N}(0,1)$. We have, $c_{ij} = 1$ and $\mathrm{cost}(M) = 1$ for every perfect matching $M$; thus,
$${\mathbb E}[\gamma^{2n}] = {\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}] = |\{M: M \text{ is a perfect matching}\}|.$$

The proof of the theorem is not difficult at all. Also I think that its statement is not surprising. Indeed, the joint distribution $\gamma_1, \dots, \gamma_{2n}$ is completely characterized by weights/covariances $c_{ij}$ and variances $\sigma_i = {\mathbb E}[\gamma_i^2]$ (that is, by the covariance matrix of $\gamma_i$'s). Thus $P={\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}]$ is a function of parameters $\{c_{ij},\sigma_i\}_{i,j}$. It is easy to see that $P$ does not depend on $\sigma_i$'s — if we add a Gaussian r.v. $\gamma'$, independent from all $\gamma_i$'s, to some $\gamma_{a}$, variance $\sigma_a$ will change, but neither $P$ nor parameters $c_{ij}$ and $\sigma_{b}$ (for $b\neq a$) will change. Thus, $P$ must depend only on $c_{ij}$'s. Further, the expression for $P$ must be symmetric and homogeneous (if we multiply all $\gamma_i$'s by $\alpha$, then $c_{ij}$'s are multiplied by $\alpha^2$ and $P$ is multiplied by $\alpha^{2n}$). Given these observations, the statement of the theorem looks very natural.


Yes. $NC$ can be seen as the class of languages recognized by alternating Turing machines that use $O(\log n)$ space and $(\log n)^{O(1)}$ time. (This was first proved by Ruzzo.) $P$ is the class where alternating Turing machines use $O(\log n)$ space but can take up to $n^{O(1)}$ time. For brevity let's call these classes $ATISP[(\log n)^{O(1)},\log n] = NC$ and $ASPACE[O(\log n)] = P$.

Suppose the two classes are equal. Replacing the $n$ with $2^n$ in the above (i.e., applying standard translation lemmas), one obtains

$TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$.

If $TIME[2^{O(n)}] \subseteq PSPACE$ then $EXP = PSPACE$ as well, since there are $EXP$-complete languages in $TIME[2^{O(n)}]$.

Edit: Although the above answer is perhaps more educational, here's a simpler argument: $EXP = PSPACE$ already follows from "$P$ is contained in polylog space" and standard translation. Note "$P$ is contained in polylog space" is a much weaker hypothesis than $NC = P$.

More details: Since $NC$ circuit families have depth $(\log n)^c$ for some constant, every such circuit family can be evaluated in $O((\log n)^c)$ space. Hence $NC \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$. So $P = NC$ implies $P \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$. Applying translation (replacing $n$ with $2^n$) implies $TIME[2^{O(n)}] \subseteq PSPACE$. The existence of an $EXP$-complete language in $TIME[2^{O(n)}]$ finishes the argument.

Update: Addressing Andreas' additional question, I believe it should be possible to prove something like: $EXP=PSPACE$ iff for all $c$, every polynomially sparse language in $n^{O(\log^c n)}$ time is solvable in polylog space. (Being polynomially sparse means that there are at most $poly(n)$ strings of length $n$ in the language, for all $n$.) If true, the proof would probably go along the lines of Hartmanis, Immerman, and Sewelson's proof that $NE = E$ iff every polynomially sparse language in $NP$ is contained in $P$. (Note, $n^{O(\log^c n)}$ time in polylog space is still enough to imply $PSPACE=EXP$.)


Is refuting candidate deciders of the halting problem computable?

The usual proof that the halting problem is undecidable already gives you exactly such an algorithm. Given an algorithm $A$, we construct an algorithm $B$ that on input $x$ computes $A$ on program $x$ and input $x$, and then enters an infinite loop iff $A$ answered "halts". Now consider giving $B$ itself as an input. If $A(B,B)=\text{"halts"}$ then $B$ doesn't halt on $B$, so $A$ is wrong. Same if $A(B,B)=\text{"doesn't halt"}$. So $\langle B,B\rangle$ is an example input on which $A$ is wrong.


Definitional equality of recursive function definition by "infinite unfolding"

Your predd2 is not a fixpoint; you could replace the Fixpoint by Definition. And the fact that they are not convertible is due to the lack of eta-conversion for inductive types in Coq.

The reason for this is that we want the conversion to be decidable, and it's already hard to decide beta-eta-conversion in the simply typed case (see Deciding equivalence with sums and the empty type by Gabriel Scherer).

You can more or less check that "a is convertible to b" by using the following notation:

Notation "n ~ m" := (eq_refl : n = m) (at level 70, no associativity).

(It has the expected behaviour on +:

Check fun n => 0 + n ~ n.
Fail Check fun n => n + 0 ~ n.

)

And you can check that there is no eta-conversion for booleans, for natural numbers, or even for the unit type:

Fail Check fun x : bool => if x then tt else tt ~ tt.
Fail Check fun x : nat => match x with | 0 => tt | S _ => tt end ~ tt.
Fail Check fun x : unit => match x with tt => tt end ~ tt.

(Those are specific cases of the eta conversion for those inductive types, but since they already fail, it still shows that the full eta conversion can't be included in the conversion)

Now, going back to your specific example (with the names changed). I use the names:

$f_i$ for the recursive function that returns $0$ immediately if its argument $n$ is between $0$ and $i-1$, and otherwise recursively calls its self on $n-i$. $f_1$ is your predd and $f_2$ is your preddd.
$\text{eta}\_\text{fun}\_f_i$ is the eta-expansion (as a function) of $f_i$.
$\text{eta}\_\text{fun}\_\text{eta}\_\text{nat}\_f_i$ is the result of eta-expanding the body (with the eta-expansion of natural numbers) of $\text{eta}\_\text{fun}\_f_i$.
$g_i$ is the function that returns $0$ immediately if its argument $n$ is $0$, and otherwise returns $f_i(n-1)$.

We have $g_1\equiv \text{eta}\_f_1 \not \equiv \text{eta}\_\text{fun}\_\text{eta}\_\text{nat}\_f_2 \equiv f_1$, which shows that the problem is indeed the lack of eta-conversion for natural numbers.

We have $g_1\equiv \text{eta}\_f_1 \not \equiv \text{eta}\_\text{fun}\_\text{eta}\_\text{nat}\_f_2 \not\equiv f_1$. The first $\not\equiv$ is still due to the same reason. I think the second one is more about unfolding of fixpoints.

Here is a Coq script that supports what I said above:

Fixpoint f1 n := (* predd *)
  match n with
  | O => O
  | S n' => f1 n'
  end
.

Definition eta_fun_f1 n :=
  f1 n
.

Definition eta_fun_eta_nat_f1 n :=
  match n with
  | 0 => f1 0
  | S n' => f1 (S n')
  end
.

Definition g1 n :=
  match n with
  | 0 => 0
  | S n' => f1 n'
  end
.

Check f1 ~ eta_fun_f1.
Fail Check eta_fun_f1 ~ eta_fun_eta_nat_f1.
Check eta_fun_eta_nat_f1 ~ g1.

Fixpoint f2 n := (* preddd *)
  match n with
  | 0 => 0
  | S n' =>
    match n' with
    | 0 => 0
    | S n'' => f2 n''
    end
  end
.

Definition eta_fun_f2 n :=
  f2 n
.

Definition eta_fun_eta_nat_f2 n :=
  match n with
  | 0 => f2 0
  | S n' => f2 (S n')
  end
.

Definition g2 n := (* predd2 *)
  match n with
  | 0 => 0
  | S n' => f2 n'
  end
.

Check f2 ~ eta_fun_f2.
Fail Check eta_fun_f2 ~ eta_fun_eta_nat_f2.
Fail Check eta_fun_eta_nat_f2 ~ g2.


Linear programming solution in one pass with ordered variables

Probably the most famous instance in which a greedy algorithm is known to solve an LP is for the special case of the transportation problem.  Hoffman ("On simple linear programs", in Convexity, vol. 7 of Proceedings of Symposia in Pure Mathematics, pages 317-327, 1963) proved that if the cost matrix for a (maximization) transportation problem satisfies the Monge property ($c_{ij} + c_{kl} \geq c_{il} + c_{kj}$ when $1 \leq i < k \leq n$, $1 \leq j < l \leq n$) then an optimal solution can be found in a greedy manner like the one you describe.

Hoffman also has a survey paper ("On greedy algorithms that succeed") from 1985 in which he discusses known cases in which a greedy algorithm gives an optimal solution to an LP.  Besides his own work cited above (about which he says, "most of the linear programming problems known [by 1963] to be susceptible to a greedy algorithm were special cases of the Monge idea"), he mentions Edmonds' linear programming interpretation of a generalization of matroids and a discussion of the case when $A$ is nonnegative, among other things.

I imagine there are more recent results, but hopefully this at least partially answers your question and gives you some ideas of where else to look.


Hard problems on subclasses of planar cubic bipartite graphs

Hamiltonicity remains NP-complete for 2-vertex-connected cubic planar bipartite graphs, but this is not actually a restriction: every cubic planar bipartite graph is 2-connected. It is a well-known open problem whether 3-connected cubic planar bipartite graphs always have Hamiltonian cycles, but if they do not then the problem is NP-complete for them as well.

(One of my recent papers looked at some related connectivity classes of cubic planar bipartite graphs but not from the point of view of NP-hardness.)


Fastest way to find an s-t min-cut from an s-t max-flow?

If you don't use the flow per se, but use the Ford-Fulkerson algorithm (or some version, like Edmonds-Karp), you can get both the max-flow and the min-cut directly as a result. When looking for augmenting paths, you do a traversal, in which you use some form of queue of as-yet-unvisited nodes (in the Edmonds-Karp version, you use BFS, which means a FIFO queue). In the last iteration, you can't reach $t$ from $s$ (this is the termination criterion, after all). At this point, the set of nodes you reached forms the $s$-part of the cut, while the nodes you didn't reach form the $t$-part.

The leaf nodes of your traversal tree form the “fringe” of the $s$-part, while the nodes in your traversal queue form the fringe of the $t$-part, and what you want is the set of edges from the $s$-fringe to the $t$-fringe. This can also easily be maintained during traversal: Just add an edge to the cut when it is examined, and leads to an unvisited node, and remove it if it is traversed (so its target becomes visited). Then, once Ford-Fulkerson is finished, you'll have your min-cut (or, rather, one of them) right there. The running time will be (asymptotically) identical to Ford-Fulkerson (or Edmonds-Karp or whatever version you're using), which should give you what you were looking for.


Dynamic Data structure for All nearest smaller values

If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a logarithmic number of nodes to check, and in the second case you can use the extra information to find the closest left subtree with a value smaller than x and then descend through it along the rightmost path that still has a value smaller than x. So the time per query or update is logarithmic.

Edited to add: Now that you have clarified that you want to identify items in the sequence by their position, you should also augment the search tree so that each node stores its number of descendants. With this information, it is straightforward to find the path to the item at position $i$, in logarithmic time, matching the time described above for the NearestSmaller query.


Finding a common factor in $\lambda$-terms that agree under certain substitutions

In case anyone is interested, I believe the following does it. I'm assuming, for simplicity, that $\phi^a$ is in $\eta\beta$ normal form.

Pick some constant $a$ arbitrarily, and let $b$ and $d$ be distinct constants that don't appear in $\phi^a$. Finally, let us write $x,y \mapsto z$ for the substitution that substitutes both $x$ and $y$ for $z$ and does nothing else.

Firstly we prove that for any constant $c\not= b$, $\phi^c$ does not contain $b$. Let $k=a,c\mapsto d$. Then $k\phi^a =_{\eta\beta} k\phi^c$ since $ka=kc = d$. Indeed $k\phi^a = k\phi^c$, since $\phi^a$ and $\phi^b$ are in normal form, and $k$ substitutes constants, so that $k\phi^a$ and $k\phi^c$ are in normal form too. $k\phi^a$ does not contain $b$, since $\phi^a$ does not contain $b$, and $k$ introduces only $d$. So $k\phi^c$ does not contain $b$, and thus $\phi^c$ does not contain $b$ since $k$ leaves $b$ alone.

Now $\phi^b$ can be decomposed into $\alpha b$ where $\alpha$ does not contain $b$ (let $\alpha = \lambda x \phi^b[x/b]$). Let $c$ be any constant, and let $i = b,c\mapsto c$. Since $ib=ic$, we know that $i\phi^c =_{\eta\beta} i\phi^b =_{\eta\beta} i(\alpha b) =_{\eta\beta} i(\alpha)ib = \alpha ib = \alpha c$. Secondly, $i\phi^c = \phi^c$ since, as we showed above, $b$ does not occur in $\phi^c$. Thus $\phi^c = \alpha c$ for arbitrary $c$.