Minimize in polynomial time a super-additive increasing function under linear constraints?

The problem as presented is NP-hard.

Suppose we have $f(y)=0, y\leq 1$ and $f(y) = y, y > 1$. Now if we have the constraints $y_1 + y_2 \geq 2.01$ and $y_i \geq 0$, and we want to minimize $\sum_i f(y_i)$, clearly we should choose one of these $y_i$ to be $1$ and one to be $1.01$.

Now, suppose we have a graph $G$, and we put a constraint like this for every edge. Replace $2.01$ by $2 + \epsilon$ for a sufficiently small $\epsilon$. (You don't even need to do this, because vertex cover has an inapproximability result.) To minimize the objective function, we want to find the minimum number of vertices that hit every edge. This is the minimum vertex cover problem, and it is NP-complete.

The only reason that this isn't exactly your problem is that the matrix $A$ is not square, because the number of variables is the number of vertices in $G$, and the number of equations is the number of edges in $G$. But you can always add dummy vertices that don't participate in the equations to make $A$ square.

Possibly your real problem has more structure so that this NP-completeness proof doesn't apply. Maybe if you told us more about the real problem, it might be solvable in polynomial time.

For convex $f$, this should be solvable in polynomial time ... see Chandra's comment.


Find all nearby points in a set, for each element of the set

I think what you are looking for is the Fixed-radius near neighbors problem.


Checking if all products of a set of matrices eventually equal zero

Your question is equivalent to whether $A_1, \dotsc, A_k$ generate a nilpotent algebra, which in turn is equivalent to each of the $A_i$ being nilpotent. Hence not only is it decidable, but in $\tilde O(n^{2 \omega})$ time where $\omega$ is the exponent of matrix multiplication.

Let $\mathcal{A}$ be the associative algebra generated by the $A_i$: that is, take all linear combinations of the $A_i$ and all finite products thereof. $\mathcal{A}$ is called nilpotent if there is some $N$ such that every product of $N$ elements of $\mathcal{A}$ is zero.

First, let's see why your condition implies that $\mathcal{A}$ is nilpotent. This follows from Konig's Lemma (compactness): every string of length $n$ over the alphabet $\{1, \dotsc, k\}$ corresponds to a product of $A_1, \dotsc, A_k$ of length $n$ in an obvious manner. Consider the infinite $k$-ary rooted tree, whose nodes are naturally in bijective correspondence with strings over $\{1, \dotsc, k\}$. Consider the sub-tree $T$ consisting of those nodes where the corresponding product of the $A_i$ is nonzero. Konig's Lemma says that if $T$ is infinite, then it has an infinite path (exactly violating your property), hence $T$ is finite. We can then take $N$ to be the maximum length of any string in $T$. So your property implies that $\mathcal{A}$ is nilpotent.

The converse is also true, since every element of $\mathcal{A}$ is a linear combination of products of the $A_i$.

Next, note that $\mathcal{A}$ is a subalgebra of $n \times n$ matrices, and hence is finite-dimensional.

Finally: a finite-dimensional associative algebra in characteristic zero has a basis of nilpotent elements (commuting or not - this is the part that contradicts Yuval's answer) iff it is nilpotent (see, e.g., here).

Thus, to solve your problem, find a basis for the associative algebra generated by the $A_i$ (by the linear-algebra version of breadth-first search) and check that every matrix in the basis is nilpotent. The upper bound $\tilde O(n^{2\omega})$ comes from solving a system of linear equations in $n^2$ variables in the breadth-first search. As $\dim \mathcal{A} \leq n^2$ the BFS can't last very long, and because these are $n \times n$ matrices to check if a matrix $A$ is nilpotent one needs only check that $A^n = 0$.


Upper bound for number of independent sets

The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.


"A mathematical theory of communication" by Claude Shannon, classics of information theory. Very readable.

(Mirror)


Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

The disjoint paths problem: given $G$ and $k$ pairs of nodes, are there node disjoint paths connecting the given pairs. Parameterized by $k$, in FPT when $G$ is undirected from the seminal work of Robertson and Seymour. NP-Hard for $k=2$ when $G$ is directed - from work of Fortune, Hopcroft and Wylie (1980).


Drunken birds vs drunken ants: random walks between two and three dimensions

Probability on Trees and Networks by Peres and Lyons mentions this in Chapter 2 (page 50):

  One way to make sense of this is to ask about the type of spaces intermediate between $\mathbb{Z}^2$ and $\mathbb{Z}^3$. For example, consider the wedge

  $$ W_f := \{ (x, y, z) : |z| \leq f(|x|) \} $$

  where $f : \mathbb{N} \rightarrow \mathbb{N}$ is an increasing function. The number of edges that leave $W_f \cap \{(x, y, z) : |x| \text{ or } |y| \leq n\}$ is of the order $n(f(n)+1)$, so that according to the Nash-Williams Criterion,

  $$\sum_{n \geq 1}\frac{1}{n(f(n)+1)} = \infty$$

  is sufficient for recurrence.


On the relation for the Myhill-Nerode theorem/syntactic monoid of a language

The syntactic monoid of a language $L$, which is $\Sigma^{\ast}$ quotiented by $\sim_{L}$, is usually bigger than the set of equivalence classes of $\Sigma^{\ast}$ quotiented by $\equiv_{L}$. Informally, the Myhill-Nerode relation $\equiv_L$ only cares about the prefixes of a word $w$ (since it reflects the processing of $w$ by a DFA), while the syntactic monoid has to encode the information about all possible infixes of $w$ (otherwise you won't get the algebraic structure $[x]\cdot[y]=[x \cdot y]$)


Here is a counterexample:
$$
(a \lor y \lor s) \land (\overline{y} \lor b \lor z) \land (\overline{z} \lor c \lor d) \land (\overline{s} \lor b \lor t) \land (\overline{t} \lor c \lor d).
$$
This formula implies $a \lor b \lor c \lor d$, but only the five listed 3-clauses, no two of which resolve to $a\lor b\lor c\lor d$.


Scott Aaronson's newspiece: Polynomial
hierarchy collapses: thousands feared tractable


Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

By adding a small ($O(k)$) sized graph to each vertex you could reduce $VC$ of size $m$ in a 3-regular graph $G$ to $VC$ of size $m+2k|V|$ in a $k-regular$ graph.

Here is a reduction for 5-regular graphs, and I believe you can easily generalize it for every $(2k+1)$-regular graphs, for every integer $k$, and perhaps some trickery would allow similar construction for $2k$-regular graphs;

Consider the graph $H$ in the photo:

(all vertices has degree 5, except for the blue vertex).

For every vertex $v$ in the 3-regular graph $G$, create two copies of $H$ and connect $v$ to their blue vertices.

It is easy to see that regardless of whether $v$ was selected for the cover, you have to include at least $5$ vertices from $H_v$ in the cover (you can take the blue and green ones).

Hence every vertex cover of size $m$ in $G$ corresponds to a $m+10|V|$ sized cover in the new 5-regular graph, and vice versa.

EDIT:

Similar trick could be applied to get $2k$-regular graphs as well. Consider for example the following reduction from 3-regular to 4-regular graphs;

Partition the graph vertices into pairs (duplicate the graph if the number of vertices is odd), and for every pair $u,v$ connect each to a blue vertex in the following structure:

For example, if your initial cubic graph is:

Then the resulting $4$-regular graph is:

And the 5-regular graph would be:


How exactly does lambda calculus capture the intuitive notion of computability?

You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it is not intuitive, or that it does not sufficiently explain what is going on. In contrast, he found Turing's analysis of computability and the ensuing notion of machine totally convincing. So, don't worry.

On the other hand, to get some idea on how a model of computability works, it's best to write some programs in it. But you do not have to do it in pure $\lambda$-calculus, although it's fun (in the same sort of way that firewalking is). You can use a modern descendant of $\lambda$-calculus, such as Haskell.


Data structure for updates on intervals and querying number of zeros

Use a segment tree — a recursive partition of the range $[1,n]$ into smaller ranges. Each interval $[a,b]$ of your update operations can be partitioned into $O(\log n)$ of the ranges in this recursive partition. For each range $[x,y]$ store:

The number $c(x,y)$ of intervals $[a,b]$ that have been increased and not decreased such that $[x,y]$ is one of the ranges into which $[a,b]$ is partitioned
The number $u(x,y)$ of cells that are not covered by partitioned subsets of intervals that are at $[x,y]$ or lower in the recursion

Then if $[x,y]$ is recursively split into $[x,z]$ and $[z+1,w]$ we have
$$u(x,y)=\begin{cases}
0&\text{if }c(x,y)>0\\
u(x,z)+u(z+1,y)&\text{otherwise}
\end{cases}$$
so we can update each $u(x,y)$ value in constant time when the other data for a range changes. Each support query can be answered by looking at $u(1,n)$.

To perform an increase$(a,b)$ operation, partition $[a,b]$ into $O(\log n)$ ranges, increment $c(x,y)$ for each of these ranges, and use the formula above to recalculate $u(x,y)$ for each of these ranges and each of their ancestors. The decrease operation is the same with a decrement instead of an increment.


2DFA that requires many states in equivalent DFA?

The tight bound is $ n(n^n -(n-1)^n) $, which was given in Removing Bidirectionality from Nondeterministic Finite Automata by Christos Kapoutsis (2005).

I am also putting a figure from this paper giving a clear picture:

To get more, I think this paper is a good starting point. To check the related recent developments, I can also recommend to check the papers listed here: dblp: Christos A. Kapoutsis.


Distinguishability a set of permutations

Here are loose lower and upper bounds.

Fix $d \le n$ as in the post.  Let $k^*$ denote the largest possible value of $k$ meeting the conditions in the post.  We show that $k^* = \exp(\Theta(d\log d)$) for $d\ge 3\sqrt n$, but $k^* \le 2$ for $d\le n^{1/3}$.  I suspect the latter bound can be strengthened (e.g. shown for larger $d$).

Lemma 1. $d!/{n\choose d} \le k^* \le d!$

Proof. The upper bound $k^*\le d!$ holds simply because each chosen permutation induces a distinct permutation on the $d$-subset $\{1,\ldots,d\}$.  For the lower bound, say that two permutations of $[n]$ conflict if, for some $d$-subset $T$ of $[n]$, they induce the same relative order on $T$.  A given permutation $\sigma$ induces a relative order on $n\choose d$ such $d$-subsets.  Each $d$-subset $T$ and relative order on $T$ is induced by $n!/d!$ permutations of $[n]$.  It follows that any given permutation $\sigma$ conflicts with at most $c = {n\choose d} \times n!/d!$ other permutations.  So, any maximal set of pairwise non-conflicting permutations must have size at least $n! / c = d!/{n\choose d}$.  $\diamond$

Corollary 1. If $d\ge 3\sqrt n$, then $k^* = \exp(\Theta(d\log d))$.

Proof. By Lemma 1 and calculation from Stirling's approximation,
$$k^* \ge d!/{n\choose d} = \frac{d^{2d+1}\exp(d^2/2n - 2d+O(1))}{n^d} = \exp(\Omega(d\log d))$$ for $d\ge 3\sqrt n$.
For the upper bound, note $k^*\le d!= \exp(O(d\log d))$.  $~~~~\diamond$

Lemma 2. If $2\le d\le n^{1/3}$, then $k^* = 2$.

We give two proofs.

Proof 1.
Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.
To finish we show $k^*\le 2$.

Fix any three permutations $\sigma_1, \sigma_2, \sigma_3$. Assume WLOG that $\sigma_1$ is the identity permutation: $\sigma_1(k) = k$ for $k\in [n]$. We show that some $d$-subset of $[n]$ is not distinguishable by some pair of the three permutations.

If $\sigma_2$ has an increasing subsequence of length $d$, then that subsequence induces the same permutation on its $d$-subset $T$ that $\sigma_1$ does, so $T$ is indistinguishable by $\sigma_1$ and $\sigma_2$, and we are done.

Otherwise, by the Erdős–Szekeres Theorem, $\sigma_2$ has a decreasing subsequence of length $n/d \ge d^2$ on some subset, say $T'$, of $[n]$. On $T'$, $\sigma_1$ is increasing and $\sigma_2$ is decreasing.

Applying the theorem to $\sigma_3$ restricted to $T'$, $\sigma_3$ has either an increasing subsequence of length $\sqrt{d^2} = d$ on some $d$-subset $T''$ within $T'$, or a decreasing subsequence of that length on some $d$-subset $T''$ within $T'$.  In the first case, $\sigma_1$ and $\sigma_3$ don't distinguish $T''$.  In the second case, $\sigma_2$ and $\sigma_3$ don't distinguish $T''$.$~~\diamond$

Here's an alternate proof of Lemma 2, by adapting the proof of the Erdős–Szekeres Theorem, for those who are interested in the details.

Proof 2. Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.  To finish we show $k^*\le 2$.

Fix any three permutations $\sigma_1, \sigma_2, \sigma_3$. Assume WLOG that $\sigma_1$ is the identity permutation: $\sigma_1(k) = k$ for $k\in [n]$. Assume for contradiction that every $d$-subset $T$ of $[n]$ is distinguishable by each pair of these three permutations.

For each pair $i, j$ with $1\le i < j \le 3$, define $I_{ij}(k)$ to be the maximum size of any subset $T\subseteq [k]$ that contains $k$ such that the order imposed on $T$ by both $\sigma_i$ and $\sigma_j$ is monotonically increasing.  Define $D_{ij}(k)$ to be the maximum size of any subset $T\subseteq \{1,\ldots,k\}$ that contains $k$ such that the order imposed on $T$ by both $\sigma_i$ and $\sigma_j$ is monotonically decreasing.  Define 3-tuple
$$s(k) = \big(I_{12}(k),\,I_{13}(k),\,D_{23}(k)\big),$$
 and $S = \{s(k) : k\in[n]\}.$

Claim 1. For every $k,\ell$ with $1\le k<\ell \le n$, we have $s(k) \ne s(\ell)$.

Before we prove the claim, note that it implies the lemma as follows. The claim implies that $|S| = n$. Each of the three values in any 3-tuple $s(k)$ is in $[d-1]$ (because, for example, there is a subset of $[n]$ of size $I_{12}(k)$ that is not distinguishable by $\sigma_1$ and $\sigma_2$). So $S\subseteq [d-1]^3$, so $n = |S|\le(d-1)^3$, implying that $d>n^{1/3}$, contradicting that $d\le n^{1/3}$ and proving the lemma.

To prove the claim, consider any $k,\ell\in[n]$ with $k<\ell$. Consider the relative order that each of the three permutations induces on the pair $k, \ell$: for each $i\in[3]$, either $\sigma_i(k) < \sigma_i(\ell)$ or $\sigma_i(k) > \sigma_i(\ell)$.  Since $\sigma_1$ is the identity, $\sigma_1(k) < \sigma_1(\ell)$.

First consider the case that $\sigma_2(k) < \sigma_2(\ell)$. By definition of $I_{12}$, there is a subset $T$ of $[k]$ that contains $k$ such that $|T| = I_{12}(k)$ and $\sigma_1$ and $\sigma_2$ are monotonically increasing on $T$.  So $T' = T\cup\{\ell\}$ is a subset of $[\ell]$ that contains $\ell$ such that $|T'| = I_{12}(k)+1$ and $\sigma_1$ and $\sigma_2$ are monotonically increasing on $T'$.  It follows that $I_{12}(\ell) \ge |T'| > I_{12}(k)$.  It follows that $s(\ell) \ne s(k)$ in this case.

For the case when $\sigma_3(k) < \sigma_3(\ell)$, by the same argument $I_{13}(\ell) > I_{13}(k)$, so $s(\ell)\ne s(k)$ in that case.
In the remaining case, $\sigma_2(\ell) < \sigma_2(k)$ and $\sigma_3(\ell) < \sigma_3(k)$.  By a similar argument $D_{23}(\ell) > D_{23}(k)$.  So $s(\ell)\ne s(k)$ in all cases, proving the claim.  $\diamond$

EDIT: Comment on the tightness of the proof of Lemma 2. The proof of Lemma 2 shows the existence of a $d$-subset $T$ which is indistinguishable by two of the permutations and that has the following stronger property: the two permutations are both increasing or both decreasing over $T$.  Given this, I believe the bound of $\Theta(n^{1/3})$ on $d$ is best possible.  That is, I believe that for, say, $d\ge 2n^{1/3}$, choosing appropriate random permutations w.h.p. yields $\exp(\Theta(d\log d))$ permutations such that, for every pair $\sigma$ and $\sigma^*$ of the permutations, there is no $d$-subset $T$ on which $\sigma$ and $\sigma^*$ are both increasing, or both decreasing.  (The argument is similar to the proof of Lemma 1 above, with the additional observation that, for a random permutation, w.h.p. there are only about ${n\choose d}/d!$ $d$-subsets on which the permutation is increasing or decreasing.)

So, to strengthen the lemma, the proof would have to somehow consider indistinguishable subsets on which the two permutations are not monotonic.


It seems to me that triangles can be done by a 2FA $A$ with $O(n^2)$ state (n being the number of vertices).

For $k=3$ the idea is as follows:

In phase 1, $A$ chooses some edge $(i,j)$ and stores $(phase 1,i,j)$ in its state
In phase 2 it moves to some edge of the form $(i,m)$ or $(m,i)$ and assumes a state of the form $(phase 2,j,m)$
In phase 3, it checks that there is some edge $(j,m)$ or $(m,j)$ and assume an accepting state if it finds one.

This can actually almost be done in a left to right fashion (then $A$ might nondeterministically decide to go first for $(j,m)$ or $(m,j)$ in phase 2). However, if the 2nd edge comes in the form $(m,i)$, $A$ needs to first read $i$ and then $m$, i.e., a single left-step is needed here.

This should result in automata with $O(n^{k-1})$ states for $k$-Clique for $k>3$ by first guessing a set $S$ of size $k-3$ and testing, that he nodes of $S$ are pairwise connected by edges and, for each of  i,j,m in the above, checking that they have edges to all nodes in $S$.


SAT variant with almost disjoint clauses

I don't know the Multicolored Clique Problem suggested by Daniello, however there is a simple reduction from 3SAT:

Given a 3SAT formula $\varphi$ over $n$ variables $x_1,...,x_n$; for each $x_i$ add two variables:

$y_{i}^T$ that represents $x_i = true$, and
$y_{i}^F$ that represents $x_i = false$

and add the clause $(\neg y_{i}^T \lor \neg y_{i}^F)$ that represents the condition that $x_i$ cannot be both true and false.

Finally replace every clause   $C_j = (l_{j1} \lor l_{j2} \lor l_{j3})$ of $\varphi$ with a clause made of three positive literals $(y_{j1}^a \lor y_{j2}^b \lor y_{j3}^c)$ where:

$a = T$ if $l_{j1}= x_{j1}$, $b=F$ if $l_{j1} = \neg x_{j1}$
$b = T$ if $l_{j2}= x_{j2}$, $b=F$ if $l_{j2} = \neg x_{j2}$
$c = T$ if $l_{j3}= x_{j3}$, $b=F$ if $l_{j3} = \neg x_{j3}$

For example $(x_1 \lor \neg x_2 \lor \neg x_3)$ becomes: $(y_1^T \lor y_2^F \lor y_3^F)$

Update:

In order to make every positive literal $y_i$ (that can be $y_i^T$ or $y_i^F$) occur only once in the upper part, you can use the following technique:

Suppose that $y_i$ occurs twice, then you can simply replace the two occurrences with two new positive variables: $y_i'$ and $y_i''$ and add the conditions for: $y_i' \leftrightarrow y_i''$:

$$(\neg y_i' \lor y_i'') \land (\neg y_i'' \lor y_i')$$

At this point repeat the split procedure ($y_i'$ becomes $y_i^{T'}$ and $\neg y_i'$ becomes $y_i^{F'}$):

$$(\neg y_i^{T'} \lor \neg y_i^{F''}) \land (\neg y_i^{T''} \lor \neg y_i^{F'}) \land (y_i^{T'} \lor y_i^{F'}) \land (y_i^{T''} \lor y_i^{F''}) $$

and add a dum clause to the upper part in order to include the $y_i^{F'}$ and  $y_i^{F''}$, for example: $(y_i^{F'} \lor y_i^{F''} \lor z_i)$, where $z_i$ is a new variable that can make the clause true.

If $y_i$ occurs more than twice the procedure is similar.


Fast algorithm for weighted bipartite matching problem

You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf but more optimizations are possible).

These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so are often efficient in practice, and are amenable to parallelization. (And they can be used as a basis for recovering the best known worst case running times, see: http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/


Hyperplanes not intersecting points on a cube

No. Let the normal vector be $(a_1,\ldots, a_n)$. If these numbers are $poly(n)$ small integers, then there is an $I$ and $J$ such that $\sum_{i\in I} a_i=\sum_{j\in J} a_j$ by the pigeon hole principle. But then we have $\sum_{i=1}^n \varepsilon_i a_i=0$ for some $\varepsilon \in \{-1,0,1\}^n$.


Are the `ArrowApply` and `Monad` typeclasses equivalent?

The problem with your counterexample is that the type you presented is not a valid instance of ArrowApply as far as I can tell.

You didn't present what the implementation of app but the only one I could come up with (where you use the input stream function once and then discard it) doesn't satisfy the 2nd and 3rd ArrowApply laws.

What definition of app did you have in mind?


What can I say about the Parikh map of a CSL?

Regarding the second part of your question: If you choose your CFL $L$ to be the set of all invalid computations of a Turing machine $M$ (see, e.g., Chapter 8.6 in the first edition of "Introduction to Automata Theory, Languages, and Computation"), $\phi(\overline{L})$ is the set of all lengths of encodings of accepting computations of $M$.

Although this does not directly answer your question, you can use this approach to construct quite complicated sets.


Complexity of simple undirected graph isomorphism problem

Yes, the best known algorithm is still the algorithm from Babai and Luks, with runtime $\exp(O(\sqrt{n \log n}))$, where $n$ is the number of vertices in the graphs. Unless I'm mistaken, even the best known conondeterministic algorithm for graph isomorphism has exponential runtime. Babai and Luks' algorithm is plausibly near-optimal for deterministic algorithms, but there is much evidence that there is a polynomial time conondeterministic algorithm for graph isomorphism out there to be discovered. In particular, it is known that graph isomorphism is in coAM, and certain circuit lower bounds imply that coAM = coNP.


Bootstrapping results that really bootstrap

A classic result provable by bootstrapping (and applicable to proving real lower bounds) is that in any computational model where we have $TIME(n) \neq TIME(n^c)$ for some constant $c > 1$, we in fact have  $TIME(n) \neq TIME(n^{1+\epsilon})$, for every $\epsilon > 0$.

The idea is that if $TIME(n) = TIME(n^{1+\epsilon})$, we can apply a  padding argument repeatedly to obtain $TIME(n) = TIME(n^c)$ for every constant $c$. You can even use such an argument to slightly improve known time hierarchy theorems in various cases.


Complexity of the recovery of an adjacency matrix from its square

It is known that squares of bipartite graphs can be recognized in polynomial time ( See this). In general, there is a characterization of the complexity of this problem based on the girth of the underlying graph.

Recently there was a optimization variant studied, which gives FPT algorithms for the problem when you want to test whether a graph has a square root with at most (respectively at least) $s$ edges for some given integer $s$.


Regular languages under change of encoding

The answer is no.
I'll give an example of a language $L$ which is regular in binary but not in unary:

Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.

It's easy to see that $L$ is regular while $L'$ is not even context free.

L'' also isn't regular either, by the link @Sylvain posted in his comment.


Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?

I used the this scholar search, and the only result which seems somehow relevant is this:

Lance Fortnow, Adam Klivans, Linear Advice for Randomized Logarithmic Space, ECCC TR05-042, 2005.

Unfortunately, I think it is not exactly what you need. In particular, the main result of the paper is $\mathbf{RL} \subseteq \mathbf{L}/O(n)$. Yet I believe the techniques used there might be helpful in the case of your question.


Algorithms for Interval Coloring with Capacities and Demands

If the demands satisfy the no-bottleneck assumption, that is $\max_i d_i \leq \min_e c(e)$ then a constant factor approximation is known even for trees. See http://dl.acm.org/citation.cfm?id=1273343 which gives a 48-approx for trees. For paths a better bound can be obtained and may have been shown but I am not sure where or whether it was published. For the general case it is not quite clear what the best known result is. One can get an easy $O(\log n)$-approximation as follows. Consider the problem of maximizing the number of requests that can be feasibly routed; there is a constant factor approximation for this problem, see http://arxiv.org/abs/1102.3643. Using this as a black box one can do a greedy set-cover like algorithm to repeatedly pack as many requests as possible to get the desired $O(\log n)$-approximation. A paper by Chalermsook on coloring rectangles may have some implications including giving an $O(\log \log n)$-approximation; the paper is available at http://sites.google.com/site/chalermsook/academic/coloring_full.pdf?attredirects=0. However it may require figuring out several technical details. One suspects that there is a constant factor approximation for the coloring problem.


Hidden Constants in Complexity of Algorithms

One place where this is approached in an interesting way for a certain class of algorithms and combinatorial problems is in analytic combinatorics. The main approach described is similar to what you suggest: you start with some concrete implementation of an algorithm and identify some repeated operation (typically the heaviest one) that you'll use to associate an explicitly countable complexity for the execution of input of a given size $N$ in the form of the number $C_N$ that the chosen operation is performed.

The methodology does not require to fix any specific model of computation, although that could be useful of course. Also note that you could either try to compute the worst case behavior or the expected behavior, or still something else.

The most important ingredient in this methodology is the analysis of the generating functions of these values. You can sometimes obtain very precise asymptotic approximations using methods from complex analysis.

A simple example that is treated in the book is quicksort. This has a quadratic worst case running time, but in practice outperforms most $\mathcal O(n\log n)$ algorithms. When making a precise analysis of the expected cost of quicksort and you compare it to mergesort, you see that it is expected to outperform the latter from a size of around 10, if I remember correctly. To be able to compute this kind of things you cannot disregard the hidden constants of course.

In fact, in quicksort you sort a list by recursively sorting sublists, so that you would get an improvement for all sizes if you use mergesort on lists smaller than size 10. An interesting note in the book mentions that in some open sourced Microsoft library, the generic sort algorithm is implemented as quicksort until you get down to a size of 10, after which mergesort is used. In the code comments it is mentioned that performance tests showed this value to be optimal.


What's the expressive/compressive power of strongly normalizing subset of untyped lambda calculus?

The maximal blowup in termsize of simply typed lambda calculus is non-elementary (2 ↑↑ O(n) see e.g. [1] page 72). This is not exactly what you are asking for, but since typed lambda calculus is a strongly normalizing subset of untyped lambda calculus, it should give you some lower bounds.

I am not sure if the general question can be answered. Untyped lambda calculus is Turing-complete, the strongly normalizing fragment is then equivalent to the set of terminating programs. Since membership in this set is already undecidable, I would not expect that an upper bound on the size of normal forms can be shown.

[1] Morten Heine Sørensen and Pawel Urzyczyn. Lectures on the Curry-Howard Isomorphism, volume 149 of Studies in Logic and the Foundations of Mathematics. Elsevier Science Inc., New York, NY, USA, 2006.


Do natural generalizations of P versus NP exist?

John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark.  All I was saying was that we do know various separations between complexity classes, like P≠EXP, MAEXP⊄P/poly, NEXP⊄ACC, etc.  So, if you believe that a particular separation, like P≠NP, is "too deep to be either proved or disproved in ZF set theory" (or whatever), then it seems to me that the burden falls on you to explain why you think that separation has to be independent of ZF, while other separations turned out not to be.  For this argument to have force, I see no necessity for the other separations to have the particular form you specified.

But to address your question anyway: well, the obvious challenge in answering is to find any complexity class A for which we can prove that A is strictly contained in NA, where NA is "the natural non-deterministic extension of A"!  (Indeed, as Robin points out above, finding such an A is equivalent to answering your question as you've stated it.)  And the only examples of such A's that I can think of are things like TIME(f(n)) (it was proved in the 1970s that TIME(f(n))≠NTIME(f(n)) for f(n)≤n log*n, since NTIME(f(n)) can simulate time slightly greater than f(n)).  (An earlier version of this post claimed that was known for all f(n).  Thanks to Ryan Williams for the correction!)  So setting A=TIME(n) and B=NTIME(n) would indeed answer your question in the affirmative.  A more "natural" example will probably need to await a breakthrough in complexity theory.

[Endnote: I wish to clarify that I didn't give things portentous names like "The Shtetl Optimized this or that"---those were Sidles's elaborations!]


Complexity of union (computational geometry)

The complexity of a union of objects is the number of pieces in the boundary of the union. In the plane "complexity of boundary" is equivalent (upto a constant factor) to "number of vertices". But in general the boundary complexity is the sum of complexities of all objects needed to describe the boundary (vertices, edges, faces, and so on). It's just that in the plane the number of vertices in the boundary is the same as the number of edges (because the boundary is a set of cycles in this case)


Quantum capacity for ensemble of Pauli channels

For your question (1), the answer is yes. The 'hashing construction' for quantum encoding is independent of the quantum channel you use, so if you use this construction for encoding, you can send information over an ensemble of Pauli channels at the right rate. (Actually, this is slightly incorrect ... you do need that the input state you use in the formula for coherent information is the same for all the channels, but in the construction discussed by Preskill it is.)

The original paper Shor and Smolin does not mention an ensemble of channels. If you take a depolarizing channel near the quantum-capacity threshold you can achieve a larger quantum capacity by considering a new superchannel where one signal of the superchannel is five consecutive uses of the original channel. When you apply the 'hashing bound' to this superchannel (acting on a 32-dimensional quantum space rather than a 2-dimensional one), you find that the formula for quantum capacity is larger than five times the formula for the original channel. There is only one channel being considered here: the superchannel composed of five uses of the original channel, and not an ensemble of channels. The ensemble of channels comes in when Preskill gives the intuition for what is happening in Shor-Smolin.

(And of course you should replace five in the above paragraph with the appropriate value of $m$, which is only five for some of these constructions.)


Suggestions on a matching/scheduling algorithm.

While the entire problem seems under-defined, I believe it's fairly clear that you're dealing with a Multi-Objective Optimization problem, with scheduling simply being the backdrop for this problem.  Most new effort in this field seems to be concentrated on Evolution Algorithms as solutions to these problems.

I personally do quite a bit of work with Particle Swarms in this area mostly because they provide very simple method of visualization in a complicated space.  Other algorithms would include Non-dominated Sorting Genetic Algorithm-II (NSGA-II), or Multiple-objective Bayesian Optimization Algorithm (mBOA).

I would agree with Tsuyoshi in that you may want to spend more time on the problem definition as well.


What is a canonical term of $\text{Id}_A(x,y)$ if $x$ is not jugdmentally identical to $y$?

Yes, in general $\mathrm{Id}_{A}(x, y)$ will not have a canonical form. Consider the case when $x$ and $y$ are distinct free variables -- obviously you can postulate that $x$ and $y$ are equal, but you can't provide a proof of it.
Even more simply, consider the empty type $0$. It has no canonical forms at all, but there's nothing stopping you from assuming that a variable has type $0$.

For standard type theory, it is provably the case that if you have a closed term $t$ of type $\mathrm{Id}_{A}(x, y)$, then $x$ and $y$ are definitionally equal.
Since the language is normalizing and $t$ is well-typed in the empty context, then we know that $t$ will evaluate to $\mathrm{refl}(z)$ for some $z$, and then by inversion we will be able to establish that  $z \equiv x \equiv y$ judgementally.


Take a path property that is not first-order expressible, e.g.
$$\nu x.p\wedge\Diamond\Diamond x$$
which says that there exists a path where the atomic proposition $p$ holds at every even position, and any valuation can be used on odd positions.


Yes, this variant, and in fact a further generalization has been considered in the literature. See the paper below for the problem they call capacitated facility location.

J. Bar-Ilan, G. Kortsarz and D. Peleg,
Generalized submodular cover problems and applications,
Theoretical Computer Science, 250:179-200, 2001.


Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$.

It is indeed hard to find a modern readable PSPACE-hardness proof for regular expression universality, as it is now considered folklore. Here is a quick proof scheme that allows you to rebuild the proof:

Consider a Turing Machine $M$ on alphabet $\Sigma$ using polynomial space $p(n)$, and let $w\in\Sigma^*$ be an input word for $M$. We will build a  regular expression $e$ that accepts all words if and only if $M$ has no accepting run on $w$.

Consider the language $L_M$ consisting of words of the form $\$C_0\$ C_1\$\dots\$ C_f\$$, where each $C_i$ is a configuration of $M$ of length exactly $p(n)$, $C_0$ is the initial configuration with $w$ on the tape, $C_f$ is accepting, and each $C_i\to C_{i+1}$ is a valid transition of $M$. A word in $L_M$ describes an accepting run of $M$.

We build $e$ on alphabet $\Sigma'=\Sigma\cup\{\$\}$ such that $e$ accepts exactly words that are not in $L_M$, by looking for a violation of the definition of $L_M$. The expression $e$ will be a big disjunction $e_1+e_2+\dots+e_k$, where each $e_i$ looks for a different kind of violation. For instance $$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$ looks for a violation of the fact that each $C_i$ has size exactly $p(n)$. The most tricky part is guessing a violation between $C_i$ and $C_{i+1}$: the expression can compare a local pattern in $C_i$ and its image in $C_{i+1}$, using $t(\Sigma')^{p(n)}t'$, where $t$ and $t'$ are expressions for local patterns. With this we can guess a violation of the transition function of $M$ on a local pattern, or a violation of the identity outside of this pattern. In the end, we obtain that $$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$$ therefore we reduced (polynomially) an arbitrary PSPACE problem to universality of a regular expression.
I left out some details, but this should allow you to build a complete proof.

Of course, as pointed out by Michael Wehar in the comments, for others $E_1$ the problem can become simpler. Classifying the complexity of this problem  has been studied extensively in this paper [1] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in this answer (there does exist NP-complete cases).

As for your remark on squaring: allowing squaring in regular expressions make the inclusion and universality problem EXPSPACE-complete [2]. Remark that this can be seen in the proof scheme above, since $(\Sigma')^{p(n)}$ can now be expressed with a logarithmic-size expression in $p(n)$ using its binary decomposition, so we can go up to an exponential $p(n)$ while keeping the size of the expression polynomial.

[1] On the equivalence, containment, and covering problems for the regular and context-free languages
Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski.
Journal of Computer and System Sciences.
Volume 12, Issue 2, April 1976, Pages 222-268

[2] The equivalence problem for regular expressions with squaring requires exponential space. Meyer, A.R. and L. Stockmeyer. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.


To convert to MaxSAT:

For each set $ S $ introduce a fresh variable $ X_S $.
If two sets $ S $ and $ D $ intersect, produce the hard clause $\lnot X_S\lor \lnot X_D$.
For each element $e$ produce the hard clause $\bigvee_{e\in S} X_S$, making sure that at least one set that contains $ e $ is selected.
For each set $ S$ with weight $W$ produce the soft clause $\lnot X_S$ with weight $W$, to minimize the total weight of selected sets.

I wrote a Python script for this (http://sat.inesc-id.pt/~mikolas/excover). This is the most naïve encoding. I believe there are ways how to make it smaller.


Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?

For your first question, without the total order, the answer to your question is that it's essentially as hard as linear programming. Here's an outline of a proof.

First, let's establish a variable $x_1>0$, which we call $\epsilon$. Now, let's choose another variable $x_i$, which we will call $1$. We want to make sure that $$\epsilon \ll 1\, .$$
To do this, consider the inequalities
$$x_1 < x_2,$$
$$x_1 + x_2 < x_3,$$
$$x_2+x_3 < x_4,$$
and so on. With a long enough chain, this will tell us that $Nx_1 < x_i$, or $\epsilon < 1/N$, for some very large $N$ ($N$ is a Fibonacci number, and so grows exponentially in $i$).

We can now manufacture a linear program with integer coefficients. If we want a coefficient of 3 on $x_t$, we add the inequalities
$$x_t < x_{t'} < x_{t''} < x_t + \epsilon$$ and let $x_t + x_{t'} + x_{t''}$ stand in for 3$x_t$. If you want larger coefficients, you can get them by expressing the coefficients in binary notation, and making inequalities that guarantee that $x_u \approx 2x_t$, $x_v \approx 2x_u$, and so on. To get the right-hand-side, we do the same with the variable $x_i = 1$. This technique will let us use linear programs of the OP's form to approximately check feasibility for arbitrary linear programs with integer coefficients, a task which is essentially as hard as linear programming.

I don't know how to analyze the second question, asking about the case where there's a total order on all subsets.


Finding the largest set of points of limited diameter

There's an $O(n^3\log n)$ time algorithm for the two-dimensional version of this problem in my paper with Jeff Erickson, "Iterated nearest neighbors and finding minimal polytopes", Disc. Comp. Geom. 11:321-350, 1994. Actually the paper primarily looks at the dual problem: given the number of points in the subset, find the smallest possible diameter; but it uses the problem you describe as a subroutine. At least at the time we wrote it, we didn't know anything subexponential for higher dimensions (although if the subset has only $k$ points in it the exponential part can be made dependent on $k$ rather than $n$ using techniques in the same paper).


This is NP-hard.
Here is a reduction from SAT.  Suppose you have a CNF formula $\varphi$ with variables $x_1,\dots,x_n$.  Add variables $x'_1,\dots,x'_n$ and clauses of the form $x_i \to \neg x'_i$ and $x_i \lor x'_i$.  For each clause in $\varphi$, we add a corresponding $\cdots \lor \cdots$ clause: e.g., if $x_i \lor \neg x_j \lor x_k$ is a clause in $\varphi$, then we add the clause $x_i \lor x'_j \lor x_k$.  Once you've added all these clauses, add up the total number of clauses; say you have at most $m$ of the first type of clause and at most $m$ of the second type of clause.  Now add unused variables $x_{n+1},\dots,x_m$.  The result is an instance of your problem with $m$ variables and at most $m$ clauses of each type.  Now $\varphi$ is satisfiable iff this instance is satisfiable.


Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?

Yes, gc is amortized constant time. Suppose you have an algorithm which runs for time $n$ with a peak working set of size $k$. Now, note that you can allocate at most $O(n)$ words during the execution of the program, and that the time cost of running a copying garbage collector is $O(k)$ (ie, the cost of a gc is proportional to the total amount of live data). So if you run the gc at most $O(n/k)$ times, then the total runtime cost is bounded by $O(n)$, which means that the amortized cost of the gc is constant. So if you have a Cheney-style collector, with each semispace being size $2k$, then it's easy to see that a full collection can't be invoked more than once every $n/k$ steps, since allocating $k$ words takes $O(k)$ time, and the working set never exceeds size $k$, which gives you the bound you want. This justifies ignoring gc issues.

However, one case where the presence or absence of gc is not ignorable is when writing lock-free data structures. Many modern lock-free data structures deliberately leak memory and rely on gc for correctness. This is because at a high level, the way they work is to copy some data, make a change to it, and try to atomically update it with a CAS instruction, and run this in a loop until the CAS succeeds. Adding deterministic deallocation to these algorithms makes them much more complex, and so people often don't bother (esp. since they are often targeted at Java-like environments).

EDIT: If you want non-amortized bounds, the Cheney collector won't do it -- it scans the whole live set each time it is invoked. The keyword to google for is "real-time garbage collection", and Djikstra et al. and Steele gave the first real time mark-and-sweep collectors, and Baker gave the first real time compacting gc.

@article{dijkstra1978fly,
  title={{On-the-fly garbage collection: An exercise in cooperation}},
  author={Dijkstra, E.W. and Lamport, L. and Martin, A.J. and Scholten, C.S. and Steffens, E.F.M.},
  journal={Communications of the ACM},
  volume={21},
  number={11},
  pages={966--975},
  issn={0001-0782},
  year={1978},
  publisher={ACM}
}

@article{steele1975multiprocessing,
  title={{Multiprocessing compactifying garbage collection}},
  author={Steele Jr, G.L.},
  journal={Communications of the ACM},
  volume={18},
  number={9},
  pages={495--508},
  issn={0001-0782},
  year={1975},
  publisher={ACM}
}

@article{baker1978list,
  title={{List processing in real time on a serial computer}},
  author={Baker Jr, H.G.},
  journal={Communications of the ACM},
  volume={21},
  number={4},
  pages={280--294},
  issn={0001-0782},
  year={1978},
  publisher={ACM}
}


obvious property of big O, big Omega, and big Theta

EDIT: Now that I have fresh eyes in the morning, I see that I have thoroughly misread the question. The answer below applies to “if $f(n)\ne O(g(n))$, then $f(n)=\Omega(g(n))$”. As noted in comments above, the question as actually stated has a trivially true answer for all functions, that is, $f(n)=O(g(n))$ is equivalent to $g(n)=\Omega(f(n))$ immediately from the definition.

The answer is positive if $f$ and $g$ belong to a “well-behaved” family of functions which ensures that they are asymptotically comparable; in particular, if they are (restrictions to $\mathbb N$ of) functions taken from a Hardy field. For example, this holds if both functions are first-order definable (with parameters) in the real exponential field $(\mathbb R,+,\cdot,\exp)$, or in any o-minimal expansion of the real field for that matter.


Fast computation of Frobenius norm under memory limits

Some of the results depend on the model under which the matrix is presented, but there's a large collection of results that use sampling or sketching techniques to estimate norms accurately. Among some of the key results are:

sketching methods based on the use of 2-stable distributions: these work even if the entries are "streamed in" in some order, and also work if you are presented instead with the A and the B entries.
column sampling methods.

Again, it would be unfair to single out a single paper, also because it's not exactly clear which model you're working in: best to google 'norm estimation' or 'column sampling' to find some of the related results. This survey by Mahoney is a useful reference for sampling methods.


Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashionable algorithms course material such as Strassen's multiplication, the AKS primality test, or the Moser-Tardos algorithm is relevant for low-level practical problems of implementing a video database, an optimizing compiler, an operating system, a network congestion control system or any other system. The value of these courses is learning that there are intricate ways to exploit the structure of a problem to find efficient solutions. Advanced algorithms is also where one meets simple algorithms whose analysis is non-trivial. For this reason, I would not dismiss simple randomized algorithms or PageRank.

I think you can choose any large piece of software and find basic and advanced algorithms implemented in it. As a case study, I've done this for the Linux kernel, and shown a few examples from Chromium.

Basic Data Structures and Algorithms in the Linux kernel

Links are to the source code on github.

Linked list, doubly linked list, lock-free linked list.
B+ Trees with comments telling you what you can't find in the textbooks.

  A relatively simple B+Tree implementation.  I have written it as a learning exercise to understand how B+Trees work.  Turned out to be useful as well.

  ...

  A tricks was used that is not commonly found in textbooks.  The lowest values are to the right, not to the left.  All used slots within a node are on the left, all unused slots contain NUL values.  Most operations simply loop once over all slots and terminate on the first NUL.

Priority sorted lists used for mutexes, drivers, etc.
Red-Black trees are used for scheduling, virtual memory management, to track file descriptors and directory entries,etc.
Interval trees
Radix trees, are used for memory management, NFS related lookups and networking related functionality.

  A common use of the radix tree is to store pointers to struct pages;

Priority heap, which is literally, a textbook implementation, used in the control group system.

  Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7

Hash functions, with a reference to Knuth and to a paper.

  Knuth recommends primes in approximately golden ratio to the maximum
  integer representable by a machine word for multiplicative hashing.
  Chuck Lever verified the effectiveness of this technique:

  http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

  These primes are chosen to be bit-sparse, that is operations on
  them can use shifts and additions instead of multiplications for
  machines where multiplications are slow.

Some parts of the code, such as this driver, implement their own hash function.

  hash function using a Rotating Hash algorithm

  Knuth, D. The Art of Computer Programming,
  Volume 3: Sorting and Searching,
  Chapter 6.4.
  Addison Wesley, 1973

Hash tables used to implement inodes, file system integrity checks etc.
Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
Semaphores and spin locks
Binary search is used for interrupt handling, register cache lookup, etc.
Binary search with B-trees
Depth first search and variant used in directory configuration.

  Performs a modified depth-first walk of the namespace tree, starting
  (and ending) at the node specified by start_handle.  The callback
  function is called whenever a node that matches the type parameter is
  found. If the callback function returns a non-zero value, the search
  is terminated immediately and this value is returned to the caller.

Breadth first search is used to check correctness of locking at runtime.
Merge sort on linked lists is used for garbage collection, file system management, etc.
Bubble sort is amazingly implemented too, in a driver library.
Knuth-Morris-Pratt string matching,

  Implements a linear-time string-matching algorithm due to Knuth,
  Morris, and Pratt [1]. Their algorithm avoids the explicit
  computation of the transition function DELTA altogether. Its
  matching time is O(n), for n being length(text), using just an
  auxiliary function PI[1..m], for m being length(pattern),
  precomputed from the pattern in time O(m). The array PI allows
  the transition function DELTA to be computed efficiently
  "on the fly" as needed. Roughly speaking, for any state
  "q" = 0,1,...,m and any character "a" in SIGMA, the value
  PI["q"] contains the information that is independent of "a" and
  is needed to compute DELTA("q", "a") 2. Since the array PI
  has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
  save a factor of |SIGMA| in the preprocessing time by computing
  PI rather than DELTA.

  [1] Cormen, Leiserson, Rivest, Stein
   Introdcution to Algorithms, 2nd Edition, MIT Press

  [2] See finite automation theory

Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.

  Implements Boyer-Moore string matching algorithm:

  [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
   Communications of the Association for Computing Machinery,
   20(10), 1977, pp. 762-772.
   http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

  [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq,
  2004
   http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

  Note: Since Boyer-Moore (BM) performs searches for matchings from
  right
  to left, it's still possible that a matching could be spread over
  multiple blocks, in that case this algorithm won't find any
  coincidence.

  If you're willing to ensure that such thing won't ever happen,
  use the
  Knuth-Pratt-Morris (KMP) implementation instead. In conclusion,
  choose
  the proper string search algorithm depending on your setting.

  Say you're using the textsearch infrastructure for filtering,
  NIDS or
  any similar security focused purpose, then go KMP. Otherwise, if
  you
  really care about performance, say you're classifying packets to
  apply
  Quality of Service (QoS) policies, and you don't mind about
  possible
  matchings spread over multiple fragments, then go BM.

Data Structures and Algorithms in the Chromium Web Browser

Links are to the source code on Google code. I'm only going to list a few. I would suggest using the search feature to look up your favourite algorithm or data structure.

Splay trees.

  The tree is also parameterized by an allocation policy
  (Allocator). The policy is used for allocating lists in the C free
  store or the zone; see zone.h.
  Voronoi diagrams are used in a demo.
  Tabbing based on Bresenham's algorithm.

  There are also such data structures and algorithms in the third-party code included in the Chromium code.

Binary trees
Red-Black trees

  Conclusion of Julian Walker

  Red black trees are interesting beasts. They're believed to be
  simpler than
  AVL trees (their direct competitor), and at first glance this seems
  to be the
  case because insertion is a breeze. However, when one begins to play
  with the
  deletion algorithm, red black trees become very tricky. However, the
  counterweight to this added complexity is that both insertion and
  deletion
  can be implemented using a single pass, top-down algorithm. Such is
  not the
  case with AVL trees, where only the insertion algorithm can be
  written top-down.
  Deletion from an AVL tree requires a bottom-up algorithm.

  ...

  Red black trees are popular, as most data structures with a
  whimsical name.
  For example, in Java and C++, the library map structures are
  typically
  implemented with a red black tree. Red black trees are also
  comparable in
  speed to AVL trees. While the balance is not quite as good, the work
  it takes
  to maintain balance is usually better in a red black tree. There are
  a few
  misconceptions floating around, but for the most part the hype about
  red black
  trees is accurate.
  AVL trees
  Rabin-Karp string matching is used for compression.
  Compute the suffixes of an automaton.
  Bloom filter implemented by Apple Inc.
  Bresenham's algorithm.

  Programming Language Libraries

I think they are worth considering. The programming languages designers thought it was worth the time and effort of some engineers to implement these data structures and algorithms so others would not have to. The existence of libraries is part of the reason we can find basic data structures reimplemented in software that is written in C but less so for Java applications.

The C++ STL includes lists, stacks, queues, maps, vectors, and algorithms for sorting, searching and heap manipulation.
The Java API is very extensive and covers much more.
The Boost C++ library includes algorithms like Boyer-Moore and Knuth-Morris-Pratt string matching algorithms.

Allocation and Scheduling Algorithms

I find these interesting because even though they are called heuristics, the policy you use dictates the type of algorithm and data structure that are required, so one need to know about stacks and queues.

Least Recently Used can be implemented in multiple ways. A list-based implementation in the Linux kernel.
Other possibilities are First In First Out, Least Frequently Used, and Round Robin.
A variant of FIFO was used by the VAX/VMS system.
The Clock algorithm by Richard Carr is used for page frame replacement in Linux.
The Intel i860 processor used a random replacement policy.
Adaptive Replacement Cache is used in some IBM storage controllers, and was used in PostgreSQL though only briefly due to patent concerns.
The Buddy memory allocation algorithm, which is discussed by Knuth in TAOCP Vol. 1 is used in the Linux kernel, and the jemalloc concurrent allocator used by FreeBSD and in facebook.

 Core utils in *nix systems

grep and awk both implement the Thompson-McNaughton-Yamada construction of NFAs from regular expressions, which apparently even beats the Perl implementation.
tsort implements topological sort.
fgrep implements the Aho-Corasick string matching algorithm.
GNU grep, implements the Boyer-Moore algorithm according to the author Mike Haertel.
crypt(1) on Unix implemented a variant of the encryption algorithm in the Enigma machine.
Unix diff implemented by Doug McIllroy, based on a prototype co-written with James Hunt, performs better than the standard dynamic programming algorithm used to compute Levenshtein distances. The Linux version computes the shortest edit distance.

Cryptographic Algorithms

This could be a very long list. Cryptographic algorithms are implemented in all software that can perform secure communications or transactions.

Merkle trees, specifically the Tiger Tree Hash variant, were used in peer-to-peer applications such as GTK Gnutella and LimeWire.
MD5 is used to provide a checksum for software packages and is used for integrity checks on *nix systems (Linux implementation) and is also supported on Windows and OS X.
OpenSSL implements many cryptographic algorithms including AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

Compilers

LALR parsing is implemented by yacc and bison.
Dominator algorithms are used in most optimizing compilers based on SSA form.
lex and flex compile regular expressions into NFAs.

Compression and Image Processing

The Lempel-Ziv algorithms for the GIF image format are implemented in image manipulation programs, starting from the *nix utility convert to complex programs.
Run length encoding is used to generate PCX files (used by the original Paintbrush program), compressed BMP files and TIFF files.
Wavelet compression is the basis for JPEG 2000 so all digital cameras that produce JPEG 2000 files will be implementing this algorithm.
Reed-Solomon error correction is implemented in the Linux kernel, CD drives, barcode readers and was combined with convolution for image transmission from Voyager.

Conflict Driven Clause Learning

Since the year 2000, the running time of SAT solvers on industrial benchmarks (usually from the hardware industry, though though other sources are used too) has decreased nearly exponentially every year. A very important part of this development is the Conflict Driven Clause Learning algorithm that combines the Boolean Constraint Propagation algorithm in the original paper of Davis Logemann and Loveland with the technique of clause learning that originated in constraint programming and artificial intelligence research. For specific, industrial modelling, SAT is considered an easy problem (see this discussion). To me, this is one of the greatest success stories in recent times because it combines algorithmic advances spread over several years, clever engineering ideas, experimental evaluation, and a concerted communal effort to solve the problem. The CACM article by Malik and Zhang is a good read. This algorithm is taught in many universities (I have attended four where it was the case) but typically in a logic or formal methods class.

Applications of SAT solvers are numerous. IBM, Intel and many other companies have their own SAT solver implementations. The package manager in OpenSUSE also uses a SAT solver.


What type of automaton is Google's Turing Doodle?

Assuming that:

we can add an arbitrarily large number of rows ("status lines")
the rows can be arbitrarily long
the tape is infinite

I tried to build an Alan Turing's Doodle machine configuration that emulates the machine $M_4$ described in "Small Turing Machines and generalized busy beaver competition" that has a halting problem that depends on an open (up to my knowledge) Collatz-like problem. The full picture is available here.

... so even if the A.T.'s Doodle is perhaps not Turing complete (due to the non-overlapping left-only jump operator available only in the first row), it is powerful enough to walk the fine line of (un)decidability :-D

EDIT: TURING DOODLE IS TURING COMPLETE

(I leave the previous answer above, because I'm not sure that this part is correct :-)

I think that even with a single left non-overlapping jump the Turing Doodle is Turing complete!. The (simple) idea is to use the tape itself to store the current state and use multiple cells to represent a larger alphabet.

For example a 2 states 8 symbols TM can be simulated using the following tape representation:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

The Turing doodle can:

read $s$ and branch to one of the two different horizontal areas representing STATE A and STATE B;
read $b2, b1, b0$ and branch to a row representing one of the eight symbols;
write the next symbol, move the head to the "macro cell" on the left or right, and store on it the next state; in the figure below these operations (that can be done on a sequence of cells using the actions move left/right and write) are called "MW";
finally transfer the control to the upper row that with a single left jump will bring the control back to step 1.

The full picture is available here.

In the same manner, given a $TM$ with an arbitrary number of states and alphabet symbols we can build an equivalent Turing Doodle machine $DM$.


The smaller this upper bound is, the easier the problem becomes. In particular, if the range is $m$, then the problem can be solved in $O(m \log m)$ time using FFT. It is impressive/interesting that the authors were able to show that the problem is still quadratically nasty for numbers that are "slightly" larger than quadratic.


Book for self study of algorithms in group theory

It really makes a difference what the input to the algorithm is: how do you specify a group?

If you want groups given by generators and relators, I would suggest Combinatorial Group Theory, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable).

If you want automatic groups (groups whose elements are strings of symbols and whose group operations are performed by finite automata, with applications in low-dimensional topology), I would suggest Word Processing in Groups by Epstein (not me!), Cannon, Holt, Levy, Paterson, and Thurston.

If you want permutation groups (the kind of group-theoretic algorithm that is most relevant e.g. for graph isomorphism) then Seress has a book Permutation Group Algorithms but I don't have a copy so I can't tell you whether it's any good.

There should be a fourth paragraph here about matrix group algorithms but I don't know of a book on that topic. There's a little coverage in Seress's book.


Two remarks first:

I have used the "randomly generate terms and check that they are well-typed" approach (you mention that "untyped" terms are generated, you can also randomly generate terms in a Church-style grammar with explicit type annotations) and it worked very well in practice, it revealed all the bugs there was to find on this particular part of the project. For practical purposes I would recommend trying this first. (On the other hand, the generator was aware of scoping rules -- it maintained a set of currently bound variables for top-down generation, this is easy to implement.)
The choice of order depends a lot on the application you have in mind: two distinct applications will require different orders. For example, people that work on type-directed program synthesis are not usually interested in enumerating equivalent programs, so they will make simplification rules such as assuming that "any term of type A -> B can be chosen to start with a lambda-abstraction" -- in your framework, ordering lambda-terms before all terms at this type. This order is very bad for compiler testing: if you only generate programs that are in normal form, you are unlikely to exercise much of your optimization strategies or runtime semantics. So I believe that assuming an order to abstract away from the intended usage is not a good modeling choice: its choice is tightly coupled with the intended usage, and I would rather reason about the usage than the corresponding order.

Now for some references.

For typed-term generation for testing purposes, you may be interested in "Making random judgments: Automatically generating well-typed terms from the definition of a type-system" by Burke Fetscher, Koen Claessen, Michał Pałka, John Hughes, and Robert Bruce Findler, 2015.

  This paper presents a generic method for randomly generating well-
  typed expressions. It starts from a specification of a typing judgment in PLT Re-
  dex and uses a specialized solver that employs randomness to find many different
  valid derivations of the judgment form.
  Our motivation for building these random terms is to more effectively falsify
  conjectures as part of the tool-support for semantics models specified in Redex.
  Accordingly, we evaluate the generator against the other available methods for
  Redex, as well as the best available custom well-typed term generator. Our results
  show that our new generator is much more effective than generation techniques
  that do not explicitly take types into account and is competitive with generation
  techniques that do, even though they are specialized to particular type-systems
  and ours is not.

For typed term enumeration for program synthesis, two recent works that I know are Example-Directed Synthesis: A Type-Theoretic Interpretation by  Jonathan Frankle, Peter-Michael Osera, David Walker, and Steve Zdancewic, 2016, and Program Synthesis from Polymorphic Refinement Types by Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama, 2016. Note that both works use refinement types as a way to encode more desired properties of the searched program -- such as a testsuite that it should pass. These refinements often constrain the search space substantially more than just types, but they are also harder to invert -- interleave with search.


Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-negligible. If you observe that it is the case, please tell me and I'll update my answer.

The report Parallel Algorithms for Depth-First Search discusses known parallel algorithms for DFS on various types of graphs. The list given on pages 9-10 indicates several algorithms in $\mathsf{NC} \setminus \mathsf{NC}_2$, such as DFS for planar undirected graphs, or in $\mathsf{RNC} \setminus \mathsf{RNC}_2$, such as DFS for general undirected graphs.
With a quick search, I could not find papers improving over the parallel algorithms for sparse multivariate polynomial interpolation over finite fields of this paper, which is in $\mathsf{NC}_3$. However, several papers that could possibly have been relevant were behind a paywall.
Computing all maximal cliques in a graph is in $\mathsf{NC} \setminus \mathsf{NC}_2$ when the number of maximal clique is polynomially bounded, according to this paper.
The maximal path problem seems to be in $\mathsf{NC}_5$ for general (undirected) graphs, I've not found a faster parallel algorithms without restrictions on the underlying graph.

Other potential candidates might include algorithms for finding perfect matchings in specific types of graphs, or algorithms for finding a maximal tree cover in arbitrary graphs (e.g. this paper mentions a randomized polytime algorithms in parallel time $O(\log^6n)$). This paper also mention solving classes of CSPs problems that arise in computer vision application, in parallel time $O(\log^3n)$.


How can relational parametricity be motivated?

Well, relational parametricity is one of the most important ideas introduces by John Reynolds, so it shouldn't be too much of a surprise that it looks like magic. Here is a fairy tale about how he might have invented it.

Suppose you're trying to formalize the idea that certain functions (identity, map, fold, reversal of lists) act "the same way on many types", i.e., you have some intuitive ideas about parametric polymorphism, and you have formulated some rules for creating such maps, i.e., the polymorphic $\lambda$-calculus or some early variant of it. You notice that naive set-theoretic semantics is not working.

For instance, we stare at the type $$\forall X : \mathsf{Type} . X \to X,$$
which should contain only the identity map, but naive set-theoretic semantics allows unwanted functions such as
$$\lambda X : \mathsf{Type} . \lambda a : X . \mathsf{if}\ (X = \lbrace 0, 1 \rbrace) \ \mathsf{then} \ 0 \ \mathsf{else}\ a.$$
To eliminate this sort of thing, we need to impose some further conditions on functions. For instance, we could try some domain theory: equip each set $X$ with a partial order $\leq_X$ and require that all functions be monotone. But that doesn't quite cut it because the above unwanted function is either constant or identity, depending on $X$, and those are monotone maps.

A partial order $\leq$ is relfexive, transitive and antisymmetric. We can try to alter the structure, for instance we could try to use a strict partial order, or a linear order, or an equivalence relation, or just a symmetric relation. However, in each case some unwanted examples creep in. For instance, symmetric relations eliminate our unwanted function but allow other uwanted functions (exercise).

And then you notice two things:

The wanted examples are never eliminated, whatever relations you use in place of partial orders $\leq$.
For each particular unwanted example you look at, you can find a relation that eliminates it, but there is no single relation that eliminates all of them.

So, you have the brilliant thought that the wanted functions are those that preserve all relations, and the relational model is born.


Your original problem formulation is not correct. It's missing some normalization on $H$, otherwise it could be the case that all eigenvalues of $H$ are always smaller than $a$, making the problem completely trivial, so it couldn't possibly be QMA-complete.
One natural normalization is $||H||\leq 1$, which you can enforce by saying that if $H$ is expressed as the sum of $m$ local terms, then each term should have norm at most $1/m$. Now all eigenvalues of $H$ must lie in $[-1,1]$. For this normalization, the complexity of constant-gap Local Hamiltonian is conjectured to be QMA-hard. Note that this problem is NP-hard because of the classical PCP theorem.


How to find largest supergroup in polynomial time?

Yes, this can be solved in polynomial time (and, I think, even in $\mathsf{NC}$).

First, it's easy to reduce to the case of transitive $G$.

Next, find the minimal blocks of $G$. (See e.g. Section 3.6(B) of Dixon & Mortimer.) This can be done by choosing a point $x \in [n]$, and for each $y \in [n]$, $y \neq x$, computing the (undirected) connected components of the orbital digraph generated by $(x,y)$. Each such connected component is a block; take the smallest ones.

If there are $b$ blocks each of size $s$, then the desired group is the wreath product $S_b \wr S_s = (S_b)^s \rtimes S_s$ in its natural action on $[n]$.


Generating all instances of a regular language up to a certain length

There are several recent papers that address your question, e.g.:

Margareta Ackerman and Jeffrey Shallit. Efficient Enumeration of Regular Languages. Conference on Implementation and Application of Automata (CIAA) , Lecture Notes in Computer Science, 4783, Springer-Verlag, Berlin Heidelberg, pp. 226-241, 2007.

Margareta Ackerman and Erkki Makinen. Three New Algorithms for Regular Language Enumeration, Computing and Combinatorics: 15th Annual International Conference (COCOON) , Lecture Notes in Computer Science 5609, Springer-Verlag, Berlin Heidelberg, pp. 178-191, 2009.

You can get these two papers from here.


Enumerating all s-t paths with cost exactly k

I've been struggling for long with two similar problems and you are just referring to the combination of them: finding the best $K$ solutions and the Target-Value search problem. Since you are asking for algorithms, let me give you the best bib references I am aware of.

First, let me reformulate the second problem:

Given a graph $G(V,E)$ and a couple of vertices $s\in V$ and $t\in V$ find the simple path $P^*$ whose cost is as close as possible to a given value $k$, i.e., if $P_{s-t}$ denotes the set of all (simple) paths from $s$ to $t$ and $g(P)$ is the cost of a path which is defined as the sum of the cost of all of its edges, then $P^* = argmin_{\pi\in P_{s-t}} \{|c(\pi)-k|\}$

This problem is known as the Target-Value search problem and was originally introduced in Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleeer, Rong Zhou and Minh Do, Heuristic Search for Target-Value Path Problem. In case a path actually exists with a cost equal to $k$ then it simplifies to your problem. Note that while in the definition I said "simple paths" between parenthesis, the work cited above refers only to Directed Acyclic Graphs so that all paths are necessarily simple. Unfortunately, I am not aware of any generalization of this algorithm to Undirected (cyclic) graphs. An improvement over that paper was provided by much the same authors in Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer and Rong Zhou, A depth-first approach to target-value search

A different problem consists of computing the best $K$ solutions. This problem can not be solved with an A$^*$-like search algorithm because duplicate detection avoids re-expanding nodes while the second best solution might require going through the same node already considered in the best solution. One of the most influential works for this problem is David Eppstein, Finding the $k$ Shortest Paths. A recent contribution of the same problem is Husain Aljazzar, Stefan Leue, K$^*$: A heuristic search algorithm for finding the $k$ shortest paths

Now, how to combine these two problems is an unknown so that if you have any ideas ... :)


Question about discarding the second register in the standard approach of hidden subgroup algorithm

Discarding in this context can be carried out by performing a Partial Trace. The system you're interested in is that of the first register. If you want to know only its state, as opposed to the combined state of the two registers, then you take the density matrix of the whole system and trace out the second register.  The resultant state will, in this case, be mixed.  What you're seeing at work is more or less purification in reverse. The resultant mixed state is the reduced state of some other pure system, namely the system comprised of the two registers.


Question 1. Yes, there are other ways than using automata. Typically, if you already now that your language is recognized by some surjective monoid morphism $\varphi: A^* \to M$, then you know that $M(L)$ (the syntactic monoid of $L$) is a quotient of $M$. For instance if $L = \{ u \in \{a,b\}^* \mid |u|_a \equiv 5 \bmod 13 \text{ and } |u|_a \equiv 6 \bmod 7\}$, then you can prove directly that $M(L) = \mathbb{Z}/91\mathbb{Z}$ without computing the minimal automaton.

Question 2. C. Brand is right. You can still use the minimal automaton, even if it is infinite. You can also just use the definition of the syntactic congruence to get a presentation of the syntactic monoid. You may also just guess a morphism recognizing your language. Three examples:

(1) Let $L = \{u \in \{a,b\}^* \mid |u|_a = |u|_b \}$. Then the morphism $\pi: \{a,b\}^* \to \mathbb{Z}$ defined by $\pi(a) = 1$ and $\pi(b) = -1$ recognizes $L$ since $L = \pi^{-1}(0)$. Thus $M(L)$ is a quotient of $\mathbb{Z}$. But every nontrivial quotient of $\mathbb{Z}$ is finite and cannot be equal to $M(L)$ (otherwise $L$ would be regular). Thus
$M(L) = \mathbb{Z}$.

(2) Let $L = \{u \in \{a,b\}^* \mid |u|_a \geqslant |u|_b \}$. This context-free language generated by the grammar $S \to SS + aSb + 1$. Its syntactic monoid is also equal to $\mathbb{Z}$, since $L = \pi^{-1}([0, + \infty[)$.

Update following Stefan's comment

(3) Let $D$ be the Dyck language (see Stefan's comment). Its syntactic monoid is the bicyclic monoid, which is the monoid presented by $<a,b \mid ab = 1>$.

(4) Let $L = \{a^nb^n \mid n \geqslant 0 \}$. Its syntactic monoid is the monoid with zero presented by $<a,b \mid ba = 0>$.


An oracle separation is easy to show. I'm not sure which paper showed it first, but for example you can already show that there exists an oracle $X$ such that

  $\mathsf{NP}^X \not\subset \mathsf{QSZK}^X,$

which implies

  $\mathsf{AM}^X \not\subset \mathsf{SZK}^X$

because $\mathsf{NP}$ is in $\mathsf{AM}$ and $\mathsf{SZK}$ is in $\mathsf{QSZK}$.
See arXiv:1801.08967 for one way to prove this. See the comment on page 3 of arXiv:1902.03660 for another way to show this.

Also note that in the unrelativized world $\mathsf{AM=SZK}$ would collapse the polynomial hierarchy, because $\mathsf{SZK}$ is closed under complement, and hence this implies $\mathsf{AM=coAM}$, which collapses $\mathsf{PH}$.


For the sake of completeness, let me update this answer with a direct proof. My original answer will remain below in case anyone finds it interesting. The basic idea of the direct proof is exactly as Evgenij suggests: check whether each possible assignment is satisfiable, keep a counter of satisfiable instances, and reuse space wherever possible.

Claim: #$P \subseteq FPSPACE$

Proof: Assume #$SAT$ is #$P$-complete; then it suffices to show a polynomial-space algorithm to solve #$SAT$. Here is a linear-space, exponential-time algorithm.

Initialize two counters of $k \le n$ bits to all 0, for number of variables $k$ in the $3CNF$ formula given as input. The first counter will keep track of which assignment we are checking (1 = true, 0 = false, for each variable $x_1$ to $x_k$). The second will keep track of the number of satisfying assignments (there are at most $2^k$ of them).

We will also need enough space ($n$ bits) to write the formula, and enough space to do "scratch work" for one clause (some very small constant number of bits, since every clause will have exactly 3 literals by definition of #$SAT$).

Here is the description of the algorithm:

For all possible assignments
   For all clauses in the Boolean formula
      Check if the assignment satisfies the given clause
   If the assignment satisfied every clause
      Increment the assignment counter
Output the value in the assignment counter

Note that once we finish work on one possible assignment, we don't need any information from it again to compute whether other assignments satisfy the formula; the only information we keep is whether it was satisfied -- in the second counter. In particular, since we can just apply binary addition of 1 to the assignment we are testing in order to always get the next assignment, and since every assignment can be checked by considering only one clause at a time (and re-using the same space for computation on every clause), the dominating factor in the space requirement is simply writing the formula itself. Alternatively, we just read from an input tape and never explicitly write the formula, then in the worst case, $k = n$ and it still takes $O(n)$ space to write the possible assignments and keep track of the number of satisfying assignments. Q.E.D.

Below is my original answer:

Although this already essentially answered, let me give a proof of a different vein (straight out of Arora/Barak):

Let #$SAT_D$ = {($\phi, K$) : $\phi$ is a 3CNF formula and it has exactly $K$ satisfying assignments}

In Chapter 17, there is a proof that #$SAT$ is #$P$-complete.
In Chapter 8, there is a proof that #$SAT_D \in IP$.

Since $IP = PSPACE$, #$P \subseteq FPSPACE$.


Is there a common mathematical symbology for collections?

Specification languages such as Z have a vast range of data types and operations on them and, at least within that community, these are standardised. This tutorial gives a great overview. Other specification languages exist, such as B and Alloy which may also satisfy your requirements.


Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables

See Theorem 23 in Section 9.3 of Ryan O'Donnell's book Analysis of Boolean functions. Even though the theorem there is stated for $\pm 1$ variables, it holds for Gaussians as well (see Chapter 10 of the book for details on that).

For the more general statement, see Exercise 7 in these lecture notes of Terry Tao.


What does PAC-learnability say about the learner runtime?

PAC comes in two flavors -- "information theoretic PAC" and "efficient PAC." The latter asks for computational efficiency whereas the former cares only about sample size.  One usually understands which is referred to from context.

Indeed, it is not known whether (efficient) PAC learning is NP-hard in general, but results on the cryptographic hardness of learning as well as on hardness of proper learning make it universally believed that learning is hard.


Searching in a string that changes often, and looking for a set of words, I would use Aho-Corasick, an extension of KMP that builds a tree (based on the set of words) and looks for the words in parallel.


What is "Flynn's algorithm" relating to linked lists?

You might be thinking of Floyd's algorithm for finding cycles.  Given a singly linked list, it finds a cycle in the list (if one exists) in constant space and time linear in the size of the list.


NFA to 2DFA: what are the upper and lower bounds?

The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction:

  The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs
  are still unknown. The problem of stating them was raised in 1978 by
  Sakoda and Sipser [32], with the conjecture that they are not
  polynomial. In spite of all attempts to solve it, this problem is
  still open.

As explained in section 6 of that survey, the question relates to the L vs. NL problem, so it may be not surprising that the problem remains unresolved.
Concerning lower bounds, section 5 states the following:

  The question 1NFAs versus 2DFAs has been solved in the unary case
  in [4] by showing that the tight cost is polynomial, more precisely
  Θ(n²). This gives also the best known lower bound for the general
  case.

EDIT (2017/09/18): Concerning upper bounds, the PhD thesis of Christos Kapoutsis provides a valuable source (thanks goes to András Salamon for his valuable comment below). Section 2 of the PhD thesis mentions the following:

  Second, it is even conjectured that this alleged exponential difference in size between 1NFAs and 2DFAs covers the entire gap from n to $2^n - 1$ which  is known to exist between 1NFAs and 1DFAs [35]² In other words, according to this conjecture, a 2DFA trying to simulate a 1NFA may as well drop its bidirectionality, since it is going to be totally useless: its optimal strategy is going to be the well-known brute-force
  one-way deterministic simulation [47]. So, once more we have an instance of the claim that the obvious, highly inefficient solution is also the optimal one.
  [...]

  ² As with 2DFAS (cf. Footnote 1 on page 8), a 1DFA is allowed to reject by just hanging anywhere along its input. Without this freedom, the gap would actually be from $n$ to $2^n$.

References:

Pighizzini, Giovanni: Two-Way Finite Automata: Old and Recent Results. In: E. Formenti (Ed.), Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA & JAC 2012, pp.3-20.

Kapoutsis, Christos: Algorithms and lower bounds in finite automata size complexity. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA 2006.


What is a substantial contribution to software design, with respect to authorship?

My view on this particular case is that the CS colleague's name should not go on the paper for the simple reason that the research had been done and written up before his/her contribution was made. The CS colleague's work made no contribution to your results.

As you said, the CS colleague is going to use the code for his/her own research, so he/she already has something for free. One question you could be asking is whether you should be on his/her subsequent papers based on this software.

In general, people who do the development work do deserve some credit even if their work helps facilitate scientific output, rather than directly contributes to it. For example, if someone wrote a program based on some design that I made, which would then form the basis of my further work, I would definitely give them credit for it, at least on the first instance.

Of course a lot of factors will influence this decision. Whether the developer is a PhD student, post-doc, professor or a "just a" programmer. Whether the person depends crucially on the publication. Whether the project's evaluation depends on joint publications (to show, for example, interdisciplinary collaboration). Political reasons: will the joint publication create goodwill for future collaborations?

It's not a black/white issue and very hard to decide. In general, it's probably best to avoid any possible badwill, because that can really spoil a (possible) collaboration.


How hard is the Circuit Isomorphism problem?

As pointed out by @Marzio De Biasi, the problem you are asking about is $\mathsf{coNP}$-complete, by a direct reduction from TAUTOLOGY: given a boolean formula $\varphi$, is $\varphi$ equivalent to the constant 1 circuit? It is easily seen to be in $\mathsf{coNP}$. (Given that Marzio really answered the question, I suggest anyone thinking of upvoting this answer flip a coin and if it lands heads then go vote for one of Marzio's other answers.)

Let me also clarify: the problem you are asking about is more typically called Circuit Equivalence. Circuit Isomorphism is the problem: given two circuits $C_1, C_2$ on $n$ inputs, is there a permutation $\pi \in S_n$ such that $C_1(\vec{x})$ and $C_2(\pi(\vec{x}))$ are equivalent? Circuit Isomorphism has a status similar to that of Graph Isomorphism, but one level higher in $\mathsf{PH}$: it is $\mathsf{coNP}$-hard (by the same reduction above), not known to be in $\mathsf{coNP}$, in $\mathsf{\Sigma_2 P}$, but not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH} = \mathsf{\Sigma_3 P}$.


Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New York, pp. 153–182

When $T_{1}$ and $T_{2}$ are isomorphic you can solve it in $O(n)$.

Shamir's paper has $O({k^{1.5}\over log\ k}n)$ for testing if one tree is a subtree of the other, https://www.cs.bgu.ac.il/~dekelts/publications/subtree.pdf

Not sure if that helps.


Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?

The Bentley-Saxe logarithmic method can sort a set in $O(n \lg n)$ time by merging sorted lists of equal size, much like merge sort.


Algorithm to determine function equality on the simply typed lambda calculus?

As I said in my comment, the answer in general is no.

The important point to understand (I say this for Viclib, who seems to be learning about these things) is that having a programming language/set of machines in which all programs/computations terminate by no means implies that function equality (i.e., whether two programs/machines compute the same function) is decidable.  An easy example: take the set of polynomially-clocked Turing machines.  By definition, all such machines terminate on all inputs.  Now, given any Turing machine whatsoever $M$, there is a Turing machine $M_0$ that, given in input the string $x$, simulates $|x|$ steps of the computation of $M$ on a fixed input (say, the empty string) and accepts if $M$ terminates in at most $|x|$ steps, or rejects otherwise.  If $N$ is a Turing machine that always immediately rejects, $M_0$ and $N$ are both (obviously) polynomially-clocked, and yet if we could decide whether $M_0$ and $N$ compute the same function (or, in this case, decide the same language), we would be able to decide whether $M$ (which, remember, is an arbitrary Turing machine) terminates on the empty string.

In the case of the simply typed $\lambda$-calculus (STLC), a similar argument works, except that gauging the expressive power of the STLC is not as trivial as in the above case. When I wrote my comment, I had in mind a couple of papers by Hillebrand, Kanellakis and Mairson from the early 90s, which show that, by using more complex types than the usual type of Church integers, one may encode in the STLC sufficiently complex computations for the above argument to work. Actually, I see now that the needed material is already in Mairson's simplified proof of Statman's theorem:

Harry G. Mairson, A simple proof of a theorem of Statman. Theoretical Computer Science, 103(2):387-394, 1992. (Available online here).

In that paper, Mairson shows that, given any Turing machine $M$, there is a simple type $\sigma$ and a $\lambda$-term $\delta_M:\sigma\rightarrow\sigma$ encoding the transition function of $M$. (This is not obvious a priori, if one has in mind the extremely poor expressive power of the STLC on Church integers. Indeed, Mairson's encoding is not immediate).  From this, it is not hard to construct a term

$t_M:\mathtt{nat}[\sigma]\rightarrow\mathtt{bool}$

(where $\mathtt{nat}[\sigma]$ is the instantiation on $\sigma$ of the type of Church integers) such that $t_M\,\underline{n}$ reduces to $\underline{1}$ if $M$ terminates in at most $n$ steps when fed the empty string, or reduces to $\underline{0}$ otherwise. As above, if we were able to decide that the function represented by $t_M$ is the constant $\underline{0}$ function, we would have decided the termination of $M$ on the empty string.


What are the limits of total functional programming?

It depends on the total functional language.

This answer sounds like a cop-out, but nothing more specific can be said. After all, consider whatever important decidable program that you're interested in. Write a program in your favorite Turing-complete language to solve it. Since the problem is decidable, your program will halt on all inputs.

(Arguably, a non-decidable problem could have interesting programs, but not such that people can use, because they'll never be able to wait long enough to know the answer.)

Now, define a new language such that it has only one valid input program: the program that you just wrote, with the same semantics as it had before. It's certainly total, since all inputs to all programs written in it (of which there's only one) always terminate.

This cheap trick is actually useful: the language Coq, for example, is a total functional language in that no program typechecks unless there is a proof that it terminates. (If you were to waive that requirement, it would be Turing-complete, so the only obstacle is finding a proof of termination.)

I'm not sure what you mean by "everything that could in theory be determined statically can be determined statically"; it sounds tautologically true. Nonetheless, total languages aren't inherently easy to analyze; you know that nothing diverges, which is a useful fact, but the relationship between input and output is still complex. (In particular, there are still infinitely many possible inputs, so you can't exhaustively try them all, even in theory.)


What is the complexity class most closely associated with what the human mind can accomplish quickly?

I don't claim this is a complete answer, but here are some thoughts that are hopefully along the lines of what you're looking for.

NP roughly corresponds to "puzzles" (viz. the NP-completeness of Sudoku, Minesweeper, Free Cell, etc., when these puzzles are suitably generalized to allow $n \to \infty$). PSPACE corresponds to "2-player games" (viz. the PSPACE-completeness of chess, go, etc.). This is not news.

People generally seem to do alright with finite instances of NP-complete puzzles, and yet find them non-trivial enough to be entertaining. The finite instances of PSPACE-complete games that we play are considered some of the more difficult intellectual tasks of this type. This at least suggests that PSPACE is "hitting the upper limits" of our abilities. (Yet our opponents in these PSPACE-complete games are generally other people. Even when the  opponents are computers, the computers aren't perfect opponents. This heads towards the question of the power of interactive proofs when the players are computationally limited. There is also the technicality that some generalizations of these games are EXP-complete instead of PSPACE-complete.)

To an extent, the problem sizes that arise in actual puzzles/games have been calibrated to our abilities. 4x4 Sudoku would be too easy, hence boring. 16x16 Sudoku would take too much time (not more than the lifetime of the universe, but more than people are generally willing to sit to solve a Sudoku puzzle). 9x9 seems to be the "Goldilocks" size for people solving Sudoku. Similarly, playing Free Cell with a deck of 4 suits of 13 cards each and 4 free cells seems to be about the right difficulty to be solvable yet challenging for most people. (On the other hand, one of the smartest people I know is able to solve Free Cell games as though she were just counting natural numbers "1,2,3,4,...") Similarly for the size of Go and Chess boards.

Have you ever tried to compute a 6x6 permanent by hand?

I suppose the point is that if you take natural problems in classes significantly above PSPACE (or EXP), then the only finite instances that people are capable of solving seem to be so small as to be un-interesting. Part of the reason "natural" is necessary here is that one can take a natural problem, then "unnaturally" modify all instances of size $< 10^{10}$ so that for all instances a human would ever try the problem becomes totally intractible, regardless of its asymptotic complexity.

Conversely, for problems in EXP, any problem size below the "heel of the exponential" has a chance of being solvable by most people in reasonable amounts of time.

As to the rest of PH, there aren't many (any?) natural games people play with a fixed number of rounds. This is also somehow related to the fact that we don't know of many natural problems complete for levels of PH above the third.

As mentioned by Serge, FPT has a role to play here, but (I think) mostly in the fact that some problems naturally have more than one "input size" associated with them.


Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density is a good way to define the cell generators of a centroidal Voronoi tessellation (CVT).

CVTs don't loose their quantization precision by translation or rotation in concert with the underlying probability distribution. Not sure what your question is.


What is the difference between standard SIFT descriptor and upright SIFT descriptor?

SIFT algorithm detects keypoints, assigns orientation to them and then constructs a descriptor of that keypoint using the assigned orientation as a reference frame. Upright SIFT descriptor does the same thing, but forces orientation to be the vector (0, 1). So it's very simple: upright descriptor simply assumes that the orientation of the features doesn't change over_time/between_images and therefore just uses the unit vector directed upwards to construct the frame of reference.


Typing relations terminology – how do I read typing relations?

The two inference rules are different, because the first requires that x:T_1 is the only assumption, while the second allows side assumptions.  This can have subtle effects of the consequence relation for the type theory prevents the type theory from modelling weakening by having as the hypothesis rule:

$$
\frac{}{\Gamma, x:A \vdash x:A}
$$

In your English gloss, I would have under the sole assumption, to avoid confusion with the assumption-gobbling inference rule:

$$
\frac{\Gamma, x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$


Inferring the Kolmogorov complexity of a string from its substrings' complexity

A simple bound is that we could use a program generating $x$, a starting index $1 \leq i \leq n$ and length $m$ to get a program generating any choice of $v$, and thus $C(v)$ is bounded as
$$\forall v: k \leq C(v) \leq C(x) + \log(n) + \log(m) + c,$$
where $c$ is some constant overhead independent from $x,v$ that represents the steps necessary to take a Turing machine, a starting index and length and return the requested substring.
This in turn gives us a lower bound for $C(x)$,
$$C(x)  \geq k - \log(n) - \log(m) - c.$$


Maximum Independent Set using Maximal MIS

If the graph is a clique (or a set of disconnected cliques), then Luby's algorithm succeeds on the first iteration.


How much would a SAT oracle help speeding up polynomial time algorithms?

Actually, acceptance of nondeterministic Turing machines in time $t$ is $O(t \log t)$-time reducible to SAT (the construction is via oblivious simulation, see Arora-Barak), so typically any time a nondeterministic machine is appreciably faster than a deterministic one, we'll see at least some speedup with a SAT oracle.

To be more concrete, primality testing comes to mind, as the best variant of the AKS algorithm appears to test primality of an $n$-bit number in time $O(n^6 \; \text{polylog}\; n)$. But if we go "old school", Pratt gave a nondeterministic TM to decide primality in time $O(n^3 \; \text{polylog}\; n)$. Acceptance of this machine can be reduced (deterministically) in $O(n^3 \; \text{polylog}\; n)$ time to a SAT instance.

The 3SUM problem may be another example, as it seems like one can guess a solution and check it in subquadratic time, and then acceptance of such a machine can be reduced to SAT in subquadratic time.