Are there established cryptographic hardness assumptions for chaotic systems?

Personally, I wouldn't bother with chaos-based encryption.  I have yet to see any scheme based upon chaos that strikes me as very promising from either a practical or a theoretical perspective.  The work on using chaos for encryption that I've seen ranks pretty high on my "bogometer".  I never see any sort of security proof or plausible evidence of security, and many such systems turn out to be broken when you take a close look.  And I find it hard to see any benefit over standard well-known approaches (e.g., CBC mode encryption; information-theoretic work based upon Wyner's wiretap channel; etc.).

But if you want to find something in this space, you might look at the following paper:

Semantic Security for the Wiretap Channel.  Mihir Bellare, Stefano Tessaro, and Alexander Vardy.  CRYPTO 2012.

It has plenty of theoretical/foundational content, and is in the vicinity of the sort of thing you mention.


Why is the "free store" memory called the "heap"?

I don't think it has anything to do with the data structure.
It's just the opposite of the stack, which carefully orders its elements and doesn't allow them to be read or written except at the top.


Is the counting version of 1-in-3 Sat #P-complete?

Yes, the counting version of 1-in-3 Sat is $\#P$-complete. This is stated in "Complexity of Generalized Satisfiability Counting Problems" (Example 3.1), the reference pointed out by Emil in the comment.

Note:
This leads us to the curious question: is the counting version of every NP-complete problem $\#P$-complete? The answers to this question (When does "X is NP-complete" imply "#X is #P-complete"?) suggest so!


Hadwiger number under matching contraction

There is no such function - here is an example where $h(G)$ is arbitrarily large while $h(G/M) \leq 4$. Make $G$ by taking two copies of an $n \times n$ grid and making every vertex of one grid adjacent to the corresponding vertex of the other grid.

$G$ contains a clique of size $n$ as a minor (i.e $h(G) \geq n$). In particular the $i$'th vertex of the clique is obtained by contracting the $i$'th row of the first grid and the $i$'th column of the second grid and then contracting these two vertices together.

Let $M$ be the matching that connects each vertex of the first grid with its copy in the second grid. $G/M$ is an $n \times n$ grid, so $G/M$ is planar and hence $h(G/M) \leq 4$.


Algorithms with finite expected running time and infinite variance

Though I'm having trouble finding the exact exponent of the power laws they purport to exist, Kroc, Sabharwal and Selman have a paper called "An Empirical Study of Optimal Noise and Runtime Distributions in Local Search" where they show WalkSat (a local solver for SAT) has power law tails in the runtime.  If the power law does not fall within the range of $(2,3]$, then obviously this isn't quite what you're looking for, but maybe it's still of some use.

It looks like Gomes, Selman, Crato and Klautz also have a paper called "Heavy-Tailed Phenomena in Satisﬁability and Constraint Satisfaction Problems" though from a quick spot check it looks like they're reporting the exponent in the power law in the range of $(1,2)$ which would violate your finite first moment condition.

Also Gomes, Selman and Crato published a paper called "Heavy-Tailed Distributions in Combinatorial Search" which might be of some relevance.

From what I understand, the sporadic nature of runtimes (for example, because of a power law behavior in running time) gives one a good reason to use random restarts and might even inform you as to when a restart should occur.  Figure 8a in the paper "Heavy-Tailed Distributions in Combinatorial Search" gives two run time plots, one without restarts and one with, where the algorithm with random restart clearly wins out.


Local Graph Isomorphism to construct Global Graph Isomorphism

This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms within each color class, then combining those using the edges between color classes. Zemlyachenko's trick could then be used to individualize $\tilde{O}(\sqrt{n})$ vertices, so that the resulting graph had bounded color classes (which led to the previous-best algorithm for GI).

Babai's recent algorithm does another kind of divide-and-conquer that is sort of along the lines you mention. It either finds a partition of the graph into small parts (where "small" here means some constant fraction smaller than the original graph; the result is that such recursion can only happen $O(\log n)$ times) or finds a large embedded Johnson scheme. In the latter case, it handles the Johnson scheme by a different recursive technique, but then handles the vertices that aren't in the Johnson scheme essentially along the lines you suggest. (Indeed, if you look at the table of contents of Babai's paper you will see there is quite a lot of talk about "local to global" principles, though it's not really the same "local to global" you're talking about here.)


One approach to encode Factoring (RSA) to SAT is to use multiplicator circuits (every circuit can be encoded as CNF).
Let's assume we are given an integer $C$ with $2n$ bits, $C=(c_1,c_2,\cdots,c_{2n})_2$. We are interested in finding two $n$-bit integers $A=(a_1,\cdots,a_n)$ and $B=(b_1,\cdots,b_n)$ whose product is $C=A*B$.
The most naive encoding can be something like this; we know that:
$$c_{2n}= a_n \land b_n$$
$$c_{2n-1}= (a_n\land b_{n-1}) xor (a_{n-1}\land b_n)$$
$$Carry:d_{2n-1}= (a_n\land b_{n-1}) \land (a_{n-1}\land b_n)$$
$$c_{2n-2}= (a_n\land b_{n-2}) xor (a_{n-1}\land b_{n-1}) xor (a_{n-2}\land b_{n}) xor d_{2n-1}$$
...
Then using Tseitin transformation, the above encoding can be translated into CNF.
This approach produces a relatively small CNF. But this encoding does not support "Unit Propagation" and so, the performance of SAT Solvers are really bad.
There are other circuit for multiplication which can be used for this purpose, but they produce a larger CNF.


A maximization problem containing summation and multiplication

I think both of your problems are in P.  Here's an algorithm that works in P without any restriction on the $(a_i,b_i)$ pairs.

Formulate your problem as the problem of choosing $x\in\{0,1\}^n$ subject to $\sum_i x_i = k$ so as to maximize
$$\textstyle f(x) = \pi(x) + \sum_i x_i a_i$$
where $\pi(x)=\prod_i \exp( x_i \beta_i)$ and $\beta_i = \ln b_i$.  Relax the problem to allow $x\in[0,1]^n$.

For intuition, note that the function $f(x)$ is convex, so it is maximized over $x\in[0,1]^n$ at some $x\in\{0,1\}^n$. (To see the latter, note that any $x\in [0,1]^n$ with $\sum_i x_i = k$ is the weighted average of integer points $x'$ in $\{0,1\}^n$ with $\sum_i x'_i = k$, and $f(x)$ is at most the corresponding weighted average of $f(x')$ over those integer points, so one of those integer points $x'$ has $f(x') \ge f(x)$.)

Anyhow, find an optimal integer solution $x$ in polynomial time as follows.
The first derivative of $f$ with respect to $x_i$ is
$$\textstyle a_i + b_i\, \pi(x),$$
so (given the constraint $\sum_i x_i = k$), there exists $\lambda$ such that for the optimal $x\in[0,1]^n$,
$$x_i = \begin{cases}
0 & \text{ if } a_i + b_i \pi(x) < \lambda \\
1 & \text{ if } a_i + b_i \pi(x) > \lambda \\
? & \text{ if } a_i + b_i \pi(x) = \lambda.
\end{cases}$$

Furthermore, WLOG there are at most two indices $i$ that are undetermined by the above condition (because otherwise three pairs $(a_i,b_i)$ lie on a single line, a condition that can be broken by an insignificant perturbation of the input).

Given any $x$ and two such indices $i$ and $j$, consider the neighboring points $x'$ and $x''$ obtained by raising $x_i$ to $1$ and lowering $x_j$ to 0, or vice versa.  Since $f$ is convex, one of these points is as good as $x$, that is, $\max\{f(x'),f(x'')\} \ge f(x)$.

Finally, to find the best $S$ in polynomial time, determine the $n\choose 2$ breakpoints $\pi$ such that $a_i + b_i\pi = a_j  + b_j \pi$ for some $i$ and $j\ne i$.  For each such $\pi$, order the indices $i$ by $a_i + b_i \pi$, and take $S$ to contain the first $k$ indices in the order (if there is a tie for the $k$th, there are at most two indices that are tied; try both, giving two sets $S$ for that $\pi$).  Take whichever of these at most $2{n\choose 2}$ sets $S$ gives the largest $f(S)$.


Gap in degree of representations of candidate boolean functions

For symmetric functions (as those you suggest), one may make use of the Minsky-Papert symmetrization technique to get an easy $(n+1)/2$ lower bound for all nonconstant functions.

The idea behind the symmetrization technique is to replace a polynomial $p(x)$ of degree at most $d$ by the symmetric polynomial $\sum_{\sigma \in S_n} p(\sigma(x))$. Then we may find a univariate polynomial $P$ also of degree at most $d$ such that $P(\sum_i x_i)  = \sum_{\sigma \in S_n} p(\sigma(x))$.

Suppose that $f$ is a symmetric non-constant Boolean function. With abuse of notation, write also $f(k) = f(x)$, where $k = \sum_i x_i$.
Let $p$ and $q$ be polynomials such that $p(x)/q(x) = f(x)$ for all $x$ (in particular $q(x)\neq 0$ for all $x$). Then $p(x)=f(x)q(x)$, and hence $\sum_{\sigma \in S_n} p(\sigma(x)) = \sum_{\sigma \in S_n} f(\sigma(x)) q(\sigma(x)) = f(x) \sum_{\sigma \in S_n} q(\sigma(x))$ for all $x$. We may thus find univariate polynomials $P$ and $Q$ such that $P(k) = f(k) Q(k)$ for all $k$. Thus $P(k)/Q(k)=f(k)$. Now we can observe:

The polynomial $P(k)$ must be 0 exactly when $f(k)=0$. This means $\mathrm{deg(p)} \geq \#\{k \mid f(k)=0\}$.
The polynomial $P(k)-Q(k)$ must be 0 exactly when $f(k)=1$ (since q is by assumption never 0). This means $\max(\mathrm{deg}(p),\mathrm{deg(q)}) \geq \#\{k \mid f(k)=1\}$.

It follows that the degree of $p(x)/q(x)$ must always be at least $(n+1)/2$.

For representation by polynomials even better bounds have been proved by von zur Gathen and Roche as well as Cohen and Shpilka. Namely any nonconstant symmetric function must have degree $n$ minus lower order terms.

In any case, the conclusion is, that for symmetric Boolean functions, the largest separation you may hope for is a factor 2.


Does the following type of hitting problem have a name?

I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem  (introduced in this paper by Kortsarz). Roughly, an input to Min-Rep consists of a bipartite graph $G=(A;B,E)$, with each of $A$ and $B$ sub-partitioned into a collection of equal-sized  so-called supervertices. A superedge between two supervertices $a,b$ is the set edges of the form $u,v$ where $u \in a$ and $v \in b$. For a vertex set $S \subseteq A \cup B$, we say $S$ covers superedge $\hat{e}$ if there exists some $(u,v) \in \hat{e}$ such that $\{u,v\} \subseteq S$. The problem is then to find the smallest subset of $S \subseteq A \cup B$ such that all nonempty superedges are covered by $S$. Phrased alternatively, we wish to distinguish (at least) one "witness" edge per nonempty superedge, and the objective function is to minimize the cardinality of the union of the various distinguished edges' endpoints.

Viewed in this light, the connection to your problem is now straightforward. The set of vertices $A \cup B$ will become your ground set $[n]$. The collection of nonempty superedges will become the subset families $\mathcal{F}_i$. If a superedge $e$ contains the edge $(u,v)$, then its corresponding subset family contains the set $\{i,j\}$, where $i$ and $j$ are the images of $u$ and $v$ in this reduction.

There is a clear bijection between solutions the Min-Rep instance and in your original problem, and this bijection preserves objective value. Thus, your problem is at least as hard as Min-Rep to approximate, and Min-Rep is known to be hard to something like $2^{\log^{1-\epsilon} n}$ under standard complexity theoretic conjectures.

Min-Rep is very intimately related to the famous graph label cover problem. My guess is that your problem is also related (or maybe even equivalent) to hypergraph label-cover (probably using a similar reduction), but I'm not familiar with the recent literature in the area, and someone else can probably elaborate on that connection.


Efficient algorithm for testing planarity of the union of two planar graphs

You might be interested in an online algorithm, which is one that processes the input in a serial manner. Here is a paper with fast algorithms that tests planarity after adding an edge or a vertex, and does so much faster than $O(m+n)$ time (it does so in $O(\log{n})$):

http://epubs.siam.org/doi/abs/10.1137/S0097539794280736?journalCode=smjcat

You will be interested in the edge-addition version of this. And you could ask your question with any two edge sets, but since you seem to have info that both $G_1$ and $G_2$ are planar, you can start with the one which is larger, knowing it is planar, then add edges from the other graph one at a time.

In a 'worst case' where $|E_1| = |E_2| = m$, you would have to decide when this $\frac{m}{2}O(\log{n})$ is better or worse than just applying a $O(m+n)$ planarity test.


Probability that a random sorting network works

Here's some empirical data for question 2, based on D.W.'s idea applied to bitonic sort.  For $n$ variables, choose $j - i = 2^k$ with probability proportional to $\lg n - k$, then select $i$ uniformly at random to get a comparator $(i,j)$.  This matches the distribution of comparators in bitonic sort if $n$ is a power of 2, and approximates it otherwise.

For a given infinite sequence of gates pulled from this distribution, we can approximate the number of gates required to get a sorting network by sorting many random bit sequences.  Here's that estimate for $n < 200$ taking the mean over $100$ gate sequences with $6400$ bit sequences used to approximate the count:

It appears to match $\Theta(n \log^2 n)$, the same complexity as bitonic sort.  If so, we don't eat an extra $\log n$ factor due to the coupon collector problem of coming across each gate.

To emphasize: I'm using only $6400$ bit sequences to approximate the expected number of gates, not $2^n$.  The mean required gates does rise with that number: for $n = 199$ if I use $6400$, $64000$, and $
640000$ sequences the estimates are $14270 \pm 1069$, $14353 \pm 1013$, and $14539 \pm 965$.  Thus, it's possible getting the last few sequences increases the asymptotic complexity, though intuitively it feels unlikely.

Edit: Here's a similar plot up to $n = 80$, but using the exact number of gates (computed via a combination of sampling and Z3).  I've switched from power of two $d = j-i$ to arbitrary $d \in [1,\frac{n}{2}]$ with probability proportional to $\frac{\log n - \log d}{d}$.  $\Theta(n \log^2 n)$ still looks plausible.


References to programming languages based on conditional logics

Check these references:

Programming languages CondLP and CondLP+:

Gabbay, Giordano,  Martelli, Olivetti, Sapino, Conditional reasoning in logic programming,  Journal of Logic Programming, Volume 44, Issues 1-3, 1 July 2000, Pages 37-74

Claudia, Oliveira, The implementation of CondLP, Lecture Notes in Computer Science, 1996, Volume 1085/1996, 713-715

Gabbay, Giordano, Martelli, Olivetti, Conditional logic programming, Proc. 11th Int. Conf. on Logic Programming, Santa Margherita Ligure, pages 272–289, 1994.

References to proof theory:

Olivetti, Pozzato, Schwind, A sequent calculus and a theorem prover for standard conditional logics, Journal ACM Transactions on Computational Logic (TOCL), Volume 8 Issue 4, August 2007


What are the different notions of one-way functions?

Usually one-way functions are used for crypto, and so you want that no efficient adversary can invert the function. Identifying efficient adversaries with randomized polynomial-time, you get  the typical notion of security which talks of randomized poly-time machines. But of course you can think of different security notions.

For super-fast crypto, you may want the one-way function to be computable in restricted models. Here a great result by Applebaum, Ishai, and  Kushilevitz shows that a poly-time computable OWF implies a OWF where each output bit depends on just O(1) input bits (which is arguably one of the simplest computational models you can think of).


What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

At first glance this looks like a mistake in Wikipedia (it wouldn't be the first one), but I think the time bound there is actually correct, with two assumptions and one small idea.

The assumption is: the alphabet size is constant, so you can ignore the $b$ factor in the runtime and output size. The second assumption is: you can represent the output DFA as a graph in memory, in a conventional adjacency list data structure (or whatever). So in particular to be able to store an edge from one state to another, you need memory cells that can store up to $n$ bits of information per cell, and (in the standard RAM model) this also means constant-time bitwise operations on these cells.

The idea is: each nonempty set of states of the NFA (corresponding to a single state of the DFA) can be formed by adding one element to a smaller set. So, to compute the transitions for a state $S$: find an element $s$ and a state $R$ such that $S=R\cup\{s\}$. Then, for each input alphabet symbol, compute the transition from $S$ as the bitwise Boolean or of the transition from $R$ (previously computed in the same construction) and the transition from $s$ (in the input NFA). Doing this takes $O(b)$ bitwise Boolean operations per state for a total time of $O(1)$ per state.

In practice, you'd probably rather use the version of the construction that only constructs reachable states, rather than all sets. But when you do it that way you can't be guaranteed to find an element whose removal leaves another reachable state, so your $n$ extra factor in the runtime presumably still applies to this version.


Instances of Noninteractive Zero knowlege Proofs

I'm not sure what exactly you are looking for.

Goldreich's book ("Foundations of Cryptography, volume 1") contains an extensive discussion of non-interactive ZK proofs. So do these lecture notes of Katz (lectures 11-13): http://www.cs.umd.edu/~jkatz/gradcrypto2/scribes.html.

You could also look at this paper: Uriel Feige, Dror Lapidot, Adi Shamir: Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. SIAM J. Comput. 29(1): 1-28 (1999) and references therein.


Calculating the distance to the kth nearest neighbor for all points in the set

Here is a simple trick that might be useful. Consider a random sample that picks every point with probability 1/k. It is easy to verify that with good probability exactly one of your k nearest neighbor would be in the sample. Compute the nearest-neighbor in the sample. Repeat this O( k log n) times. With high probability the k nearest points in the $O(k \log n)$ points computed are the k nearest neighbors to your query. Thus, finding the k nearest neighbor, is equivalent to doing $O( k \log n)$ nearest neighbor queries.

In short, give me a fast data-structure for answering nearest neighbor queries, and I would be happy to give you a fast data-structure of k-nearest neighbor.


Does a chordal graph where the size of minimal separators is constrained have name?

In this paper graphs in which the size of every minimal separator $|S| \le k$ are called graphs of separability at most $k$.

Theorem 1 of that paper implies that chordal graphs of separability at most $2$ are obtained from complete graphs by "gluing" along a vertex or an edge.


Check out Luis Von Ahn at CMU. He is the original Captcha guy. You will find enough videos like this  google techtalk on the subject of Human Computation.


I just came across a relevant paper -- Kloks/Boedlander's "Only few graphs have bounded tree width". They show that almost all graphs with $n$ vertices and $\delta n$ edges have treewidth on the order of $n^\epsilon$, $\epsilon=\frac{\delta-1}{\delta+1}$. For instance $\delta=3$ means typical tree-width grows as $\sqrt{n}$

So even if greedy method found the best decomposition for all graphs, the resulting algorithm would still be intractably slow for typical graphs


What is the VC Dimension of the $k-$Junta class

For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.

The upper bound follows essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log_2$ of that many inputs, we could find a function that avoids all 1-juntas.

To see the lower bound, consider the matrix whose columns contain the $2^{\lfloor \log_2(n+1) \rfloor} - 1 \le n$ not-all-zero bitstrings of length $\lfloor \log_2(n+1) \rfloor + 1$ that start with a zero. The inputs to shatter are the rows of this matrix (padded up to length $n$). Every function of these inputs is either constant, or else it or its negation appears as a column, so it's computed by a 1-junta.

Here's an example for the case $n=7$ which illustrates the general idea. The claim is that the VC dimension of $1$-juntas on $7$ bits is $4$. Consider the matrix

$$\begin{array}{ccccccc}
  0&0&0&0&0&0&0\\
  1&0&0&0&1&1&1\\
  0&1&0&1&0&1&1\\
  0&0&1&1&1&0&1
\end{array}$$

formed by setting the columns to be all the length-$4$, not-all-zero bit strings that start with a zero. The claim is that the rows of this matrix are shattered by 1-juntas.

To see this, let $f$ be any boolean function of the rows. We can regard $f$ as a column. Now observe that either $f$ is constant, or else $f$ or its negation appears as some column in the matrix, simply by virtue of how we defined the matrix. In the first case, $f$ is obviously a 1-junta. In the latter case, suppose $f$ appears as column $i$, and observe that we can therefore compute $f$ as just the $i$-th dictator function. It follows that $f$ is again a 1-junta. A similar argument works when the negation of $f$ appears as a column--we represent $f$ by the negation of the $i$-th dictator. Thus in every case $f$ is a 1-junta. Since $f$ was arbitrary, it follows that the set formed by the rows of the above matrix is shattered by 1-juntas.

This idea can in theory be extended to larger $k$, where you encode every function as some $k$ columns in the matrix. I don't see how best to argue this at the moment, though.


Is there a gap amplification type of result for the Graph Isomorphism Problem?

I do not know if such a thing could exist or not. But it is interesting (and perhaps timely) to note that such a "gap amplification" would likely imply a quasipolynomial time algorithm for graph isomorphism (different than the recently announced one)

In this paper, an approximation algorithm is given for the "MAX-PGI" problem of maximizing matched pairs of edges/non-edges; if we reduce from GI to "Gap-MAX-PGI", then we can approximate to distinguish which side of the gap we are on.

So, I think Dinur's proof of the PCP theorem is unlikely to be directly generalizable to such a "gap amplifier", given the hurdles that would have to be overcome.


Languages that we cannot (dis)prove to be Context-Free

Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${\bf t} = 0110100110010110 \cdots $.  To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that).  But the corresponding result for subwords is still open.


Are there any known NP problems which are conjectured to be exponentially hard on average?

It might be conjectured that the Learning Parity with Noise Problem (LPN) at constant error rate requires time $2^{n^{1-o(1)}}$.  The fastest known algorithm (Blum-Kalai-Wasserman) uses time $2^{O(n/\log n)}$.


Heuristic with worst-case exponential complexity

While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in practice, and in fact it's hard to find examples where they are provably exponential.

Two canonical examples are the simplex algorithm for linear programming and the $k$-means heuristic for clustering.

It seems highly unlikely that you'll be able to show a worst-case running time that's better than exponential for a GA-like heuristic. As Tobias points out, it would be useful to know if there's some kind of guarantee of quality if the heuristic is terminated early - but I'm pessimistic that this can be done as well.


Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

It seems to me that there is some incoherency in the question. What do you mean by better?
Are you looking for a function where $N(f) \ll D(f)$ or a function where $D(f) \ll N(f)$?

Deterministic protocols are a special case of nondeterministic protocols, so we always have $N(f) \leq D(f)$.

For examples of functions where $N(f) \ll D(f)$ have a look at the Nisan and Kushilevitz's book.


Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

These problems are polynomially equivalent.
Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are.
Attach a clique of size $n+1$ to an arbitrary vertex of each graph.
Test whether the resulting graphs are isomorphic or not.
If they are, then we can conclude that there's an isomorphism that maps the respective vertices to each other, thus we can delete them.
By repeating this test $n$ times, we can find (a possible) image for any vertex.
After this, we attach another clique, this time of size $n+2$ to a (different) arbitrary vertex of each original graph, and proceed as before, etc.
Eventually, we'll end up with two graphs that are isomorphic, with cliques of size $n+1,\ldots n+n$ hanging from their vertices, which makes the isomorphism unique.


Does fixed hyperparameters perform well regardless the number of training examples?

No. You're asking about model selection. Larger sample sizes will allow you to choose more complex models. Read up on the keywords overfit/underfit, model selection, Structural Risk Minimization, and in particular this article:
https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=705570


Why has hypercomputation research died down?

It would be better if you specified what you mean exactly by hyper-computation and gave evidence for why you think it has "died down".

In any case, assuming that you are talking about computation of functions over natural numbers (and finite strings) (since I think it is clear that models for higher type computation is a very active area, e.g. CCA) and models of computation not equivalent to computability defined by Turing machines, I don't think the claim is correct, for example see CiE'05 and CiE'11. Also see the criticisms made against the claim that hyper-computation is something new:

Martin Davis, "Why there is no such discipline as hypercomputation", 2006.
Martin Davis, "The Myth of Hypercomputation", in "Alan Turing: Life and Legacy of a Great Thinker", 2004.

If you are interested, there is also some discussion on FOM mailing list starting by Timothy Chow's email about Martin Davis' article.


The following book covers some material related to the proof of the graph minor theorem (Chapter 12).

Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173.

The author states: "[...] we have to be modest: of the actual proof of the minor theorem, this chapter will convey only a very rough impression. However, as with most truly fundamental results, the proof has sparked off the development of methods of quite independent interest and potential."

An electronic version of the book can be viewed online.
http://diestel-graph-theory.com/


For total cost, see http://en.wikipedia.org/wiki/Route_inspection_problem (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.


kmeans++ for arbitrary metric spaces and general potential function

Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false.  I've only given a cursory look at the papers, so please check this carefully to make sure I am understanding correctly, thanks.

Consider a cluster $X$ consisting of a rooted star: a root $r$ and $n-1$ nodes $v_1,v_2,\ldots, v_{n-1}$ such that $d(r, v_i) = 1$ for each $i$, and $d(v_i, v_j) = 2$ for each $i, j$ with $i\ne j$.

$OPT$ takes the center to be $r$, at cost $\sum_{i=1}^{n-1} 1^\ell = n-1$.

But suppose the center $c$ is chosen at random. Then with probability $1-1/n$ the center is one of the $v_i$'s (not the root), and then the cost is $1+\sum_{j\ne i} 2^\ell \ge (n-1)2^\ell$.  So the expected cost is at least $(1-1/n) 2^\ell \,OPT$.

BTW, the published version of the manuscript appears to be here:

https://dl.acm.org/doi/abs/10.5555/1283383.1283494


Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

Observe that the negation of a (monotone) CNF-formula F is a (monotone) DNF G which has the same hypergraph. Moreover #G = 2^n-#F where n is the number of variables of F. Thus, every known (structural) easyness and hardness result for the exact counting on CNF generalizes to DNF.

In other words, counting the number of model of beta-acyclic DNF is easy (from the paper you cite). And it is hard for alpha-acyclic DNF (just add a big clause containing every variables in a CNF).

It is also hard for hypertrees: take a DNF F and construct F' by adding a fresh vertex x in every clause. #F = #F' and H(F') is a hypertree: take T rooted in x and attached to it every other variables as leaves. Observe that this reduction also shows that the problem #(k+1)-DNF restricted to hypertree is harder than #k-DNF so I doubt that you can compile them into OBDD. Moreover, taking k = 2 (already hard for counting), the transformation leads to a hypertree 3-DNF where every edge is a path in the tree so even this restriction is unlikely to yield easy cases.

DNF however differ from CNF as approximating the number of model is possible in the first case (see On the hardness of approximate reasoning Dan Roth - Artificial Intelligence, 1996 for the hardness of approximating and Monte-Carlo Approximation Algorithms for Enumeration Problems
Richard Karp, Michael Luby, Neal Madras).


A special case of the boolean multivariate quadratic polynomial problem

This case is still NP-hard. Suppose we have an instance of 3-SAT:

$F=C_1\wedge\ldots\wedge C_n; C_i=L_{i,1}\vee L_{i,2}\vee L_{i,3}$,

where each literal $L_{i,j}$ is either $V$ or $\neg V$ for some boolean variable $V\in Var$. We can translate this into an equivalent system of equations $f_{i,j}=0$ for $i=1,\dots,n$ and $1\le j\le 4$, where each $f_{i,j}$ is a product of two linear factors, as follows.

Introduce a variable $V'$ for each $V\in Var$, variables $c_i,d_i$ for each clause $C_i$, and an auxiliary variable $z$. For all $i$ and each $1\le j\le 3$, let $t_{i,j}$ be $V'$ if $L_{i,j}=V$, and $(1-V')$ if $L_{i,j}=\neg V$. Then the fact that clause $C_i$ is supposed to be satisfied by a valuation of $Var$ can be split into the conditions:

$(1-c_i)z = (1-c_i)(1-z) = 0$, forcing the value of $c_i$ to be $1$;
$(c_i-d_i)(c_i-t_{i,1}) = 0$, forcing $c_i$ to equal $d_i$ or $t_{i,1}$; and
$(d_i-t_{i,2})(d_i-t_{i,3})=0$, forcing $d_i$ to equal $t_{i,2}$ or $t_{i,3}$.

Together these force at least one of the $t_{i,j}$ to be $1$, corresponding to one of the $L_{i,j}$ being true. Combining these for all $i$ gives a system of equations equivalent to $F$.


Select two numbers that sum to $p$, using sub-linear query time

This is almost certainly impossible.

Suppose you could solve your problem with preprocessing time $P(n)$ and query time $Q(n)$.  Then there is a simple algorithm to solve the 3SUM problem—Given a set of $n$ real numbers, do any three elements sum to zero?—in $P(n)+n\cdot Q(n)$ time.  We pre-process all the numbers, then for each number $a_k$, we find the value of $a_i+a_j$ that is closest to $-a_k$; if it matches $-a_k$ exactly, we have found a solution to the 3SUM problem.

However, the fastest algorithm known for 3SUM runs in $O(n^2)$ time, and this algorithm is widely conjectured to be optimal.  Moreover, there is a matching $\Omega(n^2)$ lower bound in a restricted but natural decision tree model of computation.  For sets of integers, there are slightly subquadratic-time algorithms that "play games with bits", but even in the integer RAM model, 3SUM is conjectured to require $\Omega(n^2/\text{polylog}\,n)$ time.

So assuming that conjecture is correct, your problem either requires (near-)quadratic preprocessing time or (near-)linear query time.


How to quantify the complexity of vectors whose components are real numbers?

You can use LZW or other standard compression methods to approximate the Kolmogorov complexity. In some real-world cases this works well. However, it is dangerous, as it can also be a pretty bad approximation to the true Kolmogorov complexity, viz. http://bactra.org/notebooks/cep-gzip.html.

Another option is to seek the smallest Boolean circuit that outputs a given string. This problem appears to be hard*, but (a) isn't uncomputable like $K(x)$, and (b) doesn't suffer from the potentially erroneous measure given by gzip etc. (since circuits are a standard non-uniform, universal model of computation).

*[Update: It's actually essentially the Minimum Circuit Size Problem, which is looking like it's not $\mathsf{NP}$-hard, but it's still quite hard.]


This problem is actually related to a scheduling problem knows as "Precedence constrained scheduling to minimize weighted completion time". The problem is as follows : Given a set of jobs, where each job has a processing time (p) and weight (w) and a precedence graph is defined on the jobs. Goal is to schedule the jobs in a single machine (non-preemptive) such that the precedence constraints are statisfied and the sum of weighted completion time is minimized. The problem is NP-hard and a 2-approximation is known.

Reduction from minimum cumulative sum problem to Precedence constrained scheduling problem :  For each element create a job with p = 1, w = 0. Also for each set create a job with p = 0, w = 1. Create the precedence graph, such that if element $e \in S$, then $e$ must be scheduled before $S$. I think this special case of the scheduling problem is also NP-hard.

See the following links,

1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf

2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps


How long does it take to find a short cycle in a random graph?

No, you can't beat $\Theta(\sqrt{n})$ queries.  I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms.  This is all anticipated in exfret's answer; I am just filling in some of the details.

Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $i$th edge of vertex $v$'s adjacency list" or "test whether vertices $v,w$ are connected by an edge".  We can assume that no query is repeated, as any algorithm that repeats a query can be transformed to one that never repeats any query.  Similarly, we can assume that the algorithm never does a connectivity query on any pair of vertices that are already known to be connected by an edge (namely, testing $v,w$ when $w$ was previously returned by a fetch query on $v$, or $v$ was previously returned by a fetch query on $w$, or we previously tested connectivity of $w,v$).

Let $E_k$ denote the event that, during the first $k$ queries, no vertex $w$ is returned by more than one fetch-query, and no fetch-query returns a vertex that was previously queried, and that no connectivity-test-query returns "connected".  We'll prove that $\Pr[E_q] = 1-o(1)$ if $q=o(\sqrt{n})$.  It follows that no algorithm that makes $o(\sqrt{n})$ queries can have a constant probability of finding a 4-cycle.

How do we prove this?  Let's compute $\Pr[E_k|E_{k-1}]$.  There are two cases: either the $k$th query is a fetch query, or it is an connectivity-test query:

If the $k$th query is a fetch query on vertex $v$, there are $2(k-1)$ vertices mentioned among the first $k-1$ queries, and if the $k$th query returns one of those then we will have $\neg E_k$, otherwise we will have $E_k$.  Now the response to the $k$th query is uniformly distributed on a set $S$ of vertices, where $S$ contains all vertices that haven't been returned by prior fetch queries on $v$, so the response to the $k$th query is uniformly distributed on a set of size at least $n-k+1$.  The probability of hitting at least one of these is $\le 2(k-1)/(n-k+1)$, so in this case, $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$.
If the $k$th query is a connectivity-test query, then $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$.

In either case, if $q=o(\sqrt{n})$ we have

$$\Pr[E_k|E_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$$

Now,

$$\Pr[E_q] = \prod_{k=1}^q \Pr[E_k|E_{q-1}].$$

If $k \le q \le \sqrt{n}$, then

$$\Pr[E_k|E_{k-1}] \ge 1 - {2q \over n - q},$$

so

$$\Pr[E_q] \ge (1 - {2 q  \over n - q})^q.$$

The right-hand side is approximately $\exp \{ - 2q^2/(n-q)\}$.  When $q = o(\sqrt{n})$, this is $1 -o(1)$.

In conclusion: $\Pr[E_q] = 1-o(1)$ when $q=o(\sqrt{n})$.  It follows that you need $\Omega(\sqrt{n})$ to have constant probability of finding any cycle (let alone a 4-cycle).


Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

Well, the easy answer is that you don't traverse the graph of moves, you just generate a random group element directly.  A non-face-center cubie in an NxNxN cube will have an orbit of size 8, 12, 24 or 48, with 8 being possible only for corner cuties and 12 only being possible for edge-center cubies with N odd.  Divide the cubies into orbits, then generate a random permutation for each orbit with the restriction that the total permutation across all orbits must be even.  Then generate orientations for all edge and corner cubies, with a mod-2 parity restriction on each edge orbit and a mod-3 parity restriction on the corners.
I believe that covers all of the parity issues with the order-N Rubik's cube group, which means this method would generate random cubes uniformly distributed across the group.
This takes $O(N^2)$ time.


Which algorithms can be expressed using a total functional language with data parallel operators?

You might want to look at the old programming language NESL which took these ideas seriously. The language is based on operations on collections, essentially lists and lists of lists and so forth, but I think trees and graphs were also considered, via tricky encodings. Some of the research done in that project (in the mid 1990s) could help answer your question. The PhD thesis (available as a book) Guy E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990 may provide some answers. It was some time ago since I looked at it.

Work done on the Bird-Meertens Formalism (BMF) falls into this category too, as did the language Charity. From the Charity wikipedia page it says that the language is not Turing complete, but can express Ackermann's function, which means that it's more than primitive recursive. Both BMF and Charity involve operators like folds and scans (catamorphisms, anamorphisms, etc), and they have their roots in Category Theory.

I short, imprecise answer is that you can express quite a lot.


The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.

Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:

Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.

Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.


Blum, Shub, and Smale proved that membership in the Mandelbrot set is undecidable in the Real RAM model of computation (known in some upstart circles as the BSS model).

The high-level argument is one sentence long: Any Real RAM computable set is the countable union of semi-algebraic sets, so its boundary has Hausdorff dimension 1, but the boundary of the Mandelbrot set has Hausdorff dimension 2.  By the same argument, almost every interesting fractal is uncomputable in the real-RAM model.


Is Prime Bounded Quadratic Congruence NP-complete?

This problem can be solved in randomized polynomial time. Look at this:

https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Therefore, if Prime Bounded Quadratic Congruence would be in NP-complete, then RP = NP.

Consequently, the answer of this question is an outstanding problem in complexity theory, so it is not worth to ask it here...


Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

Any separation of classes closed under "polynomial resources" has an oracle making them equal. (This is provided the oracle mechanism is fair and allows both machine models to make polynomial length queries and no more.)

Let $TC0^{O}$ be "$TC0$ with gates for oracle $O$". Letting $O$ be a $PSPACE$-complete language under $TC0$ reductions, we have $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$, where  in the oracle mechanism for $PSPACE$, we count the space usage of the oracle tape along with the rest of the memory. (So only polynomially length queries are asked.) Such an equality holds for many classes "closed under polynomial resources", in the sense that they can ask polynomially length queries to an oracle, but no larger. These classes include stuff like $AC0$, $TC0$, $LOGSPACE$ (under a different oracle mechanism which does not count oracle queries towards the space bound), $P$, $NP$, $PH$, and $PP$. So any separation of classes in this list must necessarily use some kind of "non-relativizing" argument. This also implies (for example) that the natural proofs of things like Parity not in $AC0$ are non-relativizing (but this is even easier: all you need here is an oracle for parity, so you get $AC0[2]$).

In the collection of proofs you cite, I believe most of them (if not all) work by assuming $TC0 = PP$ and deriving a contradiction. These kinds of results are called "indirect diagonalization". So a relativization of their proof would have to say: "if $TC0^{O} = PP^{O}$, then contradiction..." but this assumption is actually true for some oracles $O$.

In the comments, it was pointed out that $LOGSPACE^{O} = PSPACE^{O}$ in the way that I am using it. These are just subtleties with the oracle mechanism. On the LOGSPACE side, the query tape cannot be part of the space bound, since queries are polynomial length. On the PSPACE side, the query tape is taken as part of the space bound. That was to make things "fair". But if you give them exactly the same oracle mechanism then indeed you can separate them again by diagonalization. For instance, if queries do not count towards the space bound, then in PSPACE^{PSPACE} you can ask exponentially long questions to PSPACE, so this in fact contains EXPSPACE. I apologize for not saying this explicitly earlier.

Space-bounded computation is very subtle with respect to oracles. See page 5 of this article by Fortnow for a good summary of why oracle and space-bounded computation don't always mix.


Early References for Transition System Semantics of Programs

Landin's SECD machine, originally described in The mechanical evaluation of expressions in 1964, is a transition system in the form of an abstract machine, later inspiring lots of of other abstract machines such as the CESK machine.


Current tightest bounds for critical 3-SAT density

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.

The unsatisfiability threshold is known to be at most 4.4898, a slight improvement since Maneva's 2001 thesis.

J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz.  On the satisfiability threshold of formulas with three literals per clause, Theoretical Computer Science 410, 2009, 2920–2934. doi:10.1016/j.tcs.2009.02.020 (preprint from one of the authors)

The satisfiability threshold is known to be at least 3.52, which is unchanged from the time of Maneva's thesis.

A. C. Kaporis, L. M. Kirousis, E. G. Lalas.  The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Random Structures and Algorithms 28, 2006, 444–480.  doi:10.1002/rsa.20104

These bounds were recently cited by Achlioptas and Menchaca-Mendez as the best known to date.

D. Achlioptas, R. Menchaca-Mendez.  Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method, ICALP 2012, LNCS 7391, 1–12.  doi:10.1007/978-3-642-31594-7_1


Finding a basis for quantum measurement with maximum distinguishability

I figured out what I missed. $\Delta Fidelity=\frac{1}{2}\left(r_x-r_z\right)$ is indeed correct. However, what I missed was the fact that $r_z$ could be less than 0, since the only requirement is that $\left|\vec{r}\right|\le1$. Therefore, to achieve the maximum value of $\Delta Fidelity$, we set $r_x=\frac{1}{\sqrt{2}}$ and $r_z=-\frac{1}{\sqrt{2}}$. This means the actual correct answer is $|\psi\rangle=\frac{|+\rangle+|1\rangle}{2cos\left(\frac{\pi}{8}\right)}$, because a density matrix with $r_z=-1$ and $r_x=r_y=0$ is the density matrix of the $|1\rangle$ state, and the state $|\psi\rangle$ is a midway state between $|+\rangle$ and $|1\rangle$.

Thus, the general approach I took was correct, but I initially failed at performing mathematical optimization in my head.


References on model checking and pi calculi

For the $\pi$-calculus, the following texts should be of interest. [1] is a relatively gentle introduction while [2] summarises the state of the art about 10 years ago. A lot  of progress has been made since, but that's not yet written up in a textbook. The original papers [3] are also quite readable but contain much detail that may overwhelm a novice (or may be instructive, since it's usually omitted in later accounts). Milner has written a little tutorial [4]. Finally, if you have not encountered process theory, the original CCS book [5] might be a good place to do so. It deals with CCS, a predecessor to the $\pi$ calculus, and key technical ideas in the theory of $\pi$-calculus like bisimulation are explained in a simpler setting.

Regarding the spi-calculus, I suggest to look at the original paper [6], but note that the spi-calculus has largely been superseded by the applied pi-calculus [7]. The applied pi-calculus is widely used in modelling cryptographic protocols. [8] is a tutorial of applied pi.

Communicating and Mobile Systems: The $\pi$ Calculus, by R. Milner.
The $\pi$-Calculus: A Theory of Mobile Processes, by D. Sangiorgi and D. Walker.
A Calculus of Mobile Processes, Part 1 and Part 2, by R. Milner, J. Parrow and D. Walker.
The Polyadic pi-Calculus: A Tutorial, by R. Milner.
Communication and Concurrency, by R. Milner.
A Calculus for Cryptographic Protocols The Spi Calculus, by M. Abadi and A. Gordon.
Mobile values, new names, and secure communication, by M. Abadi and C. Fournet.
Applied pi calculus, by M. Ryan and B. Smyth.

If you spell out the ideas you are looking for, maybe we can give you more focussed reading recommendations.


I use these 3 slides to show why it so hard (impossible?) to come up with a fast algorithm for an NP problem:


How does Theoretical Computer Science relate to security?

Your intuition that "insecurity" is due to software that is "too useful" is correct, in a sense. There is a large and growing theoretical literature on "differential privacy" that formalizes your intuition. See for example, here: research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf

Here, we think of the input to an algorithm as being a "database", and the algorithm is "insecure" if it reveals too much information about any one person's data in the database. An algorithm is $\epsilon$-differentially private if the algorithm's output does not depend much on any one input: specifically, changing a single entry in the input database should only change the probability of any output of the algorithm by at most an $e^\epsilon$ factor.

Of course, making an algorithm private makes it less useful: a $0$-differentially private algorithm produces outputs that aren't even a function of the inputs at all! But it turns out you can try and carefully balance the tradeoff between privacy and utility, and can get very private algorithms that nevertheless are very non-trivially useful.


Characterizing closure under expansion/reduction for big-step semantics?

The notion of "next" and "last" - prior to the idea of "expansion" and "reduction" - are  essentially lost when we read a big-step operational semantics as an inductive definition, which is too bad because the way we usually prove things about big-step operational semantics is by reading it as an inductive definition!

You can prove a "full expansion" property (big step preservation) that $e \Downarrow v$ and $e \in R$ imply $v \in R$, and then observe that the proof of this property actually proves a small-step expansion property. This is because computational structure of the proof actually recovers the small-step evaluation process that Prolog/Twelf would use to execute the big-step semantics as a logic program! But for appropriately tricky semantics (especially non-deterministic ones), I've noticed it's frequently the case that you can prove a big-step property when it doesn't hold for the small-step evaluation process that Prolog/Twelf proof proof search would imply.

In my view, the best option - if we want to use big-step specifications but recover the information that was lost when we treated the big-step semantics as inductive definition - to characterize the small-step evaluation process that Prolog/Twelf would use. (This ends up basically or exactly being an abstract machine semantics.) This may not be satisfying depending on what it is you're trying to do, of course. There are a couple of versions of this: see Hannan and Miller or Ager, for instance. (There's also a bit about this in my thesis, some work I did with Ian Zerny, but I'll link to that when there's a thing to link to.) You could also carefully characterize a set of partial derivations of $e_1 \Downarrow v_1, \ldots, e_n \Downarrow v_n \vdash e \Downarrow v$ that corresponded to partial executions, but when I've contemplated this the details have seemed fraught enough that the abstract machine interpretation seems like a safer bet.


Is predicting (in the limit) computable sequences as hard as the halting problem?

Actually this is easier than solving the halting problem.

Let $f:\mathbb N\rightarrow\mathbb N$ be a function that dominates all computable functions, i.e., for all total computable functions $g:\mathbb N\rightarrow\mathbb N$, we have that for all but finitely many $n$, $g(n)\le f(n)$. It is a standard fact that there exist such functions that have strictly lower Turing degree than the halting problem, see e.g. Soare's book Recursively Enumerable Sets and Degrees. These are called the high Turing degrees.

Let $\varphi_e$, $e\in\mathbb N$ be a standard list of the partial computable functions from $\mathbb N$ to $\{0,1\}$.

Now, using $f$ we construct a predictor $p$.

$p(a_0,\ldots,a_{k-1})$ is chosen as some number $a_{k}\in \{0,1\}$ so as to make the sequence $a_0,\ldots,a_k$ agree with $\varphi_t(0),\ldots,\varphi_t(k)$ for the minimal possible $t\le k$. Since we cannot wait for possibly hanging computations to halt, we only monitor the computations until stage $f(k)$ ($f(k)$ many computations steps). If there is no such $t$ we just set $a_{k}$ arbitrarily (say $=0$).

Now suppose $q$ is minimal such that $\varphi_q$ computes the computable sequence that is actually observed. Then we will for all but finitely many $k$ use $t=q$ and hence choose the correct $a_{k}$, because $f$ dominates the running time function for $\varphi_q$, namely $s(n)=$ the least stage where $\varphi_q(n)$ has halted.


Here is the first part of the answer (without swapping).  I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question.

Introduction to the problem and its practical importance

I do not know the motivation for the question, as it was not given.
However this is a known problem of natural language processing (NLP),
and specifically of speech processing. The problem is that phonems are
not always clearly identifiable, nor are the boundaries between
lexical elements (words), which is a little bit more general than the
question. As a consequence, there can be several ways to cut the
spoken sentence into words of the language. In order to account for
that, the single linear stream of phonems is actually transformed into
what is called a "word lattice" which may be seen as a
directed acyclic graph or as an acyclic DFA (though even the
acyclicity is also a topic for discussion in some cases - see my
remark on whether the empty word can be in $W$). This word
lattice corresponds to all the ways the sentence can be cut into
recognizable words. This is often based on probabilities and Markov
models.

Well known examples of the need for word lattices are holorime
verses. See for example "Phonological ambiguity that changes the syntactic structure".

The word lattices are then used in various way for further linguistic
processing. One use is to do syntax analysis with respect to a
syntactic definition of the language, the identified lexical elements
(or their lexical category, called "part of speech") being used as
alphabet symbols at that syntactic level. In the question asked, the
collection $S$ or sentences plays the role of the language syntax that
defines allowed sentences. The set $W$ is the collection of acceptable
spoken language words that can be built from the phonems in $\Sigma$.
It is a bit simplified from the real speech processing situation. For
example, the set $W$ is finite, while in speech processing it is
considered open (actually finite, but so large ...). This is dealt with
by replacing all the words of a given category by that category
considered as a whole (I skip many details).

Many modern parsing techniques can be readily extended to the parsing
of word lattices, as most syntactic formalisms are closed under
intersection with regular sets. See for example "Recognition can be
Harder than Parsing".

The problem addressed by word lattices (and by this question) is lexical
ambiguity: the ambiguity resulting from the fact that the sequence of
lexical elements that can correspond to the analyzed string is not
unique. This can be opposed to syntactic ambiguity du to the fact that the
lexical sequence can be generated syntactically in two different ways,
as in ambiguous context-free grammars.

The issue of character swapping, here supposedly to detect
"spoonerisms", is part of various techniques to deal with input
ill-formedness that can be modeled by finite state tranducers.
Here again, closure properties are more than helpful.

A solution without swap, linear in each parameter

The set $W$ may be considered finite, as only a finite number of words
in $W$ can be used to form the alphabet for sentences. We assume
furthermore that the empty word is not in $W$. It is not strictly
necessary for the construction given here, but it could make the
parsing yield an arbitrarily long sequence, independently of the
length of the string $w$ being parsed, possibly giving a false idea of
the complexity.

We associate with each word $w\in W$ a unique symbol $\hat w$. Let
$\hat W=\{\hat w \mid w\in W\}$. This is not strictly necessary, but may
avoid confusion as to what is the alphabet.

Then you build a trie, as a DFA that recognizes the words in $W$. Each
final state recognizing a word $w_k\in W$ is then labeled with $\hat w_k$
(cf Moore machines). Then an $\epsilon$-transition is added from each
final state to the initial state, turning the DFA into a NFA that
recognizes sequences of words in $W$, and which can output $\hat w_k$
whenever $w_k$ has been recognized. Then you apply the powerset
construction to turn this NFA into a DFA $T_W$, such that the states of this new
DFA have all the labels of the trie final states they contain.

This construction, though expensive because of the powerset
construction, is done only once, independently of the sentence $w$,
and thus does not count in the complexity analysis. It is amortized over all string $w$ that will be parsed (as is the case for all parser construction techniques).

Given a string  $w\in\Sigma^*$
you build a DFA $L_{W,w}=(\{q_i\mid 0\leq i\leq |w|\},\hat W,q_0,q_n,\tau_{W,w})$ as follow:

$q_0$ and $q_n$ are respectively initial and final state
the number of states is $n+1$
there is a transition on input $\hat w_k$  from state $q_i$ to state
$q_j$ iff $w[i:j]=w_k$ where $w_k \in W$

The notation $w[i:j]$ denote the substring of $w$ from index $i+1$ to
index $j$, the first letter having index $1$.

This finite state automaton $L_{W,w}$, called a word lattice in speech
processing, generates or recognizes all sentences that are sequences
of words in $W$ that concatenate into the string $w$. Note that the literature often presents it as a directed acyclic graph rather than a DFA.

To build the transitions, you apply the DFA $T_W$ to the string
$w$. Whenever you enter a state that has a label $\hat w_k$ (It may
have several labels), it means
that you have just recognized the string $w_k\in W$. If you have read
$j$ letters, it means that $w[i:j]=w_k$ for $i=j-|w_k|$. Thus you add
the corresponding transition to the word lattice.

The DFA $T_W$ executes no more than $|w|$ transition steps, and at
each step adds at most $|W|$ transitions to the word lattice.
Hence the complexity is $O(|W|\times|w|)$

Now we have to find out which sentences in the language recognize by
the language of $L_{W,w}$ are also recognized by the DFA $M_S$ on alphabet
$\hat W$ recognizing $S$.

In other words we want the intersection of the two languages. This can
be obtained by the usual cross product construction of the two
automata, which are both DFA. The resulting automaton is a recognizer
for the solutions, and can be used to generate them non
deterministically.

Since the set $S$ is a regular set, potentially infinite, each
solution must be given explicitely as a word in $\hat W^*$, with
corresponding cost, rather than being named in constant time.
However, if the empty word is not in $W$, the length of each solution
is bound by the length of $w$.

The cross product construction gives a number of states that is the
product of that number for each automaton: $|Q_S|\times(|w|+1)$.
Each of the $|\tau_S|$ of the DFA $M_S$ is associated with each of the
$O(|W|\times|w|)$ transitions of the word lattice to determine the
transitions of the cross product.

Hence the cost of producing the DFA for the solutions is $O(|W|\times|w|\times|M_S|)$

The cross-product DFA is noted $F_{W,S,w}$. Its construction is such
that its mimics exactly the DFA $S$, but only for the sentences in
$\hat W^*$ accepted by the word lattice, i.e. all those corresponding
to the sentence $w$. Hence, it does give all the sentences in $S$ as
words in $\hat W^*$ that are equal letter-wise to $w$.

Enumerating the solutions

Here is how you can enumerate the solutions with the DFA $F_{W,S,w}$
to be conformant to the constraint that the enumeration should be
linear in the size of a trie of all solutions.

We suppose the symbols in $\hat T$ are totally ordered, for example by
the lexicographic order of the corresponding words in $T$.  We also
assume that the DFA $F_{W,S,w}$ has been pruned of all states that do
not have a path to an accepting state, and of transitions to and from
these states (this does not have to exceed the cost of building the
DFA). The missing transitions will be considered as virtually going to
a dead state; they are not needed here.

Let $d$ be the length of the string $w$. Since we
excluded the empty word from $T$, all solutions have a length less
than $d$. Hence the DFA $F_{W,S,w}$ is acyclic, i.e. represented by an
edge labeled DAG.

Initialize an array $\mathcal S$ of length $d$, indexed from 1 to $d$, storing
the words to be enumerated, and a cursor $c$ indexing the last
modified letter of $\mathcal S$.

Initialize a second array $\mathcal Q$ of length $d+1$, indexed from 0
to $d$, storing the states followed to produce/recognize the current
content of $\mathcal S$. The cursor $c$ indexes also the last visited
state.The array $\mathcal Q$ is initialised with the initial state of
the DFA $F_{W,S,w}$ at index 0.

Both arrays are used as pushdown stacks, the cursor $c$ pointing at
the top.

Then perform a simulation of a Depth First Search (DFS) on a virtual
version of the trie of all solutions recognized by the DFA
$F_{W,S,w}$, by updating only the top of the stacks.

When a transition of the DFA is followed, its label is pushed on
$\mathcal S$ and the next state is pushed on $\mathcal Q$.

When a state $q$ has just been pushed on the stack $\mathcal Q$:

If $q$ is an accepting state the content of stack $\mathcal S$ is a
solution;
if $q$ has transitions, follow the one with the smallest label;
if there are no transitions, then pop both stacks.

When the stacks are popped, let $\hat w$ be the symbol just popped
from $\mathcal S$, and $q$ be the new top of $\mathcal Q$.

if $q$ has transitions with a label greater than $\hat w$, follow
the one with the smallest label;
otherwise pop both stack.

When all transitions of the initial state at the bottom of stack
$\mathcal Q$ have been followed, the enumeration terminates.

This algorithm is essentially a virtual traversal of the trie of all
solutions, because the finite automation $F_{W,S,w}$ is deterministic
and pruned of unproductive states and transitions. Therefore the time
cost is linear in the size of that trie. The solutions are given in
lexicographic order with respect to $\hat V$.

However, though I have not explored the issue, I fear that the size of
that trie may far exceed the size of the DFA $F_{W,S,w}$. Even if S is
finite, it may be represented by a DFA that is much smaller than its
trie (precisely our problem).

Note:
$S$ does not have to be a regular set.

The essential ingredients for the solution presented and its
complexity are the deterministic real-time character of the automaton
and the cross product construction. Hence it should be applicable with
the same complexity result if $S$ were a real-time deterministic
context-free language.

More generally, all kinds of languages families may be considered,
with a complexity that depends on recognition complexity of the
family.
For example, if $S$ is a context-free language,
then the complexity for $|w|$ is at worst $O(|w|^3)$. But things get
then more complex: parsing with respect to a regular set for $S$ just
means recognizing $\hat W$-strings in $S$ that expand to the word $w$.
However, if S is a context-free language, one may be satisfied with a
recognizer as in the regular case, but one may also want to have some
or all parses with respect to a specific grammar which may itself be
ambiguous. The complexity analysis may then depend somewhat on what is
actually desired, on language properties or on grammar properties.
And this extend to a variety of other grammatical formalisms.

Allowing to swap letters

To come later. It can be done also with finite state techniques.


Techniques for proving that a sentence relativizes

Normally, the way people prove that a complexity theorem relativizes is using the following two-step procedure:

Prove the theorem.
Observe that your proof relativizes!  In other words, that nothing in the proof changes at all if all the machines mentioned in the proof get access to the same oracle A.

Yes, it's really as simple as that.  To make it rigorous, you should rewrite the whole proof adding superscripts of "A" all over the place.  In practice, though, if people notice this issue at all, they'll usually just add a remark like "this result is easily seen to relativize."

If people seem cavalier about this, it's because they've learned, from experience, that only certain techniques (such as arithmetization) can possibly cause a proof not to relativize.  So if your proof doesn't use those techniques, then it relativizes.

(A close analogy: suppose you prove a theorem about real numbers, but your proof never uses anything about the reals other than the fact that they're a field.  Then it suffices to note that fact, to show that an analogous theorem must hold for complex numbers, p-adics, etc.  There's no need to redo the proof.)

The one situation where more discussion is necessary, is where it's not even obvious what it means to relativize your theorem.  (E.g., what's the oracle access mechanism?)  As Kaveh pointed out above, there's no well-defined mathematical operation of "relativizing" a complexity theorem, just like there's no well-defined mathematical operation of "complexifying" a theorem about real numbers.  Notice that, in the latter case, it's not enough to replace every occurrence of R by C: you probably also need to replace x2 by |x|2 (in some places, not others!), and make other changes that are "obvious" to a mathematician but hard to list formally.  Likewise, in complexity theory, it's usually obvious what it means to "relativize" a theorem (i.e., who should get access to A, and what does it mean for them to access it?), but in some cases it can be quite subtle.  See here for more about this issue.

Turning your question on its head, one could ask:

Is there any example of a relativizing complexity theorem, for which it's significantly harder to prove that the theorem relativizes than that the theorem is true?

Interestingly, I can't come up with a single indisputable example (though maybe someone else can)!  Here's the best I can do:

Recent work on blind and authenticated quantum computing (by Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani, and others) might lead to examples.  In those cases, the situation is that we don't know whether the theorems relativize or not---but if they do relativize, then certainly a new idea will be needed beyond what's in the existing proofs.
Arguably, another example might be the random self-reducibility of #P.  If you asked most complexity theorists why that was true, they'd probably say it's because the permanent is both #P-complete and random self-reducible.  That's true, but it doesn't answer the question of whether #P is rsr relative to any oracle.  Well, it turns out that #P is rsr relative to any oracle, and it's not even hard to prove it---but you need to give a direct argument using polynomials, rather than appealing to properties of the permanent.
In Section 8 of my and Avi Wigderson's algebrization paper, we showed that the GMW theorem (that NP has computational zero-knowledge proofs) is algebrizing.  And that really did take new ideas: not "dramatically" new, but certainly nowhere to be found in the usual proofs of the GMW theorem.  Of course, this is for algebrization rather than for relativization.

Addendum: In answer to a further question of the OP, I don't know of any techniques whatsoever for showing that, if you could prove a certain complexity conjecture (which you haven't yet), then your proof would necessarily relativize.  Yes, as long as you restrict your "search for a proof" to relativizing techniques only, you can be sure that, if you ever succeed in finding a proof, then your proof will necessarily relativize.  And in practice, that's often what people do (e.g., because they have certain ideas about what a proof would look like, and those ideas relativize).  But I don't know of any way to guarantee, a priori, that by broadening your search to include non-relativizing techniques, you couldn't find a proof that had eluded you before.


Running multiple rounds of a BQP computation, without multiple measurements?

The principle of deferred measurement (see https://en.wikipedia.org/wiki/Deferred_Measurement_Principle) tells us that measurements in the middle of a quantum computation can be simulated by using additional quantum gates instead. In particular, instead of measuring a qubit, we can apply a CNOT gate to that qubit and another qubit (which is used only at this point of the computation).


You linked to two papers, both with conjectures.  I presume you mean Grohe's 2007 conjecture.

This question was answered in 2008:

  Theorem 5. CSP(C$_0$,_) is in NP, but neither in P nor NP-complete (unless P = NP).  Moreover, the set C$_0$ can be decided in deterministic polynomial time.

Manuel Bodirsky and Martin Grohe, Non-dichotomies in Constraint Satisfaction Complexity, ICALP 2008.  doi:10.1007/978-3-540-70583-3_16 (PDF)

The idea is to blow holes in the instance sizes of CLIQUE, by the same delayed diagonalization technique introduced by Ladner for his theorem.  Note that the set C$_0$ contains arbitrarily large cliques, and the fractional hypertree width of an $n$-clique is $n/2$.  So it is possible to have CSPs of the form CSP(A,_) that are of intermediate complexity, where A has unbounded fractional hypertree width.  This answers Grohe's conjecture in the negative.

At the same conference Chen, Thurley, and Weyer had a paper with a similar result, but that required strong embeddings so technically wasn't of the right form for the conjecture.

Yijia Chen, Marc Thurley, and Mark Weyer, Understanding the Complexity of Induced Subgraph Isomorphisms, ICALP 2008.  doi:10.1007/978-3-540-70575-8_48 (PDF)

Finally, any class of CSP instances can be transformed into a representation with worst-case fractional hypertree width.  In many cases this transformation is polynomially bounded in size and can be done in polynomial time.  This means that it is easy to generate CSPs with unbounded fractional hypertree width, even modulo homomorphic equivalence.  These CSPs are not going to be of the form CSP(A,_) since the target structures are special, but they do provide a neat reason why the CSPs defined by restricting just the source structures are not all that interesting: it is often just too easy to hide the tree-like structure of a CSP instance by changing the representation so that the source structure has large width.  (This is discussed in chapter 7 of my thesis.)


Think of $\Sigma^{*}$ encoding some sort of objects, and $Q$ as the set of all objects satisfying some property. Think of $P$ as a function which accepts (the encoding of) a pair $(x, p)$ where $x$ is an object and $p$ is alleged "evidence" of $x \in Q$. The function $P$ is a "proof checker": it verifies that $p$ actually represents valid evidence that $x \in Q$. If so, it returns $x$, otherwise it returns a default element of $Q$.

As an example, suppose $\Sigma^{*}$ encodes graphs and let $Q$ be the set (of encodings) of Hamiltonian graphs. A possible $P$ is this: decode input as $(G, \ell)$ where $G$ is a graph and $\ell$ is a list of vertices of $G$; verify that $\ell$ is a Hamiltonian cycle in $G$; if so then return $G$ otherwise return the graph on one point.

You considered the case of planar graphs. To get a suitable $P$ we need a notion of poly-time checkable evidence of planarity.

In general the input to $P$ need not encode a pair $(x, p)$. The important thing is that $P$ can extract two pieces of information from its input: the object in question and the alleged evidence that the object belongs to $Q$. For example, let us take as $Q$ the set of all sentences provable in some first-order theory. Now $P$ decodes its input as a formal proof. If the encoding is invalid, it returns $\top$. If the encoding represents a valid proof, it returns the statement that was proved by the proof (which is likely to be the root of proof tree, or the last formula in a sequence of statements, depending on how you formalize proofs).


Assignment problem with sum replaced by max

In the geometric setting, where $C(x,y) = \|x - y \|$, this formulation is called the bottleneck matching problem. It's possible that this is the generic term for it (I've seen this formulation used in the Kleinberg-Tardos algorithms book for MSTs).


Advanced techniques for determining complexity lower bounds

Lower bounds for algebraic circuits
In the setting of algebraic circuits, where a lower bound on circuit size is analogous to a lower bound on time, many results are known, but there are only a few core techniques in the more modern results. I know you asked for time lower bounds, but I think in many cases the hope is that the algebraic lower bounds will one day lead to Boolean/Turing machine lower bounds. These results often use deeper techniques from "pure math" as you put it.
I. The degree bound.
Strassen showed that the log of the degree of a certain algebraic variety associated to a (set of) function(s) is a lower bound on the algebraic circuit size of computing those functions.
II. Connected components (or more generally the dimension of any higher homology group).
Ben-Or showed that the size of a real algebraic decision tree deciding membership in a (semi-algebraic) set is at least $\log C$ where $C$ is the number of connected components of that set. Ben-Or used this to prove an $\Omega(n \log n)$ lower bound on sorting (well, element distinctness, but element distinctness reduces to sorting) in the real algebraic decision tree model. Yao extended this from connected components to the sum of the Betti numbers and proved optimal lower bounds for other problems (like $k$-equals)). In a different paper Yao extended this to algebraic decision trees over the integers.
III. Partial derivatives.
This has been the workhorse of many of the modern algebraic circuit lower bounds. I believe partial derivatives were first used to prove a lower bound by Baur-Strassen, where they showed that computing all the first partials of $f$ can be done in size $5s$ where $s$ is the size needed to compute $f$. Combined with Strassen's degree bound, this gave $\Omega(n \log n)$ size lower bounds on various functions, which are still the strongest lower bounds on the size of unrestricted arithmetic circuits for an explicit function.
The more recent use of partial derivatives seems to stem from a paper of Nisan's in which he proved lower bounds on noncommutative circuits by considering the dimension of the space of all partial derivatives. This was used to prove lower bounds on restricted kinds of depth-3 circuits by Nisan-Wigderson, and similar ideas were used to prove lower bounds on multilinear formula size by Raz (and related models by Raz and collaborators). The very recent depth 4 and depth 3 lower bounds by Gupta, Kayal, Kamath, and Saptharishi use a generalization of this idea, to count the dimension of the space of "shifted partial derivatives" - where you can take partial derivatives and then multiply by any monomials of a given degree.  Improving the GKKS result to a super-polynomial size lower bound on permanent (which would imply $\mathrm{VP} \neq \mathrm{VNP}$) may "just" be a matter of getting a better understanding of the ideal generated by permanental minors (see the conjecture at the end of their paper).
IV. Defining equations for varieties.
The idea here is to associate to "easy functions" a certain algebraic variety, find equations that vanish on this variety, and show that these equations do not vanish on your "hard function." (Hence proving that your hard function is not in the variety of easy functions, so that it's actually hard.) Especially useful in lower bounds on matrix multiplication. See Landsberg--Ottaviani on the arXiv for the latest, and references to prior lower bounds.
(In fact, I, II, and III above can all be viewed as special cases of finding defining equations for certain varieties, though the proofs that use I,II,III are essentially never phrased that way, as there wasn't really a need to.)
V. Representation theory, esp. as in geometric complexity theory.
Actually, also used by Landsberg--Ottaviani to find some equations for a certain variety. Also used by Burgisser-Ikenmeyer to get a "purely" representation-theoretic proof of a slightly weaker lower bound on matrix multiplication. Conjectured by Mulmuley and Sohoni (cf. "Geometric Complexity Theory I & II") to be useful to resolve $\mathrm{VP}$ vs $\mathrm{VNP}$ and ultimately $\mathrm{NP}$ vs. $\mathrm{P/poly}$.


If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891.
Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be augmented to a $2k$-regular graph $G'$ (by adding extra vertices and edges if necessary) and any 2-factorization of $G'$ restricts to a relaxed edge coloring of $G$.
So relaxed edge coloring is easy: the optimal number of colors is always $\lceil\Delta/2\rceil$.


When is the duality gap of semidefinite programming (SDP) zero?

There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition.  This is due to Ramana.  (For another take on this involving SOS, see [KS12].)  To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me.

One notable consequence of this work is that the problem of testing whether a given SDP is feasible is in NP if and only if it is in coNP.  (However, I think the experts expect the problem is in neither.  The best upper bound known is PSPACE.)


state-of-the-art bit complexity of the determinant

Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operations
http://dx.doi.org/10.1016/j.jco.2005.04.002

Prior to this, Kaltofen and Villard gave improved algorithms, see
http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1


Hardness of approximating fractional chromatic number on bounded degree graphs

Yes.

If I understood correctly, the proof of Theorem 1.6 in Khot (2001) establishes that it is NP-hard to distinguish between the following two cases, even if we focus on bounded-degree graphs of sufficiently high degree:

There is a $k$-colouring.
The ratio of the number of vertices to the maximum size of an independent set is at least $k^{\log(k)/25}$.

From the perspective of fractional chromatic number these two cases are:

The fractional chromatic number is at most $k$.
The fractional chromatic number is at least $k^{\log(k)/25}$.

Now we must remember that we need sufficiently high degrees (as a function of $k$). But as far as I can see, the proof has, e.g., the following convenient corollary that might already be sufficient for your purposes:

Given any constant $\alpha$, there are constants $\Delta$ and $c$ such that the following problem in NP-hard: given a graph $G$ of maximum degree $\Delta$, decide whether the fractional chromatic number of $G$ is at most $c$ or at least $\alpha c$.

An of course this already implies that there is no PTAS, unless P = NP.


I used to store them in a SVN repository, and then I found out about Mendeley, quite satisfying so far except for a few bugs. Different features are available depending on whether or not you want to pay some fee, but the free version is enough for many people -- it seems it would be for you.


PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

Each of the papers shows that there is a polynomial-time approximation scheme (PTAS) for the problem it studies if the input instance is Euclidean and that there is no PTAS if the input instance is arbitrary (if P≠NP).


Optimal greedy algorithms for NP-hard problems

The method of conditional expectations (for derandomizing the "random assignment" algorithms for Max-Cut and Max-SAT) can be viewed as a greedy strategy: for $i=1,\ldots,n$, you pick the value of a variable $x_i$ such that the expected number of constraints satisfied in the resulting reduced instance exceeds the expected number of constraints satisfied in the current instance. (In fact, the greedy algorithm for $1/2$-approximating Max-Cut is the same as the "method of conditional expectations" algorithm for $1/2$-approximating Max-Cut.)

Since the method also works for Max-E3-SAT and achieves a $7/8$-approximation, this is an example of a greedy algorithm which is an optimal approximation unless $P=NP$ (cf. Hastad and Moshkovitz-Raz's inapproximability results for Max-E3-SAT).


This paper by Barrett et al. gives a fairly intuitive description of non-signalling correlations (what Tsirelson calls non-interacting systems). Sections II.A. and II.B.1. are the most useful and easy to read, the rest is more heavy stuff.


The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph.
If all the cycles in the cover must consist of at least $k$ edges/arcs, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs).

The complexity of the directed version is fully understood:

Markus Bläser and Bodo Siebert ("Computing Cycle Covers without Short Cycles", in Proceedings of ESA 2001, LNCS 2161, pp 368--379) have proved that $k$-DCC is NP-complete for any fixed $k\ge3$.

The complexity landscape of the undirected version is more diverse, and there are some open questions:

$3$-UCC is polynomially solvable. This is a folklore result that follows from a reduction of Tutte ("A short proof of the factor theorem for finite graphs", Canadian Journal of Mathematics 6, pp 347–352, 1954) to the classical unrestricted matching problem.
David Hartvigsen (in his PhD thesis "An Extension of Matching Theory", Carnegie-Mellon University, 1984) has shown that $4$-UCC is polynomially solvable.
The complexity status of $5$-UCC is open. David Hartvigsen has some positive results on special cases of this problem ("The square-free 2-factor problem in bipartite graphs", in Proceedings of IPCO 1999, LNCS 1610, pp 234–241).
Papadimitriou has proved that $k$-UCC is NP-complete for any fixed $k\ge6$. His proof is sketched in the 1980 paper "A matching problem with side conditions" by Gerard Cornuejols and Bill Pulleyblank (Discrete Mathematics 29, pp 135--159).


How can DES have 6x4 S-Boxes and still be reversible?

DES is a Feistel-based cipher. In such ciphers, the function $\rm F$ need not be invertible. Here's the reason:

In each round, the following operation is applied:

For $i =0,1,\dots,n$

$L_{i+1} = R_i$

$R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$

Decryption is performed as follows:

$R_{i} = L_{i+1}$

$L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$

As you can see, the decryption does not need $\rm F$ to be invertible. (Since the decryption does not need to compute $\rm F^{-1}$.)


Is it known whether $BPP\cap NP\subseteq RP$?

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\mathrm{BPP} = \mathrm{RP}$ will work (eg any oracle relative to which "randomness doesn't help much"), as will any oracle which has $\mathrm{NP} \subseteq \mathrm{BPP}$ (eg any oracle relative to which "randomness helps a lot"). There are a lot of these, so I won't bother with the specifics.

It's somewhat more challenging, though still fairly straightforward, to design an oracle relative to which we get $\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$. The construction below actually does a bit better: for any constant $c$, there is an oracle relative to which there is a language in $\mathrm{coRP} \cap \mathrm{UP}$ which is not in $\mathrm{RPTIME}[2^{n^c}]$. I'll outline it below.

We'll design an oracle $A$ that contains strings of the form $(x,b,z)$, where $x$ is an $n$-bit string, $b$ is a single bit, and $z$ is a bit string of length $2n^c$. We will also give a language $L^A$ which will be decided by a $\mathrm{coRP}$ machine and a $\mathrm{UP}$ machine as follows:

The $\mathrm{coRP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$ randomly, queries $(x,\mathtt{0},z)$, and copies the answer.
The $\mathrm{UP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$, queries $(x,\mathtt{1},z)$, and copies the answer.

To make the above-specified machines actually meet their promises, we need $A$ to satisfy some properties. For every $x$, one of these two options must be the case:

Option 1: At most half of $z$ choices have $(x,\mathtt{0},z) \in A$ and zero $z$ choices have $(x,\mathtt{1},z) \in A$. (In this case, $x \not\in L^A$.)
Option 2: Every $z$ choice has $(x,\mathtt{0},z) \in A$ and precisely one $z$ choice has $(x,\mathtt{1},z) \in A$. (In this case, $x \in L^A$.)

Our aim will be to specify $A$ satisfying these promises so that $L^A$ diagonalizes against every $\mathrm{RPTIME}[2^{n^c}]$ machine. To try to keep this already long answer short, I'll drop the oracle construction machinery and a lot of the unimportant details, and explain how to diagonalize against a particular machine. Fix $M$ a randomized Turing machine, and let $x$ be an input so that we have full control over the selection of $b$'s and $z$'s so that $(x,b,z) \in A$. We will break $M$ on $x$.

Case 1: Suppose there is a way to select the $z$'s so that $A$ satisfies the first option of its promise, and $M$ has a choice of randomness which accepts. Then we will commit $A$ to this selection. Then $M$ cannot simultaneously satisfy the $\mathrm{RP}$ promise and reject $x$. Nevertheless, $x \not\in L^A$. So we have diagonalized against $M$.
Case 2: Next, assume that the previous case did not work out. We will now show that then $M$ can be forced either to break the $\mathrm{RP}$ promise or to reject on some choice of $A$ satisfying the second option of its promise. This diagonalizes against $M$. We will do this in two steps:

Show that for every fixed choice $r$ of $M$'s random bits, $M$ must reject when all of its queries of the form $(x,\mathtt{0},z)$ are in $A$ and all of its queries of the form $(x,\mathtt{1},z)$ are not in $A$.
Show that we can flip an answer $(x,\mathtt{1},z)$ of $A$ for some choice of $z$ without affecting the acceptance probability of $M$ by much.

Indeed, if we start with $A$ from step 1, $M$'s acceptance probability is zero. $A$ doesn't quite satisfy the second option of its promise, but we can then flip a single bit as in step 2 and it will. Since flipping the bit causes $M$'s acceptance probability to stay near zero, it follows that $M$ cannot simultaneously accept $x$ and satisfy the $\mathrm{RP}$ promise.

It remains to argue the two steps in Case 2:

Fix a choice of random bits $r$ for $M$. Now simulate $M$ using $r$ as the randomness and answering the queries so that $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$. Observe that $M$ makes at most $2^{n^c}$ queries. Since there are $2^{2n^c}$ choices of $z$, we can fix the unqueried choices of $z$ to have $(x,\mathtt{0},z) \not\in A$, and have $A$ still satisfy the first option of its promise. Since we couldn't make Case 2 work for $M$, this means $M$ must reject on all its choices of randomness relative to $A$, and in particular on $r$. It follows that if we select $A$ to have $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$ for every choice of $z$, then for every choice of random bits $r$, $M$ rejects relative to $A$.
Suppose that for every $z$, the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is at least $1/2$. Then the total number of queries is at least $2^{2n^c} 2^{2^{n^c}}/2$. On the other hand, $M$ makes at most $2^{2^{n^c}} 2^{n^c}$ queries across all its branches, a contradiction. Hence there is a choice of $z$ so that the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is less than 1/2. Flipping the value of $A$ on this string therefore affects the acceptance probability of $M$ by less than $1/2$.


There is not a canonical such category, for the same reason there is no canonical category of computations. However, there are large and useful algebraic structures on data structures.

One of the more general such structures, which is still nevertheless useful, is the theory of combinatorial species. A species is a functor $F : B \to B$, where $B$ is the category of finite sets and bijections between them. You can think of  species as being families of structures indexed by abstract sets of locations. This explains the functoriality over $B$ -- such families have to be invariant with respect to renaming the abstract labels. Then, the calculus of species basically replays generating function methods at the functorial level, to generate sets of data structures instead of counts.

To see this theory implemented in a programming language, you can read Brent Yorgey's Haskell Symposium paper, Species and functors and types, oh my!. I think Sage also has a species package, though of course it's oriented towards computer algebra rather than programming.


Example of a $U^\omega$ that is not Deterministic Büchi recognizable

Take an alphabet $A=\{0,1,2\}$, and $U=0^*+2A^*$. Then, $U^\omega$ is not deterministic Büchi recognizable.

To see this, imagine it is recognized by a deterministic Büchi automaton $\mathcal A$ with $n$ states. Then, look at the run of $\mathcal A$ on the word $w=2(0^{n+1}1)^\omega$.
Any inside loop of $0$ must contain a Büchi state, because otherwise pumping yields a contradiction (we get a word of the form $2A^*0^\omega$ that is in $U^\omega$ but not accepted by $\mathcal A$). But then, it means that $w$ is accepted, and therefore $\mathcal A$ does not recognize exactly $U^\omega$.


Resources for complexity results for optimization problems in restricted graph classes

Get Spinrad's book on efficient graph representations:
http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150

Also check out Li and Vitanyai's book on Kolmogorov Complexity:
http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150

You will get an appriciation for each graph class by studying succinct data structures.  When you understand why certain classes of graphs take less storage than others you gain a great understanding of how to tailor optimization problems on to them.


How to efficiently read the theoretical computer science research papers?

How long it takes one to read a paper typically depends on what one wants to get out of it. I'll outline three levels of granularity.

Coarsest level: Relevant or not? When building up a list of potentially relevant literature, we often start with a handful of important papers, and then play the game -- who cites them? Whom do they cite? Iterating this game naively would cause an exponential explosion, so we prune the search tree. Briefly scan each candidate and classify it as relevant to my topic or not. This shouldn't take more than a few minutes.
User level: I've decided the paper is relevant, but does it contain a particular result that I need? Say, some variant of Chernoff bounds for non-iid random variables? Unbounded ones? This can take a bit longer, since not all results are stated in the form I'm looking for -- but shouldn't take more than an hour.
Expert level: The paper is relevant and has useful results; now I want to get an in-depth understanding and mastery of the technique. After all, this is the are I want to innovate in! This can take arbitrarily long, since it may require going down various rabbit holes of carefully reading previous results the present one relies on, and so on. No time limit here -- decide how badly you need this and settle in for the long haul.

Update, by popular demand. OK, the paper in question falls into category (3) and you're willing to devote serious time and effort into it. My first suggestion is to read the paper at the User Level, as specified in (2) above. Try first to understand what the main results are claiming, not how to prove them. Once you understand the claims, try to flesh out the proof outline. What basic strategy is being used? Is it a construction, an existence proof, etc -- try to "decompose" it into the various techniques you know. If it's an important paper, you might discover that it invents novel techniques -- make good note of these!

Sometimes short and seemingly elementary proofs are notoriously difficult to understand in an intuitive sense -- one such paper, I believe, is Haussler's "Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension". It's easy enough to follow the proofs step by step, but most beginner readers will still not be able to say much about the "big picture", even after the 2nd or 3rd reading. In such a case, it might be useful to seek out an expert (perhaps the author himself) to try to understand how he came up with the proof.


find the most similar topological ordering of a dag

It is NP-hard. The reduction is from $CLIQUE$, so suppose we are given an undirected graph $H$ on $n$ vertices and $m$ edges, with a parameter $k$, and our task is to decide whether $\omega(H)\ge k$. We will need some sufficiently large numbers $M\gg N \gg n$, where we need about $N=n^2$ and $M=n^3$.
The graph $G$ will have two disjoint parts. The first part will have $M+M^2$ vertices such that there is an arc from each of the $M$ vertices to each of the $M^2$ vertices. In the order $L$ the $M^2$ vertices will have position $M+1$ to $M^2+M$. Since $M$ is huge, this implies that any optimal solution starts with the $M$ vertices, followed by the $M^2$ vertices. From the $M$ vertices, some can be in good position. As we can put these arbitrarily, we can easily determine this optimum; denote it by $X$.
The second part of $G$ will encode $H$. For every vertex of $H$, $G$ will have $N$ vertices. In $L$ each of these will take one of the first $M$ positions. Because of our earlier observations, none of these can keep their original position in an optimal solution, so we should place them to make other vertices 'happy'. For every edge of $H$, $G$ will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices. In $L$ each of these will have position $M^2+M+kN+1$ to $M^2+M+kN+m$. Since after the first part of $G$, we have only $kN$ places left before these positions, and $N\gg n$, this means that at most as many of these $m$ vertices can be in position, as many edges can be spanned by $k$ vertices.
To summarize, we can have $M^2+X+\binom k2$ vertices of $G$ in the same position as in $L$ if and only if $\omega(H)\ge k$.
ps. Notice that $G$ has only two levels, i.e., its longest (directed) path has length one.


Any computable transcendental number that is computable in P time but not $O(n)$

Here is the construction of such a number.  You can argue whether this means such a number is "known".

Take any function $f$ from $\mathbb{N}$ to $\{ 1, 2, \ldots, 8 \}$ where the $n$'th digit is not computable in $O(n)$ time.  Such a function exists, for example, by the usual diagonalization technique.   Interpret $f(n)$ as the $n$'th decimal digit of some real number $\alpha$.   Now, for each $n$ of the form $2^{2^k}$, $k \geq 1$, change the digits of $\alpha$ in positions $n, n+1, \ldots, 3n$ to $0$'s.   The resulting number $\beta$ evidently retains the property that the $n$'th digit is not computable in $O(n)$ time, but has infinitely many very good approximations by rationals, say to order $O(q^{-3})$, of the form $p/q$.  Then by Roth's theorem $\beta$ cannot be algebraic.  (It is not rational because it has arbitrarily long blocks of $0$'s set off by nonzeros on both sides.)


Boolean function with specific ОBDD representation

Fix $k=\log n$ and define the following function on $n$ bits: take the first $k^2$ bits and view them as $k$ numbers in the range $1..2^k$: $p_1 ... p_k$.  Now take the $p_1$'st bit, $p_2$'nd bit ... $p_k$'th bits of the input and view them as a $k$ bit number $p$.  The output is the value of the $p$'th bit of the input.

A palindromic OBDD of size $exp(k^2)$ can solve it by first reading and remembering  $p_1 ... p_k$, then reading these $k$ bits, on the first pass, and remembering $p$ and then reading the $p$'th bit on the 2nd pass.

Look at a single pass OBDD and let us restrict the function by dictating that $p_1 ... p_k$ will be equal to the last $k$ indices of the input, and thus $p$ is specified by the last $k$ bits of the input.  It is easy to see that $\Omega(n)$ bits need to be remembered about the first $n-k^2-k$ non-restricted bits of the input in order for the value of the $p$'th bit to be recovered (this is the Index function in communication complexity -- see example 4.18 in Communication Complexity book, page 49).

This gives a gap $n^{\log n}$ vs. $exp(n)$ -- to get poly vs non-poly just use $N=n^{\log n}$ bits and ignore all but the first $n$.


Modeling objects (OOP) in dependent type theory

Some early(?) work done in this area was by Bart Jacobs (Nijmegen) and Marieke Huisman. Their work is based on the PVS tool and relied on a coalgebraic encoding of classes (if I remember correctly). Look at Marieke's publication page for papers in the year 2000 and her PhD thesis in 2001. Also look at the papers by Bart Jacobs cited in the A Setzer paper you mention.

Back in those days, they had something called the LOOP tool, but it seems to have vanished from the internets.

There is a workshop series known as FTfJP (Formal Techniques for Java-like Programs) that addresses the formal verification of OO programs. Undoubtedly some of the work uses dependent type theory/higher-order logic. The workshop series has been running for some 14 years.