Separation of a preprocessed polyhedron and a plane

Theorem 3.1 requires that the hierarchical representation of $P$ is compact.  One of the requirements for compactness is that the degree of $r_i$ in $P_{i-1}$ is bounded by a constant.  See the bottom of page 3.

The definition and construction of the Dobkin-Kirkpatrick hierarchy is much more explicit in their earlier papers (references [9,10,11] in the paper you're reading).  I strongly recommend reading them first.


Shortest path on a hypergraph with no leftovers

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete.

Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3.

Proof. Clearly the problem is in NP.  It is NP-hard by the following reduction from 3D-matching.

Fix an instance of 3D matching -- a set of triples $X$ from universe $U=\{1,2,\ldots,3n\}$.  Given the instance, the reduction outputs the instance of Shortest $s$-$t$ Hyperpath in the hypergraph $G=(V,E)$ defined as follows.

First create the vertex set $V=\{b_0, a_1, b_1, a_2, b_2, a_3, b_3, \ldots, a_{3n}, b_{3n}\}$.  Define the hyperpath source and destination to be $s=b_0$ and $t=b_{3n}$.  Next, add $3n$ "path" hyperedges $$(b_0,a_1,b_1), (b_1,a_2,b_2), (b_2, a_3, b_3), \ldots, (b_{3n-1}, a_{3n}, b_{3n}).$$  Finally, for each triple $(i, j, k)$ in $X$, add hyperedge $(a_i, a_j, a_k)$.  This completes the reduction.

We'll show that there is an $s$-$t$ hyperpath of length at most $4n$ if and only if there is a 3D matching.

First suppose that there is a 3D matching $M$ (that is, an $n$-subset of $X$ such that each element in $\{1,\ldots,3n\}$ occurs in exactly one triple in $M$).  Then the $3n$ "path" hyperedges, together with the $n$ hyperedges $\{(a_i, a_j, a_k) : (i, j, k) \in M\}$ form the desired hyperpath.

Conversely, suppose there is such a hyperpath (from $b_0$ to $b_{3n}$).  By induction on the $b_i$ vertices, each of the $3n$ path hyperedges $(b_i, a_{i+1}, b_{i+1})$ must be in the hyperpath.  Then, since each vertex $a_1,\ldots,a_{3n}$ is in one such path hyperedge, each such vertex must also be in an odd number of other hyperedges in the hyperpath.  Those hyperedges must correspond to triples in $X$.  Each such hyperedge contains $3$ of the $a_i$ vertices, and the hyperpath has length $4n$ (or less), so there must be $n$ such hyperedges, and their corresponding triples must form a 3D matching. $~~\Box$

I suspect that even determining whether there exists any $s$-$t$ hyperpath is also NP-complete.

EDIT: I think the existence of an $s$-$t$ hyperpath can be determined in polynomial time by checking feasibility of this set of linear equations over $\mathbb{Z}_2$: introduce an indicator variable $x_e$ for each hyperedge $e$, then, for every vertex $v$ constrain $$\sum_{e \ni v} x_e = \begin{cases} 1 & \text{if } v\in\{s,t\} \\ 0 & \text{otherwise}.\end{cases}$$


Here is an explicit proof that a standard Chernoff bound is tight up to constant factors in the exponent for a particular range of the parameters. (In particular, whenever the variables are 0 or 1, and 1 with probability 1/2 or less, and $\epsilon\in(0,1/2)$, and the Chernoff upper bound is less than a constant.)

If you find a mistake, please let me know.

Lemma 1. (tightness of Chernoff bound)
Let $X$ be the average of $k$ independent, 0/1 random variables (r.v.).
For any $\epsilon\in(0,1/2]$ and $p\in(0,1/2]$,  assuming $\epsilon^2 p k \ge 3$,

(i)
If each r.v. is 1 with probability at most $p$, then
$$\displaystyle
\Pr[X\le (1-\epsilon)p]
~\ge~
\exp\big({-9\epsilon^2 pk}\big).$$

(ii)
If each r.v. is 1 with probability at least $p$, then
$$\displaystyle
\Pr[X\ge (1+\epsilon)p]
~\ge~
\exp\big({-9\epsilon^2 pk}\big).$$

Proof.
We use the following observation:

Claim 1. If $1\le \ell \le k-1$, then
$\displaystyle {k \choose \ell} ~\ge~ \frac{1}{e\sqrt{2\pi\ell}} \Big(\frac{k}{\ell}\Big)^{\ell} \Big(\frac{k}{k-\ell}\Big)^{k-\ell}$

Proof of Claim 1.
By Stirling's approximation,
$i!=\sqrt{2\pi i}(i/e)^ie^\lambda$ where $\lambda\in[1/(12i+1),1/12i].$

Thus, $k\choose \ell$, which is  $\frac{k!}{\ell! (k-\ell)!}$, is at least
$$
\frac{\sqrt{2\pi k}\,(\frac{k}{e})^k}
{  \sqrt{2\pi \ell}\,(\frac{\ell}{e})^\ell
~~\sqrt{2\pi (k-\ell)}\,(\frac{k-\ell}{e})^{k-\ell} }
\exp\Big(\frac{1}{12k+1} - \frac{1}{12\ell} - \frac{1}{12(k-\ell)}\Big)$$
$$
~\ge~
\frac{1}{\sqrt{2\pi\ell}} \Big(\frac{k}{\ell}\Big)^{\ell} \Big(\frac{k}{k-\ell}\Big)^{k-\ell}e^{-1}.
$$
QED

Proof of Lemma 1 Part (i).
Without loss of generality assume each 0/1 random variable in the sum $X$
is 1 with probability exactly $p$.
Note $\Pr[X\le (1-\epsilon)p]$ equals the sum $\sum_{i = 0}^{\lfloor(1-\epsilon)pk\rfloor} \Pr[X=i/k]$,
and $\Pr[X=i/k] = {k \choose i} p^i (1-p)^{k-i}$.

Fix $\ell = \lfloor(1-2\epsilon)pk\rfloor+1$.
The terms in the sum are increasing,
so the terms with index $i\ge\ell$
each have value at least $\Pr[X=\ell/k]$,
so their sum has total value at least
$(\epsilon pk - 2) \Pr[X=\ell/k]$.
To complete the proof, we show that
$$(\epsilon pk - 2) \Pr[X=\ell/k] ~\ge~ \exp({-9\epsilon^2 pk}).$$

The assumptions $\epsilon^2pk\ge 3$ and $\epsilon\le 1/2$
give $\epsilon pk \ge 6$,
so the left-hand side above is at least $\frac{2}{3}\epsilon pk\, {k \choose \ell} p^\ell(1-p)^{k-\ell}$.
Using Claim 1,
to bound $k\choose \ell$,
this is in turn at least $A\, B$
where
$A =  \frac{2}{3e}\epsilon p k/ \sqrt{2\pi \ell}$
and
$
B=
\big(\frac{k}{\ell}\big)^\ell
\big(\frac{k}{k-\ell}\big)^{k-\ell}
p^\ell (1-p)^{k-\ell}.
$

To finish we show $A\ge \exp(-\epsilon^2pk)$ and $B \ge \exp(-8\epsilon^2 pk)$.

Claim 2.  $A \ge \exp({-\epsilon^2 pk})$

Proof of Claim 2.
The assumptions $\epsilon^2 pk \ge 3$ and $\epsilon\le 1/2$
imply
(i) $pk\ge 12$.

By definition, $\ell \le pk + 1$.
By (i), $p k \ge 12$.
Thus, (ii) $\ell \,\le\, 1.1 pk$.

Substituting the right-hand side of (ii) for $\ell$ in $A$ gives
(iii) $A \ge \frac{2}{3e} \epsilon \sqrt{p k / 2.2\pi}$.

The assumption, $\epsilon^2 pk \ge 3$,
implies $\epsilon\sqrt{ pk} \ge \sqrt 3$,
which with (iii) gives (iv) $A \ge \frac{2}{3e}\sqrt{3/2.2\pi} \ge 0.1$.

From $\epsilon^2pk \ge 3$ it follows that (v) $\exp(-\epsilon^2pk) \le \exp(-3) \le 0.04$.

(iv) and (v) together give the claim. QED

Claim 3.   $B\ge \exp({-8\epsilon^2 pk})$.

Proof of Claim 3.
Fix $\delta$ such that $\ell=(1-\delta)pk$.
The choice of $\ell$ implies $\delta\le 2\epsilon$,
so
the claim will hold as long as $B \ge \exp(-2\delta^2pk)$.
Taking each side of this latter inequality to the power $-1/\ell$ and simplifying,
it is equivalent to
$$
\frac{\ell}{p k}  \Big(\frac{k-\ell}{(1-p) k}\Big)^{k/\ell-1}
~\le~
\exp\Big(\frac{2\delta^2 pk}{\ell}\Big).
$$
Substituting $\ell= (1-\delta)pk$ and simplifying, it is equivalent to
$$
(1-\delta)  \Big(1+\frac{\delta p}{1-p}\Big)^{\displaystyle \frac{1}{(1-\delta)p}-1}
~\le~
\exp\Big(\frac{2\delta^2}{1-\delta}\Big).
$$
Taking the logarithm of both sides and using $\ln(1+z)\le z$ twice,
it will hold as long as
$$
-\delta\, +\,\frac{\delta p}{1-p}\Big(\frac{1}{(1-\delta)p}-1\Big)
~\le~
\frac{2\delta^2}{1-\delta}.
$$
The left-hand side above simplifies to $\delta^2/\,(1-p)(1-\delta)$,
which is less than $2\delta^2/(1-\delta)$ because $p\le 1/2$.
QED

Claims 2 and 3
imply $A B \ge \exp({-\epsilon^2pk})\exp({- 8\epsilon^2pk})$.
This implies part (i) of the lemma.

Proof of Lemma 1 Part (ii).
Without loss of generality assume each random variable is $1$ with probability exactly $p$.

Note $\Pr[X\ge (1+\epsilon)p] = \sum_{i = \lceil(1-\epsilon)pk\rceil}^n \Pr[X=i/k]$.
Fix $\hat\ell = \lceil (1+2\epsilon)pk \rceil - 1$.

The last $\epsilon pk$ terms in the sum
total at least  $(\epsilon pk-2)\Pr[X=\hat\ell/k]$,
which is at least $\exp({-9\epsilon^2 pk})$.
(The proof of that is the same as for (i), except with $\ell$ replaced by $\hat\ell$
and $\delta$ replaced by $-\hat\delta$ such that $\hat\ell = (1+\hat\delta)pk$.)
QED


The coarsest bisimulation has a well known greatest fixed point characterisation. This greatest fixed point characterisation gives you a simple algorithm to calculate bisimulation quotients. There are quite a few immediate improvements you can make to this algorithm. A reference that contains most of these details is Joost Pieter Katoen's lecture on bisimulation minimization. If you need more detail, I suggest looking at the book

  Principles of Model Checking, Christel Baier and Joost-Pieter Katoen.


For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)


Should experts in TCS charge money to read proofs that P != NP?

I have some "real-world experience" in this nascent industry (and no, I'm not talking about my $200,000 offer to Deolalikar :-) )

In January, a software developer emailed me that he had an attempted proof of P≠NP, and that while he was almost sure there was an error, he couldn't find it.  He asked if I knew any grad students who'd be willing to find the error for him in exchange for a few hundred dollars.

To give you some context: I get a proof of either P≠NP or P=NP in my inbox roughly once per month.  Many of these emails go to a long list of complexity theorists (Cook, Karp, Fortnow, Sipser...); they often include religious or metaphysical ruminations as well as dark hints about academic conspiracies.  (In one case, there were graphic death threats against me, which led to my contacting the police.)  Virtually none of them acknowledge any possibility that the proof might be wrong, or that the author might have misunderstood the question.  And when, back in grad school, I tried to correspond with the authors, I found all of them to be fervent believers in Churchill's maxim "never, never, never, never give up."

So the software developer's request really impressed me!  This was the first time I'd ever seen a P≠NP proof accompanied by this level of self-awareness---both about the imposition being made on people's time and (more importantly) about the likelihood of error.  As it happened, my PhD student Michael Forbes sent the author a beautiful, detailed report explaining the problems with his approach; the author thanked Michael and (I think! :-) ) paid up as promised.

So yes: for amateurs who want someone to examine their P vs. NP proofs (or similar work), I think paying a grad student a few hundred bucks is a great way to go.  (Note that grad students are a much better choice than professors: not only do they have more energy and enthusiasm for such things, they also need the money more.)  I wish more amateurs availed themselves of this option.


Bin Packing with uniform size constraints

As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta>0$. Therefore, by a simple reduction from the 3-partition problem, for any constant $\delta>0$, the Bin Packing problem is NP-hard when $1/3-\delta < a_i$ for all $i$.


It is worth noting that the problem becomes NP-hard when the restriction is relaxed slightly.

With a fixed number of clauses that are also of bounded size, the average number of literals in a clause is as close to 2 as one wants, by considering an instance with enough variables.  As you point out, there is then a simple upper bound which is polynomial if the clause size is bounded.

In contrast, if the average number of literals per clause is at least $2 + \epsilon$ for some fixed (but arbitrarily small) $\epsilon > 0$, then the problem is NP-hard.

This can be shown by reducing 3SAT to this problem, by introducing new clauses with 2 literals that are trivially satisfiable.  Suppose there are $m$ clauses in the 3SAT instance; to reduce the average clause size to $(2+\epsilon)$, it is enough to add $m(1 - \epsilon)/\epsilon$ new clauses with two literals.  Since $\epsilon$ is fixed and positive, the new instance is of polynomial size.

This reduction also shows that even the version where the "large" clauses are restricted to 3 literals is NP-hard.

The remaining case is when the few large clauses are not of bounded size; each large clause seems to make the problem harder.  See the SODA 2010 paper by Pǎtraşcu and Williams for the case of two clauses: they argue that if this can be done in sub-quadratic time then we would have better algorithms for SAT.  There might be an extension of their argument to more clauses, which would provide evidence that your upper bound cannot be improved (modulo some form of the exponential time hypothesis).


Given a subset of the hypercube and a copy translated by s, find s

Here is an $O(nd)$ time randomized solution.

We will use the shifting (aka compression) technique from combinatorics, in a seemingly new algorithmic way, which I have never seen done before (see this post for the definition of the compression technique).

Let us define a partial order on $\{0,1\}^d$ called the set inclusion partial order, denoted $\preceq$, as so: Two strings $x,y$ satisfy $x\preceq y$ if $x_i = 1 \implies y_i = 1$ for all $i\in[d]$.

A subset $S\subseteq\{0,1\}^d$ is called downward closed, or downset for short, if $y\in S \land x\preceq y\implies x\in S$.

Intuitively, we will morph $A$ and $B$ into downsets a dimension at a time after which it will be clear which elements $x$ of $A$ are the "pairs" of which elements $x+s\in B$; this evidently will reveal $s$.

For reasons which will be clear let $A'=\{(x,x)\mid x\in A\}$ and $B' = \{(x,x)\mid x\in B\}$; we will modify only the left items in these pairs $(x,x)$ and the right items are fixed and only there so we can keep track of the original labels. When I say left $i$th coordinate of $(w,x)\in A'$ it will refer to the $i$th coordinate of the string on the left pair element, that is $w$.

The algorithm will proceed in $d$ rounds numbered $i=1,\ldots,d$. In round $i$, we do the following. Let $I= [d]\setminus \{i\}$ and partition $A'$ and $B'$ into equivalence classes according to coordinates $I$ of the left pair element. It will be clear soon each nonempty class has either 1 or 2 elements depending on the last unfixed left coordinate $i$ (there is always a bijection between the left and right parts of the pairs as we'll see during this inductive argument).

Here is an example: Let $i=1$. Consider the class
$C_u = \{(w,x)\in A' \mid w_I = u\}$. In each iteration, there will be a bijection between the left parts and right parts, so it remains to specify the first bit of $w$. Either both $(0u,\cdot), (1u,\cdot)$ are in $C_u$ or just one of them or none (we discard empty classes). This way among nonempty classes, the size is either 1 or 2.

The classes of size 2 are already good, don't touch them; no matter what $s$ is in the $i$th coordinate, they will work okay. The classes of size 1 either have $w_i=0$ or $w_i=1$. If the number of $w_i=0$ classes of $A'$ is different than the number of $w_i=1$ classes of $A'$, then we already know what $s_i$ must be (using the fact that $B$ is a translated version of $A$), so if the number of $w_i=0$ classes of $A'$ is equal to number of $w_i=1$ classes of $B'$, then flip the left $i$th coordinate of each element in $B'$, otherwise do nothing.

Now in both $A'$ and $B'$ set the left $i$th coordinate of the $w_i=1$ classes to 0. This is called a down-shift operation, as we gradually make the sets monotone.
This is the end of $i$th iteration.

Claim 1: At the end of the $d$th iteration, the left part of $A'$, i.e., $\{w\mid (w,x)\in  A'\}$ forms a downset. Likewise for $B'$.

Claim 2: These two downsets are equal to each other, i.e., $\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$.

Now that we have $\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$, we have a natural bijection $b$ between $A'$ and $B'$. One can see this bijection maps $(w,x) \in A'$ to $(w, x+s) \in B'$, so it directly reveals $s$.

How to implement each iteration in $O(n)$ time: We have a set of items of size $n$ that we need to partition with respect to a $d-1$ bit key (corresponding to $x_I$ for $I$ defined above) in each iteration. This we can do $O(n)$ randomized time by hashing, or $O(nd/\log n)$ deterministic time by bucketing (bucketing can be done in $O(n)$ time but $2^d$ space which could be excessive, instead we "radix it" by $\log n$).


Maximal subcoalgebras of an $F+1$-coalgebra corresponding to an $F$-coalgebra

Suppose that the functor $F$ preserves monos. In fact, I am going to assume something slightly stronger, namely that $S \subseteq T$ implies $F(S) \subseteq F(T)$ (otherwise we have to insert isomorphisms here and there). Your Kripke functors are of this kind, I think.

First a little diversion. Let $G$ be a functor from sets to sets which preserves the subset relation. Consider a coalgebra $s : S \to G(S)$ and a subset $A \subseteq S$. Call a subset $T \subseteq S$ "good" if the restriction $s_T : T \to G(S)$ of $s$ to $T$ gives a coalgebra $s_T : T \to G(T)$ and the image $s(T)$ is disjoint from $A$. Any union of good subsets is again a good subset. Indeed, suppose $T_i$'s are good and let $T = \bigcup_i T_i$. Then $s$ restricted to $T$ maps into $\bigcup_i G(T_i) \subseteq G(T)$, and obviously $T$ is disjoint from $A$. Therefore, there exists the largest good subset of $T$, namely the union of all the good ones.

Now apply the previous paragraph to the functor $G(X) = F(X) + 1$ and $A = \lbrace \mathrm{inr}()\rbrace$ to get the desired result.


Data structure to determine if sets are disjoint in o(n) time

The communication complexity of the set disjointness problem is $\Omega(n)$.  The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint.  Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ bits to determine whether their sets are disjoint, any algorithm that works on these two data structures will also necessarily involve doing at least that much computation.  It follows that testing disjointness of these two sets must take $\Omega(n)$ time, no matter what data structure you use, as long as each data structure is initialized separately.

Consequently, no such data structure exists.

Details: I'll elaborate on the proof more carefully, by sketching the reduction.

Suppose there was such a data structure, together with an algorithm $A$ that lets you test disjointness in $o(n)$ time.  Since it runs in $o(n)$ time, it must involve examining at most $o(n)$ bits of data, and in particular, at most $o(n)$ bits of the data structure for the first set and at most $o(n)$ bits of the data structure of the second set.

So, here is a communication protocol for set disjointness.  Initially, Alice initializes an instance of the data structure with her set, and Bob does the same with his set.  Start running algorithm $A$, with both of them executing the algorithm in lockstep.  Any time that algorithm $A$ examines a bit of the first data structure, Alice sends that bit to Bob.  Any time that the algorithm examines a bit of the second data structure sends that bit to Bob.  Now both Alice and Bob can execute the algorithm to completion.  At the end of the algorithm, both Alice and Bob know whether their sets are disjoint are not.  Also, the computation has taken $o(n)$ time, and they have sent only $o(n)$ bits of data (since it runs in $o(n)$ time, it can't send more than that), so we have a protocol for set disjointness with communication complexity $o(n)$.  This is impossible, so our original assumption that such an algorithm $A$ exists must also have been impossible as well.

If algorithm $A$ is randomized, then it's easy enough to send the random bits to both parties.  This doesn't affect the asymptotic complexity.

If the algorithm is in the RAM model, it can access $O(\log n)$ bits in a single operation, so we need to modify the above reduction slightly: if there is an algorithm $A$ for set disjointness that runs in $o(n/\log n)$ time, we obtain a communication protocol that sends $o(n)$ bits.  It follows that any algorithm $A$ for set disjointness must take at least $\Omega(n/\log n)$ time in the RAM model.  Since the RAM model is a standard assumption, perhaps it would be more reasonable to summarize this result as implying that disjointness queries must take at least $\Omega(n / \log n)$ time, in the worst case, no matter what data structure you use, as long as each instance of the data structure is initialized separately.


Empirical Rademacher averages versus Hoeffdings bound

The answer depends on whether you want a bound for a single, fixed $Q\subseteq M$ or uniformly over all such $Q$. For a single, fixed $Q$, the Chernoff-Hoeffding bound is essentially the best you can do (see also empirical Bernstein's inequality for "fast rates").

If you want the bound to hold simultaneously for all $Q\subseteq M$, you need apply the union bound, which amounts to multiplying the deviation probability by $2^{|M|}$ (or the sample complexity by $|M|\log 2$).

You have nothing to gain here by using Rademacher complexities. The latter are useful at capturing the combinatorial properties of VC classes, and are sharper than naive union bounds (though Massart's lemma of course has a union bound inside). In your case, the VC structure is very simple -- it's all subsets -- and so you might as well just use the simple union bound.


This example is from social choice theory, and elections in particular. We know that Arrow's theorem (and the Gibbard-Satterthwaite theorem in general) rule out the possibility of elections that are fair, non-manipulatable and without other bizarre consequences. But a seminal paper by Bartholdi, Tovey and Trick showed that finding the desired 'hack' to break a voting scheme was NP-hard, and there's been a large body of work by many researchers on the complexity of problems in the realm of election design. There's a nice survey by Faliszewski, Hemaspaandra, and Hemaspaandra on this topic.


Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do?

I posed this question as a challenge to my students and I'm proud to report that they did not disappoint! Here's an argument based on ones developed by my students Kevin Tan and Max Arseneault, providing an intuition as to how the marking rule, applied to binomial trees, gives rise to the Fibonacci sequence.

Our goal will be to find a lower bound on the number of nodes that can be in a tree in a Fibonacci heap that has order $k$. We'll say that a maximally damaged tree of order $k$ is a binomial tree of order $k$ that has lost as many nodes as possible while obeying the Fibonacci heap marking rules, subject to the restriction that the root node still has $k$ children (and, thus, the tree has order $k$). For example, here's the first few maximally damaged trees:

Notice that cutting any of the remaining nodes from their parents would trigger a cascading cut that removes a child from the root.

Our goal will be to show that if $MD[n]$ denotes the number of nodes in a maximally-damaged tree of order $k$, then $MD[n]$ satisfies the recurrence relation

$$MD[k+2] = MD[k] + MD[k+1],$$

at which point it's no longer surprising that we see the Fibonacci sequence popping up.

To do so, consider a binomial tree of order $k+2$, like the one shown here:

We'd like to remove as many nodes from this tree as we can without cutting any direct children of the root. To do so, we'll imagine partitioning the nodes in this tree into two binomial trees of order $k+1$ by separating out the order-$k+1$ child from the remaining children, as shown here:

We haven't actually cut this link - that would remove a child of the root - and instead are just doing this for accounting purposes.

Now, think about the binomial tree of order $k+1$ containing the tree root. Focusing purely on this tree, we'd like to remove as many nodes as possible while still leaving the root with $k+1$ children. Stated differently, we have a binomial tree of order $k+1$ and want to remove as many nodes as possible without removing any children of the root, which is exactly what the maximally damaged trees represent. So let's restructure the root's binomial tree to look like a maximally-damaged tree of order $k+1$, as shown here:

Next, let's focus on the child subtree of order $k+1$. We can cut away as many nodes from this tree as we'd like, provided that we don't trigger a cascading cut that would cut this subtree from the overall order-$k+2$ tree root. Since this tree is allowed to lose a child without being cut from its parent, it makes sense to remove its largest child subtree, which would be its child of order $k$, since that would immediately eliminate the most nodes. Doing that gives us the following setup:

Notice that this tree is now a binomial tree of order k and that its root has been marked.

From here, we'd like to cut away as many nodes as we possibly can. However, since the root of this subtree is now marked, we cannot cut any direct children away from the root of this subtree. If we did, that would trigger a cascading cut that would cut the whole subtree away from the global tree root, which isn't allowed. And so we're left with a smaller copy of the same problem from earlier: we have a binomial tree of order $k$ and we want to cut away as many nodes as possible without cutting any direct children of the root. That means we want to form a maximally-damaged tree of order $k$, as shown here:

.

Putting everything together, we see that the shape of the overall tree can be partitioned into a maximally-damaged tree of order $k+1$ and a maximally-damaged tree of order $k$:

Overall, this shows that $MD[k+2] = MD[k] + MD[k+1]$, which is where the Fibonacci recurrence comes in. All that's left to do is to check that the base cases satisfy $MD[0] = F_2$ and $MD[1] = F_3$ (they do) and we've got the bound of $MD[k] \ge F_{k+2}$. Tada!


What limits the performance of evolutionary computing techniques?

To bring this to something resembling theoretical computer science: In his PNAS 2008 paper A Mixability Theory of Sex in Evolution, Christos Papadimitriou has theorized that one limit on the power of genetic algorithms is that they do not optimize what you think they should be optimizing (the objective function you're using in the selection part of the algorithm) but rather they optimize "mixability" (a measure of robustness, the ability of genomes to be combined and still have a high objective function value).

So, if the space of solutions that you're trying to optimize has moderately-high plateaus of pretty good but not great solutions that combine well with each other, and a few steep spikes of high quality solutions that do not combine well, you'll be stuck on the plateaus.

Papadimitriou then uses this observation to make inferences about sexual reproduction in nature, but that's getting off-topic again.


Proof Complexity and Circuit Lower bound for coNP

For the first question, it depends on what you mean by "harder". If you mean one logically implies the other then yes.

A lowerbound in a deterministic model of computation (containing negation) works also for the complement of the language because it is deciding the language. Therefore a circuit lowerbound for an $\mathsf{NP}$ problem is also a circuit lowerbound for its complement which is in $\mathsf{coNP}$.

(If you mean finding a proof of one is considerable harder than finding a proof of the other then it is a matter of opinion and arguable.)

For the second question,
the concept of uniform proof complexity corresponds to theories in bounded arithmetic. You can translate proofs in such theories to propositional proofs using the propositional translation. See Stephen A. Cook and Phuong Nguyen, "Logical Foundations of Proof Complexity", 2010. These theories correspond to the uniform version of propositional proof systems in a similar way that uniform complexity classes like $\mathsf{P}$ are considered to be the uniform version of non-uniform complexity classes like $\mathsf{P/poly}$.
There are other nice relations between the uniform and non-uniform proof systems that add justification to this correspondence.
(Some ideas goes back to Steve'e original paper "Feasibly Constructive Proofs and the Propositional Calculus" from 1975 paper).

One can define other types of uniform proofs between these two, but it is not clear what you are asking (seems more like a post to solicit opinion about an idea than a question). You can find related stuff in Jan Krajicek's and other peoples' lecture notes on proof complexity.


What is a good special-case sorting algorithm?

It's easy to prove an Ω(n2 log n) lower bound on this problem (in the comparison sorting model): if the element at position (i,j) is always within distance 1/2 of i+j, then the grid diagonals are independent of each other, and the sorted order within each grid diagonal is arbitrary. So under this constraint the total number of orderings possible is the product (over all the diagonals of the grid) of the factorials of the lengths of the diagonals, which is exponential in n2 log n.

Which is to say that standard comparison sorting algorithms are asymptotically optimal for grids ordered as you describe.


Composition theorem for randomized communication complexity

My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, this generalizes to classical models as well.
See Theorem 69 of Troy Lee and Adi Shraibman's survey [LS09], available, e.g., at this address.

[BCW98] Buhrman, Harry; Cleve, Richard; Wigderson, Avi. Quantum vs. classical communication and computation. STOC '98 (Dallas, TX), 63--68, ACM, New York, 1999. Available at https://arxiv.org/abs/quant-ph/9802040
[LS09] Troy Lee and Adi Shraibman, Lower Bounds in Communication Complexity, Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263-399. 2009. http://dx.doi.org/10.1561/0400000040
[Nisan94] Nisan, N. The communication complexity of threshold gates. Combinatorics, Paul Erdős is eighty, Vol. 1, 301--315, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.


Evaluating the multilinearization of an arithmetic circuit?

In the case that the field $F$ is of size at least $2n$, I think this problem is hard. More specifically, I think that if the above can be efficiently solved for $F$ this large, then CNF-SAT has efficient randomized algorithms. Say we are given a CNF formula $\varphi$. One can easily come up with an arithmetic circuit $C$ that computes an ``arithmetization'' $p$ of $\varphi$, where the polynomial $p$ agrees with the formula $\varphi$ on $0$-$1$ inputs. Consider the multilinearization $q$ of $p$. Note that $q$ agrees with $p$ and hence $\varphi$ on $\{0,1\}^n$.

I claim that $q$ is non-zero iff $\varphi$ is satisfiable. Clearly, if $q=0$, then $\varphi$ cannot be satisfied. For the converse, one can show that any non-zero multilinear polynomial cannot vanish on all of $\{0,1\}^n$. This implies that a non-zero $q$ (and hence the corresponding $\varphi$) does not vanish at some input in $\{0,1\}^n$.

Therefore, checking for satisfiability of $\varphi$ is equivalent to checking if $q$ is non-zero. Say, now, that we could evaluate $q$ over a large field $F$. Then, using the Schwartz-Zippel Lemma, we could identity-test $q$ using an efficient randomized algorithm and check if it is the zero polynomial (the size of $F$ is used to upper bound the error in the Schwartz-Zippel Lemma).


Graph isomorphism with equivalence relation on the vertex set

The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). Call the problem you describe EQ-GI.

GI is just the special case of EQ-GI where each graph has just one equivalence class consisting of all vertices.

In the other direction, to reduce EQ-GI to GI, let $(G, \sim_G)$ be a graph with equivalence relation with $n$ vertices, $m$ edges, and $c$ equivalence classes. Construct a graph $G'$ whose vertex set consists of the vertices of $G$, together with new vertices $v_1, \dotsc, v_c$, one for each equivalence class in $=_G$, as well as $n+c+1$ new vertices $w_0, \dotsc, w_{n+c}$. Connect the $w_i$'s in a path $w_0 - w_1 - w_2 - \dotsb - w_{n+c}$, connect each $v_i$ to $w_0$, and for every vertex in $G$, connect it to the corresponding equivalence class vertex $v_i$. Then $G'$ has at most $n + 2c + n +1 \leq O(n)$ vertices and can be constructed in essentially the same time bound. (It also has at most $m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$ edges - which is $O(m)$ for connected graphs - but that's somewhat less relevant since most GI algorithms have running times that essentially only depend on $n$.)

Update: Since there was some confusion in the comments, I'm adding here a sketch of the correctness of the above argument. Given $(G_1, \sim_1)$ and $(G_2, \sim_2)$, let $G_1'$ and $G_2'$ be the graphs constructed as above; let $v_{i,1}$ denote the vertex $v_i$ from above in $G_1'$, and $v_{i,2}$ the one in $G_2'$, and similarly for $w_{i,1}$ and $w_{i,2}$. If there is an isomorphism $G_1' \cong G_2'$, it must send $w_{i,1}$ to $w_{i,2}$ for all $i$, since in each graph $w_{n+c}$ is the unique vertex that is the endpoint of any path of length at least $n+c+1$. In particular, $w_{0,1}$ maps to $w_{0,2}$. Since the neighbors of $w_0$ that aren't $w_1$ are exactly the $v_i$, the isomorphism must map the set $\{v_{1,1},\dotsc,v_{c,1}\}$ to the set $\{v_{1,2},\dotsc,v_{c,2}\}$ (and in particular both $\sim_1$ and $\sim_2$ must have the same number, $c$, of equivalence classes). Note that the isomorphism need not send $v_{i,1}$ to $v_{i,2}$ for all $i$, but is allowed to permute the indices of the $v$'s so long as the corresponding equivalence classes can be mapped to one another. Conversely, based on this description of how isomorphisms between $G_1'$ and $G_2'$ can look, it is easy to see that if $(G_1, \sim_1) \cong (G_2, \sim_2)$ then this gives an isomorphism $G_1' \cong G_2'$.


What would be the next step after quantum computing?

This is mainly a philosophical question and depends on your model of reality. Under some assumptions, time trevling ability will allow aditional speedup.... You can read about the CTC model, mainly introduced by Scott Aaronson, that deals with this subject.
https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.scottaaronson.com/papers/ctchalt.pdf&ved=2ahUKEwih8a_Qz-LnAhUCGewKHUFlBZMQFjABegQIBhAL&usg=AOvVaw3TMaefh-UTmCsAHKRT6EhL


Are all problems in the same time hierarchy related to each other?

If problem A is complete for the class, the class is higher than P, and problem B cannot be solved in polynomial time, then yes, there is some polynomial algorithm that makes use of the oracle and solves the problem.
By definition, if a problem A is complete for some class C, then every problem of this class is reducible in polynomial time to this problem. As a result, a polynomial algorithm for a problem B given an oracle P of the (complete for the class) problem A (we assume that the oracle spits out the answer to an instance of A in constant time) is the following:
Input: instance of problem B

Reduce the instance of B to an instance of A (polytime)
Answer the obtained instance of A using P (constant time)

However, it is not always easy to find the reduction from one problem to another in the same class.


Common solutions to 3SAT and 2SAT models comprised of the same variables

No, in general you cannot.  If $S_2(L) = (x_1 \lor \neg x_1)$, say, then the implication graph for $S_2(L)$ gives you no information on the solutions to $S_3(L)$ or $B$.
If you want to know how to solve it in practice, throw $B$ into a SAT solver.  No need to distinguish between the two types of clauses: SAT solvers already do everything there is to do.


Does approximation degree of AND depend on error?

Firstly it is well-known that the approximate degree of $\mathrm{AND}$ is $O(\sqrt{n})$:

Theorem 1. For all $n$ and $\varepsilon>0$, there exists a multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree $O(\sqrt{n}\log(1/\varepsilon))$ such that $|p(x)-\mathrm{AND}(x)|\leq \varepsilon$ for all $x \in \{\pm 1\}^n$.

Proof. We use the Chebyshev polynomials:

Fact. For all $\ell$ and $d$ there exists $p_{\ell,d} : [-1,1] \to \mathbb{R}$ of degree at most $d$ such that $|p_{\ell,d}(z)-z^\ell| \leq 2e^{-d^2/2\ell}$ for all $z \in [-1,1]$.
See Sachdeva-Vishnoi Theorem 3.3 for a proof.

We also have $$\left|\mathrm{AND}(x) - \left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)^\ell\right| \leq \left(1-\frac{1}{n}\right)^\ell \leq e^{-\ell/n}$$ for all $x \in \{\pm 1\}^n$. Thus $$\left|\mathrm{AND}(x) - p_{\ell,d}\left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)\right| \leq 2e^{-d^2/2\ell} + e^{-\ell/n}$$ for all $x \in \{\pm 1\}^n$.

Setting $\ell = n \log(3/\varepsilon)$, $d=\sqrt{2\ell \log(3/\varepsilon)}$, and $p(x) = p_{\ell,d}\left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)$ proves the theorem. Q.E.D.

Now we show that the approximate degree of $\mathrm{AND}$ becomes the exact degree of $\mathrm{AND}$ (which is maximal) for some value of $\varepsilon>0$:

Theorem 2. For all $n$, there exists $\tilde\varepsilon>0$ such that no multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree strictly less than $n$ satisfies $|p(x) - \mathrm{AND}(x)|\leq \tilde\varepsilon$ for all $x \in \{\pm 1\}^n$.

Proof.
Let $\mathcal{P} \subset \mathbb{R}^{\{\pm 1\}^n}$ be the space of functions from $\{\pm 1\}^n$ to $\mathbb{R}$ that have degree strictly less than $n$.

Claim. $\mathcal{P}$ is closed with respect to the $\ell_\infty$ norm.
This follows from the fact that $\mathcal{P}$ is a linear subspace of $\mathbb{R}^{\{\pm 1\}^n}$. It is spanned by the multilinear monomials of degree strictly less than $n$.

Claim. $\mathrm{AND} \notin \mathcal{P}$.
The Fourier transform uniquely expresses $\mathrm{AND}$ in the multilinear monomial basis. We see that the degree is $n$:
$$\mathrm{AND}(x) = \prod_{i=1}^n \frac{1-x_i}{2} = \sum_{s \subset [n]} \frac{(-1)^{|s|}}{2^n} \prod_{i \in s} x_i.$$

Claim. $\exists \tilde\varepsilon>0~\forall p \in \mathcal{P}~\|\mathrm{AND}-p\|_\infty>\tilde\varepsilon$.
Since $\mathcal{P}$ is closed, its complement is open. $\mathrm{AND}$ is in the complement of $\mathcal{P}$ which means there exists a closed ball of positive radius $\tilde\varepsilon>0$ centered at $\mathrm{AND}$ that does not intersect $\mathcal{P}$.

The final claim is exactly the theorem.
Q.E.D.

Thus we have shown that there exists $\tilde\varepsilon>0$ such that $\mathrm{deg}_{\tilde\varepsilon}(\mathrm{AND})>\mathrm{deg}_{1/3}(\mathrm{AND})$.


Generalization of Dilworth's theorem for labeled DAGs

With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled elements, large antichains of $b$-labeled elements, but no large antichains containing both many $a$-labeled and $b$-labeled elements, then there is a decomposition of $G$ as a partition $L_1, \ldots, L_n$, where:

the partition $L_1, ..., L_n$ is what we call a "layering", i.e.:

each $L_i$ is a convex set, i.e., if $x, y \in L_i$ and $x \leq z \leq y$ then $z \in L_i$
for all $i < j$, there is no $x \in L_i$ and $y \in L_j$ such that $y \leq x$

for any antichain $A$ of $G$, there is some $i$ such that $A$ is "almost contained" in $L_i$, i.e., $|A \setminus L_i|$ is less than a constant
for each $L_i$, one of the following is true:

$L_i$ contains a large antichain of $a$-labeled elements and contains no large antichain of $b$-labeled elements
$L_i$ contains a large antichain of $b$-labeled elements but contains no large antichain of $a$-labeled elements

Further, such a partition can be computed in PTIME.

I have posted our current proof online. It's very rough and essentially not proofread because we have no use for the result for now, but I still thought it was tidier to add an answer to this CStheory question with our current progress. Don't hesitate to get in touch with me if you're interested in the result but can't make sense of the proof.


Why have we not been able to develop a unified complexity theory of distributed computing?

My take is that the abstractly-motivated Turing machine model of computation was a good approximation of technology until very recently, whereas models of distributed computing, from the get-go, have been motivated by the real world, which is always messier than abstractions.

From, say, 1940-1995, the size of problem instances, the relative "unimportance" of parallelism and concurrency, and the macro-scale of computing devices, all "conspired" to keep Turing machines an excellent approximation of real-world computers.  However, once you start dealing with massive datasets, ubiquitous need for concurrency, biology through the algorithmic lens, etc., it is much less clear if there is an "intuitive" model of computation.  Perhaps problems hard in one model are not hard -- strictly less computationally complex -- in another.  So I believe that mainstream computational complexity is finally catching up (!) with distributed computing, by starting to consider multiple models of computation and data structures, motivated by real-world considerations.


What are the simplest turing-complete systems?

The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Game of Life. Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

Another simple example is a Bitwise Cyclic Tag System:

The "program" is a sequence of instructions $0, 01, 11$ (i.e. $C = p_{n} p_{n-1} ... p_2 p_1; \; p_i \in (0|01|11)^+$)
; the "data" is a binary string (i.e. $w \in \{0,1\}^+$).

If $p_1$ is the "current instruction" and the data is $w = a_1 a_2 ... a_m$; you can put the program and the data side by side ($p_{n}...p_2 p_1 \leftrightarrow a_1 a_2 ...a_m$), and the "execution" of $p_1$ is:

if $a_1 = 1$ and $p_1 = x1$ then append $x$ to $w$
delete $a_1$ from $w$
rotate $C$ ($p_1$ is moved to the left of $C$ and $p_2$ becomes the current instruction)

The universality can be proved by simulating the more general cyclic-tag system.


Philosophy behind monotonicity requirement for inductive types

When you write an inductive, you are defining a type by an equation. For example, if we write $F_1(X)=X^X=X\to X$, bad should satisfy $F_1($bad$)=$bad.

In general such equations can have several solutions, or none. For example, for $F_2(X)=X^X\times X$, you have (at least) two distinct solutions: $0$ (empty set) and $1$ (singleton). So you want some way to pick a specific solution.

The fact that you declared your type as inductive means that you pick the smallest solution (and coinductive would've meant the largest). So you want to be sure that this smallest solution exists. One way to ensure this is to ask for $F$ to be monotonous because then, the Knaster–Tarski theorem implies that it has a smallest fixpoint.

Aside from inconsistencies, I don't see a reason to ban other classes of equations, as long as you have a way to pick a specific solution. But unless you are sure that there is always a smallest solution for those equations, and that you will pick it, you probably shouldn't call it inductive.


Obfuscation transformation and code maintainability

From comments ...

Do you mean relation between code obfuscation and code maintenance?

Obviously good obfuscation means poor maintainability, so an alternate question is: how can a small part of the source code be reobfuscated without having to obfuscate the whole source code again? This leads to: "how can I build an efficient incremental obfuscator?" ... unfortunately obfuscators heavily depend on the target programming languages, so I don't think there are many academic papers on that subject.

However, if you need a more theoretical approach then you can start with a survey on the subject: for example: Code Obfuscation Literature Survey (with good references at the end). Or look for papers which cite the negative result of Barak et al.: On the (Im)possibility of Obfuscating Programs .

Otherwise - if you are more "code-oriented" - you can search for information (and source code) on how real incremental obfuscators work (.NET obfuscator, ProGuard obfuscator, ...). Some years ago I used ProGuard to obfuscate a Java application (in Netbeans environment); it is an open source project, so you can download the full source code (http://proguard.sourceforge.net/). Incremental obfuscation is obtained keeping a mapping file that allows to mantain classes/variables/methods/etc.etc. names consistent across subsequent builds.


A natural problem in $\textrm{S}_2^\textrm{P}$?

How about a problem complete for promise-$\mathsf{S_2^p}$?

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Chris Umans. On the complexity of succinct zero-sum games. Computational Complexity 17:353-376, 2008.

From the abstract:

  We prove that approximating the value of a succinct zero-sum game to within an additive factor is complete for the class promise-$\mathsf{S_2^p}$, the "promise" version of $\mathsf{S_2^p}$. To the best of our knowledge, it is the first natural problem shown complete for this class.

(Historical note: it is not too surprising that not many natural problems are known to be in $\mathsf{S_2^p}$ but not known to be in its subclasses $\mathsf{MA}$ or $\mathsf{P^{NP}}$. If you check the original papers of Russell--Sundaram and Canetti (independently), it seems as though the definition of $\mathsf{S_2^p}$ was made more or less specifically to capture their improved arguments placing $\mathsf{BPP}$ in $\mathsf{PH}$, rather than to capture some set of of natural problems.)


Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$?

If $\mathsf{L} = \mathsf{P}$ then $\mathsf{DSPACE}(O(f(n))) = \mathsf{DTIME}(2^{O(f(n)})$ for all time-constructible functions $f(n) \geq \log n$ using standard padding arguments. I am not sure what happens if $f(n)$ is not time-constructible.

If $\mathsf{L} \neq \mathsf{P}$ then $f(n) = \log n$ will be an example. Therefore there is a time-constructable function $f(n)$ where the containment is proper iff the containment is proper for $f(n) = \log n$ .


Monotone bijections between lists of intervals

Here is an attempt to prove that the problem without the reverse condition is NP-hard.

The basic idea is that disjoint intervals in $S$ like this one:

 [S]  +-a-+ +-b-+
      +---c-----+  c<a, c<b (here < is interval inclusion)

can have a valid mapping to a "pyramid" in $T$:

 [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+
      +-z-----+  z<x, z<y OK

The reduction is from Unary 3-Partition (which is NPC).
Given $3m$ integers $A = \{a_1,a_2,...,a_{3m}\}$ and an integer $B$, does exists a partition of A in $m$ sets $A_1,...,A_m$ such that every $A_i$ have exactly 3 elements and their sum is $B$?

Suppose that $max = \sum a_i + 3m$

We construct $S$ adding $3m$ base intervals $BI_i$ of length $3*max$ (red lines in the figure),
on top of each base interval  we add a marker pyramid of $max$ intervals of increasing length (green lines in the figure).
To base interval $BI_i$ we also add $a_i$ disjoint unit intervals of length 1 (black lines in the figure). Finally we add a long interval $L$ to cover all $BI_i$ (blue line in  the figure).

Then we construct $T$ starting from a copy of $L$, then we add $m$ sum groups $G_j$, each one  made with a copy of three stacked base intervals stretched in such a way that their marker pyramids don't intersect (see red+green lines at the bottom of the figure).
Then we add on top of the three base intervals of $G_j$ a sum pyramid of $B$ intervals of increasing length (disjoint from the marker pyramids).

Suppose that there exists a bijection between S and T that preserves the interval inclusion (in one direction from S to T).

Then each marker pyramids of S must correspond to a marker pyramid in T (the only way to have an inclusion chain of $max$ intervals), so exactly three base intervals ($BI_{j_1},BI_{j_2},BI_{j_3}$) of $S$ must be mapped to each group $G_j$. Furthermore, the unit intervals of $BI_{j_k}$ must be mapped to the sum pyramid of $G_j$ and cannot be "exchanged" between different groups.

In a similar way it can be proved that if there exists a bijection then the original unary 3-partition problem has a solution.

Reduction example from the unary 3-partition problem $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Note: as observed in the comments the blue intervals L in S and T are not essential for the reduction.

If the reverse condition is also required, then you can build two DAGs using the relation $I_i \subseteq I_j$ to build arcs $(I_j \rightarrow I_i)$. A bijection that preserves interval inclusion in both directions exists iif the two DAGs are isomorphic. So the problem cannot be harder than the DAG isomorphism problem, which is GI-complete (and if you prove that it is NP-complete then you prove that GI is NP-complete, too).


Generating uniform integers in a range from a random generator with another range

I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy.

Description of the scheme. Thinking as an algorithm, the scheme is the following. It has two parameters, an integer $n$, and a bound $m$, $0 \leq n < m$, with the invariant that $n$ was drawn uniformly at random in $[0, m[$. (I'll rephrase everything to ranges of the form [0, n[ rather than $\{1, \ldots, n\}$ because it's simpler.)

At each step we do the following:

if $m < q$, then we need more entropy: let $n'$ be the result of calling the oracle that samples in $[0, p[$ uniformly, and recurse with $n := n p + n'$ (i.e., a combination of the current $n$ and the new draw) and $m := m p$ (a larger interval). It is clear that if $n$ is uniform in $[0, m[$ and $n'$ is uniform in $[0, p[$ then the combination $n p + n'$ is uniform in $[0, mp[$
if $m \geq q$, then let $M$ be the largest multiple of $q$ which is smaller than $m$. If $n$ is in $[0, M[$, then we return $n \text{ mod } q$ as the result: this is uniform. Otherwise, the remainder $n - M$ is uniform in the range $[0, m - M[$, so we recurse with $n := n - M$ and $q := q - M$.

In pseudocode, reformulating the second point to substract $q$ multiple times instead of finding $M$, we get the following very simple algorithm:

int algo(int n, int m) {
  // invariant: n is uniform in the range [0, m[
  if (m < q)
    return algo(p*n + randint(p), m * p);
  if (n < q)
    return n;
  return algo(n-q, m-q);
}

algo(0, 1);

Optimality. This algorithm is, I think, optimal. To see why, let me reformulate it in terms of decision trees. What the algorithm does is, at every level, if we have at least $q$ leaves then turn into leaves the largest multiple of $q$ that you can, and grow the other nodes; otherwise just grow all nodes. (This makes it clear that the scheme is uniform, because the labels in $[0, q[$ on the tree are used in exactly the same way.)

Let us consider the (generally infinite) tree $T$ obtained by such a scheme, and consider a hypothetical tree $T'$ which denotes a uniform strategy with a better expected score.

It is clear that the performance of the tree depends only on the number of internal nodes at every depth. In other words, if I can show that, at every level, the number of internal nodes of $T'$ is at least that of $T$, then $T'$ cannot be better than $T$.

But consider any depth $k$. It is clear that, in $T$, the number of internal nodes is precisely $p^k - M$ for $M$ the largest multiple of $q$ which is below $p^k$: let's write $M = mq$. Now if $T'$ does better than this and has less than this number of internal nodes, let us divide the $p^k$ possible outcomes at depth $k$ of $T'$ between the decided ones and the yet undecided ones: more than $mq$ must be decided (to be better than $T$) and they must be split between $q$ outcomes, so the most probable outcome $v$ at that level must have probability at least $(m+1)/p^k$. Now by maximality of $m$ we have $(m+1)q > p^k$, so that $(m+1)/p^k > 1/q$. But by uniformity the probability of $v$ overall (so, in particular, at depth $k$) should not be more than $1/q$. So $T'$ cannot be uniform: outcome $v$ has probability $> 1/q$.

Hence, $T'$ never does better than $T$.

Expected performance. To compute the expected performance of this optimal strategy, one can just write out an equation system based on which recursive calls are performed by the pseudocode above (with the indicated probability distribution). The value of the parameters is bounded, so presumably, for given values of $p$ and $q$, this should be solvable as a geometric series or something like that. (This can be interpreted as an equation system describing the expected number of draws required for a decision forest with $n$ root nodes, $n$ being the number of nodes at the current level.)

Extending to multiple draws. One can generalize this scheme to draw multiple values, in the following way: when you have made a draw in $[0, q[$, instead of starting at a single-root decision tree for the next draw, start at a forest with $m$ nodes, the number of the outcomes with the same label at the level at which you decided, to use this remaining entropy. My conjecture would be that the resulting scheme would have the same performance as the $p$- and $q$-ary solution sketched in my question (so be optimal for multiple draws while concluding faster for a single draw). I have no proof of this fact, though.


Essentially, you are asking for a graph "separator" of a certain kind, and while this doesn't answer your question directly, your question is likely related to the notion of the rankwidth of a graph. You can find more information in this paper, this paper or especially this paper

Note that the notion of rankwidth uses "rank over the finite field $\mathbb{F}_2$", which may or may not be the field you were asking about.


Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

The answer is no - for a fixed $Q$ let $t$ be the number of vertices in the smallest graph $H$ not in $Q$. Now, consider $n$ much bigger than $t$. For a random graph on $n$ vertices, the probability that the $t$ first vertices induce $H$ depends only on $t$. Partitioning the vertex set into $n/t$ disjoint sets of size $t$ and considering the probability that none of the sets are equal to $H$ shows that the probability of being in $Q$ tends to $0$ as $n$ increases.


There is a naive algorithm for programs with bounded-size inputs: enumerate all programs in order of increasing length (or execution time, which is a bounded function of the length). If you can prove that the program is equivalent to the original, stop; otherwise keep searching.

This algorithm is sound. In order for it to be complete, you need to be able to prove all rejected programs are not equivalent to the original. This is possible in finitary machine models, as long as you have a bound for the input size.

Note that when the program execution time depends on the input, there may not be an optimal solution. If you look for e.g. a worst-case bound, you'll very quickly run into undecidable equivalences when you quantify over all possible unbounded inputs, and into untractable problems if the inputs are bounded.

A decade ago, “Denali: A Goal-Directed Superoptimizer” by Rajeev Joshi , Greg Nelson and Keith Randall was able to find optimal programs of about 5 machine instructions. I haven't looked at more recent results.


Array implementation of dictionary data structure

I believe you are looking for the paper Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees by Franceschini and Grossi.


NP-completeness: sum of "some" paths in a spanning tree

You are asking for the minimum weight fundamental cycle basis (in an unweighted graph). I think the standard reference for its NP-hardness is:

Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (1982), "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software, 8 (1): 26–42, doi:10.1145/355984.355988.


Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them.

Your regularity theorem holds with length-preserving functions.
If you want to allow length-increasing functions (that you need for PCP), you need a more powerful transducer model, for which undecidability quickly kicks in.


Automatic proofs or model checking in an extremely simplified functional language

The ACL2 system includes all of the features of your language, and supports impressive automated theorem proving about program in that language.

In ACL2, you would write the theorem you describe as:

(defthm f-g-equal (equal (f x) (g x)))

having previously defined f and g.


Computability and Recursion, by Soare.
http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

This paper is the first of the history of computation papers available here:
http://www.people.cs.uchicago.edu/~soare/History/


"Complex" problems are normally defined as problems which cannot be solved by (probabilistic) polynomial-time Turing machines.

When there are extra information available for solving the problem, the model changes to machines which take advice. That is, instead of $\rm{BPP}$ machines, we consider $\rm{P/poly}$  circuits; i.e. polynomial-size circuits (equivalently, polynomial-time Turing machines which take polynomial advice).

In some cases, we may consider even stronger solvers: Instead of poly-sized circuits, we may use circuits whose size is sub-exponential. (e.g. circuits whose size is $n^{\log n}$). One might note that, an exponential-size family of circuits can decide any language (even undecidable ones) by merely incorporating the look-up table in its code. (In particular, the size of the look-up table is $O(n2^n)$.)

Let's consider the Decisional Diffie-Hellman (DDH) assumption.
I don't go into details. Just assume that $p$ is a large prime, all computations are over $\mathbb{Z}^*_p$, and $g$ is its generator.

  DDH: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for $\rm{PPT}$ machines.

A stronger assumption is:

  DDH-1: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for $\rm{P/poly}$ circuits.

An even stronger assumption is:

  DDH-2: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for sub-exponential circuits.

I saw both DDH and DDH-1 assumptions in the literature. DDH-2 may also exist, but I can't recall whether I ever saw it.

One example of sub-exponential hardness assumption is that, some languages in $\rm{E}$ don't have sub-exponential circuits. Such assumption is used by Impagliazzo & Wigderson in P=BPP unless E has sub-exponential circuits:
Derandomizing the XOR Lemma.

Description of Some Terms

While obvious, I'm going to define several terms here. Let $f \colon \mathbb{N} \to \mathbb{N}$ be a function. Then:

$f(n) = n^{\Theta(1)}$ is called polynomial. (e.g. $n, n^3, 7n^{100}$.)
$f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
$f(n) = 2^{\Theta(n)}$ is called linear exponential. (e.g. $2^n, 3^n, 10^n$.)
$f(n) = 2^{n^{\Theta(1)}}$ is called exponential. (e.g. $2^n, 3^{n^4}$.)
$f(n) = 2^{n^{o(1)}}$ is called sub-exponential. (e.g. $2^{n^{1/n}}, n^{\log n}$.)


What is the most Accurate way of Determining an Object's Color?

You can fit a model to estimate a posterior probability of a color space point to belong to a certain coin type. Take a look at Gaussian mixture model. Another (somewhat arbitrary, but simpler) approach is to use nearest-neighbour interpolation.


Planar separator theorem and tree decomposition

As far as i know the simplest (in my opinion) self contained proof of the planar separator theorem is unpublished; it is a combination of the following (somewhat non-trivial) theorem with the "Baker layering" trick.

The treewidth of a planar graph of diameter d is <= 3d-1
[H. L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth.
Theor. Comput. Sci., 209(1-2):1–45, 1998, Theorem 83]

Now to the "Baker layering" trick: do a BFS from an arbitrary vertex and number the layers
1,2....sqrt(n), 1, 2, ... sqrt(n) .. etc
Now there exists an i such that the total number of vertices living in layers labelled i is at most sqrt(n). Let the set of these vertices be S. Consider any connected component of G-S. Such a component must live in at most sqrt(n) consecutive layers, and thus it has diameter <= 2sqrt(n). Since planar graphs of diameter sqrt(n) have treewidth at most 3sqrt(n) we have that G-S has treewidth <= 6sqrt(n) and so G has treewidth <= 7sqrt(n). Tada.

There is a small silly bug in the proof above; the fact that a connected component of G\S lives inside sqrt(n) layers does not mean that the diameter is actually at most sqrt(n) ... but thus is easily fixed by contracting the layers up until the layer of this component into a single vertex. Then diameter of (a supergraph of the component) is at most 2sqrt(n), and we are done.


Small number of inequalities defining integer hull of integer programming problem

"Is there research on this". Well, a great share of the operation research consists in finding linear (or, now, semidefinite or other convex cone) relaxations of combinatorial problems, such that the linear relaxation matches or nearly matches the exact integer hull; so if it nearly matches, then one can perhaps prove some results such as "the optimum in the relaxation does not approximate the exact optimum by more than factor X".

An interesting approach is to lift the problem to a higher dimension. In general, the projection of a polyhedron to lower dimension may have many more constraints than the original, thus the converse (expressing a polyhedron as a projection of a higher dimension polyhedron) may be interesting so as to lower the number of constraints. This led to the family of methods known as "lift and project".


What forms of randomness are 'allowed' in FPRASs?

It's the standard model for any randomized algorithm, e.g., generate a random bit.

You can't generate a uniformly random number in the unit interval in the standard model.  You can't even represent a real number in a finite amount of space.  If you want to compute with real numbers, you need a different model of computation designed for reasoning about computation with real numbers.


Reachability on DAG (best-known algorithm)

[Rooted trees with edges directed away from the root] are DAGs,

and from reachability on such a DAG, one can recover

the root as the unique vertex from which every other vertex is reachable
and
the tree by observing that x is adjacent to y if and only if [x≠y and [one of {x,y} is

reachable from the other of {x,y}] and [there is no vertex z such that [[z is not in {x,y}] and

[[x is reachable from z is reachable from y] or [y is reachable from z is reachable from x]]]]]

.

Thus, by this formula, there are  $n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(\hspace{-0.02 in}n^{n-2}\right)$  distinct reachability oracles

for [rooted trees with edges directed away from the root].

$\log_2\hspace{-0.06 in}\left(n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(n^{n-2}\right)\hspace{-0.03 in}\right) \;\; = \;\; \log_2\hspace{-0.06 in}\left(\hspace{-0.02 in}n^{n-1}\right) \;\; = \;\; (n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n) \;\;$,

so any encoding of [reachability oracles for rooted trees with edges directed away from the root]

will need to use more than $\;\;\; \left((n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n)\right)-3 \;\;\;$ bits for more than 3/4 of such DAGs.

By this paper,

"has n1+o(1) space complexity"  and  "Can answer reachability queries in O(1) time"

are incompatible:

As described at the bottom of page 5 and the top of page 6,

"butterfly graph"s are directed acyclic.

Accordingly, all of their subgraphs are also DAGs.

By Theorem 1.2 and the two sentences after that,

for constant time,    "the space needs to be  $n^{1+\Omega \hspace{.02 in}(1)}$ ."

(I'm not aware of any positive results.)


Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange.


Syntactic characterisation of the intersection of CTL and LTL

Note that by "equivalent", we actually need to interpret LTL over trees. Thus, we say that a CTL formula $\phi$ is equivalent to an LTL formula $\psi$, if $\phi$ is equivalent to the CTL* formula $A\psi$.

Thus, we essentially compare LTL and CTL in the common grounds of CTL*.

Given this, it's not hard to construct a procedure to check the equivalent. Simply check whether the formula $\phi \iff A\psi$ is a tautology in CTL*. This can be done in 2EXPTIME. However, since satisfiability of CTL is only EXPTIME complete, it might be possible to reduce this to EXPTIME (but I haven't given it much thought).


Two sources: The Fan Chung book on spectral graph theory  and Dan Spielman's notes on the same.


How to describe the set of "all computable functions" using Coq?

The usual definition of partial recursive functions using Turing machines and classical logic (with a few novelties) has been implemented in Coq: see

Zammit, Vincent (1997) A Proof of the S-m-n theorem in Coq. Technical report. University of Kent, The University of Kent, Canterbury, Kent, UK


In Extending Type Theory with Forcing by  Guilhem Jaber, Nicolas Tabareau and Matthieu Sozeau, 2012, intuitionistic forcing is presented as an internalization of the presheaf construction, implemented as a type-preserving translation in the style of Bernardy and Lasson's parametricity translation.

This means that you can define terms in your usual type theory, and then "translate them" into a "forcing layer" where they are interpreted as translations at a different translation type. For example, the translation induced by indexing over decreasing natural numbers lets you use your usual terms in a post-translation theory where a later modality is definable. This sounds rather close to your idea of working internally in the topos of trees.

It seems that they have a new, simpler Coq plugin implementing these ideas at CoqHott/coq-forcing, and in particular SI.v builds this forcing translation for step-indexing. Unfortunately, while it does the work of building the model, there is no example of using it for step-indexed definitions in practice (the only thing translated instead of defined in the forcing layer is Forcing Translate eq, which isn't terribly informative). You could try to experiment to see how (in)convenient this is to use.


Precise definition for cryptographic protocol?

There are several definitions of cryptographic protocols, each of which tries to capture some particular features of interest.

I start with Goldwasser, Micali, and Rackoff definition (1985): They first defined interactive Turing machines (ITM), based of which they defined (two-party) interactive protocols. An ITM is a special TM equipped with one read-only and one write-only communication tape. A pair of ITMs  constitutes an interactive protocol if the read-only communication tape of party A coincides with the write-only communication tape of party B, and vice versa. The power of parties and the adversary model is then defined accordingly (see the paper).

The multi-party case was later defined by Goldreich, Micali, and Wigderson (1987). They modeled a secure multi-party game in an elegant way, though the paper (as Goldreich states himself) leaves a lot of doors open. For a more concrete discussion see: http://www.wisdom.weizmann.ac.il/~oded/pp.html.

Finally, a much stronger model was proposed by Canetti (2001). In his paper, he defines a framework called Universal Composability (UC), based on which he defines the cryptographic protocols and puts forward a notion of security for them.

As far as I recall, the last paper cites a lot of other works which try to define and model security protocols. Therefore, I strongly advise you to take a look at it.


The question has been answered in the comments by Tsuyoshi & Chandra!  I am adding this CW answer so I can accept it to indicate the question is closed.  Thanks, everyone!


What are the differences between logical relations and simulations?

I have an answer to this question which is possibly novel.  In fact, I am still thinking through it for the last 6 months or so, and it hasn't been written about in papers yet.

The general thesis is that relational reasoning principles like "logical relations", "simulations", and even "invariants" are manifestations of data abstraction or information hiding.  Wherever there is information hiding, these principles crop up.

The first people to discover it were automata theorists.  Automata have hidden state.  So you need relational reasoning to talk about their equivalence.  Automata theorists struggled with homomorphisms for a while, gave up, and came up with a notion called "relational covering", which is a form of simulation relations.

Milner picked up the idea in a little-known but very fundamental paper called "An algebraic notion of simulation between programs" in 1971.  Hoare knew it and used it in coming up with "Proof of correctness of data representations" in 1972 (but used abstraction functions instead of relations because he thought they were "simpler").  He later retracted the simplicity claim and went back to using relations in "Data refinement refined".  Reynolds used relational reasoning in "Craft of Programming", Chapter 5 (1981).  He thought relations were more natural and general than abstraction functions.  If you go back and read this chapter, you will find relational parametricity ideas lurking around, waiting to be discovered.  Sure enough, two years later, Reynolds published "Types, abstraction and parametric polymorphism" (1983).

It looks like all these ideas have nothing to do with types, but they really do.  Stateful languages and models have built-in data abstraction.  You don't need to define an "abstract data type" to get information hiding.  You just declare a local variable and hide it.  We can teach it to first year students in Java classes in the first few weeks.  No sweat.

Functional languages and models, on the other hand, have to get their information hiding via types.  Functional models don't have built-in data abstraction.  We have to add it on explicitly, using $\forall$ or $\exists$.  So, if you translate a stateful language into a functional language, you will notice all the local state getting translated into type variables.  For an explicit description of how this works, see my paper "Objects and classes in Algol-like languages", but the ideas really come from Reynolds 1981 ("The Essence of Algol"). We are just understanding those classic ideas better now.

Take two machines $M$ and $M'$ that you want to prove equivalent.  Milner 1971 says, define a relation between the states of $M$ and $M'$ and show that the two machines preserve the relation.  Reynolds parametricity says, think of the states of the machines as belonging to types $X$ and $X'$.  Define a relation $R$ between them.  If the machines are of type $F(X)$ and $F(X')$, parameterized by the types of their states, then check that the two machines are related by the relation $F(R)$.

So, simulations and relational parametricity are essentially the same idea.  It is not merely a superficial resemblance.  The former is made for stateful languages where there is built-in data abstraction.  The latter is made for stateless languages where data abstraction is obtained via type variables.

What about logical relations then?  On the surface, logical relations appear to be a more general idea.  Whereas parametricity talks about how to relate type variables within the same model, logical relations appear to relate types across different models.  (Dave Clarke wrote a brilliant exposition of this earlier.)  But my feeling is (and it still needs to be demonstrated) that this is an instance of some form of higher-type parametricity which hasn't yet been formulated.  Stay tuned for more progress on that front.

[Note added] The connection between logical relations and simulations is discussed in our recent paper Logical relations and parametricty: A Reynolds programme for Category Theory and Programming Languages.


What are some good introductory books on type theory?

Software Foundations by Benjamin C. Pierce would be a good place to start. It would be a make a good precursor to his Types and Programming Languages. There is also Simon Thompson's Type Theory and Functional Programming and Girard's Proofs and Types.


The Design of Approximation Algorithms by Williamson & Shmoys (http://www.designofapproxalgs.com/) is a great book for many approximation methods such as greedy algorithms, semidefinite programming, etc. Also, it covers some topics within complexity that are closely related to approximation algorithms (inapproximability, Unique Games-based hardness of MAX-CUT).


It is NP-complete for directed graphs. Even deciding if there exist a path from $s$ to $t$ using vertex $u$ is NP-complete.

The 2-node disjoint path problem is NP-hard for directed graphs$^1$.

  Given a directed graph $G$ and vertex pairs $(s_1,t_1)$ and
  $(s_2,t_2)$, does there exist two node disjoint paths that goes from
  $s_1$ to $t_1$ and $s_2$ to $t_2$?

We can reduce this problem to your problem:
Split each vertex of $G$, so each vertex $v$ in $G$ become $v^-$ and $v^+$, and edge $uv$ become $u^+v^-$, also there are edges $v^-v^+$. Add one new vertex $u$, and edges $t_1^+u$ and $us_2^-$. Let this graph be $G'$.

There exist a path from $s_1^-$ to $t_2^+$ in $G'$ that uses $u$ if and only if there exist a node disjoint path between $(s_1,t_1)$ and $(s_2,t_2)$ in $G$.

The directed subgraph homeomorphism problem, Steven Fortune, John Hopcroft, James Wyllie.


Difference between theory and practice of security and cryptography?

Oh boy, where to start.

The big one is definitely black boxes. Crypto researchers make a fuss about things like uninstantiability problem of the Random Oracle Model. Security researchers are at the other extreme and would like everything to be usable as a black box, not just hash functions. This is a constant source of tension.

To illustrate, if you look at the formal analysis of security protocols, for example BAN logic, you will see that symmetric encryption is treated as an "ideal block cipher." There is a subtle distinction here — BAN logic (and other protocol analysis techniques) don't claim to be security proofs; rather, they are techniques for finding flaws. Therefore it is not strictly true that the ideal cipher model is involved here. However, it is empirically true that most of the security analysis tends to be limited to the formal model, so the effect is the same.

We haven't even talked about practitioners yet. These guys typically don't even have a clue that crypto primitives are not intended to be black boxes, and I doubt this is ever going to change — decades of trying to beat this into their heads hasn't made a difference.

To see how bad the problem is, consider this security advisory relating to API signature forgeability. The bug is partly due to the length-extension attack in the Merkle-Damgard construction (which is something really really basic), and affects Flickr, DivShare, iContact, Mindmeister, Myxer, RememberTheMilk, Scribd, Vimeo, Voxel, Wizehhive and Zoomr. The authors note that this is not a complete list.

I do think practitioners deserve the lion's share of the blame for this sad state of affairs. On the other hand, perhaps crypto theorists need to rethink their position as well. Their line has been: "black-boxes are impossible to build; we're not even going to try." To which I say, since it is clear that your constructions are going to get (mis)used as black boxes anyway, why not at least try to make them as close to black boxes as possible?

The paper Merkle-Damgard Revisited is a great example of what I'm talking about. They study the security notion that "the arbitrary length hash function H must behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher." This kind of theoretical research has the potential to be hugely useful in practice.

Now let's get to your example of circuit evaluation. I beg to disagree with your reasoning. It's not like you would take a compiled binary and blindly turn it into a circuit. Rather, you'd apply circuit evaluation only to the underlying comparison function which is usually quite simple. Fairplay is an implementation of circuit evaluation. A colleague of mine who's worked with it tells me that it is surprisingly fast. While it is true that efficiency is a problem with circuit evaluation (and I do know of real-world instances where it was rejected for this reason), it is far from a showstopper.

The second reason I disagree with you is that if you think about some of the typical real-life scenarios in which you might conceivably want to carry out oblivious circuit evaluation — for example, when two companies are figuring out whether to merge — the computational costs involved are trivial compared to the overall human effort and budget.

So why then does no one use generic secure function evaluation in practice? Great question. This brings me to my second difference between theory and practice: trust actually exists in practice! Not everything needs to be done in the paranoid model. The set of problems that people actually want to solve using crypto is much, much smaller than what cryptographers imagine.

I know someone who started a company trying to sell secure multiparty computation services to enterprise clients. Guess what — no one wanted it. The way they approach these problems is to sign a contract specifying what you can and cannot do with the data, and that you will destroy the data after you're done using it for the intended purpose. Most of the time, this works just fine.

My final point of difference between theory and practice is about PKI. Crypto papers frequently stick a sentence somewhere saying "we assume a PKI." Unfortunately, digital certificates for end users (as opposed to websites or employees in a corporate context, where there is a natural hierarchy) never materialized. This classic paper describes the hilarity that ensues when you ask normal people to use PGP. I'm told that the software has improved a lot since then, but the underlying design and architectural issues and human limitations are not much different today.

I don't think cryptographers should be doing anything differently as a consequence of this lack of a real-world PKI, except to be aware of the fact that it limits the real-world applicability of cryptographic protocols. I threw it in because it's something I'm trying to fix.


This is called the (linear) assignment problem. It can be solved efficiently through linear programming over the Birkhoff polytope.


Hardness of node partitioning under shortest path constraint

Let’s call an assignment of vertex labels feasible if it satisfies all the inequality constraints, ignoring the condition on the number of distinct labels.

Here is what I think is a proof that it is NP-complete to decide whether a given directed graph G=(V, E) with integer (possibly negative) edge weights has a feasible assignment of labels which uses at most k distinct labels, for k=|V|/2.  We construct a reduction from the following NP-complete problem [WY92].

Equal Subset Sum
Instance: A finite set S of positive integers.
Question: Do there exist two disjoint nonempty subsets S1 and S2 of S whose sums are equal to each other?

Let S={a1, …, an} be a set of positive integers, where n=|S|.  Construct a directed graph G with 2n vertices u1, …, un, v1, …, vn by connecting ui and vi in both directions for each i.  Give the weight ai to the edge (ui, vi) and −ai to the edge (vi, ui).

Consider the instance (G, n) of the current problem.  Note that an assignment l of labels is feasible if and only if for each i, it holds l(vi)=l(ui)+ai.  From this, we can prove the following, establishing that the above transformation is a reduction from Equal Subset Sum to the current problem.

Claim.  G has a feasible assignment which uses at most n distinct labels if and only if there exist two disjoint nonempty subsets S1 and S2 of S whose sums are equal to each other.

Proof.  First observe that if we are given a feasible assignment l (which might use any number of distinct labels), we can construct a directed graph Hl from G by removing the edges with negative weights and merging vertices with equal labels.  Note that Hl has exactly n edges whose weights are a1, …, an.  Also, note that the number of vertices of Hl is equal to the number of distinct labels used in l.

For the “only if” direction, given a feasible assignment l which uses at most n distinct labels, consider the directed graph Hl.  Since Hl has at most n vertices and exactly n edges, Hl contains a cycle C ignoring the direction of edges.  Let S1 be the set of weights of edges appearing in C in one direction, and S2 be the set of weights of edges appearing in C in the other direction.  It is easy to see that the sum of S1 is equal to the sum of S2.

For the “if” direction, fix S1 and S2 be the subsets of S satisfying the condition.  Without loss of generality, assume that S1={a1, a2, …, as} and S2={as+1, as+2, …, as+t}, where s=|S1| and t=|S2|.  Then we assign the following labels to the vertices of G:

l(u1)=l(us+1)=0.
l(ui)=l(vi−1) for 2≤i≤s and s+2≤i≤s+t.
l(ui)=0 for s+t+1≤i≤n.
l(vi)=l(ui)+ai for 1≤i≤n.

It is easy to verify that this assignment is feasible and uses at most n distinct labels.  (The graph Hl in this case consists of two edge-disjoint paths from the vertex labeled 0 to the vertex labeled $\sum_{i=1}^s a_i = \sum_{i=s+1}^{s+t} a_i$ and n−s−t edges originating at the vertex labeled 0.)  QED.

References

[WY92] Gerhard J. Woeginger and Zhongliang Yu.  On the equal-subset-sum problem.  Information Processing Letters, 42(6):299–302, July 1992.  http://dx.doi.org/10.1016/0020-0190(92)90226-L


Translating typed functional language to untyped lambda calculus

There's an old way of doing what you're asking for, coming from domain theory. Let $D$ be the collection of all values of the untyped $\lambda$-calculus. We can undestand $D$ to be some sort of a domain, or the set of closed normal terms, it does not really matter. We define a type to be a retraction $r : D \to D$, i.e., a continuous map (or a closed term if you want definable types) such that $r \circ r = r$. Such an $r$ represents the collection of its fixed points $D_r = \{x \in D \mid r(x) = x\}$. The map $r$ itself is a coercion from $D$ to $D_r$. Because it is a retraction, it does not do anything to elements of $D_r$.

Now, given any map $f : D \to D$ say that it maps $D_r$ to $D_q$ when $f = q \circ f \circ r$. This equation says that:

$f$ is already determined by its restriction $f{\restriction}_{D_r}$ to $D_r$ (because $f = f{\restriction}_{D_r} \circ r$),
the image of $f$ is contained in $D_q$ (because $f = q \circ f$).

Putting these two together, we see that $f$ can be thought of as going from $D_r$ to $D_q$ (it is important that $f$ does not carry any additional information about how to map elements outside $D_r$, or else we could  have several different functions that all act the same way on $D_r$).

Actually, any map $g : D \to D$ can be coerced to a map from $D_r$ to $D_q$ by the retraction $g \mapsto q \circ g \circ r$.

Let us see how this relates to your question. You would like to have a way of saying that a map $f$ maps integers to integers (I presume you mean natural numbers since you speak of Church numerals). So what we need is a map $r$ such that $r (r x) = x$ if, and only if, $x$ represents an integer. Once we have such a map we can express the fact that $f$ maps integers to integers with the equation $f = r \circ f \circ r$.

So it remains to write down a map $r$ in the untyped $\lambda$-calculus whose fixed points are Church numerals (and also some diverging terms which denote bottom). I think this might work:
$$r(x) = \mathtt{rec}\;\mathtt{Z}\;(\lambda n\,y \,. \mathtt{S}\,y)\;x,$$
where $\mathtt{rec}$ is a simple recursor over natural numbers, $\mathtt{Z}$ is zero and $\mathtt{S}$ is successor. Intuitively, speaking, if $x$ behaves like a natural number, then $r(x)$ will "rebuild" it into standard form $\mathtt{S}(\mathtt{S}(\cdots \mathtt{Z}))$.

We need to be a bit careful about how $\mathtt{rec}$ is implemented. It has to satisfy
$$\mathtt{rec}\;x\;f\;\mathtt{Z} = x$$
and
$$\mathtt{rec}\;x\;f\;(\mathtt{S}\,n) = f\;n\;(\mathtt{rec}\;x\;f\;n),$$
and it should "crash" when we feed it something that does not behave like a numeral.


For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose lengths are the 3SUM inputs and the other has segments whose lengths are the bins you have to pack them in, then you can do it with no additional cutting iff the 3SUM instance is solvable. For two-dimensional polygons it remains hard, even for connected regions: thicken the segments of a one-dimensional problem to unit-height rectangles and connect them by thin "strings" that have too small an area to affect the 3SUM part of the problem but are easy to handle in the decomposition.

(Disclaimer: I borrowed this reduction idea from some not-yet-published joint work with many other people on hardness of some other problems.)


Where is the proof of universality of Rule110 in Stephen Wolfram's book?

Found it:

cyclic tag system to tag system p.669

glider p.678

The pictures are very helpful!


I think this may have been a typo in Agrawal's paper. The best I know is how to write an $n \times n$ determinant as a projection of an $O(n^3)$-sized permanent, by writing the determinant as an algebraic branching program (and I think this is currently the best known). See the comments on this answer.


Perhaps my favorite open problem is of interest: the edge clique-cover problem on cographs. In the edge clique-cover problem, you want to cover the edges of the cograph with a minimal number of cliques. It is unknown if this problem is NP-complete.

To illustrate that the problem is probably hard, let $K_n^m$ be the complete multipartite graph with $m$ partite sets each of size $n$. This is a cograph. There exist $m - 2$ pairwise orthogonal Latin squares of order $n$ if and only if the edge clique-cover of $K_n^m$ is $n^2$. This was shown by Park, Kim and
 Sano. This is a formula for the "cocktail party graph", that is, the case where $n = 2$.


The answer is NOT $\lceil \frac{mn}2\rceil$ for all large $m, n$ if e.g. $p=6$ and $q=3$. Why? Notice that because of the remainders $\mod 3$ now the graph is the (vertex) disjoint union of three bipartite graphs and from each we can select the bigger half. For example if $m=n=100$, then this way we can place (at least) 5002 knights. (This is because $x+y \mod 6$ has six classes which are in three pairs, the differences between the cardinalities of the pairs is $1,1,2$.)

I do not know what happens if we add the condition that $p$ and $q$ are relative primes. (Note that apart from the 2 divisor this is equivalent to $p+q$ and $p-q$ being relative primes, in fact this is the condition that we need and which also shows that $p+q$ being odd is necessary.)


I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if
\begin{align*}
\Phi :=
\forall \vec{x}.\exists \vec{y}.\left( A \cdot \vec{x} \le b \implies \left( A \cdot \vec{y} \le b \wedge \bigwedge_{1\le i\le m} f_i(\vec{x}) = g_i(\vec{y}) \right)\right)
\end{align*}
is valid. It is clear how to derive equivalence of $P_1$ and $P_2$ in the same way. Now $\Phi$ has a fixed quantifier-alternation prefix, and is consequently decidable in $\Pi_2^\text{P}$, the second level of the polynomial-time hierarchy (Sontag, 1985). I'm pretty confident that it is possible to also prove a matching lower bound, I recall reading somewhere that inclusion between two polytopes is $\Pi_2^\text{P}$-hard.

If you are looking for tool support in order to solve such problems in practice, modern SMT-solvers such as z3 fully support this theory.


Kolmogorov Complexity of an arbitrary string

A string $x$ is $c$-compressible if $K(x) \leq |x| + c$. If $x$ is not compressible by $1$, $x$ is  said to be incompressible (or random, if you will).

There are $2^n$ bit strings of length $n$, and there are $\sum_{i=0}^{n-1} 2^i = 2^n-1$ descriptions that are of length less than $n$. Because each description describes at most one string, there is at least one incompressible bit string for each length $n$.

Also, at least $2^n-2^{n-c+1}+1$ strings of length $n$ are incompressible by $c$. Once again, at most $2^{n-c+1}-1$ strings of length $n$ are $c$-compressible, because we have at most that many descriptions of length at most $n-c$. Then the remaining $2^n-(2^{n-c+1}-1)$ strings are incompressible by $c$.


Advantages and specific applications of massively parallel programming thesis idea

Build a "CUDA-SAT solver" and outperform the winners of the annual Sat competitions ! :-)

Edit: I posted the answer quickly ... but - after a Google search - I found that my idea is not so original, see: NVIDIA CUDA Architecture-based Parallel Incomplete SAT Solver ... however I think that a public available project/source code of a CUDA-powered SAT solver that can be compiled and used on a standard PC (Linux and/or Win) equipped with a CUDA GPU graphics card would be very appreciated.

As a second best, I suggest you to try to implement a parallel genetic algorithm and pick one (or more) of the many possible applications to show the performance gains due to the parallelization.


Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm

Since PIT is in $\mathsf{coRP}$, if there is no efficient derandomization then $\mathsf{P} \neq \mathsf{RP}$ (and, in particular, $\mathsf{P} \neq \mathsf{NP}$, but that's not so surprising, since we expect that to be true anyways). This also implies, of course, that $\mathsf{P} \neq \mathsf{BPP}$, so anything which implies $\mathsf{P} = \mathsf{BPP}$ becomes false. For example, sufficiently strong pseudorandom number generators do not exist, and $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$ would have subexponential size circuits!


Hyperdoctrines and Monadic Second Order Logic

I don't know!
No, your assumption is not right. You can quantify over higher-order functions and predicates in IHOL (in fact, predicates are just functions into a type of propositions). The setup looks a bit like this:

$$
\begin{array}{llcl}
\mbox{Sort} & \omega & ::= &  \omega \to \omega \;\; | \;\; \omega \times \omega \;\; | \;\; 1  \;\;|\;\; \mathrm{prop}  \;\;|\;\; \iota\\
\mbox{Term} & t & ::= & x \;\;|\;\; \lambda x.t \;\;|\;\; t\;t' \;\;|\;\; (t,t) \;\; | \;\; \pi_1(t) \;\;|\;\; \pi_2(t) \;\;|\;\; () \\
&            &  |  &
     p \Rightarrow q \;\;|\;\; \top \;\;|\;\; p \wedge q \;\;|\;\; \bot \;\;|\;\; p \vee q  \\
& & | & \forall x:\omega.p \;\;|\;\; \exists x:\omega.p  \;\;|\;\; t =_\omega t' \\
& & | & f(\vec{t})
\end{array}
$$

You give the usual typing rules to judge the well-formedness of a term. The first line of terms are the usual simply-typed lambda calculus, the second two lines are the propositions of higher-order logic (typed as elements of $\mathrm{prop}$), and the third line are whatever constants you use to form individuals (elements of $\iota$).

Then the idea is that you want to extend the Kripke semantics for first-order intuitionistic logic to higher-order logic, by extending the hyperdoctrine semantics with additional structure. A first-order hyperdoctrine is a functor $P : C^\mathrm{op} \to \mathrm{Poset}$ between a category $C$ with products (used to interpret the terms in context), and a category of posets (the truth value lattices), satisfying some conditions to make substitution work right.

To get to IHOL, you additionally assert that

$C$ is cartesian closed (to model the ability to quantify over function types), and
$C$ has an internal Heyting algebra $H$ satisfying the property that for every $\Gamma \in C$, $\mathit{Obj}(P(\Gamma)) \simeq C(\Gamma, H)$. You use $H$ to model $\mathrm{prop}$, and the isomorphism tells you that terms of type $\mathrm{prop}$ really do correspond to truth values.

This structure is almost an "elementary topos". If you additionally require that $P(\Gamma)$ is a poset of subojects of $\Gamma$, then you're there. (This essentially says that you can add a comprehension principle to your logic.)


Constructing integer sets in which a certain equation has no solution

Consider an equation
$$\tag{E}a_1x_1+\dots+a_kx_k=0.$$
Let $s=\sum_ia_i$ be the sum of its coefficients.

If $s=0$, the equation (E) has solutions in every nonempty set $S$, hence you are out of luck.

If $s\ne0$, let $p$ be the smallest prime not dividing $s$. Note that $p=O(\log |s|)$. Then (E) has no solution such that $x_i\equiv1\pmod p$ for all $i=1,\dots,k$, hence the set
$$S=\{1,p+1,\dots,(n-1)p+1\}$$
works, with maximum $(n-1)p+1$. For a fixed equation (E), this is $O(n)$, and the set can be computed as easily as it gets.


Powerful algorithms that are just too hard to implement-- how to be sure they are right?

Several years ago, there has been a (rather harsh) debate on a topic similar to this. It all started when several complex proofs turned out to be incorrect, and some researchers started to raise doubts on the very nature of proofs (well, I should have said "provable cryptography," but for the sake of generality, I didn't). Both sides of the controversy accused the other to misunderstand the concepts. Here's a link for more info.

Proofs are our (mathematical) tools to prove theorems/algorithms are correct, but when they became too complex, we may slip and prove wrong things to be right. The recent 100-or-so-page proof on P≠NP is an excellent example. However, this does not rule out the very nature of proofs: Nothing's wrong with them.

One last point: I think studying the philosophy of science will give us more insight on this. (Under the given link, see the bullet "How do we know whether a mathematical proof is correct?")


Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

The planar version of many NP-complete problems belong to $NTISP(n,n^q)$ for some $q<1$

See for example "Lower Bounds and Complete Problems in Nondeterministic Linear Time and
Sublinear Space Complexity Classes" by P. Chapdelaine and E. Grandjean (2006)


"Almost sorting" integers in linear time

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

Unfortunately, the running time is not quite linear. The article above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n*log (\nu(n))$ (assuming $\nu(n) < n$).

EDIT, in response to the clarifications in the question:

What you're doing is simply a bucket sort. However, the algorithm for bucket sort isn't linear in this case. The problem: you have to sum the natural numbers and then perform division on each one of them. Since the numbers are unbounded in size, $N/V[i]$ is no longer a constant-time operation. It will take longer to perform the more numbers you need to sum.

How much longer? Division depends on the number of digits, so it's $lg(n)$, times $n$ division operations. That probably sounds familiar. :)


Theorem Exactly computing $F(w,t)$ is #P-hard.

proof.  Reduce from the counting version of Subset Sum, the #Subset Sum problem, defined as follows. Input is a set $W = w_1, \ldots, w_n$ of non-negative integers, and an integer $t$. The task is to count the number of subsets $W' \subseteq W$ that add up to exactly $t$. This problem is known to be #P-hard, even when for all $i$, $w_i \leq t$ and $t = 2^{O(n)}$. In particular, the $w_i$'s are $O(n)$ bit integers.

Suppose now we could compute F in polynomial time. Then we could solve the #Subset Sum problem by outputting:

$$2^n \cdot \left( F(\frac{W}{t}, 1-\frac{1}{t}) - F(\frac{W}{t}, 1) \right) = 2^n \cdot P\left[\sum_{i=1}^n \frac{w_iX_i}{t} = 1 \right],$$
which is precisely the number of subsets of $W$ that add up to $t$.


The obvious resource for planar graphs in Coq would be the (modern port of) the four color theorem in Coq/SSReflect, by Georges Gonthier (and others) which obviously does need to define planar graphs.

It's not immediately obvious to me how planar graphs are characterized, though the relevant file is here and it seems to involve a combination of Euler characteristic and Jordan paths.

One could conceivably use the forbidden minor characterization, and use the modern library by Doczkal and Pous though I have a hard time imagining that it's easy to prove anything using that characterization. It'd be more interesting to prove that it is a characterization. This again uses SSReflect. See also the paper.

Finally, using any of the existing (mature) libraries for graphs, one might want to use the definition used in the flyspec project, described here, which defines (in section 2.3) planar graphs in terms of faces, which need to be orientable, connected to other faces with inverse orientation, with a cycle around each vertex, and obeying the Euler theorem. The paper is very nice, and describes the Gonthier approach as well in the subsequent sections.