Calculate Huffman code length having probability?

The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.

One can see this by constructing a Huffman tree with a probability distribution with probabilities proportional to the Fibonacci numbers $$\{1,1,1,2,3,5,8,13, \ldots, F_n\}.$$ (The third 1 is deliberate.) When combining these into a Huffman tree, you are faced with lots of choices. One set of choices yields a tree of depth approximately $n$; another, approximately $n/2$.

For the probabilities $$\frac{1}{34}, \frac{1}{34}, \frac{1}{34}, \frac{2}{34}, \frac{3}{34}, \frac{5}{34}, \frac{8}{34}, \frac{13}{34},$$
we have the large-depth Huffman tree where the longest codeword has length 7:

and the small-depth Huffman tree where the longest codeword has length 4:

Both of these trees have $43/17$ for the expected length of a codeword, which is optimal.

It is possible to show that the length of the longest codeword is no more than a factor of $\log_\phi(2)\approx 1.44$ larger than $-\log_2 p$, where $\phi$ is the golden ratio; the worst case example is the large-depth one above, using Fibonacci numbers. So for your example the length is at most $28$. And because there are 1024 codewords, the length of the longest one has to be at least $\log_2 1024 = 10$.  So the correct answer is the length of the longest codeword is between $10$ and $28$. But unless the OP changed the wording of the question, these bounds don't seem to be what the problem was asking for.


This problem is PSPACE-complete even in the case in which the edge weights obey the triangle inequality. See

Hsi-Ming Ho, Joel Ouaknine, The Cyclic-Routing UAV Problem is PSPACE-Complete, FoSSaCS 2015


Does Approx Carathéodory's theorem implies dimensionality reduction

The approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the dimensionality reduction, the answer is no - the supporting subsets are different subsets, and their number is too large. In particular, the number of possible subsets is $n^{O(1/\epsilon^2)}$ - but there is some connection...

Specifically, let $P$ be a set of $n$ points in high dimenionsional Euclidean space of diameter $1$. Let $Q$ be an $\epsilon$-net in the convex-hull of $P$. That is, any pair of points of $Q$ is in distance at least $\epsilon$ from each other, and every point of $CH(P)$ is in distance at most $\epsilon$ from some point of $Q$.

Now, by the approximate Caratheodory theorem, we know that $|Q| = n^{O(1/\epsilon^2)}$. Now, imagine that you do some experiment, and with probability half the experiment succeeds for half the points of $Q$ (or, more formally, half the pairs of $Q \times Q$ -- since we look on vectors formed by differences of points of $Q$). How many times do you have to repeat the experiment till all the points are served? Well, roughly $\log_2 |Q| = O(\epsilon^{-2} \log n)$, which is, surprise surprise, the target dimension in the JL lemma. This is of course, does not imply the JL lemma - it is somewhat of a "coincidence" - a wrong calculation that gives the right bounds...

There is a useful lesson here however - a set of $n$ points in high dimensions, induces roughly $n^{O(1/\epsilon^2)}$ points that are $\epsilon$-distinct, independent of the ambient dimension.


The asymptotic behavior of a recurrence related to stable matchings

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily.

First, let's notice that for $b_n=a_{2^n}$, we have the recurrence

$$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$

Now, let's assume that $b_n = r s^{2^n}$. The equation becomes

$$r s^{2^n} = 3 r^2 s^{2^n} - 2 r^4 s^{2^n},$$

and $s^{2^n}$ factors out. Solving the equation $r = 3r^2 - 2r^4$, we find two positive roots,  $r = 0.366 = \frac{1}{2}(\sqrt{3}-1)$ and $r= 1$. Let $r_0$ be the smaller of these roots.

Suppose we could show that $\frac{b_{n-1}^2}{b_n} = r_0$. Then we can show by induction that $b_n=r_0 s^{2^n}$ for some value of $s$. Suppose this is true for some value $n$. Then
\begin{align}
b_{n+1} &= \frac{b_{n}^2}{r_0} = \frac{\left(r_0 s^{2^n}\right)^2}{r_0} = r_0 s^{2^{n+1}}.
\end{align}

In fact, we won't quite show this; what we will show is that $\frac{b_{n-1}^2}{b_n}$ goes to $r_0$ as $n$ goes to $\infty$. With some analysis (given in an appendix), we can complete the proof that $b \approx r_0 s^{2^n}$ for some value of $s$. The actual value of $s$ depends on the initial conditions, and the only way I know to get it is computationally. Maple seems to say that $s$ is around 2.280142. If you start with $a_1=2$, $a_2=7$, Maple gives $s \approx $ 4.189425.

Why does $\frac{b_{n-1}^2}{b_n}$ go to $r_0$? Take the recurrence, and divide $b_{n-1}^2$ by both sides. This gives

$$ \frac{b_{n-1}^2}{b_n} = \frac{1}{3-2\left(\frac{b_{n-2}^2}{b_{n-1}}\right)^2},$$
or, letting $t_n = b_{n-1}^2/b_n$,
$$t_n=\frac{1}{3-2 t_{n-1}^2}.$$
This has three fixed points, but the only attractive point is $r_0$, and $t_n$ approaches this point from any initial value except the two other fixed points.

Appendix:

Here is a sketch of the argument that if $\lim_{n\rightarrow \infty} t_n = r_0$, then $s$ exists. We'll consider an approximation to $s$ based on $b_n$. Let
$$s_n = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}.$$
Then
$$\frac{s_n}{s_{n-1}} = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}\left(\frac{r_0}{b_{n-1}}\right)^{\frac{2}{2^{n}}}
= \left( \frac{b_nr_0}{b_{n-1}^2}\right)^{\frac{1}{2^n}}
= \left( \frac{r_0}{t_n}\right)^{\frac{1}{2^{n}}} .
$$
If $\lim_{n \rightarrow \infty} t_n = r_0$, this equation implies that $$ \prod_{m=n}^\infty \frac{s_{m+1}}{s_m} \rightarrow 1 \quad \mathrm{as} \quad n \rightarrow \infty,$$ and thus that $s =\lim_{n\rightarrow \infty} s_n $ exists.

But in order to show that $b_n$ grows like $r_0 s^{2^n}$ as $n \rightarrow \infty$, you need not just that $s_n$ converges, but that it converges quickly. The exponent on $\frac{r_0}{t_n}$ above takes care of that. What we would like to show is that
$$\lim_{n\rightarrow\infty} \frac{s^{2^n}}{s_n^{2^n}} = 1.$$

But
$$
 \frac{s^{2^n}}{s_n^{2^n}}
= \prod_{m=n}^{\infty} \left(\frac{s_{m+1}}{s_m}\right)^{2^{n}}
= \prod_{m=n}^{\infty} \left(\frac{r_0}{t_{m+1}}\right)^{\frac{1}{2^{m+1}}2^{n}} \approx \left(\frac{r_0}{t_{n}}\right)^{2^n\left(\sum\limits_{m=n}^\infty \frac{1}{2^{m+1}}\right)}= \frac{r_0}{t_n},$$
which goes to $1$ as $n \rightarrow \infty$.


Bounds on sum of squares of node degrees in undirected graphs

It's $\Theta(m^2)$ for multigraphs (consider a graph with $m$ edges between the same pair of nodes and all other nodes isolated) and $\Theta(mn)$ for simple graphs (the sum of squared degrees equals the number of directed two-edge walks; each edge can be continued to form a two-edge walk in $O(n)$ ways; consider $K_{m/n,n}$).


Existence of zero-knowledge proof for location

I think part of the problem you are having finding a solution is that you are using the wrong name for this concept. While it is indeed closely related to the idea of a zero knowledge proof, this type of protocol, accepting input from multiple parties, is known as either Secure Function Evaluation or Secure Multi-Party Computation.

Let's first simplify the game and assume it is played on a lattice, so that the points are discrete. It seems to me that you simply wish to compute $|J \cup K|$. Trivially, this is equal to $|J \cup K| = |J| + |K| - |J \cap K|$. Now, I assume you do not mind each party learning the number of locations the other party holds. In this case, $|J|$ and $|K|$ are public. In this case all that is required to determine $|J \cup K|$ is $|J \cap K|$. Now, if we think of the inputs of Player 1 (henceforth Alice) and Player 2 (henceforth Bob) as being a vector of length equal to the total number of locations possible, with zeros everywhere except for the location that player holds (which is set to 1). In this case $|J \cap K|$ is simply the inner product of their two vectors. Fortunately there are SFE protocols for exactly this inner product computation (see here for example). So Alice and Bob simply calculate $|J \cup K|$.

Now, what about the case you give, where the locations are not discrete, but are rather parameterised by a pair of real numbers which have some range associated with them? In this case it is not sufficient to determine whether two points exactly coincide, but we need to also determine which points are close enough to one another to overlap in the area covered. This can be done fairly easily: The first step is to discretize the set of possible locations, hence imposing some fixed resolution on the problem (in practice you only need the range covered by each location to extend a few pixels in each direction). Once you have done this, the protocol would proceed as follows: Bob prepares a register equal in size to the total number of possible discretized locations. Everywhere is zero, unless that location is within distance $D=2E$ of one of his locations in which case it is set to 1. Alice prepares her vector as before, with a 1 at only her discretized locations. Then Alice and Bob run the secure dot product protocol. The number returned by this is simply the number of locations held by Alice such that the area covered by that point overlaps with the area covered by some location held by Bob. (Adjusting the $D$ parameter can be done to set some minimum overlap if desired). In this way, Alice and Bob can count the number of points where the overlap exceeds some threshold, and the total number of distinct locations they would hold between them.


Find an approximate argmax using only approximate max queries

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$. Consider drawing the input by picking a permutation of these values uniformly at random.

The idea should be that if we fix the indices of all values except for values $B$ and $\frac{n-1}{n}B$, then we should be able to show the difference in the algorithm's probability of picking one versus the other is very small: The variation distance between the results of the algorithms' queries is very small given the 50-50 distribution on assignments of these values to the two available indices and the results of any sequence of queries.

This argument holds for each pair of adjacent values, so we get a chain of constraints on the probability the algorithm picks the highest, second-highest, ... values. This gives an upper bound on the expected value of the algorithm, so we set that upper bound to $B-1$ and see what the number of queries has to be.

I couldn't improve on $\log n$ with the above approach yet, but I think you might get $(\log n)^2$ if you can leverage the fact that queries can't help with multiple steps at once. I.e. if a query changes when we move the highest value to a different index, then one of those times it it doesn't change when we move any other value to a different index.

Differential privacy might be helpful for one of these steps, e.g. if we only think about the case where we swap the location of the two highest values, the "sensitivity" of this query is just $\frac{B}{n}$ and then advanced composition might be helpful.

Sorry this is half-baked, but hope it can be useful!


Does hyper-computational power of infinite time Turing machines also require infinite memory?

I think we have a reference here to Joel Hamkin's model of infinite time computation, not just some made up idea of infinite time machines. In that model time is measured by ordinal numbers. The machine has access to an infinite tape. After $\omega$ steps, every cell of the tape has been potentially written to, and we can't throw away any cell because its content may be needed during further computation. So yes, you'd need infinite space, but that's not a problem when you've got infinite time already.


Does every Turing-recognizable undecidable language have a NP-complete subset?

No.

Turing-recognizable undecidable languages can be unary (define $x \not\in L$  unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP.


Is there a non-deterministic linear time algorithm for CNF-SAT?

This is only an extended comment.
A few times ago I asked (myself :-) how fast a multitape NTM that accepts a (reasonably encoded) NP-complete language can be. I came up with this idea:

3-SAT remains NP-complete even if variables are represented in unary. In particular we can convert a clause - suppose $(x_i \lor \neg x_j \lor x_k)$ - of an arbitrary 3-SAT formula $\varphi$ on $n$ variables and $m$ clauses in a sequence of characters over alphabet $\Sigma = \{ +, -, 1 \}$ in which every variable occurrence is represented in unary:

$ + 1^{i} 0,- 1^{j} ,+ 1^{k} $

For example, $(x_2 \lor -x3 \lor +4)$ can be converted to:

+110-1110+11110

So we can convert a 3-SAT formula $\varphi_i$ in an equivalent string $U(\varphi_i)$ concatenating its clauses. The language $L_U = \{ U(\varphi_i) \mid \varphi_i \in 3-SAT \}$ is NP-complete.

A 2-tape NTM can decide if a string $x \in L_U$ in time $2|x|$ in this way.

the first head scans the input from left to right and with the internal logic it keeps track when it enters or exit a clause or reach the end of the formula. Whenever it finds a $+$ or $-$, the second head starts moving right with it on the $1^i$ that represents $x_i$. At the end of $1^i$, if the second head is on a $0$ then it guesses a truth value $+$ or $-$ (it makes an assignment) and writes it on the second tape; if it finds a $+$ or $-$ then that variable has already been assigned a value;
in both cases, using the internal logic, the NTM matches the truth value under the second head (the assignment) with the last seen $+$ or $-$; if they match then the clause is satisfied;
then the second head can return to the rightmost cell;
with the internal logic the NTM can keep track if all clauses are satisfied while the first head moves towards the end of the input.

Example:

Tape 1 (formula)    Tape 2 (variable assignments)
+110-1110+11110...  0000000000000...
^                   ^
+110-1110+11110...  0000000000000...
 ^                  ^
+110-1110+11110...  0000000000000...
  ^                  ^
+110-1110+11110...  0+00000000000... first guess set x2=T; matches +
  ^                  ^               so remember that current clause is satisfied
+110-1110+11110...  0+00000000000...
  ^                  ^
...
+110-1110+11110...  0+00000000000...
    ^               ^
...
+110-1110+11110...  0++0000000000... second guess set x3=T
       ^              ^              don't reject because current
                                     clause is satisfied (and in every
                                     case another literal must be parsed)

The time can be reduced to $|x|$ if we add some redundant symbols to the clause representation:

$ + 1^{i} 0^i,- 1^{j} 0^j ,+ 1^{k} 0^k \; ... \; \text{+++}$

($\text{+++}$ marks the end of the formula)

In this way the second head can return to the leftmost cell while the first scans the $0^i$ part.
Using $\text{++}$ as a clause delimiter and $\text{+++}$ as a marker for the end of the formula we can use same representation for CNF formulas with an arbitrary number of literals per clause.


Reducing $n$ in $(n,k)$ secret sharing while keeping it effective

This sounds related to Wyner's "wiretap channel": Wyner showed that an asymmetry between receiver and eavesdropper could be used to achieve information-theoretic security. There have been many, many follow-up works since then.

Reference:
A. D. Wyner, The wire-tap channel. Bell Sys. Tech. J., vol. 54, pp. 1355-1387, 1975.


Chomsky Schützenberger enumeration theorem

There is a proof in the book of Kuich & Salomaa, Semirings, Automata, Languages and another one in the paper of Panholzer, "Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function", J. of Automata, Languages and Combinatorics 10 (2005), 79–97.   I wish there were a simple and clear proof of the result.


What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?

I don't see an easy way of counting without enumerating. You can easily visit all hamiltonian paths with an exaustive depth-first search with backtracking. You can actually cheat a bit, and realize that, if N is the number of hamiltonian paths that start by going to the right, the total number of hamiltonian paths is 2N (due to the symmetry if the grid).  This does not extend all the way (for some vertices not all paths will lead to the same number of cycles, but you can upper bound the number of hamiltonian paths easily with a similar argument (with the bonus that you can solve parts of it exactly to improve your bound with symmetry arguments). This is the strategy I'd choose.

But if you don't want this, some generic heuristics:

You can also easily upper bound the number of hamiltonian paths as |E| choose |V|-1 (where |E| is the number of edges and |V| the number of vertices in the graph), which can be a lot better for a sparse graph than |V|! (the naive bound that assumes that the graph is complete).
An easy way to improve this bound is by trimming known-bad combinations, by not considering twice edges from the same vertex. So you'd get something like prod_v(deg_v-1) (which should still upper bound the number of hamiltonian paths, since you're now counting cycles more than once, I think).


minimizing size of regular expression for finite sets

The following argument is essentially from (1): The decision versions of the two problems are contained in the second level of the polynomial hierarchy (more precisely: in the complexity class $\Sigma^P_2$), as follows. Guess a regular expression of size at most $k$, and check if it is equivalent to the given deterministic finite automaton (respectively: to the language given as a list of words).

I believe that no further results regarding your problems are known. For a similar-looking optimization problem, where the objective is to find a minimum equivalent nondeterministic finite automaton instead of a regular expression, the following results are known:

For input described as DFA, the minimum equivalent NFA problem is ${\bf DP}$-hard, see (1). Here, ${\bf DP}$ stands for "difference polynomial time"; this is the "Sigma" complexity class at the second level of the Boolean hierarchy.
For input described as a list of words, the minimum equivalent NFA problem is ${\bf NP}$-hard, see (2).
For $L \subseteq \{0,1\}^m$ and input described as a truth table, the minimum equivalent NFA problem is ${\bf NP}$-complete, see (2).

Beware: Unlike the setting of infinite languages, I do not see a straightforward reduction from the NFA minimization case to the problems from your question.

References:

(1) Hermann Gruber and Markus Holzer. Computational Complexity of NFA Minimization for Finite and Unary Languages. In: 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber and Markus Holzer. Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP. In: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.

Edit:
I think that grammar based codes are not so closely related: in that setup, the given language is a singleton set. But for such a singleton language $L=\{w\}$, the minimum size regular expression is (trivially) given by $w$.


Complexity results for Lower-Elementary Recursive Functions?

Concerning (bonus) question 3: the functions definable in the variant with $\log(x)$-bounded summation are all in the complexity class uniform $\mathsf{TC}^0$. This follows from the construction in Chandra, Stockmeyer and Vishkin "Constant depth reducibility", SIAM J. Comput. 13 (1984) showing that the sum of $n$ numbers of $n$ bits each can be computed by poynomial size constant depth circuits with majority gates.

With constant bounded summation you get a subclass of uniform $\mathsf{AC}^0$. Constant bounded summation can be reduced to addition and composition, and addition can be computed by constant depth boolean circuits using the carry-lookahead method.


New theories and publications on computer science

I can think of two cases where this (more or less) happened.

Valiant published his first paper on PAC learning in Communications of the ACM 27 (1984). Charlie Bennett got Stephen Wiesner's paper on quantum cryptography published in SIGACT News 15 (1983). I believe that at the time of publication, the editors had more latitude in accepting articles without extensive peer review than in the standard model of refereed journals.

In both cases, the idea turned out to be enormously valuable, and I am sure the prestige of Valiant and of Bennett helped the work get published. In both cases, the research was quite a bit better worked out than "barely a sketch", but it was still very sketchy, and not completely convincing to contemporary researchers.

If you are an unknown researcher, in order to get anybody to pay attention, you probably need to work out your ideas at least as well as they were worked out in these two cases, and even then I am not sure whether you could get sketchy ideas published without having the backing of a respected researcher (as Wiesner did).v

Ralph Merkle did not succeed in getting his sketchy ideas on what was to become public-key cryptography published until after Diffie, Hellman, Rivest, Shamir and Adelman had worked out the sketchy ideas in enough detail to convince everybody they were worthwhile. Fortunately, somebody put him in touch with Diffie and Hellman, who were clever enough to see the value of his ideas, talented enough to work them out in some detail, and honest enough to give him his fair share of the credit. See this article.


Parallel (NC) replacements for Gaussian elimination?

Yes, it is in $\mathsf{NC}^2$:

  Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7 (1987), no. 1, 101–104.

The following (earlier) paper shows that solving a system of linear equations reduces to computing the rank, and thus, together with the above result, solving the system (in particular, finding a basis for the nullspace) is also in $\mathsf{NC}^2$:

  Allan Borodin, Joachim von zur Gathen, John Hopcroft. Fast parallel matrix and GCD computations. Information and Control 52(3):241-25, 1982.


Concise introduction to algorithms for mathematicians

I like this textbook very much:

Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani: Algorithms
Published by McGraw-Hill 2007.

I don't calculate your suggested ratio but I think you will also like it :)


Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable (c.e.) subset $S \subseteq \mathbb{N}$ contains either finitely many elements of $L$ or all but finitely many elements of $L$.
Let $f : \mathbb{N} \to \mathbb{N}$ be an enumeration of $L$ without repetitions. The map $f$ is not computable, or else $M$ would be a computable subset of $\mathbb{N}$, which a maximal set is not.
We claim that $f$ is a counter-example to your question. Consider any c.e. subset $S \subseteq \mathbb{N}$:

If $S \cap L$ is finite then $f^{-1}(S) = f^{-1}(S \cap L)$ is finite (as $f$ is injective) and therefore a computable set.
If $S \cap L$ contains all but finitely many elements of $L$ then $f^{-1}(S) = f^{-1}(S \cap L)$ contains all but finitely many elements of $\mathbb{N}$, therefore it is a computable set.

In your question you hint at the analogy between computability and continuity. Indeed there is one, but we need to be a bit more sensitive about computability.
Let $$\mathcal{E}  = \{S \subseteq \mathbb{N} \mid \text{$S$ is c.e.}\}$$ be the set of all c.e. subsets of $\mathbb{N}$, and let $W : \mathbb{N} \to \mathcal{E}$ be a standard enumeration of c.e. sets. We can think of $\mathcal{E}$ as the "computably open" subsets of $\mathbb{N}$. Indeed, they're closed under finite intersections and unions of computable families.
Say that a map $F : \mathcal{E} \to \mathcal{E}$ is computable if there exists a computable $r : \mathbb{N} \to \mathbb{N}$ such that $F(W_n) = W_{r(n)}$ for all $n \in \mathbb{N}$. (This is just the standard notion of computability for numbered sets.)
Your question can be rectified into a theorem like this (I just inserted the emphasized "computable"):
Theorem: A map $f : \mathbb{N} \to \mathbb{N}$ is computable if, and only if, its inverse image map $f^{-1} : \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ restricts to a computable map $f^{-1} : \mathcal{E} \to \mathcal{E}$.
I will leave the (easy) proof as an exercise. The above can easily be generalized from number-theoretic maps to languages.


Outstanding conjectures and open problems in (algorithmic) game theory?

Here are several open problems:

1-Major open problem is the problem of computing approximate Nash equilibria.

2- Existence of efficient algorithm for computing pure Nash equilibria in congestion
games?

3-finding equilibria with minimum inefficiency?

4-Tim Roughgarden, in Communications of the ACM , posed the following open problem:

  to what extent is “incentive-compatible” efficient computation fundamentally less powerful
  than “classical” efficient computation?

Algorithmic game theory,
Communications of the ACM, Volume 53 , Issue 7,  (July 2010)

Also, these references contains some open problems:
Nisan, Roughgarden, Tardos, and Vazirani, editors. Algorithmic Game Theory. Cambridge
University Press, 2007.

T. Roughgarden. Algorithmic game theory: Some greatest hits and future directions. In TCS ’08, p. 21–42.


Novel proof of pumping lemma for regular languages

Essentially the same argument is made by Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9) for the variant of the pumping lemma where $N$ letters are marked and all three of $x$, $y$, $z$ must contain marked letters.  See also Autebert, Boasson, and Cousineau (1978) for more properties of abstract families of languages satisfying this variant of the pumping lemma.


Convergence and representation theorems for machine learning

I recommend Neural Network Learning: Theoretical Foundations by Anthony and Bartlett. You'll find exhaustive answers to your questions there. Very briefly, theoretical learning problems tend to separate very cleanly into two orthogonal components: statistical and computational. Thus, a universal learner unconstrained by computational issues could construct the smallest Turing machine (or MATLAB program) consistent with the input data; such a learner would be near-optimal statistically in a well-defined sense.

Nobody studies such learners (beyond intro-class homework problems) because they are computationally infeasible (actually uncomputable, in my example). When computational constraints enter the picture, it becomes much more nuanced: often times, what is the obvious course of action for the statistician is dismissed out of hand as infeasible by the algorithmist.

In any case, the Anthony+Bartlett book seems like the perfect introduction for a mathematically inclined beginner.


Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

I think the paper "Subcubic Equivalences Between Path, Matrix, and Triangle
Problems" by V. Vassilevska Williams and R. Williams is what you're looking for. Its abstract contains the list of the following problems on graphs:

The all-pairs shortest paths problem on weighted digraphs (APSP).
Detecting if a weighted graph has a triangle of negative total edge weight.
Listing up to $n^{2.99}$ negative triangles in an edge-weighted graph.
The replacement paths problem on weighted digraphs.
Finding the second shortest simple path between two nodes in a weighted digraph.

According to the abstract the paper is about the following:

  We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable
  in $O(n^3)$ time are equivalent under subcubic reductions.


What are the historical roots of Milner's bigraphs?

Much of the category theoretic groundwork for bigraphs was done in terms of Reactive Systems:

Leifer, J. J. and Milner, R. (2000). Deriving bisimulation congruences for reactive systems. In Palamidessi, C., editor, Proceedings of the 11th International Conference on Concurrency Theory (CONCUR'00), volume 1877 of Lecture Notes in Computer Science, pages 243-258. Springer-Verlag. (link)

This was the result that showed that bisimulation is a congruence in the presence of sufficient RPOs.

As you correctly noted, there are definitely links with various ambient calculi - particularly in capturing the notion of "place".

The Chemical Abstract Machine (Cham) has also been cited as significant - probably in terms of the semantics of reactions as well as a few other concepts (such as membranes) that look familiar when viewed from the bigraphs world.  This to me probably shows the clearest sign of being an ideological ancestor of bigraphical reactive systems in many ways.

Finally, I think it's worth just looking at the thread of Milner's work from CCS, to pi-calculus, to reactive systems, to bigraphs.  You see a definite trend within that strand of work, in the introduction of additional abstractions or the ability to explicitly encode certain information that was perhaps otherwise only implicitly included in previous modeling formalisms.

This is by no means complete, but I think it's definitely fair to see the development of bigraphs as a natural progression from many, many different ideas.


Data Strcuture to represent dependencies amongst modules

Your problem is the following:

Given a dag $G$, with labels $\ell:V\to L$ on the vertices, and a set $O \subseteq L$, find the smallest subset $S \subseteq V$ of vertices such that for each $o \in O$, there is a vertex in $S$ labelled $o$.

This problem is NP-hard, by reduction from set cover.

(The reduction: given sets $T_1,\dots,T_n$ and universe $U$, define a dag with one source vertex for each $T_i$, one sink vertex per element of $U$, labelled with that element, and an edge $T_i \to t$ for each $t \in T_i$; and set $O=U$.  Then the smallest subset of vertices that meets the requirements is also the minimum set cover.)

Since it is NP-hard, you'll need to use any of the standard methods for dealing with NP-hardness: heuristics, an approximation algorithm, an exponential-time algorithm, etc.  I suggest reducing this to integer linear programming.  Add a zero-or-one boolean variable $x_v$ for each vertex $v$; for each edge $v \to w$, add the inequality $x_v \ge x_w$; for each label $o \in O$ in the output set, add the inequality $\sum_{\ell(v)=o} x_v \ge 1$, where the sum ranges over all vertices with label $o$; and then minimize the objective function $\sum_{v \in V} x_v$.  Then, apply an off-the-shelf ILP solver.  Of course this may be exponential time in the worst case, but I suspect it's about as you're likely to get in practice, within any reasonable amount of programming effort.

The data structure to use is a graph.  The problem remains NP-hard no matter what data structure you use, so choice of an appropriate data structure isn't going to make the problem any easier.


Isomorphism notion between sets of triples

Your problem reduces to graph isomorphism, so is not $\mathsf{NP}$-complete unless the polynomial hierarchy collapses.

In fact, you've essentially already given the reduction in your question: given a 3-uniform (=every hyperedge has size 3) hypergraph $G$, construct from it the graph $f(G)$ which has the same vertex set, and such that $\{u,v\} \in E(f(G))$ iff there exists a $z \in V$ such that $\{u,v,z\} \in E(G)$. (When $G$ is a hypergraph, I use $E(G)$ to mean the set of hyperedges.) Then $G_1$ and $G_2$ are isomorphic-in-your-sense iff $f(G_1) \cong f(G_2)$ as graphs. It is not hard to check that this reduction only takes polynomial time (note that $|E(f(G))| \leq |V(G)| |E(G)|$).

It is also probably worth mentioning that there is already a well-established notion of hypergraph isomorphism that is different from your notion. If we consider a hypergraph $G$ as a vertex set $V$ together with a collection of hyperedges $E \subseteq P(V)$ (each hyperedge is a subset of $V$), then two such hypergraphs are isomorphic if there is a bijection $\pi\colon V_1 \to V_2$ such that $E_2 = \pi(E_1)$. (Here I am abusing notation twice: by "$\pi(E_1)$" I mean $\{\pi(e) : e \in E_1\}$ and by $\pi(e)$ for $e \subseteq V$ I mean $\{\pi(v) : v \in e\}$.) Hypergraph isomorphism in this sense is Karp-equivalent to graph isomorphism, but by a slightly less immediate reduction than from your problem. However, fast (in theory) algorithms for hypergraph isomorphism are often more difficult than those for graph isomorphism (see, e.g. Babai and Codenotti, FOCS 2008).


Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs

I'll provide a naive approach which give $O(m^2 \cdot max_f)$ running time but shows the problem is P. First turn the graph to undirected graph. Suppose one edge is in first graph and the other in the second graph, contract both of them and name them $s,t$. We can find a minimum edge cut that separates s and t in time max_f which is a running time of best maximum flow algorithm on unit weight graph. We run this algorithm for all possible pair of edges. But why this works? trivially there is no smaller cut and the two sides are not edgeless. On the other hand if a graph G is connected  minimum edge cut C between two vertices s, t always cuts the graph into two connected subgraphs.


A System for Visualizing Bibliography Information

To elaborate a little on my comment (which is slightly tangential).

There is a fun site called eigenfactor that provides nice visualizations of how various parts of science cite each other, and their relative size by publication/citation volume. Unfortunately their primary focus seems to be calculating impact factors for journals and so they operate on the level of journals, not individual papers/authors. However, they have a pretty interesting way of identifying subfields.

They use the number of citations from a journal A to a journal B as a weight on the edge from A to B. They then consider a random walk on the resulting graph. Such a walk tends to linger in topic clusters, and thus when they try to create a shortest description of the walk they tend to name the clusters and use a second index inside the cluster (kind of how you would have unique city names, and unique street names in each city, but redundant across cities). I thought it was a pretty nice way of finding clusters, and produces clusters that mimic how most people would divide the topics in science (with the occasional hilarious classification like putting Phys. Rev. Letters in Chemistry instead of Physics) You can read more in their paper or on the mapequation site.


Proving skip-lists strongly weight-balanced in expectation

As you asked it, the question about the expected length (given the height) does not make sense without a prior distribution on the length of the string.

You should instead consider the number of times you get tails before you get $h$ heads in a row, since this will give you the number of descendants of a node of height $h$ in a skip list.  Let's represent this value with the random variable $X=X(h)$.  When we start, or right after we get tails, the probability of starting and finishing a run of $h$ or more heads before getting tails again is $2^{-h}$.  If we hit tails before getting $h$ heads in a row, we're back to square one.  Thus $X$ is actually distributed as $\mathrm{Geometric}(2^{-h})$ and we have $\mathrm{E}(X) = (1-2^{-h})2^h$.

Edit:

Sorry, this gives you the expected number of towers in the left subtree.  The number of nodes in the left subtree will be of the same order of magnitude though, since towers in between the first and last will have geometrically distributed height with expected value 2.  Also, if you want to consider the right subtree as well, which probably makes more sense, you simply go until you get $h+1$ heads in a row instead of just $h$.  In this case you get the number of descendants as defined in Devroye's paper that you linked to.


Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

Regarding the NP-hardness tag, your problem can be shown to be in $P$ (and thus likely not $NP$-hard) via a reduction to min-cost flow with $O(nK)$ vertices and $O(nK^2)$ edges.

It will help to have a visual to refer to for the construction. Below is a figure showing how we construct the min-cost flow instance with $n=K=3$, with the set family $A=\{1,2\}, B=\{1,2,3\}, C=\{2,3\}$.

All edges are directed rightwards. Red edges have cost 0 and capacity 1. Blue edges have cost 0 and capacity $K$. Black edges have capacity $1$ and cost indicated in the figure. We demand that $s$ route $K=3$ units of flow to $t$.

We refer to the nodes corresponding to $[n]$ (above labeled $1$, $2$, and $3$) as "number nodes" and those corresponding to the $K$ sets (above labeled $A$, $B$, and $C$) as "set nodes". The unlabeled nodes are called "central nodes", and we say that a given central node corresponds to the unique adjacent number node.

All costs and capacities are integral, so w.l.o.g. we can consider only integral feasible solutions to the problem. The capacity constraints on the red edges ensure that, in any feasible solution, each set node must send over exactly one unit of flow to $t$, corresponding to the constraint that we pick one element from each set. This unit of flow must have arrived from one of the $nK$ central nodes, which in turn must have arrived from its corresponding number node. Finally, this number node received its flow from $s$.

Thus, if we track the path taken by each unit of flow in a solution to the constructed flow instance, we see that it goes through both a number node $c$ and through a set node $S$, corresponding to a choice of a number $c$ from that set $S$ in the original instance. As for the costs, any solution that routes $p_i$ units of flow to a number node labeled $i$ must incur a cost of at least $\sum_{j=1}^{p_i}\left(2j-1\right) = {p_i}^2$ on the node's out-edges. In an optimal solution, this holds with equality. As all other edges have zero cost, optimal solutions to this flow problem thus have cost $\sum_{i=1}^{n}{p_i}^2$, as desired.

In general, $s$ has a blue edge to each of $n$ number nodes (labeled $1, 2, \cdots, n$), each of which is adjacent to its own distinct set of $K$ different central nodes. The edges connecting the number nodes to the central nodes all have capacity $1$ and varying costs equal to the first $K$ positive odd numbers. A central node corresponding to a number node with label $c$ is then connected with a blue edge to each of the set nodes for which the set contains $c$. The set nodes correspond to each of the $K$ sets. Finally, all set nodes are connected to $t$ with a red edge.

More generally, the same construction works with any convex cost structure, after the necessary modifications.


Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

This version of the answer incorporates feedback from Emil Jeřábek.
As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit complexity. In particular, fix a binary encoding of boolean circuits and define $L$ as the language defined by

$L_n$ is not decided by any circuit of size $2^{n/2}$, and
any language $L'_n \subseteq \{0,1\}^n$ which precedes $L_n$ lexicographically is decided by some circuit $C$ of size at most $2^{n/2}$,

where the notation $L_n$ means the slice $L_n = L \cap \{0,1\}^n$.
To do this in exponential time with a $\Sigma_2^\mathsf{P}$ oracle, you can use binary search over subsets of $\{0,1\}^n$ (think of them as $2^n$ bit integers) to find the first such set which has circuit complexity $> 2^{n/2}$. You just keep the current guess of $L_n$, and use the oracle to test if there exists a $L'_n \prec_{\text{lex}} L_n$ of circuit complexity at least $2^{n/2}$. Since this gives a machine in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ which writes down the whole slice $L_n$, clearly we can also decide membership in $L_n$, and, therefore, in $L$.
This is very much as in Kannan's argument, but scaled up and streamlined to use the exponential time. Then you should be able to use a scaled-up version of the Karp-Lipton theorem to show that if $\mathsf{NEXP} \subseteq \mathsf{P/poly}$, then $\mathsf{EXP}^{\Sigma^\mathsf{P}_2} \subseteq \mathsf{NEXP}^{\mathsf{NP}}$, and you can carry out the case analysis in Kannan's proof.


Computing distances with approximation less than 2 in general graphs?

As far as I know, there is no published result on computing distances of approximation less than 2 in subquadratic space and sublinear query time. For retrieving approximate distances quickly, you may want to look at results and references in "Faster Algorithms for All-pairs Approximate Shortest Paths" by Baswana and Kavitha (journal version of their FOCS paper has a good review of related work); none of these achieve subquadratic space.

For compactly retrieving approximate distances, you may want to look at the results and references in the above two papers. [As an addition to the answer by Gabor, a word of caution: be careful about the notion of sparsity in above papers -- for approximation $2$, a graph is said to be sparse if $m = o(n^2)$, as you probably know already].

As Sariel pointed out in one of the comments above, a natural lower bound on space for computing distances of approximation less than $2$ is $\Omega(m)$, that is, linear in the size of the graph. If the query time is not bounded, this lower bound can not be improved (trivially, one can use shortest path algorithm by just storing the graph). For constant query time, I know of two lower bounds. First, Patrascu and Roddity had some conditional lower bounds in their FOCS 2010 paper that apply for approximation less than $2$. Second, Sommer et. al. had some lower bounds for extremely sparse graphs. I am not aware of any other (non-trivial) lower bounds.

In terms of upper bounds, the results from above papers do not seem to generalize to approximation less than $2$. We recently made some progress on this problem. The paper should be on ArXiv soon, but if you like, send me an e-mail and I'll be happy to share the paper.

Hope this helps.

~Rachit Agarwal


Testing whether letters can be scheduled to achieve a word in a regular language

The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words:

$x111$, $x000$,
$y100$, $y010$, $y001$,
$00c11$, $01c10$, $10c01$, and $11c00$

The reduction is from the problem Graph Orientation, which is known to be NP-hard (see https://link.springer.com/article/10.1007/s00454-017-9884-9). In this problem, we are given a 3-regular undirected graph in which every vertex is labeled either "$\{1\}$" or "$\{0,3\}$". The goal is to direct the edges of the graph so that the outdegree of every vertex is in the set labeling that vertex.

The reduction needs to take as input a Graph Orientation instance and produce a list of triples as output. In this reduction, the triples we output will always satisfy certain constraints. These constraints are listed below, and we will refer to a list of triples as valid if and only if they satisfy these constraints:

The characters $x$, $y$, and $c$ are only given intervals containing exactly one index. In other words, whenever these characters are placed, they are placed in specific locations.
For every triple $(i, l, r)$ present in the instance with $i \in \{0,1\}$, the triple $(1-i, l, r)$ is also present.
If $(\alpha, l, r)$ and $(\alpha',l',r')$ are both triples present in the instance then either $l < l' \le r' < r$, or $l' < l \le r < r'$, or $\{\alpha,\alpha'\} = \{0,1\}$ with $l = l' < r = r'$.
If $(\alpha, l, r)$ is a triple then the number of triples $(\alpha', l', r')$ with $l \le l' \le r' \le r$ is exactly $r-l+1$.

Note the following lemma, proved at the end of this post.

Lemma: for a valid list of triples, the characters $x$, $y$, and $c$ must be placed exactly as indicated by the triples, and for any pair of triples $(0, l, r)$ and $(1, l, r)$, the two characters for that triple must be placed at indices $l$ and $r$.

Then the idea of the reduction is the following.

We use pairs of triples $(0, l, r)$, and $(1, l, r)$ to represent edges. The edge goes between endpoints at index $l$ and at index $r$. Assuming we produce a valid list of triples, the characters from these two triples must be placed at $l$ and $r$, so we can treat the order in which they are placed as indicating the direction of the edge. Here $1$ is the "head" of the edge and $0$ is the "tail". In other words, if the $1$ is placed at $r$ then the edge points from $l$ to $r$ and if the $1$ is placed at $l$ then the edge points from $r$ to $l$.

To represent vertices, we place an $x$ or $y$ character at an index and use the next three characters as the endpoints of the three edges which touch the vertex. Note that if we place an $x$, all three edges at the vertex must point in the same direction (all into the vertex or all out of the vertex) simply due to the strings that are in finite language $A$. Such vertices have outdegree $0$ or $3$, so we place an $x$ exactly for the vertices labeled $\{0,3\}$. If we place a $y$, exactly one of the three edges at the vertex must point in the same direction due to the strings in $A$. Such vertices have outdegree $1$, so we place a $y$ exactly for the vertices labeled $\{1\}$.

In some sense, we are done. In particular, the correspondence between solving this instance and solving the Graph Orientation instance should be clear. Unfortunately, the list of triples we produce may not be valid, and so the "edges" described may not work as intended. In particular, the list of triples might not be valid because the condition that the intervals from the triples must always contain each other might not hold: the intervals from two edges may overlap without one containing the other.

To combat this, we add some more infrastructure. In particular, we add "crossover vertices". A crossover vertex is a vertex of degree $4$ whose edges are paired such that within each pair one edge must point into the crossover vertex and one out. In other words, a crossover vertex will behave the same as just two "crossing" edges. We represent a crossover vertex by placing the character $c$ at some index $i$. Then note that the language $A$ constrains the characters at $i-1$ and $i+2$ to be opposite (one $0$ and one $1$) and the characters at $i-2$ and $i+1$ to be opposite. Thus, if we use these indices as the endpoints for the four edges at the crossover vertex, the behavior is exactly as described: the four edges are in pairs and among every pair one points in and one points out.

How do we actually place these crossovers? Well suppose we have two intervals $(l, r)$ and $(l', r')$ which overlap. WLOG, $l < l' < r < r'$. We add the crossover character into the middle (between $l'$ and $r$). (Let's say that all along we spaced everything out so far that there's always enough space, and at the end we will remove any unused space.) Let the index of the crossover character be $i$. Then we replace the four triples $(0, l, r)$, $(1, l, r)$, $(0, l', r')$, and $(1, l', r')$ with eight triples with two each (one with character $0$ and one with character $1$) for the following four intervals $(l, i-1)$, $(i+2, r)$, $(l', i-2)$, $(i+1, r')$. Notice that the intervals don't overlap in the bad way anymore! (After this change, if two intervals overlap, one is strictly inside the other.) Furthermore, the edge from $l$ to $r$ is replaced by an edge from $l$ to the crossover vertex followed by the edge from there to $r$; these two edges are paired at the crossover vertex in such a way that one is pointed in and one is pointed out; in other words, the two edges together behave just like the one edge they are replacing.

In some sense, putting in this crossover vertex "uncrossed" two edges (whose intervals were overlapping). It is easy to see that adding the crossover vertex can't cause any additional edges to become crossed. Thus, we can uncross every pair of crossing edges by inserting enough crossover vertices. The end result still corresponds to the Graph Orientation instance, but now the list of triples is valid (the properties are all easy to verify now that we have "uncrossed" any crossing edges), so the lemma applies, the edges must behave as described, and the correspondence is actually an equivalence. In other words, this reduction is correct.

proof of lemma

Lemma: for a valid list of triples, the characters $x$, $y$, and $c$ must be placed exactly as indicated by the triples, and for any pair of triples $(0, l, r)$ and $(1, l, r)$, the two characters for that triple must be placed at indices $l$ and $r$.

proof:

We proceed by induction on the triples by interval length. In particular, our statement is the following: for any $k$ if some triple has interval length $k$ then the character in that triple must be placed as described in the lemma.

Base case: for $k = 0$, the triple must be placing a character $x$, $y$, or $c$ at the single index inside the interval. This is exactly as described in the lemma.

Inductive case: assume the statement holds for any $k$ less than some $k'$. Now consider some triple with interval length $k'$. Then that triple must be of the form $(i, l, r)$ with $r = l+k'-1$ and $i \in \{0,1\}$. The triple $(1-i, l, r)$ must also be present. The number of triples $(\alpha',l',r')$ with $l \le l'\le r' \le r$ is exactly $r-l+1 = k'$. These triples include triples $(0, l, r)$ and $(1, l, r)$ but also $k'-2$ other triples of the form $(\alpha',l',r')$ with $l < l' \le r' < r$. These other triples all have interval length smaller than $k'$, so they all must place their characters as specified in the lemma. The only way for this to occur is if these triples place characters in every index starting at index $l+1$ and ending at index $r+1$. Thus, our two triples $(0, l, r)$ and $(1, l, r)$ must place their characters at indices $l$ and $r$, as described in the lemma, concluding the inductive case.

By induction, the lemma is correct.


This isn't a characterization of NP: it's just an NP-complete problem (well, I assume it's NP-complete, anyway). OK, if so, you could characterize NP as the class of problems reducible to your matrix problem but how are you going to define reductions? Using reductions from some existing model of computation (e.g., Turing machines) would be self-defeating. What advantages would such a characterization have over, say, considering NP to be the class of problems reducible to, say, independent set?

Also, the "structure" matrix $M$ plays no role in the problem except via its determinant so there's no reason for it to be a matrix, rather than just a natural number.


Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

I got a reply from the problem author, wanted to post the info here for reference:

Apparently the problem was solved by Pascal Hennequin in his PhD thesis. Chern and Hwang discuss the solution in Transitional behaviors of the average cost of quicksort with median-of-(2t+1).

I also found that googling quicksort "2t+1" yields the above paper :).


Justifying simplifying assumption about message distributions for perfectly secret encryption?

My initial crack at a solution is the following, please let me know what you think

Fix an encryption scheme (Gen, Enc, Dec) satisfying definiton 2.1 for all distributions over
$\mathcal{M}$ that assign non-zero probability to each $m\in
\mathcal{M}$. Fix a distribution $p_{\mathcal{M}}$ over $\mathcal{M}$
for which $\exists m \in \mathcal{M}$ such that $p_{\mathcal{M}}(m) = 0$. Let $N$ denote the set of all such $m$. To avoid triviality, assume $\exists$ at least 2 messages $m_0, m_1 \in \mathcal{M}$ such that $p_{\mathcal{M}}(m_0) > 0$ and $p_{\mathcal{M}}(m_1) > 0$.

Now, we let $p^* = p_{\mathcal{M}}(m_0)$, and create an "altered"
distribution as follows. Let $p'_{\mathcal{M}}(m) =
p_{\mathcal{M}}(m)$ for all $m \in \mathcal{M} \setminus (N \cup
\{m_0\})$, and let $p'_{\mathcal{M}}(m) = \frac{p(m_0)}{| N \; \cup \;
  \{m_0\} |}$ (that is, the altered distribution is the same as the
original, except it distributes the probability $p_{\mathcal{M}}(m_0)$
evenly amongst $m_0$ and all the messages in $N$). For notational
convenience, let $N' :=  N \; \cup \;
  \{m_0\} $.

Now,
$p'_{\mathcal{M}}$ is a distribution in which all messages have
non-zero probability, so (Gen, Enc, Dec) is perfectly secret with
respect to this distribution. That is, Gen and Enc define a distribution
over the set of ciphertexts $\mathcal{C}$ such that:

$$p'(M = m \mid C = c) = \frac{p'(M=m, C = c)}{p'(C = c)} = p'(M = m)$$

for all $m \in \mathcal{M}, c \in \mathcal{C}$. (Here $p'$ denotes the
joint probability over messages and ciphertexts determined by the
distribution $p'_{\mathcal{M}}$ over $\mathcal{M}$, the distribution
over keys generated by Gen, and the randomness of Enc). Then, I claim, (Gen,
Enc, Dec) must be perfectly secret with respect to the original
distribution, $p_{\mathcal{M}}$ over $\mathcal{M}$.

Claim 1: For all $m \not \in  N'$, and for all $c \in \mathcal{C}$:
 $$p'(M=m, C=c) = p(M=m,
  C=c)$$
(where $p'$ is as before and $p$ denotes the
joint probability over messages and ciphertexts determined by the
distribution $p_{\mathcal{M}}$ over $\mathcal{M}$, the distribution
over keys generated by Gen, and the randomness of Enc). The reason
this holds is that Gen and Enc act independently of the
  distribution over $\mathcal{M}$. Since $p'_{\mathcal{M}}(m) =
  p_{\mathcal{M}}(m) \forall m \not \in  N'$, the claim follows.

Claim 2: For all $c \in \mathcal{C}$:
$$p(M=m_0, C=c) = \sum_{m \in N'} p'(M=m, C=c) $$
First, we note that for any $c\in \mathcal{C}$ and for any $m \in
\mathcal{M} \setminus N'$, $p(C=c \mid M= m) = p'(C = c \mid M = m)$,
since the randomness of Gen and Enc are completely independent of the
distribution over $\mathcal{M}$, and so the message-conditional
probability of any particular ciphertext is equal. Then, fix $c\in \mathcal{C}$
$$
\begin{align*}
p(M=m_0, C = c) &= p(C=c \mid M=m_0)p(M=m_0) \\
&= p'(C = c \mid M = m_0)p(M = m_0), \text{ by the above discussion} \\
&= p'(C=c)p(M= m_0), \text{ since (Gen, Enc, Dec) is perfectly secret
  for } p'_{\mathcal{M}} \\
&= p'(C=c) \sum_{m \in N'} p'(M = m) \\
&= p'(C=c) \sum_{m \in N'} p'(M = m \mid C = c) \\
&= \sum_{m \in N'} p'(M=m, C=c)
\end{align*}
$$

Thus, since
$$p(C = c) = \sum_{m \in \mathcal{M}} p(M=m, C=c) = \sum_{m
  \in \mathcal{M}} p'(M=m, C=c) = p'(C=c)$$
 we see that the
distribution over ciphertexts remains the same with respect to both distributions
over $\mathcal{M}$. Combined with Claim 1, we see that

$$
\begin{align}
p(M =m \mid C=c) &= \frac{p(M=m, C=c)}{p(C=c)} \\
&= \frac{p'(M=m, C=c)}{p'(C=c)} \\
&= p'(M=m \mid C=c) \\
&= p'(M=m) \\
&= p(M=m)
\end{align}
$$

for all $m \in \mathcal{M} \setminus N'$ and all $c \in
\mathcal{C}$. For $m \in N' \setminus \{m_0\}$,
$$p(M= m \mid C = c) =
0 = p(M=m)$$
.

What remains to be seen is that $p(M=m_0 \mid C =
c) = p(M =m_0)$. This is the case, since for all $c \in \mathcal{C}$
$$
\begin{align}
p(M=m_0 \mid C = c) &= \frac{p(M=m_0, C=c)}{p(C=c)} \\
&= \sum_{m \in N'} \frac{p'(M=m, C=c)}{p'(C=c)}, \text{ by Claim 2} \\
&= \sum_{m \in N'} p'(M=m \mid C=c) \\
&= \sum_{m \in N'} p'(M=m), \text{ since (Gen, Enc, Dec) is
  perfectly secret w.r.t }p'_{\mathcal{M}}\\
&= p(M=m_0), \text{ by definition of }p'_{\mathcal{M}}
\end{align}
$$
And so the claim is proven.


Cryptography without assumptions -- seeking an overview

The key phrases you are probably looking for are "information-theoretic cryptography" and "quantum cryptography".  Searching the literature on these topics will turn up lots of work of the sort you are looking for.  Some example highlights below:

For confidentiality: the one-time pad, the Wyner wiretap channel, secret sharing, quantum key exchange, etc.
For integrity and authentication: universal hash functions.
For anonymity: anonymous communication (e.g., DC nets, onion-based schemes, p2p networks based upon rapidly mixing random walks), distance bounding protocols.
For security based upon physical assumptions: PUFs (physically unclonable functions), integrity codes (Capkun et al.), quantum cryptography, security using TPMs or tamper-resistant hardware.

There are lots of papers on those topics; too many to summarize all the results in the literature.


Communication complexity problems with linear distance

Let $C:\{0,1\}^{n} \to \{0,1\}^{2n}$ be an error correcting code with linear distance. Let $g: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}$ be a function whose randomized communication complexity is large (say, $\Omega(\sqrt{n})$ or $\Omega(n))$.

Define $f: \{0,1\}^{2n} \times \{0,1\}^{2n} \to \{0,1,*\}$ to be the partial function that on codewords of $C$ outputs $f(x,y) = g(C^{-1}(x),C^{-1}(y))$, and it outputs $*$ if at least one of $x,y$ is not in $C$.

Clearly, the communication complexity of $f$ is equal to the communication complexity of $g$, and $f$ satisfies the property that for every two different inputs on which $f$ outputs 0 or 1, the distance between them is linear.


representing code path as graph walks.. a provable graph walk?

This paper matches some of your criteria:

Nenad Dedic, Mariusz H. Jakubowski, Ramarathnam Venkatesan: A Graph Game Model for Software Tamper Protection. Information Hiding 2007: 80-95

It uses random walks on the flow graph of a program to make the program more tamper resistant.


Complexity of factoring in number fields

The following answer was originally posted as a comment on Gil's blog

(1) Let $K=\mathbb{Q}(\alpha)$ be a number field, where we assume $\alpha$ has a monic minimal polynomial $f\in\mathbb{Z}[x]$.  One can then represent elements of the ring of integers $\mathcal{O}_K$ as polynomials in $\alpha$ or in terms of an integral basis -- the two are equivalent.

Now fixing $K$ as in (1) there's a polynomial-time reduction from the problem over $K$ to the problem in $\mathbb{Q}$.  To verify that the computations (e.g. intersecting an ideal with $\mathbb{Z}$ or factoring a polynomial mod $p$) can be done in polynomial time see Cohen's book referred to in the previous answer.

As a precomputation for each rational prime $p$ dividing the discriminant of $\alpha$ (that is the discriminant of $f$) find all primes of $\mathcal{O}_K$ lying above $p$.

(2) For primality testing, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ let $p\in\mathbb{Z}$ be such that $\mathfrak{a}\cap\mathbb{Z} = p\mathbb{Z}$ (this can be computed in polynomial time and the number of bits of $p$ is polynomial in the input).  Check in polynomial time whether $p$ is prime. If not then $\mathfrak{a}$ is not prime.  If yes then find the primes of $\mathcal{O}_K$ lying above $p$ either from the precomputation or by factoring $f$ mod $p$.  In any case if $\mathfrak{a}$ is prime it must be one of those primes.

(3a),(6a) For factoring into primes, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ find its norm $y = N^K_\mathbb{Q}(\mathfrak{a}) = [\mathcal{O}_K:\mathfrak{a}]$. Again this can be found in polynomial time and consequently is not too large. Factor $y$ in $\mathbb{Z}$ (either classically or using Shor's algorithm, depending on the reduction you want).  This gives a list of rational primes dividing $y$, and hence as in 2 we can find the list of primes of $\mathcal{O}_K$ dividing $y$.  Since $\mathfrak{a} | y\mathcal{O}_K$ this gives the list of primes dividing $\mathfrak{a}$.  Finally it is easy to determine the exponent to which a prime divides a given ideal.

(3b),(6b) But Gil wants factorization into irreducibles, not into primes. It turns out that given the prime factorization of $x\mathcal{O}_K$ it is possible to efficiently construct one factorization of $x$ into irreducible elements of $\mathcal{O}_K$.  For this let $h_K$ be the class number, and note that it is possible to efficiently compute the ideal class of a given ideal. Now to find an irreducible divisor of $x$ select $h_K$ prime ideals (possibly with repetition) from the factorization of $x$.  By the pigeon-hole principle some subset of those multiplies to the identity in the class group; find a minimal such subset.  Its product is then a principal ideal generated by an irreducible element.  Divide $x$ by this element, remove the relevant ideals from the factorization and repeat.  If the factorization has less than $h_K$ elements then just take a minimal subset of all the factors.

(4) I think it's possible to count the factorizations into irreducibles, but this is a bit of extra combinatorics -- please give me time to work it out.  One the other hand, determining all of them is not interesting in the context of sub-exponential factorization algorithms since there are in general exponentially many such factorizations.

(5) I have no idea.


The application you mention is called "proof of useful work" in the literature, see for instance this article.

You can use a fully homomorphic encryption scheme (where the plaintext is the CNF instance) to delegate the computation to an untrusted party without disclosing the input.

This doesn't answer exactly your question, since such scheme doesn't map a CNF into another CNF, but it does work for the intended application.


Commitment schemes with verification in NC0

No. $\;\;\;\;$ There is also no secure commitment scheme where the verification

routine can be done with bounded fan-in in depth $\:o(\hspace{.02 in}\log(\hspace{.02 in}\log(k)))\:$,

since such circuits have input locality $\:(\hspace{.02 in}\log(k))^{o(1)}$,$\:$ which means one can

efficiently brute-force the bits that might affect the verification circuit's output.


Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)

In any graph, the parity of the number of vertex covers is equal to the parity of the number of edge covers.

To see why, check this answer and observe how the parity of $|C|$ is equal to the parity of $\Delta_{|V|} = O_{|V|} - E_{|V|}$, which is in turn equal to the parity of $O_{|V|} + E_{|V|}$, which is the number of edge covers.

Computing the parity of the number of vertex covers is $\oplus$P-hard: therefore computing the parity of the number of edge covers is $\oplus$P-hard as well.

At least the second half of the question has been settled.


If you're okay with additional variables, then the answer is yes. This follows from Balas's extended formulation for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{hull} ( \cup_j P_j)$ admits an extended formulation of size at most $\sum_{j}(\operatorname{xc}(P_j)+1)$, where $\operatorname{xc}(\cdot)$ denotes extension complexity. (The extension complexity of $P_j$ is at most the number of inequalities defining $P_j$.)

I have not thought about whether this can be done in the original space of variables.


What does 'gadget' mean in NP-hard reduction?

A "gadget" is a small specialized device for some particular task. In NP-hardness proofs, when doing a reduction from problem A to problem B, the colloquial term "gadget" refers to small (partial) instances of problem B that are used to "simulate" certain objects in problem A. For example, when reducing 3SAT to 3-COLORING, clause gadgets are small graphs that are used to represent the clauses of the original formula and variable gadgets are small graphs that are used to represent the variables of the original formula. In order to ensure that the reduction is correct, the gadgets have to be graphs that can be 3-colored in very specific ways. Hence we think of these small graphs as devices that perform a specialized task.

In many cases, the main difficulty of proving NP-hardness is constructing appropriate gadgets. Sometimes these gadgets are complicated and moderately large. The creative process of creating such gadgets is sometimes called "gadgeteering."


Super-polynomial time approximation algorithms for MAX 3SAT

One can get a $7/8+\varepsilon/8$ approximation for MAX3SAT that runs in $2^{O(\varepsilon n)}$ time without too much trouble. Here is the idea. Divide the set of variables into $O(1/\varepsilon)$ groups of $\varepsilon n$ variables each. For each group, try all $2^{\varepsilon n}$ ways to assign the variables in the group. For each reduced formula, run the Karloff and Zwick $7/8$-approximation. Output the assignment satisfying a maximum number of clauses, out of all these trials.

The point is that there is some variable block such that the optimal assignment (restricted to that block) already satisfies a $\varepsilon$-fraction of the maximum number of satisfied clauses. You'll get those extra clauses exactly correct, and you'll get $7/8$ of the the remaining fraction of the optimum using Karloff and Zwick.

It is an interesting question if one can get $2^{O(\varepsilon^2 n)}$ time for the same type of approximation. There is a "Linear PCP Conjecture" that 3SAT can be reduced in polynomial time to MAX3SAT, such that:

if the 3SAT instance is satisfiable then the MAX3SAT instance is completely satisfiable,
if the 3SAT instance is unsatisfiable then the MAX3SAT instance isn't $7/8+\varepsilon$ satisfiable, and
the reduction increases the formula size by only a $poly(1/\varepsilon)$ factor.

Assuming this Linear PCP Conjecture, a $2^{O(\varepsilon^c m)}$-time $7/8+\varepsilon$ approximation, for all $c$ and $\varepsilon$, would entail that 3SAT is in $2^{\varepsilon n}$ time, for all $\varepsilon$. (Here $m$ is the number of clauses.) The proof uses the Sparsification Lemma of Impagliazzo, Paturi, and Zane.


Is eta-equivalence for functions compatiable with Haskell's seq operation?

First, let us be explicit about how seq distinguishes $\bot$ from $\lambda x . \bot$:

bottom :: a
bottom = bottom

eta :: a -> b
eta x = bottom

-- This terminates
fortytwo = seq eta 42

-- This does not terminate
infinity = seq bottom 42

It is therefore an experimental fact that in Haskell $\bot$ and $\lambda x . \bot$ are operationally distinguishable. It is also a fact, and a quite obvious one, that seq is computable because Haskell computes it. So much about Haskell. You are asking about the very particular phrasing of the Haskell documentation. I read it as saying that seq is supposed to satisfy the two given equations, but those two equations are not sufficient for the definition of seq. Here is why: I can give you two models of (simply typed) $\lambda$-calculus in which seq is computable and satisfies the given equations, but in one of the models $\bot$ and $\lambda x . \bot$ agree, while in the other they do not.

In a simple domain-theoretic model where $\lambda$-expressions are interpreted in the domain of continuous functions $[D \to E]$ we have $\bot = \lambda x . \bot$, obviously. Take effective Scott domains or some such to make everything computable. It is easy to define seq in such a model.

We can also have a model of $\lambda$-calculus in which seq distinguishes $\bot$ and $\lambda x . \bot$, and then of course $\eta$-rule cannot hold. For instance, we can do this by interpreting functions in the domain $[D \to E]_\bot$, i.e., the function space domain with an extra bottom attached. Now $\bot$ is, well, the bottom of $[D \to E]_\bot$, while $\lambda x . \bot$ is the element just above it. They cannot be distinguished by application because they both evaluate to $\bot$, no matter what you apply them to (they are extensionally equal). But we do have seq as a map between domains and it alwyas distinguishes bottom from all other elements.


Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

I think you could be interested by the counting class Span-P (which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time). It was introduced in this paper. Both 1) and 2) are in Span-P. For 1): guess a subgraph, then guess a Hamiltonian circuit, then output the graph (of course order the nodes beforehand so that you don't output the same graph twice). For 2) something similar should work.

In this paper they also show that a version of 1) is Span-P complete (page 375). The only difference is that a number $k$ is also part of the input and they want only the Hamiltonian subgraphs of size $k$ (I'm assuming the "positive integer $c$" was a typo). Also at the end of Section 6 ("A variation of the above...") they specifically mention your problem (so without the restriction of size $k$) and they that they do not know if it is Span-P hard.


Cryptographic systems that don't leak linear combinations of encrypted bits

Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing.

The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack: an attacker cannot distinguish the encryption of messages $M_1,\dots,M_n$ (chosen by the attacker) from the encryption of random strings $R_1,\dots,R_n$ (chosen randomly and not revealed to the attacker).  This fact is proven in Bellare & Rogaway's lecture notes, or is easy to derive yourself via a hybrid argument.

Now your result follows.  Let $\ell$ be any linear function of the message.  Then it follows that no attacker can predict $\ell(M_i)$ better than random guessing.  Why?  $\ell(R_i)$ is a random bit.  So, if knowledge of $E_k(M_i)$ lets you distinguish $\ell(M_i)$ from random (i.e., distinguish $\ell(M_i)$ from $\ell(R_i)$), then it would also let you distinguish $E_k(M_i)$ from $E_k(R_i)$, which would violate semantic security.


Is there an efficient algorithm for finding edges that are part of all hamiltonian paths?

A polytime algorithm that can find such a collection of edges even in the promise version of this problem can be used as a blackbox to solve the Hamiltonian Path problem in polynomial time, and thus this promise problem is NP-Hard under Cook reductions. The idea here is to use the algorithm for solving the promise problem on a sequence of graphs, many (but not all) of which potentially violate the promise given in the problem statement. Importantly, nothing is assumed of the output of the algorithm when it is fed a promise-violating graph as input, just that it outputs something (perhaps even adversarially). We can, of course, always cut the algorithm off and return the empty set as its solution if its execution is taking longer than some provided time bound (a bound only proven to hold only in promise-satisfying instances) and satisfy this requirement. It is the nature of the change in the algorithm's output (or lack thereof) on the sequence of instances that interests us.

Suppose you have a graph $G=(V,E)$ in which you wish to determine the existence of a Hamiltonian path, and oracle access to a function $\varphi$ such that $\varphi(G) = h(G)$ (where $h$ is defined as in David's post) whenever $G$ contains a Hamiltonian path (and returns an arbitrary answer otherwise). Intuitively, the algorithm searches for a supergraph $H$ of $G$ on which $\varphi(H) = h(H)$ is violated. If such a graph can be found, it must be the case that $H$ (and all of its subgraphs, including $G$) is not Hamiltonian. Conversely, not violating the inequality on any graph in the sequence shows that the original $G$ is Hamiltonian.

Now construct a sequence of graphs $G_0 \cdots G_{n-1}$ as follows:

Let $G_0 = G$
Pick a permutation $\pi$ of $V$ such that no $(\pi_i, \pi_{i+1})$ is an edge of $\varphi(G_0)$.*
For $i = 1$ to $n-1$

Let $e_i = (\pi_i, \pi_{i+1})$
Let $G_i = G_{i-1}$ with edge $e_i$ added (if it did not already exist in $G_{i-1}$)

Note that $h(G_x) \supseteq h(G_y)$ when $x < y$ (i.e. containment of some fixed edge in $h$ is hereditary among the $\{G_i\}$). Thus, if $e_i \in \varphi(G_i)$ for some $i \geq 1$, it must be the case that $G$ does not contain a Hamiltonian Path, since $\varphi(\cdot)$ is not hereditary on this graph family (recall that $e_i$ is not in $\varphi(G_0)$) and thus $\varphi(G_i) \neq h(G_i)$ for some $G_i$.

However, if $e_i \not \in \varphi(G_i)$ for all $i$, no single addition of an edge was necessary in the construction of the first (set of) Hamiltonian Path(s) in the sequence in which we constructed $\{G_i\}$. Since $G_{n-1}$ contains a Hamiltonian path by construction, a simple inductive argument implies $G_0$ must contain one as well.

Thus, Hamiltonian Path can be solved via $O(n)$ queries to an oracle solving this promise problem (assuming they produce an arbitrary output on promise-violating graphs), meaning that any time bound $f(n)$ for an algorithm solving this problem implies a time bound of $O(n f(n))$ for solving Hamiltonian Path, and thus $f(n)$ (and any provable upper bound on the running time for a TM solving this problem) cannot be a polynomial unless $P = NP$.

*This is easy to do because $|h(G_0)| \leq n$ by definition, and we could always of course prematurely determine the nonexistance of a Hamiltonian path if $|\varphi(G_0)|$ is any larger than that.


Number of vertices at distance $k$ for each vertex of restricted sparse graph

Thank you for the interesting question!

First, let's consider the easy part.  Given that you want the distances from every vertex for all distances, you are asking for all-pairs shortest paths.

Therefore you need to find $|V|(|V|-1)/2$ distances between pairs of vertices, and you cannot do better than essentially $c|V|^2/2$ steps for some small constant $c$.

Your restriction to low bounded degree $d$ implies that $|E| \le d|V|/2$.  For $d\le 8$ this means $|E| \le 4|V|$.

As Shir points out in a comment, running BFS starting from each vertex therefore takes at most $C(|V|+|E|)|V| \le C(|V| + 4|V|)|V| = 5C|V|^2$ steps for some small constant $C$.  The actual running time will probably be less, since your $d\le 8$ is an upper bound; depending on the graph the multiplier may be closer to the average degree.

So the solution will have an unavoidable $|V|^2$ factor, multiplied by a constant between $c/2$ and $(1+(d/2))C$.

That is as far as a purely asymptotic analysis goes.
However, you indicate you need to do this millions of times (presumably for different graphs), so even a small improvement is likely to be worthwhile, and that it would be worth improving the constants.

Assuming that $c$ and $C$ are similar, the question is then whether it is possible to reduce the multiplier from the $(d/2)+1$ upper bound (which seems to be around $3$ in your setting), to get it closer to the optimal $1/2$.

Depending on the structure of the graph, a modified BFS may give a lot of information about intermediate shortest paths.  If you start a BFS at $u$, then see vertex $v$ in the search at distance $d$, then see vertex $w$ at distance $d+e$ in the subtree rooted at $v$, you can conclude that $d(u,w)=d+e$ and $d(u,v)=d$, but also that $d(v,w)=e$.  In short, one can extract some of the entries $d(v,w)$ in the distance matrix (where $v$ and $w$ are different from $u$) from the shortest path tree rooted at $u$.  This seems to be essentially the idea of this SO answer to a related question.

Whether the cost of extracting additional information out of the shortest path trees is worth the cost depends on the structure of your graphs.  For this to be worthwhile, it should allow a lot of information to be extracted from the first few BFS searches, so that many of the later vertices from which a BFS would be started already have their entries in the distance matrix filled in and can be skipped.

The following question then seems interesting:

  How should a "good" set of starting vertices be chosen?

With "good" I mean a small set $U$ of vertices so that after modified BFS has been run with each $u\in U$ as the starting vertex, then all (or nearly all) of the remaining vertices all have their shortest path vectors fully computed.  Examining some low-degree graphs this seems to be an interesting idea: for a path, either endpoint allows a single BFS to compute all the distance vectors; for a cycle, taking two vertices far apart works.  For trees, a single BFS starting from an internal vertex $u$ can be used to derive the distance matrix, since if $d(v,w)$ is not known at the end of the BFS, then $v$ and $w$ must be descended from different children of $u$, and then $d(v,w) = d(v,u)+d(u,w)$ which are both known.

The Nash-Williams decomposition of a graph into edge-disjoint forests might then be relevant.  The arboricity of a graph with maximum degree $8$ seems to be at most $4$ (I might be wrong here; however, David Eppstein confirms that arboricity of bounded degree graphs is bounded).  So it might be possible to find a small number of vertices from which BFS search trees yield all relevant shortest path information, i.e. so that the distance matrix can always be computed using these trees, and so that the edges of the BFS search trees cover the graph.  I do not know how large "small" is in this statement, or even if it can always be made to be $4$.

David Eppstein, Arboricity and bipartite listing algorithms, IPL 51, 207–211, 1994.  doi:10.1016/0020-0190(94)90121-X (preprint)

I didn't find anything solving this particular version of the problem when searching, but expect it has been thought about already.
There is a recent paper which uses a distributed Nash-Williams decomposition to obtain maximal independent sets.
Perhaps someone else has a pointer to a more directly relevant paper.

Leonid Barenboim and Michael Elkin, Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using Nash-Williams Decomposition, Distributed Computing 22, 363–379, 2010.  doi:10.1007/s00446-009-0088-2 (preprint)


Here is an attempt at an $n^2$ DP-based algorithm:
Compute $M(\ell)$, the maximum such sum that uses only $a_1,\ldots,a_\ell$ (but it is not required that $a_\ell$ is used!). To compute $M(\ell)$ you have to take into account: (1) $M(\ell-1)$ and (2) all combinations of using $M(i-1)$, for some $i<\ell$, and picking $a_i$ and $a_\ell$, on top of it. This looks like a linear outer loop with a linear inner loop. The penalty does not seem to hurt: just add $a_\ell-a_i-2$ in the latter case. A non-linear penalty would be a different story.


Wikipedia-style explanation of Geometric Complexity Theory

I'm not exactly sure what level is suitable for Wikipedia article (different articles seem to be aimed at different levels of expertise) or exactly what you're looking for. So here's a try, but I'm open to feedback.

Geometric complexity theory proposes to study the computational complexity of computing functions (say, polynomials) by exploiting the inherent symmetries in complexity and any additional symmetries of the functions being studied.

As with many previous approaches, the ultimate goal is to separate two complexity classes $\mathcal{C}_{easy}, \mathcal{C}_{hard}$ by showing that there is a polynomial $p$ which takes functions $f$ as inputs (say, by their coefficient vectors) such that $p$ vanishes on every function $f \in \mathcal{C}_{easy}$ but does not vanish on some function $g_{hard} \in \mathcal{C}_{hard}$.

The first key idea (cf. [GCT1, GCT2]) is to use symmetries to organize not the functions themselves, but to organize the (algebro-geometric) properties of these functions, as captured by polynomials such as $p$ above. This enables the use of representation theory in attempting to find such a $p$. Similar ideas relating representation theory and algebraic geometry had been used in algebraic geometry before, but to my knowledge never quite in this way.

The second key idea (cf. [GCT6]) is to find combinatorial (and polynomial-time) algorithms for the resulting representation-theoretic problems, and then reverse-engineer these algorithms to show that such a $p$ exists. This may be taken in the spirit of using Linear Programming (an algorithm) to prove certain purely combinatorial statements.

Indeed, [GCT6] suggests reducing the representation-theoretic problems above to Integer Programming problems, then showing that the resulting IPs are solved by their LP relaxations, and finally giving combinatorial algorithms for the resulting LPs. The conjectures in [GCT6] are themselves motivated by reverse-engineering known results for the Littlewood-Richardson coefficients, an analogous but easier problem in representation theory. In the case of LR coefficients, the Littlewood-Richardson combinatorial rule came first. Later Berenstein and Zelevinsky [BZ] and Knutson and Tao [KT] (see [KT2] for a friendly overview) gave an IP for LR coefficients. Knutson and Tao also proved the saturation conjecture, which implies that the IP is solved by its LP relaxation (cf. [GCT3,BI]).

The results of [GCT5] show that explicitly derandomizing Noether's Normalization Lemma is essentially equivalent to the notorious open problem in complexity theory of black-box derandomization of polynomial identity testing. Roughly how this fits into the larger program is that finding an explicit basis for the functions $p$ that (do not) vanish on $\mathcal{C}_{easy}$ (in this case, the class for which the determinant is complete) could be used to derive a combinatorial rule for the desired problem in representation theory, as has happened in other settings in algebraic geometry. An intermediate step here would be to find a basis for those $p$ that (do not) vanish on the normalization of $\mathcal{C}_{easy}$, which is by construction a nicer algebraic variety -- in other words, to derandomize Noether's Normalization Lemma for DET.

Examples of symmetries of complexity and functions

For example, the complexity of a function $f(x_1, \dotsc, x_n)$ - for most natural notions of complexity - is unchanged if we permute the variables $f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$ by some permutation $\pi$. Thus permutations are symmetries of complexity itself. For some notions of complexity (such as in algebraic circuit complexity) all invertible linear changes of the variables are symmetries.

Individual functions may have additional symmetries. For example, the determinant $\det(X)$ has the symmetries $\det(AXB) = \det(X^{T}) = \det(X)$ for all matrices $A,B$ such that $\det(AB) = 1$. (From what little I picked up about this, I gather that this is analogous to the phenomenon of spontaneous symmetry-breaking in physics.)

Some Recent Progress [this section definitely incomplete and more technical, but a complete account would take tens of pages....I just wanted to highlight some recent progress]

Burgisser and Ikenmeyer [BI2] showed a $\frac{3}{2}n^2$ lower bound on matrix multiplication following the GCT program as far as using representations with zero vs nonzero multiplicities. Landsberg and Ottaviani [LO] gave the best known lower bound of essentially $2n^2$ on the border rank of matrix multiplication using representation theory to organize algebraic properties, but not using representation multiplicities nor combinatorial rules.

The next problem after Littlewood-Richardson coefficients is the Kronecker coefficients. These show up both in a series of problems that is suspected to eventually reach the representation-theoretic problems arising in GCT, and more directly as bounds on the multiplicities in the GCT approach to matrix multiplication and permanent versus determinant. Finding a combinatorial rule for Kronecker coefficients is a long-standing open problem in representation theory; Blasiak [B] recently gave such a combinatorial rule for Kronecker coefficients with one hook shape.

Kumar [K] showed that certain representations appear in the coordinate ring of the determinant with nonzero multiplicity, assuming the column Latin square conjecture (cf. Huang-Rota and Alon-Tarsi; this conjecture also, perhaps not coincidentally, shows up in [BI2]). Hence these representations cannot be used to separate permanent from determinant on the basis of zero vs nonzero multiplicities, though it still might be possible to use them to separate permanent from determinant by a more general inequality between multiplicities.

References
[B] J. Blasiak. Kronecker coefficients for one hook shape. arXiv:1209.2018, 2012.

[BI] P. Burgisser and C. Ikenmeyer. A max-flow algorithm for positivity of Littlewood-Richardson coefficients. FPSAC 2009.

[BI2] P. Burgisser and C. Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. arXiv:1210.8368, 2012.

[BZ] A. D. Berenstein and A. V. Zelevinsky. Triple multiplicities for $\mathfrak{sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation. J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput. 31(2), 496–526, 2001.

[GCT2] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput., 38(3), 1175–1206, 2008.

[GCT3] K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] K. D. Mulmuley. Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's Normalization Lemma. FOCS 2012, also arXiv:1209.5993.

[GCT6] K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.

[K] S. Kumar. A Study of the representations supported by the orbit closure of the determinant. arXiv:1109.5996, 2011.

[LO] J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. arXiv:1112.6007, 2011.

[KT] A. Knutson and T. Tao. The honeycomb model of $\text{GL}_n(\mathbb{C})$ tensor products. I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson and T. Tao. Honeycombs and sums of Hermitian matrices. Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186.


For some obscure reason everyone is answering in comments, so let me comment in an answer.

While I am not aware of any standard macros for this, I'm partial to the G&J format (which is basically the format you use in the question. Namely,

  PROBLEM NAME
  INSTANCE: description of instance
  QUESTION: description of problem


Is there an efficient algorithm to determine the parity of the longest path in a graph?

Based on Gadi's answer on Math.SE (which proves NP-hardness using a Cook reduction), here is a proof of NP-hardness using a Karp reduction (as requested).
General case
The reduction is from Hamiltonian Cycle through Hamiltonian Path.
Part 1: Hamiltonian Cycle $\le_m^P$ Hamiltonian Path
We begin with a graph $G$ with $n$ vertices and want to know if it contains a Hamiltonian cycle.  We use a standard reduction to Hamiltonian Path (see Theorem 8.19 of Algorithm Design, which gives the directed graph version). Specifically,

pick a vertex $v \in G$,
add a vertex $v_0$,
for each edge $(v, u)$, add an edge $(v_0, u)$,
add vertices $u_1$ and $u_2$, and
add edges $(v, u_1)$ and $(v_0, u_2)$.

Call this graph $G_1$. If $G$ has a Hamiltonian cycle, then $G_1$ has a Hamiltonian path (that with end points $u_1$ and $u_2$). If $G_1$ has a Hamiltonian path, then it's end points must be $u_1$ $u_2$ since they have degree one, so other vertices in the Hamiltonian path give a Hamiltonian cycle when equating $v$ and $v_0$.
Part 2: Hamiltonian Path $\le_m^P$ Parity of Longest Path Even
This reduction continues the one started above, so we have the graph $G_1$ with $n_1 = n + 3$ vertices.
If $n_1$ is odd, then a Hamiltonian path in $G_1$ (if one exists) would have to be of even length. In this case, we use the same reduction as Gadi, which adds a disjoint path of length $n_1 - 2$ to $G_1$ to form a graph $G_2$.
If $n_1$ is even, then a Hamiltonian path in $G_1$ (if one exists) would have to be of odd length. The case of odd $n_1$ is better, so we reduce to it by adding a vertex $w$ and edge $(w, u_1)$, forming a graph $G_2$. Now, a Hamiltonian path in $G_1$ (if one exists) would have to be of even length (and have end points $w$ and $u_2$ since they both have degree one), so we complete the reduction as above by adding a disjoint path of length $n_1 - 1$ to form a graph $G_2$.
If $G_1$ contains a Hamiltonian path, then the length of the longest path in $G_2$ is even (of length $n_1 - 1$ when $n_1$ is odd and of length $n_1$ when $n_1$ is even). If $G_2$ contains a longest path of even length, then $G_1$ must contain a Hamiltonian path since we know there is a path of odd length that is one shorter than the length required in a Hamiltonian path.
Restricted to cubic graphs
I do not see how the reduction for the general case can be made to work for cubic graphs since all cubic graphs have an even number of vertices. However, your requirement that the algorithm should say Yes iff the parity of the longest path is even is contrary what I have always heard regarding parity, which is the algorithm says Yes iff the parity is odd.
Restricted to cubic (and planar) graphs when Yes iff longest path of odd parity
The reduction for the general case can be made to work for cubic planar graphs when the algorithm says Yes iff the parity of the longest path is odd.
This time, we reduce from Hamiltonian Path directly. Thus, we begin with a cubic planar graph $G$ with $n$ vertices and want to know if it contains a Hamiltonian path.
Since $n$ is even, we want to add a disjoint graph with a longest path of size $n-2$. This is possible for $n \ge 10$ as pictured...

...since that is the shortest (even) length of the longest path possible via this path gadget.
For $n < 10$, we do a brute force search for the existence of a Hamiltonian path in $G$ and add the smallest path gadget if we don't find one.


Tradeoff Bounds for Halfspace Range Counting

Matoušek's stronger time bound is correct.

The proof of Theorem 6.1 (in the journal version) uses an indirection trick that reduces the space bound required for logarithmic query time from $O(n^d)$ to $O(n^d/\operatorname{polylog} n)$.  Intuitively, the trick is to cluster the points into subsets of polylogarithmic size, build a linear-space data structure for each subset, and then build a standard logarithmic-query-time structure over the subsets.  Plugging the improved space bound into  Matoušek's multi-level/tradeoff machinery—described in gory generality in the longer version of Agarwal's survey—gives Matoušek's form of the time-space tradeoff.  (In fact, the indirection trick is just a very careful application of the standard tradeoff machinery.)


How many samples are needed to reconstruct a path?

Here’s a simple idea: try a certain number $s$ of samples, and for each vertex, record how many times its colour agreed with the provided bit.

For vertices outside the path, they agree with probability $1/2$ on each iteration, while for vertices on the path, the probability is $1/2+1/2k$, where $k$ is the number of vertices on the path.

Thus, if $s\approx k^2\log n$, the Chernoff–Hoeffding inequality ensures that with probability at least $2/3$, all vertices outside the path agree for less than $s(1/2+1/4k)$ samples, and all vertices on the path agree for more than $s(1/2+1/4k)$ samples, which lets you pinpoint the path. If you don’t know $k$ in advance, you can just bound it by $n$.


Preservation under Substitution with Telescopes

The most general form of substitution theorems speaks about arbitrary contexts:

Define what it means to have a substitution $\sigma : \Gamma \to \Delta$ from a context $\Gamma$ to a context $\Delta$ (it's a simultaneous substitution giving a term $\Gamma \vdash e : A$ for every $y : A$ appearing in $\Delta$, and in case of type dependencies we have to do it recursively).
Prove that if $\Delta \vdash e : A$ then $\Gamma \vdash e\sigma : A\sigma$.

In such generality there is no reliance on exchange rules and it all works in dependent type theory as well. The case suggested by Max New in his answer is a special case.


Deterministic error reduction, state-of-the-art?

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions.

In Dwork's lecture notes as well, the condition required is that the expansion be $C/\delta$ for some constant $C$ (looking at a points in distance c is essentially using powering to improve expansion). Which again can be obtained with degree $O(1/\delta)$.

Perhaps there is a lower bound of $\Omega(1/\delta)$ on number of runs required.


Information theory and convex optimization

The books below may be more to your liking, but in general, the texts/lecture notes are written for the use of (mainly) postgraduate students in engineering and cannot presume deep knowledge of convex analysis.

Csizsar, I., and Korner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd Ed, Cambridge.
Berger, T., Rate Distortion Theory, quite old probably late 70's or early 80s, can't remember the publisher maybe Wiley.
Yeung, R.W., A First Course in Information Theory, Springer.

The research articles on Shannon theory and related fields in, say, IEEE Transactions on Information Theory, may fit the bill better, though not always.

An older text which may also be of interest is

Wolfowitz, J., Coding Theorems of Information Theory, Springer, 1960's.


Intersection models for weakly chordal graphs?

If I would like to know something about intersection models, the first reference I would check is the "Topics in Intersection Graph Theory" by McKee and McMorris.  Theorem 1.5 answers your (combinatorial) question.


Time complexity analysis for Reingold's UST-CONN algorithm

It seems that the time complexity of Reingold's algorithm is not treated in either the Reingold's paper or in Arora-Barak textbook. It would also appear that the analysis is rather tedious, as the time complexity depends on the exact expander graph used in the construction and on some constants that are chosen to "sufficiently large".

To get some rough idea on the time complexity, observe that Reingold's algorithm, given graph $G$, transforms it (implicitly) into an expander graph $G'$ and traverses every walk of length $l = O(\log n)$. The $O$-notation hides some quite large constants here. The graph $G'$ has constant degree of $d = 2^b$ for some sufficiently large $b$, meaning that there are $d^l = O(n^c)$ such walks for some rather large constant $c$. Skimming some lecture notes on the topic it would seem that $c \ge 10^9b$.


Conferences with proceedings published in the LIPIcs series:

STACS
FSTTCS
CCC (since 2015)
TQC (Theory of Quantum Computation, Communication and Cryptography)
ICALP
APPROX/RANDOM
SoCG
SWAT
ESA
MFCS


Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS?

This book will be helpful:

http://books.google.co.uk/books/about/Extremal_combinatorics.html?id=g6X2VWuB8qIC


Learning road map for functional programming from the viewpoint of category theory

There's no agreed upon "bible" for CT for computer science in the same way as for mathematicians (Mac Lane), probably because the field is younger and a bit broader. It really depends on whether you want to understand . Here are a few computer science concepts with category theory counterparts:

Simple types (which correspond to Cartesian Closed Categories)
dependent types (Locally Cartesian Closed Categories)
Abstract data types (categorical algebras, coalgebras, as described in e.g. Uustalu & Vene)
Programing with effects (Monads, monoidal categories, building on the foundational observations of Moggi)
Ressource aware programing (Closed Monoidal Categories (?))
CPS translations can be interpreted through the lens of the Yoneda lemma (see here for a brief explanation)

I'm missing a few, there are applications of category theory from everything to domain theory to database management.


Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) show that the nondeterministic time complexity of $\mathrm{PRESARITH}$ is at least $2^{2^{\Omega(n)}}$. In particular, $\mathrm{PRESARITH} \notin \mathsf{NEXP}$.
However, we have the containments
$$ \mathsf{
BPP \;\subseteq\; BQP \;\subseteq\; PP \;\subseteq\; PSPACE \;\subseteq\; EXP \;\subseteq\; NEXP
}
$$

Thus, it directly follows that $\mathrm{PRESARITH} \notin \mathsf{BQP}$, and in particular it is not in $\mathsf{BPP}$ either.


Approximation algorithms for Maximum Independent Set on special classes of graphs

There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: see this entry in the graph classes website.


About a year ago I co organized a workshop on complexity and cryptography: status of Impagliazzo's worlds, and the slides and videos on web site may be of interest.

The short answer is that not much has changed in the sense that most researchers still believe we live in "Cryptomania" and we still have more or less the same evidence for this, and not much progress on collapsing any of the worlds for one another.

Perhaps the most significant piece of new information is Shor's algorithm that shows that at least if you replace P with BQP, the most commonly used public key cryptosystems are insecure. But, because of Lattice based cryptosystems, the default assumption is that we live in cryptomania even in this case, though perhaps the consensus here is a bit weaker than the classical case. Even in the classical case, there seems to be much more evidence for the existence of one-way functions ("Minicrypt") than the existence of public key encryption ("Cryptomania"). Still, given the effort people have spent in trying to break various public key cryptosystem, there's significant evidence for the latter as well.