Consequences and state-of-the-art of NP ≠ ZPP?

Yes, it is safe to claim that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$ -- and that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{BPP}$.

One consequence of $\mathsf{NP} = \mathsf{ZPP}$ is that computational cryptography is impossible.  This is described as the world Algorithmica in Impagliazzo's famous five worlds:

A Personal View of Average-Case Complexity.  Russell Impagliazzo.  1995 Complexity Conference. (A PDF version is here).

Note that as far as practical consequences go, Impagliazzo says it doesn't matter much whether we have $\mathsf{P} = \mathsf{NP}$ or $\mathsf{NP} \subseteq \mathsf{BPP}$ (he even calls the latter the "moral equivalent" of $\mathsf{P} = \mathsf{NP}$).

See also What if P = NP? for additional practical consequences (assuming the constants hidden by asymptotic notation are not too large).

I don't know whether there are any surprising implications for complexity classes.


Extending the example pointed out by Emil Jerabek in the comments, $\mathsf{EXPSPACE}$-complete problems arise naturally all over algebraic geometry. This started (I think) with the Ideal Membership Problem (Mayr–Meyer and Mayr) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies (Bayer and Stillman). Many natural problems in computational algebraic geometry end up being equivalent to one of these problems. Also see the Bayer–Mumford survey "What can be computed in algebraic geometry?"


Quantum complexity of TQBF with an untrusted oracle

This question is more complicated to state than its predecessor Quantum complexity of TBQF, but in hindsight it is also way easier to answer.
Theorem: The complexity is $\tilde{O}\left(2^{n/4}\right)$, using a single call to Grover's algorithm to check if there is a path falsifying the oracle.  Moreover, this is optimal in the black box case.
Consider a TBQF query $F = \exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots f(x, y)$.  Assume w.l.o.g. that the oracle says $F$ is true.  The oracle is telling the truth about $F$ if, when we use the oracle to choose how to play each $x_k$ move, there is no choice of $y$'s that falsifies the oracle.  But this is just a single call to Grover to search through the space of such $y$'s.  There are $2^{n/2}$ $y$'s, so the complexity is $\tilde{O}\left(\sqrt{2^{n/2}}\right) = \tilde{O}\left(2^{n/4}\right)$.
For the black box lower bound, given a black box boolean function $f(y)$ defined on $n/2$ bits $y$, we can construct a degenerate TBQF formula $F = \exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots f(y)$ which simply ignores $x$.
(Thanks to Paul Christiano for discussion.)


Average-case tautologies/contradictions, beyond the random k-CNF model

Paul Beame has two papers (with various coauthors) where the resolution complexity of certain distributions of random formulas are studied. These formulas arise by expressing properties, such as k-colorability or having independent sets of size k, of random graphs from the usual distribution $G(n,p)$. Here are the links:

Paul Beame, Russell Impagliazzo, and Ashish Sabharwal. The resolution complexity of independent sets and vertex covers in random graphs. Computational Complexity, 16(3):245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell, and Cristopher Moore. The resolution complexity of random graph k-colorability. Discrete Applied Mathematics, 153:25-47, 2005.


Relativization with Respect to Non-Recursive Oracles

I can't resist putting in a plug for some recent results, indicating that it can be interesting to consider computation relative to the (non-computable) set of Kolmogorov-random strings.

Let $R$ be the set of Kolmogorov-random strings; that is, the set of strings $x$ such that $K(x)$ is greater than or equal to $|x|$.  (Actually, each "optimal" prefix Turing machine $U$ gives a different version $R_U$ of this set; usually it doesn't make much difference which $U$ we use to define $K$; it affects $K(x)$ only by $O(1)$.)

Buhrman et al. showed (at CCC 2010) that $BPP$ is poly-time truth-table reducible to $R$, and earlier work showed that $PSPACE$ is in $P^R$, and NEXP is in $NP^R$.

These might seem like fairly worthless results, since they give a non-computable upper bound on complexity classes!  However a recent paper (see http://www.eccc.uni-trier.de/report/2010/138/ ) shows $PSPACE$ is an upper bound on the class of decidable sets that are poly-time truth-table reducible to $R_U$ for every $U$.  That is, $PSPACE$ is sandwiched between the class of decidable problems that are Turing and truth-table reducible to $R$.

The same paper also shows that Exponential Space is an upper bound on the class of decidable problems that are in $NP^{R_U}$ for every $U$.  I would guess that it might be possible to characterize $NEXP$ in this way.


Does there exist a complexity class such that the number of accepting paths is a prime number?

Many other complexity classes which have appeared in literature are defined in terms of the number of accepting paths.  Just for fun, examples from the Complexity Zoo include GapP, AWPP, C=P, Few, FewP, LWPP, ModkP, SPP and WPP.  Also do not forget the logarithmic-space versions of these classes.

A serious fact is that the definition of randomized complexity classes such as the very important BPP can be viewed as based on the number of accepting paths.

As for the class of decision problems which have a nondeterministic polynomial-time Turing machine such that yes-instances have a prime number of accepting paths and no-instances have a composite number of accepting paths: As Philip White and other people wrote in comments on the question, you could define it.  Whether that class has any interesting property or not is a separate issue.


Minimum order of partite in a bipartite graph

This is an upper bound on $N$ for the second formulation:

Assume that I pick $N$ uniformly random sets.

The probability of a pair of elements not to be covered by a specific set is
$$1-\left(\frac{a}{L}\right)^2$$

Therefore the chance that it is not covered by any set is:
$$\left(1-\left(\frac{a}{L}\right)^2\right)^N$$

Using the union bound, the chance that some pair will not be covered is at most:

$$P={L \choose 2}\left(1-\left(\frac{a}{L}\right)^2\right)^N$$

This means that if $P<1$, there exists some proper covering using $N$ sets. Notice that:

$$P={L \choose 2}\left(1-\left(\frac{a}{L}\right)^2\right)^N<L^2e^{-N(\frac{a}{L})^2}$$

Therefore it is enough to demand $L^2e^{-N(\frac{a}{L})^2}<1$, which gives us a bound on $N$:

\begin{align}
L^2e^{-N(\frac{a}{L})^2}<1\\
-N(\frac{a}{L})^2<-2\ln L\\
N>2\ln L\cdot(\frac{L}{a})^2
\end{align}

Which means that there exists a proper covering using $2\ln L\cdot(\frac{L}{a})^2$ sets of size $a$.

Now notice that every set covers $a\choose 2$ pair of elements, while $L\choose 2$ pairs exist, so a lower bound for $N$ would be:
$$\frac{L\choose 2}{a\choose 2}\approx (\frac{L}{a})^2$$

So the upper bound is tight up to factor $O(\log L)$. (If I had to bet, I'd say the lower bound is loose while the upper is asymptotically tight).

This means that if your goal is to compute the value of the optimal $N$ - answering $(\frac{L}{a})^2\sqrt{\log L}$ would give an approximation ratio of $O(\sqrt{\log L})$.


Is it possible to create an algorithm-aware optimizer?

Actually, optimizing compilers do that kind of things. I am for
example thinking of the work of Robert Paige at NYU. The problem is of
course to identify situations where a given type of transformation may be useful.
That require identifying computational structures, and knowing some of
the algebraic properties of the data being manipulated.

A classical example, very simple, is the strength-reduction in
loops, where you replace a product by a sum. It usually does not change
much the complexity (see more below), but can effectively speed up your algorithm, at
the cost of one extra variable. This is a special case of finite
differencing techniques.

I think you should find example in the litterature on high-level
optimization, which is quite different from peep-hole optimization in
the code generation process. See the two wikipedia article for various types of code optimization.

Regarding the identification of such situations, they can sometimes be
found by formal analysis of program. It can also help to make them
more apparent by using very high-level abstractions in the programming
process.

Many such transformations improve the program without changing the
complexity. But it much depends on what complexity you are considering
and what is a unit operation.

For example if you consider arithmetics of unbounded integers,
addition has linear cost, while multiplication has a higher cost
(quadratic in the naive case). Using reduction in strength in loops
will reduce complexity.

I unfortunately do not remember more spectacular cases.

There is also some significant litterature on program transformations, with a variety of techniques that started in the 1970ies. Some transformations may not bring much by themselves, but may enable other transformations. Pattern matching in equational algebras is one way of identifying possible tranformations that has been considered. This may be one reason why very high level abstractions can help the process.


Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

Productive here just means that it isn't stuck.

An unorthodox (seemingly impredicative ) formulation of the sieve of Eratosthenes is

      S = {n : n ∈ N, n > 1} \ ⋃p ∈ S { p q :  q ∈ N, q ≥ p }

The following code is stuck, reflecting the above definition more or less verbatim:

primes = gaps 2 $ foldr (\p r-> union [p*p, p*p+p..] r) [] primes

union (x:xs) (y:ys) = case compare x y of            -- ~= sort ( (x:xs) ++ (y:ys) )
                        LT -> x : union  xs (y:ys)
                        EQ -> x : union  xs    ys
                        GT -> y : union (x:xs) ys

gaps c (x:xs) | c < x     = c : gaps (c+1) (x:xs)    -- ~= [c,c+2..] \\ (x:xs)
              | otherwise =     gaps (c+1) xs        --    when null((x:xs)\\[c,c+2..])

because primes list isn't primed with any initial data, so we get unbounded recursion. Asking take 10 primes produces no output (GHCi actually closes).

The following is also stuck (or blows up, whatever you prefer to call it):

primes = (2:) . gaps 3 . foldr (\p r-> union [p*p, p*p+p..] r) [] $ primes

because each union demands to know the head of further results on its right, to produce its results. Asking take 10 primes produces [2, and then no output (GHCi will actually close itself on this "racing to the bottom" ).

But this

primes = (2:) . gaps 3 . foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] $ primes

works fine, because now getting the head of the further results doesn't trigger the next union call right away.

On SO you ask how one could come up with such definition.

You could start with Turner's sieve,

primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y<- xs, rem y x /= 0]

then turn it into an optimal trial division sieve, by postponing the filters creation to the right moment,

primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span(<p*p)xs = h ++ sieve ps [y | y<- t, rem y p /= 0]

then make it a kind of the sieve of Eratosthenes,

primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span(<p*p)xs = h ++ sieve ps (minus t [p*p, p*p+p ..])

minus (x:xs) (y:ys) = case compare x y of
                        LT -> x : minus  xs (y:ys)
                        EQ ->     minus  xs    ys
                        GT ->     minus (x:xs) ys

The last step is to realize that (...(((xs-a)-b)-c)-...) == xs - (a+(b+(c+(...)))). (And the next step, that (a+(b+(c+(...)))) == a + ( (b+c) + ( ((d+e)+(f+g)) + ( ... ))).)

(or, it could "dawn on" you).

(edit:) one more way is to tweak your SO code actually. :) with just some minor tweaks it becomes the very nice

primesA :: [Integer]
primesA = 2 : 3 : sieve 5 [9, 15 ..]

sieve p cs@(c : t)
   | p == c    =     sieve (p + 2) t
   | otherwise = p : sieve (p + 2) (union cs [p*p, p*p+2*p ..])

(though not properly postponed at all) which is finally fixed with

primesA = [2,3,5] ++ sieve 7 (foldr (\p r-> p*p : union [p*p+2*p, p*p+4*p ..] r)
                                    [] $ tail primesA)

sieve p cs@(c : t)
   | p == c    =     sieve (p + 2) t
   | otherwise = p : sieve (p + 2) cs

as can be seen, your sieve is what I called gaps above.


Finding a random regular graph with degree d

The standard simple way of generating random regular graphs is:

while the degree < d

choose a random perfect matching from the edges still possible to add to the graph
If no matching is possible, restart the process.

The problem with this is that the higher edge degree you want, the more likely it is for the algorithm to get stuck. I see many papers limiting themself to $|V|>d^3$, so I don't know if this process will work for you.


The quad-edge data structure (Delaunay/Voronoi)

I think Guibas and Stolfi's “edge algebra” formalism is a bit unnecessary.

All that's really necessary is to remember the distinction between primal and dual graphs.  Each face $f$ of the primal graph has a corresponding dual vertex $f^*$;  each edge $e$ of the primal graph has a corresponding dual edge $e^*$; and each vertex $v$ of the primal graph has a corresponding dual face $v^*$.  Primal edges connect primal vertices and separate primal faces; dual edges connect dual vertices and separate dual faces.  The dual of the dual of anything is the original thing.  See Figure 4 in Guibas and Stolfi's paper:

Guibas and Stolfi propose thinking about each edge (either primal or dual) as a collection of four directed, oriented edges; for simplicity, I'll call these darts.  Each dart $\vec{e}$ points from one endpoint $\text{tail}(\vec{e})$ to the other endpoint $\text{head}(\vec{e})$, and locally separates two faces $\text{left}(\vec{e})$ and $\text{right}(\vec{e})$.  The choice of which endpoint to call $\text{tail}(\vec{e})$ is the dart's direction, and the choice of which face to call $\text{left}(\vec{e})$ is its orientation.  (Guibas and Stolfi use “Org” and “Dest” instead of “tail” and “head”, but I prefer the shorter labels, because Unnecessary Abbreviations Are Evil.)

For any dart $\vec{e}$, Guibas and Stolfi associate three related darts:

$\text{tailNext}(\vec{e})$: The dart leaving $\text{tail}(\vec{e})$ next in counterclockwise order after $\vec{e}$.
$\text{flip}(\vec{e})$: The “same” dart as $\vec{e}$, but with $\text{left}(\vec{e})$ and $\text{right}(\vec{e})$ swapped.
$\text{rotate}(\vec{e})$: The dual dart obtained by giving $\vec{e}$ a quarter turn counterclockwise around its midpoint.

These three functions satisfy all sorts of wonderful identities, like the following:

$\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
$\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
$\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
$\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
$\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
$\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

For a complete list, see page 83 of the paper (but beware that the authors use postfix notation $e~Flip$, presumably because it's closer to the declarative code e.Flip).  Guibas and Stolfi call any triple of functions satisfying all these identities an edge algebra.

Moreover, given these three functions, one can define several other useful functions like

$\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$ — swap head and tail vertices
$\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$ — the next dart after $\vec{e}$ in counterclockwise order around the face $\text{left}(\vec{e})$

Finally, knowing these functions tell you absolutely everything about the topology of the subdivision, and any polygonal subdivision of any surface (orientable or not) can be encoded using these three functions.

The quad-edge data structure is a particularly convenient representation of a surface graph that provides access to all these functions, along with several other constant-time operations like inserting, deleting, contracting, expanding, and flipping edges; splitting or merging vertices or faces; and adding or deleting handles or cross-caps.

Have fun!


Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)

Don't know about "an implementation" but check out

Computing Pathwidth Faster Than 2^n
Karol Suchan and Yngve Villanger
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009,Copenhagen, Denmark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.


Example of where violation of strict positivity condition in inductive types leads to inconsistency

It is actually possible to relax strict positivity and remain consistent. For instance, it suffices to only have a positivity condition. That is, we can accept type definitions like

$$
  T \triangleq \mu\alpha. (\alpha \to 2) \to 2
$$

where recursive type variables occur to the left of an even number of arrows and retain consistency.

However, theories permitting this sort of inductive type do not have set-theoretic models -- you cannot interpret types as sets and terms as elements of sets. In this case, we are saying that $T$ is isomorphic to its double-powerset (i.e., $T \simeq \mathcal{P}(\mathcal{P}(T))$), and this violates Cantor's theorem.

Since dependent type theories are often used to formalize mathematics, their designers are usually hesitant to add principles which are not compatible with a set-theoretic semantics, even if they are consistent.

EDIT: I'm adding this edit in response to Andrej's question. The type $T$ is consistent if you add it to (say) Agda; there are no problems with it at all. We only have a problem if we combine non-strict positivity with excluded middle.

The intuition for why is safe is (IMO) best seen through the lens of parametricity. In System F, we can show using parametricity that for any definable functor $F$, the type $\mu F \triangleq \forall \alpha.\; (F\alpha \to \alpha) \to \alpha$ is indeed an inductive type.

Now, recall that a definable functor $F$ is a type operator $F : \ast \to \ast$, together with an operator
$$\mathrm{map} : \forall \alpha,\beta.\;(\alpha \to \beta) \to F\;\alpha \to F\;\beta$$
satisfying the functoriality conditions (i.e., $\mathrm{map}\;id = id$ and $\mathrm{map}\;f\;\circ \mathrm{map}\;g = \mathrm{map}\;(f \circ g$).

Now, we can define a type operator for the double powerset

$$C = \lambda \alpha.\; (\alpha \to 2) \to 2$$

and because $\alpha$ occurs only positively, we can also define a map operator for it:

$$
map_C = \lambda f : \alpha \to \beta, a' : (\alpha \to 2) \to 2, k : \beta \to 2.\; a' \;(\lambda a:\alpha.\; k\;(f\;a))
$$

So we know that $T = \mu C$ is a legitimate inductive type.


What are bounded-treewidth circuits good for?

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $k$ being singly exponential.

The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), determinism (the inputs to OR-gates are mutually exclusive), decomposability (the inputs to AND-gates depend on disjoint sets of variables), and stucturedness (the AND-gates split the variables in some fixed way throughout the circuit, as described by a v-tree). This class has been studied in knowledge compilation and is known to enjoy tractable SAT and tractable model counting (recapturing probabilistic evaluation and counting), but other problems have been studied for this class such as enumeration, quantification, etc.

So one way to use bounds on the treewidth of a circuit is to convert it to this d-SDNNF class which has more explicit properties in terms of the circuit semantics, and for which there are several known results on the tractability of various tasks.


How do you decide when you have enough research results to write a paper and to which journal you submit the paper

JCR is part of the ISI Science Citation Index family of databases, which is not especially reliable in its measurement of computer science impact. See for instance this report from Informatics Europe which specifically warns against using ISI databases to measure the impact of computer scientists.

In any case, if you want your papers to get attention from other computer scientists, publication in selective conferences is still the way to go. We can argue whether it should be, but that's what it is. Some conferences (e.g. SIGGRAPH) count as a journal directly (their proceedings are published as a special issue of a journal), others (e.g. FOCS/STOC/SODA) expect their authors to later turn the same material into an expanded and more polished journal paper, but the conference is to a large extent how to signal other researchers that your work is worth paying attention to. If you're not familiar with the conferences in the area, choosing one sponsored by ACM or IEEE over one that isn't is a good rule of thumb, as is choosing one that calls itself a "symposium" over one that calls itself a "workshop".

However, that doesn't mean that you have to partition your work into least publishable units as you describe your coworkers doing, and it also doesn't mean that saving up multiple small results into a single paper is a good way of making your papers stronger. It's certainly possible to publish papers like that but to my mind the better ones are often the ones that have a single strong main result, perhaps with additional results on the side not to strengthen the paper but rather to provide more complete coverage of its subject.


On Closure Properties of #P in the Context of PF ∘ #P

Note that FP and PF are the same complexity class. It is stated in proposition 2.1 on page 3 that FP ∘ #P = FP $^{\# P{ [1]}}$


Is linearizability equivalent to consensus problem?

The thing you get wrong is "we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes." We don't know that, and in fact it is wrong.

What the quote from the JACM95 paper shows is that single-writer multi-reader registers can be implemented using message passing. And only this kind of registers, or any other objects that can be implemented (given a minority of crashes) from such registers. This includes for example multi-writer multi-reader registers (MWMR).

In contrast, linearizability is not limited to objects that can be implemented using single-writer multi-reader registers. One example of such objects are those that support (atomic) Read-Modify-Write operations.

In fact as Attiya et al point out (Section 7) such objects cannot be implemented by MWMR registers precicely because they allow solving consensus (cf. Wait-free synchronization by Herlihy) and thus implementability would contradict the FLP result.


Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

The SOET problem is NP-Complete as we show in the following paper:

Axel Dahlberg, Jonas Helsen, Stephanie Wehner, How to transform graph states using single-qubit operations: computational complexity and algorithms,
 CoRR abs/1805.05306 (2018).

See Corollary 3.4.1


Computing the edge orbits of a graph (and discussing definitions)

It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction.

First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ that preserve $G$'s edge structure. Similarly, we define $\Gamma_E(G)$ to be the group of automorphisms over the set of edges $E$ that preserves $G$'s edge incidence structure.

For any vertex-automorphism $\pi \in \Gamma_V(G)$, we observe that there is a natural edge-automorphism $\pi':E \to E$ induced by $\pi$. Let $\Gamma'_V(G)$ denote the group of such induced edge-automorphisms.

  Theorem: $\Gamma'_V(G)$ is isomorphic to $\Gamma_E(G)$ for all simple, connected $G$ with three or more vertices, with three exceptions: $K_4$, $K_4$ with one edge deleted, and the graph illustrated above within the question.

In other words, the example presented in the question happens to be on one of the very few graphs that make the distinction between $\Gamma_E(G)$ and $\Gamma_V'(G)$ important. Also, it is trivial to observe that this isomorphism does not hold for graphs with two or fewer vertices.

I believe that the canonical reference for this result is [1], though the proof is somewhat complicated with several cases. There are references to some more streamlined proofs of this result in [2], but I haven't tracked those down.

Whitney, Hassler. "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54.1 (1932): 150-168.
Hemminger, R. L. "On Whitney's line graph theorem." The American Mathematical Monthly 79.4 (1972): 374-378.


ETH based lower bound for $k$-COLORING of bounded degree graph

The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction.
Also, the reduction $k$-COLORABILITY $\leq_p$ $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$) given by Emden-Weinert et al. [2] is a linear reduction.
From these observations, it follows that, unless ETH fails, there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$), .
Detailed Explanation:
Let $G$ be a graph of maximum degree $4$ as constructed in the hardness result of Cygan et al [1].
Add $k-4$ new vertices to $G$ and connect them to all vertices of $G$ as well as to themselves, the resulting graph $G'$ has an unbounded degree but, all except $k-4$ of the vertices has degree at most $k$. We do not know whether $G'$ is $k$-colorable. The number of newly added edges and vertices for a constant $k$ is $O(n)$, thus any $2^{o(n)}$ algorithm for $k$-coloring of $G'$ falsifies ETH.
The second step is to reduce the maximum degree of $G'$ by the method provided in the work of Emden-Weinert et al. [2]. Their method roughly speaking is as follows: they take a high degree vertex $u$ then remove $k$ edges of $u$ and add $k-1$ new edges to $u$ to connect it to a specific gadget with $O(k)$ many vertices. This procedure clearly reduces the degree of $u$ by one, and if we repeat this process $n-k$ times, the degree of $u$ will be at most $k$. They showed that the newly created graph after this step exhibits a similar coloring scheme as the original graph (except for the gadgets). As long as there is a high degree vertex, they repeat the mentioned degree reduction procedure. Additionally, based on their construction, we know that the maximum degree of vertices inside gadgets is at most $k-1+\lceil \sqrt{k} \rceil$, thus once the procedure ends, the resulting graph has the claimed maximum degree.
Observe that we have to perform the aforementioned procedure only on $k$ vertices of $G'$ and since their degree is $n+k-4$, after at most $O(kn)$ iterations the procedure stops. Additionally in each iteration, we add at most $O(k)$ new vertices, which means by the end of the procedure, the constructed graph has at most $O(k^2n)$ vertices. Hence, any $2^{o(k^2n)}$ algorithm for $k$-coloring of this graph, would result in a $2^{o(n)}$ algorithm for $3$-coloring of the input graph $G$. Since $k$ is a fixed constant, we conclude that any $2^{o(n)}$ algorithm for k-coloring on this graph would lead us to a $2^{o(n)}$ algorithm for $3$-coloring of $G$.


Yes. The simplest way to understand this is to understand the zero-knowledge proof that you know a 3-coloring of a graph. 3-coloring is NP-complete, so an arbitrary hash function $h$ and target value $w$ can be represented as a graph where knowing a 3-coloring for that graph is equivalent to knowing a $v$ such that $h(v) = w$.

That isn't the most efficient way to do it; for that you'd want zk-snarks or one of the zillion similar encodings. That approach is similar but you're modeling your hash function as a modular matrix multiplication instead of a graph coloring. But the answer is yes, there is a zero-knowledge protocol for proving you know the preimage of a value for a hash function.


Evidence that matrix multiplication can be done in quadratic time?

I don't know about others but I can tell you why I tend to believe that $\omega=2$. When you read through the history and development of fast matrix multiplication algorithms, I think that it is hard not to get feeling that all that we need is just a slightly better basic algorithm from which, even using known techniques, $\omega=2$ will follow. Basically, all algorithms today (including group theoretic ones) start with some "simple" construction that is then amplified. Those constructions are clever but they give the reader some sort of an "ad-hoc" feeling. I don't see a reason to believe that we cannot come up with better simple constructions.


Dependences imposed on Subset Sum Problem

This is not a solution, but a reference suggestion.

The problem should be (a special case of the decision version of) the partially-ordered knapsack problem.  For example, you can look at the following paper and the references therein.

S.G. Kolliopoulos and G. Steiner: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155 (2007) 889-897.  http://dx.doi.org/10.1016/j.dam.2006.08.006


Sequent calculus for nonmonotonic/defeasible logics?

There is a paper by Beyersdorff and Chew on the proof complexity of calculi for non-monotonic logic. In the references of this paper you will find links to the papers where these calculi are defined.


Binary multiplication and parity convolution

Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (no need to propagate carry bits), but multiplication of integers is an operation people consider essential, and so has direct support in ALUs and programming languages.


Are (empirical) Rademacher complexity always positive?

Yes, the empirical Rademacher complexity is non-negative, and this follows from Jensen's inequality.

For completeness, the empirical Rademacher complexity $\hat{R}(\mathcal{F}, X)$ given a sample $X = \{x_1, \ldots, x_m\}$ and a class of real-valued functions $\mathcal{F}$ whose domain contains $X$ is
$$
\hat{R}(\mathcal{F}, X) := \mathbb{E}_\sigma \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)},
$$
where the expectation is over $m$ independent random variables $\sigma:= (\sigma_1, \ldots, \sigma_m)$ sampled uniformly from $\{-1, 1\}$.

Notice that $\sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)}$ is a convex function of $\sigma$, because it is the supremum of linear functions. Then, by Jensen and linearity of expectation,
$$
\mathbb{E}_\sigma \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)}
\geq \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\mathbb{E}[\sigma_i] f(x_i)}
= 0.
$$

The final equality follows because $\mathbb{E}[\sigma_i] = 0$ for all $i$.


What are some problems where we know we have an optimal algorithm?

Any algorithm which takes linear time and has to read its whole input must be asymptotically optimal. Similarly, as Raphael comments, any algorithm whose runtime is of the same order as output size is optimal.


Most optimal parallel method for calculating the integral of a 2D function

You can partition your domain for subsequent parallel processing as follows. There are a few possible options. You can try a static geometric decomposition, including recursive bisection, quad or oct-trees and a space-filling curve.

Recursive bisection techniques are used to partition a domain (e.g., a finite element grid) into subdomains of approximately equal computational cost while attempting to minimize communication costs, that is, the number of channels crossing task boundaries
A divide and conquer approach is taken. The domain is first cut in one dimension to yield two subdomains. Cuts are then made recursively in the new subdomains until we have as many subdomains as we require tasks. Notice that this recursive strategy allows the partitioning algorithm itself to be executed in parallel. Advanced variants include recursive graph bisection and recursive spectral bisection.

Here is an example. In the following picture, assume that magenta points requires twice as much work as cyan ones.

Then, you continue applying recursive bisection by cycling through the axes until # pieces = # processors, obtaining something like the following:

The idea behind quad-trees is the following one. Partition all of space into quadrants (octants in 3-space). If any piece contains too much work, partition it into quadrants, and so on. See the next picture for an example.

The best general-purpose geometric load-balancing comes from space-ﬁlling curves.
The order in which points are visited in the space-ﬁlling curve determines how the geometric objects are grouped together to be assigned to the processors. The following image shows an Hilbert space-filling curve.

You problem may also be amenable to a solution using what is known as a scattered decomposition. Used when there is a structured domain space (e.g., an image) and the processing requirements are clustered, such as modeling a crash or processing an image with only a few items of interest. Suppose there are P processors. Cover the problem domain with non-overlapping copies of a grid of size P and assign each processor a cell in each of the grids. If you use more pieces:

Less load imbalance, i.e., computation time
More overhead and/or communication time

Finding a good tradeoff may require experimenting running the application and measuring how parallel time is affected by different scattering strategies.

Here is an example. The first picture show an example image that must be processed. Say it contains sea water and an island, and you may want to process the vegetation on the island. The image is partitioned using a very simple domain decomposition technique. The second picture shows an example of scattered decomposition.

Finally, you can use an advanced technique known as Adaptive Mesh refinement (AMR): grids are broken into blocks of ﬁxed extents, when needed blocks are reﬁned into children with same extents. Block size are chosen to optimize balance of cache efﬁciency (optimization possible since loops operate on ﬁxed size array), communication, and load balance.
Often balancing blocks per processor sufﬁces; if communication is excessive then use a space-ﬁlling curve. Rebalancing requires only simple collective communication operations to decide where blocks go. The technique can be used for arbitrary dimensions. If block size is 1, adaptive blocks are quad or oct-trees.
See the next picture for an example.

Hope this helps.


Delaunay Triangulation of Parallelepiped

Testing whether a pair of points $p_i$ and $p_j$ are the endpoints of a Delaunay edge can be solved as a linear programming feasability problem: Lift each point to one higher dimension by making its last coordinate be the sum of squares of the other coordinates. Then look for a hyperplane passing through $p_i$ and $p_j$, such that all the other points are on one side of it. This can be represented in linear inequality constraints by seeking a vector $v$ and scalar $c$ such that the dot product of $v$ with each point is at least $c$, and is exactly $c$ in the case of $p_i$ and $p_j$.

So for any set of points in any dimension, it's possible to find the Delaunay edges one by one, by solving a number of linear programs that is polynomial in the number of points. The reason Delaunay triangulation is hard is not because of the edges, it's because there may be too many higher-dimensional features.


Space complexity for multiplying $m$ matrices

Letting m be [number of vertices minus 1] and letting each matrix be

[the adjacency matrix of the result of giving the vertex t a loop]

gives a reduction from st-connectivity to your problem, so no such algorithm is known.


What are the obstructions to extending $L=SL$ to $L=NL$?

The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk.  The standard counterexample here is a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex, $t$), and each vertex also has an edge leading all the way back to the leftmost vertex, $s$.  To get from $s$ to $t$ by a random walk then takes ~$2^n$ time.  So, what is the small-space randomized algorithm for directed connectivity that we're hoping to derandomize, analogous to what Reingold did for $USTCON$?  (To put it another way, how do we show $RL=NL$, let alone $L=NL$?)  For directed connectivity, of course there's Savitch's algorithm, but that takes $O(\log^2 n)$ space, and for general graphs no one has managed to improve it for half a century, with or without the use of randomness.


Smallest set that intersects some given sets

Your first problem is the hypergraph transversal problem (aka the HITTING SET problem). The second problem is the FEEDBACK VERTEX SET problem. Both the problems are NP-complete.


Decide if a given sequence is regular or context-free

As you already noted, a single example or any finite number of words in $L$ is not going to be the right notion. So why not look beyond? A somewhat famous paper did so in 1967 and revealed what happens when you try to learn in the limit.

An alternative interpretation of your question leads to the field of descriptive complexity theory where one looks for a minimal representation $\langle M,w\rangle$ of a string in terms of a TM $M$ and an input word $w$ to it. Asking whether a single word had been (better?) generated by a CFG or a DFA is indeed ill-posed: either one would be a special case of such a pair $\langle M,w\rangle$.

Finally, given $w\in\Sigma^*$, asking for the smallest DFA $A$ and CFG $G$ with $w\in L(A)$ and $w\in L(G)$ is going to disappoint. The simplest DFA (with just one state) and the simplest CFG (with one non-terminal) will do because the universal language $\Sigma^*$ is blatantly regular. To make this intersting you'd need some negative instances, which brings you back to reading said famous article. I recommend it.


Hardness of LWE on not-uniform vector samples

Since you are specifically interested in $q=2$, I will focus on this case in my answer. A note on your choice of tags: you tagged your question with "lattice" and "lattice-theory"; however, your question seems much more closely related to questions in coding theory. I elaborate below.

A good starting point is to observe that LPN with matrix $A$ reduces to the hardness of decoding a linear code generated by the parity-check matrix $B$ of $A$ - or rather, in the decisional case, to distinguishing a codeword from random.

proof: for any secret vector $s$, $B\cdot\chi = B\cdot(As + \chi) \approx_{\mathsf{LPN}} B\cdot U_m = U_{m-n}.$

Hence, one can reword your question as follows: for which choice of code matrix is the corresponding decoding problem hard? Coding theory gives essentially the following informal answer: it is hard for most choices of codes. Specifically, there are only few linear codes for which we do know of an efficient decoding algorithms - hardness of decoding seems to be the rule rather than the exception.

Some examples of bad choices of $A$: if $A$ is an LDPC code, then its parity-check matrix $B$ is sparse, and distinguishing $B\cdot\chi$ from random is easy (given that $\chi$ is a distribution over sparse vectors). Reed-Solomon codes can also be decoded efficiently when the noisy codeword has sufficiently low noise rate, hence should be used with care (but if there is enough noise, they should still work).

In general, we do not have any generic reduction stating "if $A$ has the following structure, then the LPN problem with respect to the matrix $A$ is as hard as the standard LPN problem." However, we do have good conjectures regarding what properties of $A$ make the corresponding LPN problem hard. Two of the main such properties is for the code to have a good minimal distance - ideally, meeting the Gilbert-Varshamov bound (which is achieved with good probability by a linear code generated by a uniformly random matrix, corresponding to the standard LPN assumption), and to satisfy the uniform output property (see the next two references). This was investigated in this paper, where new candidate efficient linear codes (with linear-time encoding) were suggested as plausible candidates for giving an intractable variant of LPN (see also the master thesis of the first author, specifically the chapter 5).

While LPN with a random parity-check matrix $B$ is the most well-studied form of the assumption, a bunch of specific alternative choices of code matrix have been used in the cryptography literature. These includes LDPC codes, which are at the core of the famous cryptosystem of Alekhnovich (note that if the code matrix $A$ is an LDPC code, the LPN variant is insecure; however, when its parity-check matrix $B$ is an LDPC code, meaning that $A$ is a sparse matrix, then it leads to a plausible assumption), MDPC codes, used to construct variants of the McEliece cryptosystem, quasi-cyclic codes, codes generated by Toeplitz matrices, and others. An overview of candidates which have been used in the literature is given, with pointers, in one of my recent papers.


Question about an old result of Erdős and Simonovits

Yep. The writing is not great (but this is a nice result [but there should be an easier proof by now]). Anyway, you should read the $n^{1+\alpha}$ in the proof as a fixed quantity $\tau$, which is the number of edges in the original graph. The rest then follows.


Characterisation of P in terms of register machines

The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of Handbook of Theoretical Computer Science, Vol. A.

For simulations between RAM and Turing machines see Theorems 2.5 and 2.6, pp. 26--27. It also contains pointers to historic references.


Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

The following algorithms works well if the underlying field has a very small order $s$.

Suppose we know $q$ is irreducible, of a fixed degree $d$. Then, mod $q$, we know $x^{s^d} = x$ holds. Hence it suffices to pre-compute $p(x) \mod x^{s^d} - x$.

In general, $q(x)$ may decompose into a product of irreducible polynomials $q = q_1 \dots q_r$. In this case, a similar argument applies to computing $p$ modulo each $q_1, \dots, q_r$ separately, and then piecing the results together. So we really need to compute $p(x) \mod x^{s^{d'}} - x$ for each $d' \leq d$.


A conjecture on 4-coloring maximal planar graphs

Conjecture 2 is already proved.
Quote from J.A. Tilley, The a-graph coloring problem(2017):

Theorem A.1. Let $G$ be an a-graph with boundary cycle $uxvy$ for the exterior 4-face and let $G$ have a 4-coloring $c$. Suppose, without loss of generality, that $c(x)=1$, $c(y)=1$ or 2, $c(u)=3$, and $c(v)=3$ or 4. Then there is either a 1–2 path between $x$ and $y$ or a 3–4 path between $u$ and $v$.

Proof. Suppose that G with 4-coloring c is a minimal counterexample to the theorem. Clearly G cannot have either an interior
xy edge or an interior u v edge. Let X be the set of vertices of G adjacent to x; they form an internal path between u and v that
includes at least one interior vertex of G. At least one of those interior vertices of G belonging to X is colored 2, for otherwise
the path between u and v would be colored 3–4, contradicting the supposition. Contract the various edges joining x to each
vertex of X colored 2, and change the color of x to 2. The result is a 4-colored a-graph F . The edge contractions do not create
any 3–4 path between u and v . By the minimality assumption, F must therefore have a 1–2 path between x and y. Reverse
the contractions and restore the color of x to 1 to reveal a 1–2 path between x and y in G, contradicting the supposition and
establishing the truth of the theorem.

Definiton: in the above paper, an a-graph is a plane graph such that one face has a 4-vertex cycle as boundary and all other faces have a triangle as boundary.


Time complexity of d-dimensional convex hull

I don't know any nontrivial lower bounds other than the $\Omega(n\log n)$ algebraic-decision-tree lower bound for two dimensions, which also extends to larger $d$.

As for upper bounds: In 3d, the whole hull can be found in $O(n\log n)$; in four or higher dimensions that doesn't work because the hull complexity grows exponentially with $d$, but nevertheless for any fixed $d$, finding all vertices can be done in time $O(n^2)$ (determining whether a given point is a vertex can be done in linear time by solving a linear program), and the Chan reference below improves this slightly.

See

Ottmann and Scheurer, "Enumerating extreme points in higher dimensions", STACS 1995 and Nordic J. Comput. 2001

Chan, "Output-sensitive results on convex hulls, extreme points, and related problems", DCG 1996

Helbling, "Extreme points in medium and high dimensions", ETH thesis 2010


$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

In the first paper which you link to (Garey-Johnson-Tarjan) they show how to construct a 3-input OR on Figure 6. This gadget has the property that it can link 3 edges with the only requirement that at least one of them needs to be used. So start from your original cubic 3-connected graph and suppose that it has a face larger than $d$. Then insert this gadget into this face onto edges $e,f,g$, where $e$ and $f$ are adjacent, and $g$ is opposite to them. Since $e$ and $f$ are adjacent, anyhow one of them had to be used in the original cubic graph, so the gadget will do nothing. On the other hand, since $g$ is on the opposite side of the face, the size $d$ will be almost halved. Here 'almost' means that this inserted gadget also has some size $c$, so the new faces will have size at most $d/2+c$. Repeating this gets rid of all faces whose size is more than $2c$.


Is there an additive time hierarchy theorem?

I don't see the need for your clarification, since through linear speed-up those sets are exactly the same. It is clear why you need to avoid using asymptotics, since $f(n)-g(n)$ and $f(n)$ are asymptotically the same, but not using asymptotics doesn't somehow make the linear speed-up theorem not true.

Some further insight can be gained. $g(n)$ is actually $g(f(n))$,i.e. it must depend on $f(n)$ to work for all functions. Why? Suppose g(n) is non-constant. Pick $f(n) = 2 g(n)$ . Then clearly $f(n)$ and $f(n)-g(n)$ are equal by the linear speed-up theorem. If $g(n)=c$ is constant, then we can pick a non-constant $f(n)$ so that the conjecture doesn't hold.

What if we allow dependency on $f(n)$? Well then by taking the known deterministic hierarchy theorem and doing some basic arithmetic we can see that any $g(f(n))$ that is $o((1 - \frac{1}{ \log f(n)} ) f(n) )$ works. However I am not sure if just by stating the same theorem in a slightly different form opens up the possibility of some new insight.


A recent and interesting attempt to model flocking behavior is Bernard Chazelle's work (see the four most recent papers (as of Mar 2012). He's also running a summer school on computation and biology at the Institute for Advanced Science.


Shor is probably referring to this fantastic lecture by Emre Telatar that walks you through the steps in polar coding. Do watch it! In doing so, you shall see that the best mental model to have in mind while trying to wrap your head around the polar code is the erasure channel.


Finding all possible simple cyclic paths in a digraph

Efficient Algorithms are already known in the literature.

See e.g.,

Tarjan, R E and Read, R C (1975) Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3):237-252
Johnson, D. B. (1975) Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing 4(1):77-84.


Statistical Distance Growth Given K Independent Copies

See the "inclusion-exclusion" Lemma 2.2 here
https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf .
For distributions $p,q,p',q'$, we have
$$
||p\otimes q-p'\otimes q'||
\le
||p-p'||
+
||q-q'||
-
||p-p'||
\cdot
||q-q'||.
$$

From here, it immediately follows that if $p=p_1=p_2=\cdots=p_k$
and $q=q_1=p_2=\cdots=q_k$ and furthermore $||p-q||=d$,
then the TV between the corresponding products is upper-bounded by $1-(1-d)^k$. This is proved explicitly in Lemma 4.2 in the linked paper.


Existence of long induced paths in expander graphs

The answer should be positive if your bounded-degree graph has both the property of having constant expansion and $\Omega( \log n)$ girth. The argument would be: start at a vertex, then for $n^\epsilon$ steps take a walk in which each step is chosen at random among those that don't take us back to where we were the step before. (So if the graph is $d$-regular we have $d-1$ random choices at each step.)

Now I claim that, for every $i$ and $j$, if I look at steps $i$ and $j$ of the walk, the probability that there is an edge between the vertex at step $i$ and the vertex at step $j$ is $n^{-\Omega(1)}$. Then, if $\epsilon$ is chosen sufficiently small, a union bound will show that the walk will induce a path with probability $1-o(1)$.

If $|i-j|$ is less then the girth, then the probability of an edge between $i$ and $j$ is just zero. If $j> i+ \Omega(\log n)$, then the expansion of the graph should be enough to argue that the existence of the edge $(i,j)$ happens with probability $n^{-\Omega(1)}$. This is because, for a fixed start vertex $v$, the distribution of the walk after a number of steps equal to the girth is uniform over a set of size $n^{\Omega(1)}$, and so has collision probability $n^{-\Omega(1)}$; every subsequent step should only decrease the collision probability (this is true for an actual random walk, but it should also be true for this non-backtracking walk), and so the collision probability, and hence the min-entropy, of the distribution stays $n^{-\Omega(1)}$, and the probability of hitting one of the $O(1)$ neighbors of $v$ is also $n^{-\Omega(1)}$.


It is NP-complete to determine whether a tree can be embedded into the two-dimensional integer grid, with the tree vertices placed on distinct grid points and the tree edges placed on grid edges.

See e.g. Gregori, IPL 1989.


Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free

A proper minor-closed family of graphs has bounded treewidth if and only if it's forbidden minors includes a planar graph. Thus, either the family contains all planar graphs or has bounded treewidth. In the former case the treewidth can be $\Omega(\sqrt{n})$ and in the latter case the treewidth is $O(1)$.


We prove it ($P2^c \implies P2^b$) by strong induction (wiki). This proof has actually been given in the "Paxos Made Simple" paper (see the arguments between $P2^b$ and $P2^c$). I re-organize it in the order of "what we know, what we want to prove, and how to prove". Hope it helps.

What we know:

Base case: Some proposal with number $m$ and value $v$ is chosen.

Inductive assumption: Every proposal issued with a number in $m \ldots (n-1)$ has value $v$.

The chosen rule of a proposal: For the proposal number $m$ to be chosen, there must be some set $C$ consisting of a majority of acceptors such that every acceptor in $C$ accepted it.

The issue rule of a proposal: It is the existence of a set $S$ such that $P2^c (1)$ + $P2^c (2)$.

What we want to prove is:

Goal: Any proposal issued with number $n > m$ also have value $v$.

Proof:

Combining "base case" and "chosen-rule" with "inductive assumption", we obtain:
The $C$-condition: Every acceptor in $C$ has accepted a proposal with number in $m \ldots (n-1)$ (Note: because at least each of them has accepted a proposal with number $m$),
and every proposal with number in $m \ldots (n-1)$ accepted by any acceptor has value $v$ (Note: due to the inductive assumption and the fact that a proposal must be issued by a proposer before it can be accepted by an acceptor).

Now consider the set $S$ in $P2^c$ which consists of a majority of acceptors. Because $S \cap C \neq \emptyset$, $P2^c(1)$ cannot happen. Then $P2^c(2)$ must be true. $P2^c(2)$ is actually the "value-issued rule": the value $v'$ of the proposal with number $n$ is the value of the highest-numbered proposal among all proposals numbered less than $n$ accepted by the acceptors in $S$, therefore $v' = v$ because of the $C$-condition.

Related posts:

The proof of P2b in Paxos made simple@cstheory
Correctness proofs of classic Paxos and Fast Paxos@cstheory.


Is memory usage for a tail call not constant and can you get a memory overflow?

The stack usage for tail-recursive functions is bounded by a constant (i.e., is $O(1)$). However, you may still need to manipulate the stack at each recursive call in order to ensure that arguments are where the procedure expects them to be. Here's an example of such a program, written in Ocaml.

let rec frob n a b c d e f g =
  if n = 0 then
    a
  else
    frob (n-1) b c d e f g a

What this does is take decrement a counter, and rotate its arguments until it reaches 0. This program will compile to the following machine code:

_camlFrob__frob_1030:
    subl    $28, %esp
L101:
    movl    %eax, 0(%esp)
    movl    %ebx, 24(%esp)
    movl    _caml_extra_params + 0, %ebp
    movl    _caml_extra_params + 4, %ebx
    movl    0(%esp), %eax
    cmpl    $1, %eax
    jne     L100
    movl    24(%esp), %eax
    addl    $28, %esp
        ret
        .align  16

    L100:
        movl    %ebx, 20(%esp)
        movl    %ebp, 16(%esp)
        movl    %edi, 12(%esp)
        movl    %esi, 8(%esp)
        movl    %edx, 4(%esp)
        movl    %ecx, 0(%esp)
        addl    $-2, %eax
    movl    0(%esp), %ebx
    movl    4(%esp), %ecx
    movl    8(%esp), %edx
    movl    12(%esp), %esi
    movl    16(%esp), %edi
    movl    20(%esp), %ebp
    movl    %ebp, _caml_extra_params + 0
    movl    24(%esp), %ebp
    movl    %ebp, _caml_extra_params + 4
    jmp     L101

As you can see, it is not pushing anything on the stack (the contents of %esp), but it does need to shuffle the contents of the stack around before making the tail call (jmp L101). (As an aside, decrementing the n variable is accomplished by subtracting 2 from %eax, since Ocaml uses a tagged representation of integers.)

I seem to recall that the problem of putting variables into slots so as to minimize the amount of stack/register shuffling you need to do is NP-complete, and that consequently most compilers rely on heuristics to figure out what to do.

(P.S. I don't know what's wrong with the indentation -- it's fine in the preview....)


Update:  I expanded this answer into a paper Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons.

Yes, such an algorithm exists.  I will only prove the $\mathrm{lg}(n!)+o(n)$ bound, but under a likely randomization assumption we also get $\mathrm{lg}(n!)+O(n^{1-ε})$.  I will also describe an attempt for $n^{0.5+o(1)}$ and $O(n^{0.5-ε})$.

We can assume that all elements are distinct, by annotating them if necessary; the average case uses distinct elements in random order.  We can compute the average number of comparisons by adding the entropy loss for each comparison relative to using a fair coin.

The starting point is insertion sort with a binary search to decide where to insert the next element into the sorted subset $S$.  When $(1-ε)2^m ≤ |S| ≤ 2^m-1$, an insertion uses at most $m$ comparisons, which (in terms of entropy) is optimal up to an $O(ε)$ additive factor (and for average-case complexity, $2^m ≤ |S| ≤ (1+ε) 2^m$ also works).  Now, when $|S|$ is not close to a power of 2, insertion of an element $A$ is suboptimal (even in the average case and regardless of how we balance each query), but if wasting $o(1)$ comparisons, we could steer $A$ to an approximately uniform distribution over an interval of $S$ of length close to a power of 2, we get the desired optimality.

We achieve this by adding elements in batches, and sometimes efficiently comparing elements of the batch with each other, such that the interval of $S$ corresponding to an element $A$ decreases in a quasi-random manner (and with the probability distribution of $A$ inside the interval nearly uniform), and when the interval length is close enough to a power of 2, doing the binary search to insert $A$.

Common constructs

We will keep a subset $S$ of sorted elements, and for each unsorted element $A$, we will keep track of the minimal interval $I_A$ of $S$ where $A$ is known to be located.  $|I_A|$ is the length of $I_A$; $I_A=I_B$ is by the identity of the intervals.

Let $\mathrm{Compare}(A,B)$ be: Compare $A$ with $B$, and then (in random order) compare $A$ and $B$ against corresponding elements of $S$ until their intervals are disjoint (or have length 1).  The element of $S$ is chosen (in a consistent manner) to make the probabilities for the comparison as close to 1/2 as possible, assuming that when $\mathrm{Compare}$ is called, $(A,B)$ is  uniformly distributed on $I_A⨯I_B$.  Because of the disjointness in the end, $\mathrm{Compare}$ preserves the uniformity assumption.

The following sections can be read independently of each other.

A $\mathrm{lg}(n!)+o(n)$ algorithm

Given:  A sorted list $S$, and a batch of $m$ unsorted elements; $m∈ω(1)∩o(|S|)$; the unsorted elements are random relative to $S$.

Repeat (1)-(3) while possible:
1. Pick two elements $A$ and $B$ from the batch with $I_A=I_B$ (any choice will work).
2. Run $\mathrm{Compare}(A,B)$.
3. If $|I_A|$ is close enough to a power of 2,(note 1) remove $A$ from the batch (without forgetting $I_A$); and do similarly with $B$.
Finally:  Insert all elements into $S$ and complete the sort.

Note 1: For "close enough", any $o(1)$ relative error (as a function of $m$) works as long as $m-o(m)$ elements will be removed in step (4) (possible by note 2).  Under a conjectured randomization assumption, using $c \log \log m / \log m$ relative error captures $m(1-\log^{-Θ(c)}m)$ elements, allowing a $\mathrm{lg}(n!)+O(n \log \log n / \log n)$ average comparison sorting algorithm.

Note 2: Because the same sequence of comparisons leads to the same bounding interval, almost all elements will go through step (1) $Ω(\log m)$ times (unless removed in step 4).  In the beginning, if $A < B$ and we pick $A$, we compare $A$ against element $S[≈(1-1/\sqrt{2})|S|]$, and each application of step (3) to $A$ has $O(1)$ probability of reducing $|I_A|$ in $≈1/(1-1/\sqrt{2})$ times.  Now for every ratio $a>1$ that is not a rational power of 2, we have $∀ε>0 ∀d>0 ∃m,n∈\mathbb{N} \,\, 1-ε < \frac{a^m}{d2^n} < 1+ε$, and so we get the $o(n)$ bound.

A likely $\mathrm{lg}(n!)+O(n^{1-ε})$ algorithm

Modulo a randomization assumption, we can achieve $\mathrm{lg}(n!)+O(n^{1-ε})$ average comparisons as follows.

Randomly shuffle the items, and sort the first half into a list $S$, while keeping the second half as an unsorted batch.
Repeat until the batch is empty:
Randomly choose $A∈\text{batch}$.  Let $G = \{ B∈\text{batch}: |P(A < B) - 0.5| < n^{-0.51ε} \}$.  If $G$ is empty, remove $A$ from the batch and insert into $S$. Otherwise:

If there is $B∈G$ such that with probability $Θ(1)$ (say ≥0.05), $\mathrm{Compare}(A,B)$ makes $|I_A|$ within $n^{-ε}$ relative error of a power of 2, run $\mathrm{Compare}(A,B)$ and if successful (i.e. $|I_A|$ is within $n^{-ε}$ relative error of a power of 2), remove $A$ from the batch and insert into $S$.
If there is no such $B∈G$, run $\mathrm{Compare}(A,B)$ for a random $B∈G$.

If our randomization assumption works out (i.e. the distribution of interval lengths and positions is random enough), then throughout much of the process, a typical $A$ can be efficiently compared with a choice of $n^{Θ(1)}$ elements (with $n^{Θ(1)}$ different interval lengths). Thus, we can typically choose a comparison for (1) above, and if we are unlucky with the comparison result, we still get $Θ(\log n)$ chances, thus achieving (if $ε$ is small enough, say 0.01) a $\mathrm{lg}(n!)+O(n^{1-ε})$-comparison algorithm.  With some changes and approximations, the total compute can be made quasilinear:  Given an element $A$, compute promising interval lengths, and then look up $B$s with the right approximate center and interval lengths.

There are a number of ways to optimize comparisons, but the obstacle is that each comparison may end up being unlucky and we have a limited number of comparisons.  If after optimization, $\mathrm{Compare}(A,B)$ does an average of 4 comparisons and 'succeeds' with 1/4 probability, we get $ε≈(1-ε)/4/\log_{4/3} 2 ≈ 0.09$.

A perhaps much better approach is to wait until an interval is close to a power of 2, controlling not the individual interval lengths but the distributions of lengths.

An attempt at a $\mathrm{lg}(n!)+n^{0.5+o(1)}$ algorithm

Suppose that $|S|=n$ and we are given an unsorted batch of $n$ elements with the intervals $I_A$ also given, with $|I_A|$ typically $n^{1-o(1)}$ and with $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ distributed uniformly (up to a random error, and holding with sufficient precision even if conditioned on $A < S[i]$).  Then, we can sort the items wasting an average of $n^{0.5+o(1)}$ comparisons as follows:
(*) Insert all elements in the order of their initial $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$.  This way all elements are inserted when their interval length is close to a power of 2.

The sorting algorithm will be: Randomly shuffle the list and sort the first half $S$. To insert the second half, make the distribution right, and do the (*) above.

To make the $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ distribution right, we can make a 'random' distribution, and then withhold the right fraction of the elements for each $|I_A|/2^{\lfloor \mathrm{lg} |I_A| \rfloor}$ while randomizing the rest (repeating if necessary).  However, while this should correct $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ globally, we do not know whether it can be controlled locally with the required precision (hence the word "attempt" above).

To make a 'random' distribution, we can randomly use $\mathrm{Compare}(A,B)$ with $P(A < B)≈0.5$, except that with the initial $I_A$ all identical, we do not expect randomization at a sublogarithmic depth (i.e. with $I_A$ long enough).  However, I conjecture that we get randomization at a sublogarithmic depth using generalizations (probably any reasonable choice will work) of $\mathrm{Compare}$ to $k=ω(1)$ elements: If we keep $k=ω(1)$ elements entangled (i.e. connected using comparison results), we should have about $k$ noncommuting choices for each comparison with $S$.  This should allow $O(\log_k n + \log k)$ randomization depth, as desired (assuming that $k$ is not too large as we need depth $Θ(\log k)$ to distentangle the elements).  I expect that the compute can be made quasilinear if using a small enough $k$.

Since a comparison with $1/2+n^{-0.5}$ yes probability only wastes $O(1/n)$ entropy, the initial randomization and the slight nonuniformity of the elements in their bounding intervals should only need $n^{o(1)}$ entropy waste.  If the distribution shaping succeeds well enough, the entropy waste stems primarily from interval length mismatches during (*) (hence the $n^{0.5+o(1)}$).

A possible $\mathrm{lg}(n!)+O(n^{0.5-ε})$ combination:  If the distribution shaping works well enough and we make the batch size equal $|S|+n^{0.5+ε}$ and selectively reject $≈n^{0.5+ε}$ elements in (*) (above), we can insert all but these $≈n^{0.5+ε}$ elements with entropy waste $n^{0.5-ε/2+o(1)}$ as follows.  Split $S$ into $n^ε$ nearly equal intervals, and when during insertion, $I_A$ settles on an interval, reject (i.e. cancel the insertion) if the interval is too long, thus reducing the variation in the lengths of these intervals $Θ(n^{ε/2})$ times, which in turn reduces the length variations of random length $n^{1-o(1)}$ intervals in $n^{ε/2-o(1)}$ times, as needed.  Now, we can use the above $\mathrm{lg}(n!)+O(n^{1-ε})$ algorithm to insert the remaining elements with $O(n^{0.5-ε'})$ waste if $ε$ is small enough.

Worst-case complexity of sorting:  Most likely, there is a sorting algorithm with $\mathrm{lg}(n!)+o(n)$ worst-case comparisons.  For finding median, there is a linear gap between the average case ($1.5n+o(n)$ comparisons) and the worst case (at least $(2+ε)n-O(1)$ comparisons).  However, for sorting, there is plenty of freedom for arranging comparisons and for finding new sorting algorithms.


Have fixed parameter integer program algorithms ever been implemented for research use?

The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available.

Lovasz and Scarf proposed (in 1992) a generalized basis reduction algo that also solves IP in fixed dimensions, but avoids the ellipsoidal approximations required by Lenstra's algorithm. An implementation of this algo was reported in 1993 by Cook, Rutherford, Scarf, and Shallcross (this paper is available in ResearchGate).

One of the key steps in Lenstra's algorithm uses basis reduction (BR) to locate "thin directions" for the polytope. Branching on such a direction produces only a small (i.e., polynomial number) of subproblems. In a series of papers, Aardal and coauthors essentially applied this BR step to help solve (using standard MIP solvers) otherwise hard-to-solve IP instances (see, e.g., this paper and this paper). We (also see arXiv) have studied a similar, but arguably simpler and more general, approach (full disclosure: self-citation here!) to solve IP feasibility problems: apply BR to the constraint matrix $A$ of the IP feasibility problem (of the form $\{\mathbf{l} \leq A \mathbf{x} \leq \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}$), and use standard techniques to solve the resulting reformulated IP feasibility problem. The BR could be performed using standard software tools such as NTL.


Can a probabilistic Turing machine solve the halting problem?

edit: I just realized some of the things I wrote were total nonsense, sorry for that. Now I changed the proof and made the definition of probabilistic machine I am using more precise.

I don't know whether I get right your definition of probabilistic Turing machine: it is a machine with an additional tape on which an infinite incompressible string is written, and beside that it acts just like a deterministic machine? If we fix the incompressible string, the class we get doesn't seem to be interesting.

I think we can define a probabilistic Turing machine in several ways. I will use a definition that seems quite natural (and for which my proof works ;) Let's define a probabilistic machine like that: it gets an additional tape on which some infinite string is written, we say that this machine decides a language $L$ if for every $x \in L$ it halts and accepts with probability $>\frac{1}{2}$, when the probability is taken over those additional random strings, and for every $x \not \in L$ it halts and rejects with probability $>\frac{1}{2}$.

We will now show that if there exists such a probabilistic machine $P$ that solves the halting problem for the deterministic machines, we could use it to build a deterministic machine $H$ that solves the halting problem for the deterministic machines - and we know that such a machine cannot exist.

Assume such $P$ exists. We can construct a deterministic machine $M$ that takes as an input a probabilistic machine $R$ with some input $x$, which

halts and accepts if and only if $R$ accepts $x$ (i.e. $R$ halts and accepts $x$ on more than half random strings).
halts and rejects if and only if $R$ rejects $x$ (i.e. $R$ halts and rejects $x$ on more than half random strings).
loops otherwise

Basically, $M$ will for all $i \in 1, 2, ...$ simulate $R$ on input $x$ and on every string from ${{0,1}}^i$ as a prefix of the string on $R$'s random tape. Now:

if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and accepted without trying to read more than $i$ bits from the random tape, $M$ halts and accepts
if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and rejected without trying to read more than $i$ bits from the random tape, $M$ halts and rejects
otherwise $M$ runs the simulation with $i := i+1$.

We have to convince ourselves now, that if $R$ accepts (rejects) $x$ with probability $p >\frac{1}{2}$, then for some $i$ it will accept (reject) for $>\frac{1}{2}$ prefixes of length $i$ of the random string without trying to read more than $i$ bits from the random tape. It is technical, but quite easy - if we assume otherwise then the the probability of accepting (rejecting) approaches $p >\frac{1}{2}$ as $i$ goes to infinity, hence for some $i$ it will have to be $p >\frac{1}{2}$.

Now we just define our deterministic machine $H$ solving the halting problem (i.e. deciding whether a given deterministic machine $N$ accepts a given word $x$) a as $H(N,x) = M(P(N,x))$. Note that $M(P(N, x))$ always halts, because deciding a language by our probabilistic machines was defined in such a way that one of those two always occurs:

the machine halts and accepts for more than half random strings
the machine halts and rejects for more than half random strings.


I can give several answers to your question.

Algorithmic randomness. When should we call a sequence $x_1,\ldots,x_n$ of bits random? A priori, all sequences have the same probability, so it's not clear on what grounds we should single out one sequence or another as not being random. This is partly a philosophical question, but "applied philosophy" has given rise to several definitions of algorithmic randomness, detailed in the Wikipedia entry. These notions are actually for infinite sequences, but some of them can also be used for finite sequences, for example the notion of Kolmogorov-random sequence that you mention in your question. The trouble with these notions is that one cannot compute random sequences – that's a feature of the definitions.

Pseudorandomness. Complexity theorists and (theoretical) cryptographers prefer a more permissive notion of randomness. Suppose you need a random sequence to run algorithm A which belongs to complexity class C. A pseudorandom sequence is a sequence that "fools" algorithms of complexity class C – that is, it looks random to such algorithms. More formally, algorithms of class C cannot distinguish a small set of pseudorandom sequences from a truly random sequence. As joro mentions in their comment, for this definition to make sense, you need to look at a collection of pseudorandom sequences, since one sequence could always be distinguished from a random sequence (at least in non-uniform computation models).

There are no known pseudorandom sequences against complexity classes beyond some very weak ones, though there are constructions which work assuming some complexity assumptions. Such constructions are not necessarily useful for practical applications, for three reasons: (1) you are given a large set of sequences rather than one sequence, and you have to run your (decision) algorithm on all of them; (2) constructions in complexity theory tend to be impractical; the pseudorandom sequences are probably really hard to generate in practice, especially for realistic values of $n$ (the input size); (3) asymptotic analysis doesn't usually yield concrete bounds, so it would be hard for you to figure out what parameters to use; worse, if the security of the construction relies on some non-explicit complexity assumption (e.g. P$\neq$NP), the guarantee could be purely asymptotic, and not give any explicit bounds.

Practical randomness. Random numbers are used in practice in two kinds of situations: numerical simulations and cryptography. When using random numbers for numerical simulations, the "quality" of the numbers is not as important as the time it takes to generate them; in practice, even rather simple pseudorandom number generators seem to "work". A search of the relevant literature will reveal some modern examples. Some of the old pseudorandom number generators were indeed bad (in some situations), but the this threshold has been crossed, and from an engineering perspective the problem can be considered solved.

Random numbers used for cryptographic purposes need to be more secure, since now we're against somebody who's construction the algorithm for the express purpose of reverse engineering the random stream. In this case one needs to be a bit more careful and use a secure, industry standard stream cipher. Such ciphers are available, and I strongly urge against using anything else, especially anything which you designed yourself. For extra security, XOR the output of several stream ciphers using independent keys.


Heuristics for tsp without triangle inequality

I hope this partly answers your question: Most known heuristics like Greedy, Naerest Neighbor, Lin-Kerninhan etc.
perfrom quite well for (symmetric) TSP without triangle inequality.

You may check these heuristics with the Concorde TSP Solver
which is the best TSP solver I know so far.

In theory, there is no heuristic for TSP without triangle inequality that performs well
(like Christofides for metric TSP).
This is due to the well known fact that TSP cannot be approximated within any
polynomial time computable function unless P=NP.


Complexity class associated with exhaustive search

It's a little vague, but I like the question. I wrote a paper about it a LONG time ago.
Maybe this will help the Anonymous questioner:

Brute Force Search and Oracle-Based Computation

Here's a summary. Informally, if you do not keep any scratch work from previous trials, and just try all possible solutions in lexicographical order until a desired solution is found, then brute force corresponds precisely to $P^{NP}$. If you keep around even $3$ bits of scratch work from one possible solution to the next, then you can do $PSPACE$, via Barrington's theorem. There are other possibilities, such as what happens when you don't run in lex order but according to some other efficiently computable list of all strings.

[WARNING WARNING WARNING: It's likely that I disagree with almost all opinions stated in this paper. It was written about 10 years ago, by someone with the same name but who is essentially a different person.]


Synchronizing sequences for rubik's cube?

Synchronizing sequence over a finite state machine: a sequence of state transitions that leads the machine to a known unique final state independently of the (unknown) initial state.

In the Rubik's cube there are obviously no "self stopping" configurations: every move leads to a new configuration, so you are forced to look at the current configuration in order to decide the next move. This implies that a synchronizing sequence (as usually defined) cannot exist.

A trivial demonstration: suppose that $SSEQ = m_1 m_2 m_3 ... m_n$ is a synchronizing sequence of moves that leads to a solved Rubik's cube independently of the initial configuration. Now pick a wrong configuration and apply the reverse sequence $m^{-1}_n m_{n-1}^{-1} ... m_1^{-1}$ where $m_i^{-1}$ is the inverse of move $m_i$ (and is well defined because if you apply the same move to two different cube configurations you cannot obtain the same configuration). This reverse sequence leads to a unique configuration $c_0$. If you apply sequence $SSEQ$ to $c_0$ you obviously don't end to a solved Rubik's cube.

What you can do is to allow to stop every subsequence looking at the content of a particular cube's coordinate. For example run subsequence 1 until corner at (0,0,0) contains the red+yellow+blue block, then proceed to subsequence 2 (which will correctly position another block, and so on. In this case you can reach a known final configuration running a fixed sequence of moves made of subsequences that can stop looking at the content of a fixed sequence of blocks. This is very similar to what is usually called an homing sequence.

Perhaps another nice question is "What is the shortest sequence of moves and monitored coordinates that leads to a known final configuration in this modified homing version?".

For example to put a known block at monitored coordinate (0,0,0) (asterisk * in the figure), the length of the first trivial subsequence must be 28

F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate

EDIT:
Another interesting question (suggested by Tsuyoshi and Kaveh in the comments) arise if we consider the case in which the sequence of moves automatically stops when the cube is solved: if no information is gathered/stored during the moves then we must scan all cube's configurations (similar configurations obtained rotating the whole cube should be grouped in equivalence classes).

But what is the shortest sequence that scans all cube's configurations, or better does the configuration graph of the cube have a Hamiltonian path?.

This is a special case of a more general unsolved problem: for an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, I cite the book: Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys and the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.


The references I use (and like) are selected chapters in Schrijver's 3-volume Combinatorial Optimization: Polyhedra and Efficiency (Springer) and Vygen's Combinatorial Optimization (Springer). There is a book devoted to submodular functions by Fujishige: Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics, North-Holland (2nd edition from 2005).


What is the intuition behind "hardness of approximation"?

One important reason why problems that look equally hard to compute exactly might be very different to approximate relates to the fragility of NP-completeness reductions.

The simplest example I can think of the relation between VERTEX COVER and MAX INDEPENDENT SET. The two problems are complementary: given a graph $G = (V, E)$ with a vertex cover $S$, the set $V\setminus S$ is an independent set. This is why it's easy to show that one problem is NP-hard by reduction from the other.

But suppose I can get "close" to a good vertex cover, in that instead of finding the smallest cover $S$, I find a worse cover $S'$ where $|S'| = 2 |S|$. This means that instead of finding the maximum independent set of size $n - |S|$, I've found one of size $n - 2|S|$.

Suppose in this graph the max independent set size was $n/2$. Then essentially my approximation to the vertex cover found nothing at all.

In other words, the NP-hardness reduction only preserved the exact solution relationship, not the approximate solution relationship.

To preserve approximations, you need a different kind of reduction called an $L$-reduction, and once you limit yourself to such reductions, you realize that the two problems are indeed quite different.


Nonregular Languages in Sublogarithmic Space

Yes. I think the main reference is Turing Machines with Sublogarithmic Space by Szepietowski (1994). (Link to books.google)


PhD Development; Literature Review Tactics

I'm a younger researcher so I have no personal advice, but I have found this method by Michael Nielsen quite effective.

One unusual but very useful style was to set a goal like reading 15 papers in 3 hours. I use the term "reading" here in an unusual way. Of course, I don't mean understanding everything in the papers. Instead, I'd do something like this: for each paper, I had 12 minutes to read it. The goal was to produce a 3-point written LaTeX summary of the most important material I could extract: usually questions, open problems, results, new techniques, or connections I hadn't seen previously. When time was up, it was onto the next paper. A week later, I'd make a revision pass over the material, typically it would take an hour or so.
I found this a great way of rapidly getting an overview of a field, understanding what was important, what was not, what the interesting questions were, and so on. In particular, it really helped identify the most important papers, for a deeper read.
For deeper reads of important papers or sections of books I would take days, weeks or months. Giving lectures about the material and writing LaTeX lecture notes helped a lot.

In particular, I found his opinion on identifying useful material mirrored my own:

Most material isn't worth spending a lot of time on. It's better to spend an hour each seriously reviewing 10 quantum texts, and finding one that's good, and will repay hundreds of hours of study, than it is to spend 10 hours ploughing through the first quantum text that looks okay when you browse through it in the library. Understanding mathematics deeply takes a lot of time. That means effort spent in identifying high quality material is often repaid far more than with (say) a novel or lighter non-fiction.

The whole comment is definitely worth the read.
As far as managing your materials go, I have yet to find an application as useful as Papers. It hooks into your institution's library proxy and allows you to get at licensed content quickly without VPNing in to campus. It's also great for organizing papers by topic and searching over your library via author, title, conference, etc. Unfortunately it's Mac OS X specific. I'm curious if anyone has experience with alternatives on other operating systems.


Lookup complexity in augmented interval tree

Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.

Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$.
Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.

Illustrated example:

Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$).
All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored.
However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.

Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time.
Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time.
Because we prune a tree-walk we also have an upper bound of $O(n)$ time.
This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.


Is there a formalization of normalization of impredicative system F?

Coq without Prop is not strong enough, because it's basically Martin-Löf type theory with universes.
Coq with Prop is strong enough, because you can encode sets of normalizing terms via predicates $S : \mathrm{Term} \to \mathrm{Prop}$, and impredicative universal quantification lets you express arbitrary intersections.


Random grid point in a d-dimensional ball

Let $B$ be the ball you want to sample in. Let $B'$ be the ball centered at the same point, but larger in radius by $\sqrt{d}$. Sample a random point in $B'$ Round off to the nearest integer point. Now, if this integer point is in $B$, accept it. Otherwise, discard it and try again.

This works because every point of the original ball is contained in a unit cube in ball $B'$.

When will this be efficient? You want the ball of $r+ \sqrt{d}$ to be not too much larger than the ball of radius $r$. The ratio of these distances is

$$ \left(\frac{r+\sqrt{d}}{r}\right)^d = \left(1 + \frac{\sqrt{d}}{r}\right)^d \leq \exp\left({\frac{d^{3/2}}{r}}\right).$$

So it works well if $r > d^{3/2}$.

How do you find a random point in $B'$? Thomas's answer give an algorithm for this.

If $r < d^{3/2}$, use the Metropolis algorithm. Start with a point $P$ in the ball—the lattice point closest to the center is easiest. Now, repeatedly perform the following steps.

Choose a random coordinate.
Keeping the remaining coordinates fixed, compute the lowest and highest integer values for this coordinate that are still in the ball.
Pick a random value $v$ for this coordinate, and set this coordinate to $v$ in $P$.

This is guaranteed to converge, and there are theorems that will tell you how quickly it will converge ... I am fairly sure that this case is one that converges in polynomial time.


Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?

Although families of circuits aren't usually defined this way, you actually could require this for non-uniform families of circuits; i.e., require circuit families to be consistent. There still would be circuit families for non-uniform languages, and P/poly would still contain all the same languages with this definition (P/log would change, though). Then you could indeed leave out any finite number of circuits, and the function would still be well-defined.
You wouldn't cause any paradoxes.

One question you could ask is: are there any advantages to this alternate definition of P/log? My guess is that there are.


Counting the number of thick regions which overlap a square

I think that the maximum number of pairwise disjoint fat regions which overlap the square should be strongly related to circle packing.

The worst-case shape for a region is something like a "ball & chain". Below I have depicted such a region for $\beta=2$ with diameter 1

.

and these can pack within distance 1 of the unit square obviously much more tightly than I've depicted them.

Note that the actual ball & chain region is defined by the green area, and the outer circle is just a guide to depict the fact that these regions have fatness 2. In fact, the chain part of the region, can "bend" to allow more regions to be packed.


Is modal $\mu$-calculus "equivalent" to bisimulation?

For Q1, the answer is yes if we consider image-finite systems: for all node $t$ and label $a$, the number of $a$-successors of $t$ must be finite. In this case you don't even need fixpoints of the $\mu$-calculus, only the fragment called Hennessy-Milner Logic to distinguish non-bisimilar structures [HM85]. This is known as the Hennessy-Milner Theorem. Intuitively, the non-bisimilarity can be seen in a finite amount of steps of the form "there exists an $a$-successor", or "for all $a$-successor".
For more general cases, the paper [FCM17] might be of interest, in particular it gives at the end an example of two non image-finite structures (actually two nodes in the same structure) which are not bisimilar, but cannot be distinguished with  HML formulas. I suspect this is still true for $\mu$-calculus formulas, but to be verified.
As for Q2, I'm not sure there is a clear "maximal class". A class $\mathcal C$ with your conditions must at least satisfy the following requirements:

at most one element per bisimulation equivalence class
$\mathcal C$ is countable

But then you have some room, since starting from such a class you can always replace one element by another which is bisimilar to it.
It is not even true that $\mathcal C$ must only contain finitely describable elements, since you can always take $\mathcal C=\{T\}$, where $T$ is any structure, and complete it to a maximal class, and it would satisfy the requirements (although artificially). You probably have other conditions in mind for such a class, that would rule out the above example.
A natural such class is the set of regular ranked binary trees (where successors are ordered). Here "regular" means that the number of distincts subtrees is finite, even though the tree can be infinite.
[HM85] Matthew Hennessy & Robin Milner (1985): Algebraic laws for nondeterminism and concurrency. Journal of the ACM, doi:10.1145/2455.2460.
[FCM17] Ferlez, J., Cleaveland, R. and Marcus, S., 2017. Bisimulation and Hennessy-Milner Logic for Generalized Synchronization Trees. arXiv preprint arXiv:1709.00827.


Name: iterated reweighted least square

Goal: minimize function of the form $ \sum w(\theta)F(\theta)^2$, $\theta\in R^n$, $F(\theta) \in R^m$, $w(\theta)\in R$

Conditions:  depend on case

Algorithm: obvious - fix weights, solve quadratic problem, recalculate weights

Best known app: geometric median,  M-estimators,$L_p$ norm, compressed sensing

Theory:  proven on-case-to-case basis


The problem of minimizing the sum of distances from points to cluster centers is called the $k$-median problem. In a general metric space, the $k$-median can be approximated to within a factor of $3+\epsilon$ and is $\mathsf{MAX SNP}$-hard. In Euclidean space, the problem admits a PTAS. This is a good survey and has references for the above facts.


You can solve this in $O(n\log n)$ time using a variation of Dijkstra's algorithm. We can get away with not performing all distance updates when we visit a new node. If we visit a node $y$, we need only to update the distances of everything walkable from $y$ to 0, and to update the distances to the two nodes $y_-$ and $y_+$ with the closest values to $y$ less and greater than $y$ which have not been picked yet.

These updates are sufficient to keep the heap returning the minimum element because any closest node you jump to must have been numerically just above or just below an already visited node.

Each node gets updated to 0 at most once (if we pop out all zero distance nodes from the queue to avoid quadratic behavior), and each time we add a node, we only do O(1) other updates. Finding the values $y_-$ and $y_+$ can be done in linear time if we also keep an ordered doubly-linked list of all the nodes, sorted by their integer values. Building this doubly-linked list takes $O(n \log n)$ time, and finally the $O(n)$ updates to and pops from the heap take $O(n \log n)$ time, for a total runtime of $O(n \log n)$


Combinatorial characterization of exact learning with membership queries

To drive home the point of anonymous moose's example, consider the concept class that consists of functions that output 1 on only one point in {0,1}^n. The class is of size 2^n, and 2^n queries are needed in the worst-case. Take a look at worst-case Teaching Dimension (Goldman & Schapire) which provides something similar to what you're looking for.


Are variables in RHS of Chomsky Normal Form productions distinct?

Yes. The production rules of the form $A \rightarrow BB$ are allowed. One of the motivations behind CNF is to make the parse tree a binary tree so that we can have a unified way of talking about the relationship between the depth of the parse tree and the length of its yield. So having rules of the form $A \rightarrow BB$ does not disrupt this goal. However, replacing $A \rightarrow BB$ by $A \rightarrow B_1B_2$, $B_1 \rightarrow B$ and $B_2 \rightarrow B$ might create problems in analyzing the depth of parse tree especially when you have rules like $B \rightarrow XY$. This will create intermediate nodes in the parse tree with outdegree one, while the goal of CNF is to "push" such nodes to the leaves.


What happens if we try to extract a witness but it actually does not exist from a term of existential type?

Any value. It depends upon which $t$ you are given. A term of type $\exists y.(\neg(0 = 0) \Rightarrow 0 = S(y))$ is a pair of an int $y$ and a function that takes a proof of $\neg(0=0)$ and gives you a proof of $0 = S(y)$. You can use a term of type $\neg(0 = 0)$ and type $0 = 0$ (from reflexivity) to derive a term of any type you want. This includes a term of type $0 = S(0)$, $0 = S(1)$, $\ldots$. So, you can make $y$ any integer you want.


Kolmogorov complexity with weak description languages

Let's assume there exists some "decidable" complexity $D(s)$ differs from Kolmogorov complexity $K(s)$ by shift, by factor or, more generally, by any decidable monotonic unbounded numerical function $f(n)$ such that $K(s) > f(D(s))$.

As $D(s)$ is decidable, it is possible to choose (effectively) a sequence of strings $s_n$ such  that $f(D(s_n))> \mathrm{vff}(n)$ where $\mathrm{vff}$ is some "very very fast growing function" such as $\exp(\exp(\exp(n)))$.

Suppose that we have $K(s_n) > \mathrm{vff}(n)$, i.e. Kolmogorov complexity of string $s(n)$ grows fast with $n$. But index $n$ also identifies the string $s(n)$ and, therefore, may be treated as upper bound of $K(s_n)$ (with some const shift). Any number $n$ needs only $\log(n)$ bits to represent it, and this contradicts with fast growing of complexity of $K(s_n)$.

Thus for any decidable monotonic unbounded numerical function $f$, there exists strings $s$ such that $K(s) \not> f(D(s))$.


An intuitive justification - Metric Embedding Based Approximation Algorithms

The way I remember it is that you also get a lower bound on the expected cost in the embedding. Namely for any two points $x$, $y$ at distance $d(x,y)$ in the original metric, their distance $d'(x,y)$ in the embedding satisfies $d(x,y) \leq d'(x,y)$. If I'm not mistaken, the first lecture mentions that too.

Then, everything is straightforward.

Look at the optimal TSP instance $I$ of the graph $G$. Then consider the embedding of $I$ (call it $I'$) into the tree metric. $I'$ is also an instance of TSP for the tree metric, and its cost is bounded by $E[cost(I')] \leq \alpha \cdot cost(I)$.

Therefore, if you compute $J'$, which is the optimal TSP for the tree metric, $E[cost(J')] \leq E[cost(I')] \leq \alpha \cdot cost(I)$.

Lift $J'$ back into your initial graph, which gives you an instance $J$. Thus, $cost(J) \leq E[cost(J')]$. And thus, using the previous chain of inequalities,  $cost(J) \leq \alpha \cdot OPT$.


What is the smallest Turing machine where it is unknown if it halts or not?

The largest Turing machines for which the halting problem is decidable are:

$TM(2,3), TM(2,2), TM(3,2)$ (where $TM(k,l)$ is the set of Turing machines with $k$ states and $l$ symbols).

The decidability of $TM(2,4)$ and $TM(3,3)$ is on the boundary and it is difficult to settle because it depends on the Collatz conjecture which is an open problem.

See also my answer on cstheory about Collatz-like Turing machines and "Small Turing machines and generalized busy beaver competition" by P. Michel (2004) (in which it is conjectured that $TM(4,2)$ is also decidable).

Kaveh's comment and Mohammad's answer are correct, so for a formal definition of the standard/non-standard Turing machines used in this kind of results see Turlough Neary and Damien Woods works on small universal Turing machines, e.g. The complexity of small universal Turing machines: a survey (Rule 110 TMs are weakly universal).


Worst case ratio between minimum clique cover and maximum independent set

The Lovász $\vartheta$ function is an efficiently computable function with the property

$$
\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G),
$$
where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have an efficient approximation to $\alpha(G)$ within a factor of $n^{1-\varepsilon}$ . However, this is impossible, unless P=NP.

The above argument is conditional on the conjecture P $\neq$ NP. However, Feige showed that, unconditionally, there exists a constant $c$ and an infinite family of graphs for which

$$
\alpha(G) \leq \vartheta(G) < 2^{\sqrt{\log n}}\\
\bar{\chi}(G) > \frac{n}{2^{c\sqrt{\log n}}}
$$

So the gap between $\alpha(G)$ and $\bar{\chi}(G)$ is $n^{1 - o(1)}$, no need for conjectures.


Rank-robustness of the parallel complexity of linear algebra problems

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$.

If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination vanishes (say over $\mathbb{F}_2$). From all sets of maximal rank you select the lexicographically smallest.

Now given an $n \times n$-matrix of rank at most $\log n$, we can find a basis of its column span in $\mathrm{AC}_1$ as follows: Divide the columns into two halfves, compute a basis recursively. From these two bases we can compute a common basis using the algorithm from above.


Topological sort with alternative choices of predecessors

Yes, a valid ordering and a graph that goes with it can be found in polynomial time. I think it's easier to understand this if you look for the topological ordering first, and the graph second.

What you are trying to find is an ordering of the vertices with the property that, for each vertex $v$, at least one of its predecessor sets appears in its entirety before $v$. This can easily be found by a greedy algorithm if it exists:

Initialize an empty ordering and then, while the ordering does not include all of the vertices:

Find a vertex $v$ such that one of the predecessor sets of $v$ has already been included in the ordering
Add $v$ to the end of the ordering

If this succeeds, you have found your topological ordering, and you can choose the graph to be the one that connects each $v$ to its previously-appearing predecessor set. If it fails, then you have found a subset $S$ of vertices (the ones not yet added) so that every predecessor set of a vertex in $S$ contains another vertex in $S$, blocking any solution from existing.

Incidentally, the class of valid orderings for a problem of this type form an antimatroid, and all antimatroids can be represented in this way. This idea that you might have more than one way of satisfying the prerequisites for an object but that, once satisfied, a vertex can never become un-satisfied, is the defining principle of an antimatroid.