Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

Update: High resolution cover can be found here. (via Artem)

A: Pushdown Automata
B: Regular Expressions
C: Context Free Languages
D: Finite Automata
E: Mathematical Truth
F: NP-Complete Problems
G: Turing Machines
H: Time/Space Complexity


Algorithm for finding heavy hitters in a weighted stream

Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?)
This is probably not the ideal solution, but it's a start.

Weighted Heavy Hitters Algorithm.
Input: $S=\{(\text{id}_i,\text{weight}_i)\}_{i=1}^N$ a weighted stream.

1. Create an unweighted stream $S'=\{\text{id}_j\}_{j=1}^{N'}$ as follows. For every weighted update $(\text{id}_i,\text{weight}_i)$ in $S$, include the unweighted update $\text{id}_i$ in $S'$ independently with probability $\text{weight}_i$.

2. Apply an unweighted heavy hitters algorithm (i.e. Space Saving or Batch Decrement) to $S'$ and output the heavy hitters for $S$.

Clearly this algorithm has $O(1)$ update time. To verify that this algorithm is correct we must prove the following claim.

Claim. With high probability, for every $\text{id}$, the count of $\text{id}$ in $S'$ is close to the sum of the weights of $\text{id}$ in $S$.

Let $w_\text{id}$ be the "true" weight of $\text{id}$ in $S$ and $W_\text{id}$ the weight of $\text{id}$ in $S'$. Let $w=\sum_\text{id} w_\text{id}$ be the total weight of $S$ and $W=\sum_\text{id} W_\text{id}$ be the total weight of $S'$.

Our claim is that $|W_\text{id}-w_\text{id}| \leq \varepsilon w$ for all $\text{id}$ with high probability.

Clearly $\mathbb{E}\left[W_\text{id}\right]=w_\text{id}$. It remains to show concentration bounds. To this end, we use the following result.

Bernstein's Inequality. Let $X_1, \cdots, X_n \in \{0,1\}$ be independent random variables. Then $$\mathbb{P}\left[ \left| \sum_{i=1}^n X_i - \mathbb{E}\left[X_i\right] \right| > t \right] \leq 2 \cdot \exp\left(-\Omega\left(\frac{t^2}{t+\sum_{i=1}^n \mathsf{Var}\left[X_i\right]}\right)\right)$$ for all $t > 0$.

Thus  $$\mathbb{P}\left[ \left| W_\text{id}-w_\text{id} \right| > \varepsilon w \right] \leq 2 \cdot \exp\left(-\Omega\left(\frac{\varepsilon^2 w^2}{\varepsilon w+w_\text{id}}\right)\right) \leq 2 \cdot \exp\left(-\Omega\left(\varepsilon^2 w\right)\right).$$

Note that if $w_\text{id}=0$, then $W_\text{id}=0$. So we need only consider the $\text{id}$s that appear in the stream. In particular, we can take a union bound over at most $N$ $\text{id}$s:

If $w \geq O\left(\log(N)/\varepsilon^2\right)$, then the weights in $S'$ are close to the weights in $S$ with high probability and the claim is verified.

What about when $w \leq O\left(\log(N)/\varepsilon^2\right)$? Then we can first repeat each weighted update $T$ times. This increases the weight to $Tw$. The good news is that $S'$ is only length $O(Tw)$ and transforming $S$ into $S'$ takes $O(1 + Tw/N)$ (amortized) time per update with high probability. So we just need to find a $T$ with $ O\left(\log(N)/\varepsilon^2\right) \leq Tw \leq O(N)$.


putting objects in buckets -- optimization problem

I assume that $\cal O$ and $\cal B$ are of polynomial size. One way to solve this problem is to reduce it to the Maximum Cost Bipartite Matching Problem. Consider the following bipartite graph $G = (L\cup R, E)$:

$L = \{b_i: b\in {\cal B}, 1\leq i \leq\mu_b\}$, that is,  for
every bucket $b$ and $i\in \{1,\dots, \mu_b\}$, we introduce a vertex
$b_i$
$R = \cal O$
$E = L \times R$, the cost of the edge $(b_i,o)$ equals $E(o,b)$.

We find a maximum cost matching $M$ in $G$. Now we construct the solution to our original problem: bucket $b$ contains those objects that are matched in $M$ with vertices $b_1, \dots, b_{\mu_b}$. Clearly, each bucket $b$ contains $\mu_b$ objects. The value of this solution equals the cost of $M$.


What do we know about provably correct programs?

"Certifying compiler" usually means something slightly different: it means that you have a compiler which can prove that the machine code it emits correctly implements the high-level semantics. That is, this is a proof that there are no compiler bugs. The programs that people give to the compiler can still be wrong, but the compiler will generate a correct machine code version of the wrong program. The biggest success story along these lines is the CompCert verified compiler, which is a compiler for a large subset of C.

The Compcert compiler itself is a program with a correctness proof (done in Coq), which guarantees that if it generates code for a program, it will be correct (with respect to the operational semantics of assembly & C that the CompCert designers used).  The effort to machine-check these things is quite large; typically the correctness proof will be anywhere from 1x to 100x the size of the program you are verifying. Writing machine-checked programs and proofs is a new skill you have to learn -- it's not mathematics or programming as usual, though it depends on being able to do both well. It feels like you are starting from scratch, like being a novice programmer again.

There are no special theoretical barriers to this, though. The only thing along these lines is the Blum Size theorem that for any language in which all programs are total, you can find a program in a general recursive language which will be at least exponentially larger when programmed in the total language. The way to understand this result is that a total language encodes not just a program, but also a termination proof. So you can have short programs with long termination proofs. However, this doesn't really matter in practice, since we're only going to ever write programs with manageable termination proofs.

EDIT: Dai Le asked for some elaboration of the last point.

This is mostly a pragmatic claim, based on the fact that if you can understand why a program works, then it's unlikely that the reason is  some vast invariant millions of pages long. (The longest invariants I've used are a few pages long, and boy do they make the reviewers grumble! Understandably so, too, since the invariant is the reason the program works stripped of all the narrative that helps people understand it.)

But there are also some theoretical reasons, as well. Basically, we don't know very many ways to systematically invent programs whose correctness proofs are very long. The main method is to (1) take the logic in which you prove correctness, (2) find a property which can't be directly expressed in that logic (consistency proofs are the typical source), and (3) find a program whose correctness proof relies on a family of expressible consequences of the inexpressible property. Because (2) is inexpressible, this means that the proof of each expressible consequence must be done independently, which lets you blow up the size of the correctness proof. As a simple example, note that in first-order logic with a parent relation, you can't express the ancestor relation. But $k$-ancestry (ancestry of depth $k$) is expressible, for each fixed $k$. So by giving a program that uses some property of ancestry up to some depth (say, 100), you can force a correctness proof in FOL to contain proofs of those properties a hundred times over.

The sophisticated take on this subject is called "reverse mathematics", and is the study of which axioms are required to prove given theorems. I don't know that much about it, but if you post a question on its application to CS, and I'm sure at least Timothy Chow, and probably several other people,  will be able to tell you interesting things.


On the class of the FNP version of the Hamiltonian Cycle problem

The FNP version of an NP-complete language $L$ asks to solve the following problem on every input $x$:

1) If $x \not\in L$, output "NO".

2) If $x \in L$, output some witness "w" such that a polynomial-time entity, given $(x,w)$, can verify that $x \in L$.

Consider the transformation $T$ of the above scheme: If the FNP machine answered "NO", $T$ answers "NO". Otherwise, $T$ answers "YES".

Obviously $T$ is a Karp-reduction of any NP-complete problem to the corresponding FNP-complete instance.


Strong seeded randomness extractors with low entropy loss

I'm not sure if this is what you are looking for, but as I recall, there is a mathematical proof that AMLS (advanced multi-level strategy) is maximal. This document does not contain the proof, but an outline of it is on page 9: Coin Toss

As a practical example, I seed AMLS with timer output to update a hashed accumulator used for seeding a reference PRNG, whose output I then use for research. The output of the seed accumulator does very well on randomness tests on its own, but it is very slow.


Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

The problem does not have a polynomial kernel unless NP is in coNP/poly. The cross-composition technique from our paper applies in a nontrivial way.

Let me show how the classic Vertex Cover problem OR-cross-composes into the k-FLIP-SAT problem; by the results in the cited paper, this is sufficient. Concretely, we build a polynomial-time algorithm whose input is a sequence of Vertex Cover instances $(G_1,k), (G_2, k), \ldots, (G_t, k)$ that all share the same value of $k$ and all have exactly $n$ vertices. The output is an instance of $k$-FLIP SAT with a parameter value of $O(k + \log t)$, which is sufficiently small for a cross-composition, such that the $k$-FLIP SAT instance has answer yes iff one of the input graphs has a vertex cover of size $k$. By duplicating one input (which does not change the value of the OR) we can ensure that the number of inputs $t$ is a power of two.

The composition proceeds as follows. Number the vertices in graph each input graph $G_i$ as $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$. Make a corresponding variable in the FLIP-SAT instance for each vertex of each input graph. Additionally, make a selector variable $u_i$ for each input instance number $i \in [t]$. For each input graph $G_i$, we add some clauses to the formula. For each edge $\{v_{i,x}, v_{i,y}\}$ of graph $G_i$, add the clause $(v_{i,x} \vee v_{i,y} \vee \neg u_i)$ to the formula, which will encode "either one of the endpoints of this edge is set to true, or the instance $i$ is not active". In the initial assignment, all vertex-variables are set to false and all selector variables $u_i$ are set to false, so that these clauses are all satisfied. To build the OR-behavior into the composition we will augment the formula to ensure that a satisfying assignment sets at least one selector to true, and must then also form a vertex cover of the selected graph.

To make sure we can do this selection while keeping the flip distance small compared to the number of inputs $t$, we use the structure of a complete binary tree with $t$ leaves, which has height $\log t$. Number the leaves from $1$ to $t$ and associate the $i$-th leaf with the variable $u_i$ that controls if input $i$ is active or not. Create a new variable for each internal node of the binary tree. For each internal node, let its corresponding variable be $x$ and the variables of its two children be $y$ and $z$. Add the clause $(\neg x \vee y \vee z)$ to the formula which captures the implication $(x \rightarrow (y \vee z))$, enforcing that $x$ can only be true if one of its children is true. To complete the formula, add a singleton clause saying that the variable of the root node of the binary tree must be true. In the initial truth assignment, the values of all variables for internal nodes is set to false, which satisfies all clauses of the formula except for the singleton clause requiring the root node of the tree to have its variable true.

This completes the description of the formula and truth assignment. Set the parameter $k'$ of the FLIP DISTANCE problem to be equal to $(k + \log t + 1)$, which is suitably bounded for a cross-composition. It remains to show that we can flip $k'$ variables to make the formula true iff some input graph $G_i$ has a vertex cover of size $k$.

In the reverse direction, suppose that $G_i$ has a size-$k$ vertex cover. Set the $k$ variables corresponding to the $k$ vertices in the cover to true by flipping them. Set the selector variable $u_i$ to true to encode that input $i$ is activated, and flip the variables of the $\log t$ internal binary tree nodes on the path of leaf $i$ to the root to true. It is easy to verify that this is a satisfying assignment: the implications in the binary tree are all satisfied, the root node's value is set to true, the clauses that check edges of $G_{i'}$ for $i' \neq i$ remain satisfied because $u_{i'}$ remains false, while the clauses for graph $G_i$ are satisfied because for every edge we set at least one endpoint to true.

For the forward direction, suppose that the formula can be satisfied by flipping at most $k + \log t + 1$ variables. Then we must flip the variable of the root node to true. The implications in the binary tree enforce that at least one selector variable of a leaf is set to true, say $u_i$. To satisfy the implications encoded in the binary tree, all internal nodes on the path from $u_i$ to the root were set to true, accounting for $1 + \log t$ flips. Since $u_i$ is set to true, the clauses made for graph $G_i$ are not satisfied on the literal $\neg u_i$, so they are satisfied because one of the endpoints of each edge of $G_i$ is set to true. Since at least $1 + \log t$ variables of the binary tree were flipped, at most $k$ vertex-variables are flipped to true in this solution. This encodes a vertex cover of size $k$ in $G_i$ and proves that one of the inputs is a YES-instance. This completes the proof.


We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.

Here are some basic results for this:

Case 1: $k=2^{n-1}-\mathrm{poly}(n)$

Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\phi$ on $m$ arbitrary inputs (e.g. the lexicographically first $m$ inputs). Suppose $\ell$ of these inputs satisfy $\phi$. Then we know $a \geq \ell$ as there are at least $\ell$ satisfying assignments and $a \leq 2^n - (m-\ell)$ as there are at least $m-\ell$ unsatisfying assignments. The length of this interval is $2^n - (m-\ell) - \ell = 2k$. So if we output the midpoint $2^{n-1} -m/2 + \ell$ this is within $k$ of the correct answer, as required.

Case 2: $k=2^n/\mathrm{poly}(n)$

Here we have a randomized poly-time algorithm: Evaluate $\phi$ at $m$ random points $X_1, \cdots, X_m \in \{0,1\}^n$. Let $\alpha = \frac{1}{m} \sum_{i=1}^m \phi(X_i)$ and $\varepsilon = k/2^n$. We output $2^n \cdot \alpha$. For this to have error at most $k$ we need $$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$$ which is equivalent to $|\alpha - a/2^n| \leq \varepsilon.$ By a Chernoff bound, $$\mathbb{P}[|\alpha - a/2^n| > \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$$ as $\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$.
This implies that, if we choose $m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (and ensure $m$ is a power of $2$), then with probability at least $0.99$, the error is at most $k$.

Case 3: $k=2^{cn + o(n)}$ for $c < 1$

In this case the problem is #P-hard: We will do a reduction from #3SAT. Take a 3CNF $\psi$ on $m$ variables. Pick $n \geq m$ such that $k < 2^{n-m-1}$ -- this requires $n = O(m/(1-c))$. Let $\phi=\psi$ except $\phi$ is now on $n$ variables, rather than $m$. If $\psi$ has $b$ satisfying assignments, then $\phi$ has $b \cdot 2^{n-m}$ satisfying assignments, as the $n-m$ "free" variables can take any value in a satisfying assignment. Now suppose we have $\hat{a}$ such that $|\hat{a}-a| \leq k$ -- that is $\hat{a}$ is an approximation to the number of satisfying assignments of $\phi$ with additive error $k$. Then $$|b-\hat{a}/2^{n-m}| = \left| \frac{a - \hat{a}}{2^{n-m}}\right| \leq \frac{k}{2^{n-m}} < 1/2.$$
Since $b$ is an integer, this means we can determine the exact value of $b$ from $\hat{a}$. Algorithmically determining the exact value of $b$ entails solving the #P-complete problem #3SAT. This means that it is #P-hard to compute $\hat{a}$.


Here's a collection of some of the responses of problems between P and NPC:

Factoring
Isomorphism problems: Graph Isomorphism [not NPC unless $\sum_2^p=\prod_2^p$] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, Ring Isomorphism and Automorphism (via @Joshua Grochow)
Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)
The Turnpike Problem of reconstructing points on line from distances (via @Suresh Venkat)
Problems arising from the Unique Games Conjecture (via @Moritz)
Discrete Log Problem and others related to cryptographic assumptions (via @Joe Fitzsimons)
Determining winner in parity games (via @mashca)
Determining who has the highest chance of winning a stochastic game (via @Peter Shor on MO)
Numbers in boxes problems (via @Joshua Grochow)
Agenda control for balanced single-elimination tournaments (via @virgi)
Knot triviality (via @JeffE)
(Assuming NEXP≠EXP) padded versions of NEXP-complete problems (via @Joshua Grochow)
Problems in TFNP (via @Marcos Villagra)
Intersecting Monotone SAT (via @András Salamon)
Minimum Circuit Size Problem (via @Eric Allender)
Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)
The Cutting Stock Problem with a constant number of object lengths (via @Suresh Venkat)
Monotone Self-Duality (via @Danu)
Planar Minimum Bisection (via @turkistany)
Pigeonhole Subset Sum (via @user834)
Square Root Sums (via @JeffE)
Deciding Whether a Graph Admits a Graceful Labeling (via @Oleksandr Bondarenko)
Gap version of the closest vector in lattice problem GapCVP$(\sqrt{n})$ (via @MCH)
The linear divisibility problem [known to be $\gamma$-complete but not NPC] (via @Oleksandr Bondarenko)
Finding the VC dimension (via @Mohammad al Turkistany)
Finding the minimum dominating set in a tournament (via @Mohammad al Turkistany)


Lower bounds for learning in the membership query and counterexample model

Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time.  There is a whole paper developing such hardness results using something called the "representation problem".

To answer your linked-to question: Schapire, in his dissertation, in addition to proving that "weak learning" = "strong learning," also improved on Angluin's bound and gave an algorithm that uses $O(n)$ equivalence queries and $O(n^2+ n \log m)$ membership queries for learning DFA.

One easy way to get lower bounds is information-theory.  You can figure out how many distinct targets there are and how many bits a query gives you, etc.  These upper bounds come close but aren't there.  There are also issues one needs to think about regarding how the "counterexamples" arrive to the learner.  A well-chosen counterexample can give away quite a lot of information.

Update to the discussion above: Angluin and Dohrn address the question learning with random counterexamples in a recent paper.


Is there a Boolean formula that is resistant to bias from a polytime adversary?

There does not exist such a family of circuits. Assume to the contrary that $\{\phi_k\}_{k \in \mathbb N}$ was such a family.

We will now show the strategy that achieves bias at least $\frac{1}{20k}$ for $k$ big enough, by referring to Impagliazzo's Theorem 4.7.2 on page 71 of http://cseweb.ucsd.edu/~russell/format.ps :

Let $\mathcal A$ be the strategy that:

1) Picks a bit string uniformly from $x \in \{0,1\}^k$, and picks a number $ i \in \{0,\ldots,2k-1\}$ uniformly. Now, $i = 2j+b$, for $b \in \{0,1\}$ for an unique $j$ and $b$.

2) $\mathcal A$ should send the first $j$ messages in correspondance with the first $j$ coordinates of $x$.

3) If $b=0$ Then $\mathcal A$ should wait for answer from the other party. Otherwise, it should just proceed:

4) $\mathcal A$ picks a new bit string $(x'_{j+1}, \ldots x'_k) \in \{ 0,1 \}^{k-j}$ uniformly, and then calculate 2 estimates of the Expected value of $\phi$, calculated by making polynomially many uniform samples from $\{0,1\}^{k-j-b}$ corresponding to the remaining conversation of the honest party:

$E_1$ : Estimate of expected value where preceding conversation is fixed, and  $(x_{j+1}, \ldots x_k)$ is fixed.
$E_2$ : Estimate of expected value where preceding conversation is fixed, and  $(x'_{j+1}, \ldots x'_k)$ is fixed.

5) The bit string corresponding to the highest expected value, is used for the rest of the conversation.

If assuming perfect estimation of expected value, we achieve at least $\frac{1}{16k}$ bias, and since there is some (exponentially decreasing error) caused by the estimation (which can be bounded by additive Chernoff-Hoeffding bound), we just say a bias of at least $\frac{1}{20k}$ for $k$ big enough.

For now, I will just refer to Impagliazzo's proof for the analysis. It is not the easiest proof to read, if one is not used to his style of writing, but it is correct, and I can explain specific details, if anybody have interest.


How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?

Update: The description below is for a different problem (in which you have all pairwise distances in a set rather than pairwise distances between two distinct sets). I'll leave it up anyway since it is closely related.

This problem is called the beltway problem, and is a special case of the general $d$-torus embedding problem. It is also closely related to the turnpike problem, in which the distances differences are absolute (not modulo some number).

It is not known whether the beltway problem admits a poly-time algorithm. There are various pseudo-poly-time algorithms for related questions. The best reference (alas an old one) is the paper by Lemke, Skiena and Smith.


Commonality of minimal Kolmogorov structure functions

Lemma 1 below shows that with a standard TM encoding, the fraction of strings that are MKSSs is bounded away from both 0 and 1. This answered a question posed in the original post.

Lemma 2 shows that there is a (non-standard) encoding in which almost all strings are MKSSs.  This answers the question in the current post affirmatively.

Lemma 3 shows that there is a (non-standard) encoding in which almost no strings are MKSSs.

Let $\mu(n)$ be the probability that a random string of length $n$ or less is a minimal Kolmogorov structure function, as defined in your previous post.

Lemma 1. For any conventional TM encoding scheme,
$$0 < \liminf_{n\rightarrow\infty} \mu(n) < 1$$

Proof. First we show that $\liminf_{n\rightarrow\infty} \mu(n) < 1$.  For any string $B$, let $P^*_B$ be an MKSS for $B$.  Define $P'_B$ to be the TM obtained from $P^*_B$ by adding a useless state.  Then $|P'_B| \le |P^*_B|+c$ for some fixed constant $c$, and $P'_B$ is not an MKSS.  It follows that, for every $n$, for every string of size at most $n$ that is an MKSS, there is a string of size at most $n+c$ that is not an MKSS.  Hence, among the strings of length at most $n+c$, the number that are not an MKSS is at least the number of strings of length at most $n$ that are an MKSS.  It follows that $1-\mu(n+c) \ge \mu(n)/c'$ for $c'\approx 2^c$.  It follows that $\liminf_{n\rightarrow\infty} \mu(n) \le 1-1/(c'+1) < 1$.

Next we show that $\liminf_{n\rightarrow\infty} \mu(n) > 0$.  For any string $B$, we have that $P^*_B$ is an MKSS, and $$|P^*_B| \le K(B) \le |B| + c_1$$ for some fixed constant $c_1$.  So, for every $n$, the number of strings of length at most $n+c_1$ that are an MKSS is at least the number of strings of length at most $n$.  It follows that $\mu(n+c_1) \ge 1/c_2$ where $c_2\approx 2^{c_2}$. It follows that $\liminf_{n\rightarrow\infty} \mu(n) \ge 1/c_2 > 0$.  $~~\Box$

Next we show that using non-standard TM encoding schemes we can make almost all strings MKSSs.  Fix arbitrarily large constant $k\ge 0$. Given a binary string $B$, if $B=1^kM$ ($k$ ones followed by some string $M$) then $B$ encodes the TM whose standard encoding is $M$.  Otherwise, $B$ encodes a TM that outputs $B$.  (This is a TM encoding scheme in the sense that there is a computable function mapping standard encodings to equivalent non-standard encodings, and vice versa.)

Lemma 2. For this TM encoding scheme, for any $n$, if $B$ is a random string of length at most $n$, then $B$ is an MKSS with probability at least $1-O(1/2^k)$.

Proof.
Let $K'(B)$ and $P'_B$ denote the Kolmogorov complexity and MKSS of $B$ with respect to this non-standard TM encoding scheme.
Let $K(B)$ denote the Kolmogorov complexity of $B$ with respect to the standard TM encoding scheme.
Say that a string $B$ is good if $B$ isn't of the form $1^k M$ for some $M$, and $K(B) \ge |B|-k$.

Consider any good string $B$.  Since $B$ isn't of the form $1^kM$, one (non-standard) encoding of a TM that outputs $B$ is $B$ itself. Further, any other encoding, say $P$ (with this encoding scheme), of a TM that outputs $B$ must be of the form $1^k M$, where $M$ is the standard encoding of a TM that outputs $B$.  Any such encoding $P$ has length at least $K(B)+k \ge |B|$.  Hence, $K'(B) = |B|$.

$B$ has an encoding (namely $B$) of size $K'(B)$ that outputs a set of size 1 containing $B$, so the MKSS $P'_B$ for $B$ has size $|P'_B| \le |B|$.

Now, fix any $n$, and consider any length-$n$ good string $B$ such that $B$ is not an MKSS.  Hence, $|P'_B| < |B|=n$ and $P'_B = 1^k M$ for some standard encoding $M$ such that, on input $n$, $M$ outputs a set $S_B$ containing $B$ such that
$$k+|M| +\log|S_B| = |P'_B| + \log |S_B| \le K'(B) = |B| = n.$$
It follows that $|M|+\log|S_B| \le n - k$.

Now, composing $M$ and the index of $B$ in $S_B$, there exists a TM with standard encoding $M'$ that, on input $n$, outputs $B$, and such that
$$|M'| = |M| + \log |S_B| + O(1) \le n-k+O(1).$$

Since $M'$ uniquely determines $B$ (among strings of length $n$), it follows that there are at most $2^{n-k+O(1)}$ good length-$n$ strings that are not MKSS's.

Now, among all $2^n$ length-$n$ strings $B$:

at most $2^{n-k}$ have $K(B) \le n-k$ (by the standard counting argument), and
at most $2^{n-k}$ have the form $1^k M$ for some $M$.

So, at least $2^n - 2^{n-k + 1}$ are good, and, among those,

at most $2^{n-k+O(1)}$ are not MKSS's (as shown above).

It follows that, for every $n$, among all $2^n$ length-$n$ strings, at least $$2^n - O(2^{n-k+O(1)}) = 2^n(1-O(1/2^k))$$ are MKSS's.  Hence, among all strings of length at most $n$, at least a fraction $1-O(1/2^k)$ are MKSS's. $~~\Box$

Just for fun, here is another non-standard encoding scheme in which almost all strings are not MKSS's.  Use the encoding scheme from Lemma 2, but augment it to make the empty string encode a TM that, on input $n$, outputs all strings of length $n$.

Lemma 3. With this modified encoding scheme, the probability that a random string of length $n$ or less is an MKSS is $O(1/2^k)$.

Proof. Following the proof above, among the strings of length $n$ or less, the fraction that are good is at least $1-O(1/2^k)$.  To finish we show that no good string is an MKSS. For any good string $B$, we have $K'(B)=|B|$.  The empty string $M$ encodes a TM that, on input $n=|B|$, outputs a set $S_B$ of size $2^n$ containing $B$.  Hence $|M| + \log |S_B| = 0 + n = |B| = K'(B)$.  Hence, the empty string is the MKSS for (any good) $B$, and $B$ is not an MKSS. $~~\Box$.


"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = EXP.

The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.


It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound in

"An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization", Vida Dujmovic, Sue Whitesides, Algorithmica 40:15–31, 2004.

Also, it's a lower bound rather than an upper bound, but:

"An $n^{1.618}$ lower bound on the time to simulate one queue or two pushdown stores by one tape", Paul M.B. Vitányi, Inf. Proc. Lett. 21:147–152, 1985.

Finally, the one I was trying to find when I ran across those other two: the ham sandwich tree, a now-obsolete data structure in computational geometry for triangular range queries, has query time $O(n^{\log_2\varphi})\approx O(n^{0.695})$. So the golden ratio is properly in the exponent, but with a log rather than as itself. The data structure is a hierarchical partition of the plane into convex cells, with the overall structure of a binary tree, where each cell and its sibling in the tree are partitioned with a ham sandwich cut. The query time is determined by the recurrence $Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$, which has the above solution. It's described (with a more boring name) by

"Halfplanar range search in linear space and $O(n^{0.695})$ query time", Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Lett. 23:289–293, 1986.


As far as I know, $\mathsf{NC^1}$ evaluation is not known to be in $\mathsf{NC^1}$, and is conjectured to be outside $\mathsf{NC^1}$. See

Emil Jerabek, "On theories of bounded arithmetic for $\mathsf{NC^1}$",  Ann. Pure Appl. Logic 2011


Your first question is answered in this paper: https://www.cs.cornell.edu/fbs/publications/RecSafeLive.pdf
Given an LTL formula, translate it into a Büchi automaton, and remove states that have no path to an accepting state. Then, change all states to be accepting. If the language of the automaton does not change, then the property is a safety property. If the language of the automaton becomes $\Sigma^\omega$, then it is a liveness property.


Subclasses or characterizations of modular or pseudo-modular planar graphs

The median graphs are a subclass of modular graphs with almost the same definition but where the vertex w is always unique. The squaregraphs (plane graphs in which all bounded faces are quadrilaterals and all vertices either have degree 4 or belong to the unbounded face) form a natural and interesting subclass of the planar median graphs. I believe that all planar median graphs can be constructed by gluing together cubes and squaregraphs, but I don't think this result has been published.


A good exposition of the random restriction method

A relatively simple setting to illustrate the method of random restrictions is Subbotovskaya's original application of the method to prove an $\Omega(n^{1.5})$ lower bound on the formula size of the parity function, where formulas use arity-2 AND and OR operations. Section 6.3. of Jukna's Boolean Function Complexity has a nice exposition. Also, see these lecture notes from Swastik Kopparty's class in Rutgers.


Counting complexity of a scheduling problem.

Edit: It seems that the questioner knew that this was an open problem: https://mathoverflow.net/questions/33796/existence-of-a-pseudo-polynomial-time-algorithm-for-a-counting-problem.  For what it is worth, it took me some time to find the paper, and I think that the time was wasted.

This question is stated as an open problem in [Ber09], where the same problem except that the numbers in the input are written in binary is shown to be #P-complete by a reduction from the counting version of the Subset Sum problem.

References

[Ber09] Gerardo Berbeglia.  The counting complexity of a simple scheduling problem.  Operations Research Letters, 37(5):365–367, Sept. 2009.  http://dx.doi.org/10.1016/j.orl.2009.05.004


What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes

I believe one core difference is that in CSP, processes synchronize when messages are received (i.e. a message cannot be sent from one process unless another process is in a receiving mode), while the Actor model is inherently asynchronous (i.e. messages are immediately sent to other processes' address, irrespective of whether they're actively waiting on a message or not).

There should be another answer that is more well-developed, however.


You're missing what resolution refutation works for -- namely, just propositional logic.

For example, try using that algorithm on "There exist integers x, y, z such that x3 + y3 + z3 = 33."

There are sets of axioms for which the set of theorems is decidable -- the real closed field axioms are the most important example of that, and they in fact also allow quantifier elimination.

There are sets of axioms for which the set of theorems is not decidable -- by undecidability of Diophantine equations, all Σ1-sound extensions of Robinson arithmetic are examples of that.


Have you considered Seidel's algorithm ?


Applications of association schemes to complexity theory and other TCS

One application that I know of is the connection between combinatorial designs (which are related to associative schemes) and coding theory. Delsarte's program in particular has lead to some interesting LP based bounds for codes. I don't know much about these but I remember that Alex Samorodnitsky has worked on these connections (for example, this, this, this and this). Perhaps some expert can shed more light on this.


0-1 Linear Programming: computing the Optimal Formulation

This seems to be NP-hard to do exactly, by reduction from subset sum. Suppose we had an efficient procedure to compute $O$. Given positive integers $v_1,\dots,v_n$ encoded in binary, we wish to test whether there is a subset summing to $s$. Preprocess by throwing out any integers larger than $s$.

Call the procedure to obtain a small set $O$ of points satisfying $v_1x_1+\dots+v_1x_n\leq s$, satisfying your minimality conditions (the preprocessing ensures $|S_c|\geq n$). This set will certainly contain a point on the hyperplane $v_1x_1+\dots+v_1x_n= s$ if there is one.


How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?

Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees.

(Apologies if the below is extra verbose -- you said that you're new to graph algorithms, and I want to make sure you can follow the reasoning.)

Your problem is a special case of the Santa Clause problem, and the (significantly) more general version that requires each vertex $v_i$ to have in-degree $\geq d_i$ can be solved using Max $s-t$ Flow as follows (your problem is the special case where each $d_i$ is exactly $1$, read up more on maximum flow here). Given an instance $G = (V,E)$ of your problem, we construct a new graph $G'$ with $|V| + |E| + 2$ vertices as follows:

A source node $s$
An edge layer consisting of one node $u_i$ for each $e_i \in E$
A vertex layer consisting of one node $w_i$ for each $v_i \in V$
An sink-node $t$

Further, we connect these nodes with (directed) arcs as follows

$s$ has an arc to each $u_i$ node, with capacity-$1$
Each $u_i$ node has an arc to both $w_j$ and $w_k$, where $v_j$ and $v_k$ are the endpoints of $e_i$ in $G$, again with capacity-$1$.
Each $w_i$ has an arc to $t$, with capacity $d_i$.

Here's an MSPaint diagram of the reduction on a particularly simple example. All drawn edges in $G_2$ are actually downward-oriented arcs.

The claim is that the max $s-t$ flow in this graph is $\sum_i d_i$ iff $G_1$'s edges can be directed so that the min in-degree is $\geq d_i$. Additionally, when the problem is solvable, the optimal solution will be easy to extract*.

The analysis is as follows. The graph has integer weights, so w.l.o.g. we can consider only integer-valued $s-t$ flows (this is called the Integral Flow Theorem). Additionally, the weights on the edges between the $\{w_i\}$ and $t$ ensure that the only way we can get $\sum_i d_i$ units of flow to $t$ is by first getting at least $d_i$ units of flow to each $w_i$. How does flow get to the $\{w_i\}$ nodes? It must originate at the $\{u_j\}$ nodes, which correspond to edges of $G$. Because each $\{u_j\}$ is only getting (at most) $1$ unit of flow from $s$, each $u_j$ gets to pick at most one of its two out-neighbors to send its flow to.

Thus, the interpretation of this flow problem construction is that each edge-node gets to pick at most one vertex-node that can get its unit of flow, and each vertex node $w_j$ must be chosen at least $d_j$ times. This is just like your problem, where we have an edge $e_i$ direct itself towards a vertex $v_j$ (in $G_1)$ if $u_i$ sends a unit of flow to $w_j$ (in $G_2$). In particular, the set of utilized arcs between $\{u_i\}$ and $\{w_j\}$ will tell you exactly how to orient some subset of the edges so that every vertex $v_j$ has at least $d_j$ in-edges. The rest, of course, can be oriented arbitrarily.

* Actually, this construction solves a more general problem, in which we want to maximize the number of vertices with at least $d_i$ in-edges.


Well, split graphs correspond to the case where $V_1$ is an independent set and $V_2$ forms a clique, but I'm not aware of another name in the case where $V_2$ has no particular restriction.


It seems your problem is in $NL$. Here is an algorithm.
First, nondeterministically guess a path from $s$ to $t$. If you guess incorrectly, reject. Call this algorithm $A$.
Consider the following nondeterministic algorithm $B$, which determines if there are at least two paths. Given a graph and $s,t$, for all pairs of distinct edges $e,f$, guess a path from $s$ to $t$ that includes $e$ but not $f$, then guess a path from $s$ to $t$ that includes $f$ but not $e$. If the guesses are correct, accept. If no acceptance occurs for all choices of $e$ and $f$, reject. Note $B$ is implementable in nondeterministic logspace.
Now, the set $L(B)$ is the set of $s$-$t$ graphs with at least two paths from $s$ to $t$. Because $NL = coNL$, the complement of $B$ is also in $NL$, i.e., we can determine if $s$ and $t$ have less than two paths, in nondeterministic logspace.
The final algorithm is: "Run $A$. If $A$ accepts, then run the complement of $B$ and output its answer."
I don't know of a reference.
UPDATE: If you really want a reference, check out the first paragraph of Section 3 of this paper. But this is probably only one of many references that cite this consequence. It would be more reasonable to call the result "folklore" rather than citing a paper that happens to mention it.
UPDATE 2: Let's suppose you want to determine if there is a unique simple path. In that case, algorithm $A$ doesn't have to change: if there is a path at all then there is a simple path. I believe the following modification will work for algorithm $B$.
We want to rewrite algorithm $B$ so that it accepts iff there are at least two simple paths.
First consider the following polynomial-time algorithm for the problem. Find a shortest path $P$ from $s$ to $t$. For every edge $e$ in $P$, check if there is another $s$-$t$ path that does not go through $e$. If you find such a path then accept. If you never find another path then reject. Because $P$ is shortest, it does not have a cycle, and if there is another path that doesn't use some edge of $P$, then there is another path which is simple and doesn't use some edge of $P$. (This algorithm is used for the "second shortest paths" problem.)
We will implement this algorithm in $NL$. If we had an $NL$ algorithm for querying the edges $e$ in a fixed path $P$, we could implement the above in nondeterministic logspace: iterating through all edges $e$ in $P$, guess an $s$-$t$ path and check that for every edge visited along the way, none of them are equal to $e$.
So what we need is a "path oracle", an $NL$ algorithm with the property: given $i=1,\ldots,n$, in every computation path the algorithm either reports the $i$th edge on a particular fixed $s$-$t$ path, or reject. We can get a path oracle by using $NL=coNL$ to isolate the lexicographically first path.
Here is a sketch of the path oracle.

Find $k$, the length of the shortest path from $s$ to $t$, by trying all $k=1,\ldots,n$ and using $NL=coNL$.
Set variables $u:=s$, $x:=1$, $j:=k$.
For all neighbors $v$ of $u$ in lexicographical order,
Determine whether or not there is a path from $v$ to $t$ of length $j-1$ (using the result $NL=coNL$).
More precisely, run the nondeterministic algorithm for $s$-$t$ connectivity (of length $j-1$) and the algorithm for its complement, simultaneously. When one of them accepts, go with its answer (it must be correct; both cannot accept). If both reject then reject.
If there is no path, proceed to the next neighbor. If you've exhausted all neighbors then reject.
If there is a path, then if $x=i$, output $(u,v)$ as the $i$th edge on the path from $s$ to $t$. Otherwise increment $x$, decrement $j$, set $u := v$, and start the for-loop again if $v \neq t$.
If $x < i$ after reaching $t$ output bad $i$ (the given $i$ was too big).

Given $i$, this algorithm either outputs the $i$th edge on the lexicographically shortest path $P$ from $s$ to $t$, or rejects.


Conceptually simple linear-time suffix tree constructions

I'm not sure if there were any new results directly simplifying the construction of suffix trees. However, there has been at least one result giving a very simple algorithm for constructing suffix arrays in linear time.

Note that there's more than a conceptual equivalence between these two data structures, since you can use a suffix array (with $\cal{O}(1)$ time for querying the longest common prefix) to build an equivalent suffix tree. This should be a relatively simple exercise, but I can give more details if required.

Also, for practical purposes it's even easier to build suffix arrays in $\cal{O}(n \lg n)$ time, but I guess I'm going slightly off-topic here.


Its not clear what you want to estimate, or what you mean by looking at a random cut. But it is hard to learn much about a graph by just observing the size of a random cut. This is because a random cut will always cut $m/2$ edges in expectation (where $m$ is the number of edges in the graph), independent of the structure of the graph. Of course, the entire graph can be thought of as a vector of length ${n \choose 2}$, so if you get to observe the -exact- size of that many random cuts, because they are likely to be linearly independent, you can reconstruct the graph. There's nothing special about cuts here: you're just observing the exact value of the dotproduct of $d$ linearly independent vectors with an unknown vector of length $d$, and this system of linear equations will have an exact solution.


DAG reachability with O(n log n) space and O(log n)-time queries?

See "interval labeling" and "2-hop labeling" which are apparently quite efficient in practice, both in time and space, and may give you what you want. In general there's quite a bunch of "reachability indexing" schemes for DAGs.


Is there a method of solving the game of "war"

I've been working on war for the past couple of days.

In particular I've been interested in the longest possible game, given no cycles. By backtracking, starting from the end position, I managed to avoid anything that goes into cycles. I used a dynamic greater-than relation to avoid having to decide what cards had what value from the start.

Even with those optimizations, I've only managed to create the following table, where the left column is the number of cards in play, and the right column is the length of the longest possible game:

1   0       13  62
2   1       14  467
3   3       15  85
4   7       16  261
5   9       17  107
6   17      18  >=935
7   17      19  137
8   29      21  168
9   31      23  209
10  53
11  45
12  79

Interestingly I found, that odd number of cards, give a much larger chance of cycles. This makes it much easier to find the longest game, as there are far fewer positions to consider. The maximum length of these games is ery close to a second order polynomial.


What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Even, Selman, and Yacobi conjectured that there does not exist a disjoint $NP$-pair $(A, B)$ such that all separators of $(A, B)$ are $ \le_T^p $-hard for $NP$. This conjecture implies that $UP \ne NP$.

S. Even, A. Selman, and J. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:159–173, 1984.


MSO properties, planar graphs and minor-free graphs

Being 4-colorable?  Certainly MSO, and trivial on planar graphs.  It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.


I don't think they are polynomially related. Consider the OR function on n bits. There is a polynomial $p(x) = \frac{1}{n} (x_1 + x_2 + \ldots + x_n)$, which approximates it with one sided error $\epsilon = 1- \frac{1}{n}$ because on the all zero input the polynomial is zero, and on any other input its value is between $\frac{1}{n}$ and 1.

However any polynomial approximating the OR function to one sided error $\epsilon/2$ (which is approximately $1/2$) is a bounded-error approximation of OR which is known to require degree $\Omega(\sqrt{n})$.


Generating graph for random walk given hitting time distribution

There are lots of different kinds of random walks (discrete vs continuous, weighted vs constant, classical vs quantum) so the exact approach will differ some what in each case, but I will attempt to outline a fairly general approach here.

Usually the evolution of that system will be given by $A^t$ for some matrix $A$, where $t$ is time. The exact nature of $A$ will depend on the type of random walk you have in mind, but in any case, we expect the system to be in a state $A^t v$ after time $t$, where $v$ denotes the starting state. The question then becomes: given a set of hitting times $\{t_i\}$, corresponding states $\{u_i\}$, and hitting overlaps $\{p_i\}$, can we find some matrix $A$ which satisfies $u_i^\dagger A^{t_i} v = p_i$ for all $i$? Certainly this will not always be the case (since we could have conflicts where orthogonal states are required at the same time), so I assume you are really interested in how to find $A$ when there does exist an $A$ satisfying these relations.

EDIT: My previous answer was incorrect beyond this point, so I have replaced that portion.

I am not 100% sure of the most efficient way to find $A$. You have a system of equations in the enteries of $A$, and these can obviously be solved numerically using, for example, Buchberger's algorithm. However, this approach is not computationally efficient, and there may exist a more straight forward approach.

If you simply want find a transition matrix which approximates this, then you can use any number of optimization strategies, though these too may be inefficient.

Note, here I have assumed a very general model which should be true for all random walks, but it makes it hard to say anything concrete about how hard long it will take to numerically find a solution. If you have more information (i.e. is this a discrete time walk? Is it classical (I assume so)? Are weighted transitions probabilities allowed or do they have to be constant? Is this associates with some lattice (1d, 2d, or an arbitrary graph)?) Then you can possibly do much better. In the worst case, though, this problem seems to be NP-hard (since you get an integer programming problem if you restrict the transition probabilities to be multiples of some constant).


What is the Quantum Cheshire Cat experiments' import to Quantum Computing?

The quantum Cheshire Cat experiments appear to require postselection even to exhibit. Of course, postselection is itself a computational resource (and an extremely powerful one!) for "bounded" error quantum computation, and one whose power is characterised. To wit: the class PostBQP of decision problems decideable with bounded error using poly-size quantum circuits, conditioning on some single bit having the value 1 (provided that this occurs with non-zero probability) is precisely the class PP. (Recall also that PP contains NP as a subset.)

Perhaps one might ask whether quantum Cheshire cats might somehow represent a useful idiom in the design of  PP algorithms for difficult problems. Alternatively, perhaps quantum Cheshire cats correspond to some intriguing feature of quantum mechanics that can be described without resorting to (anything equivalent to) postselection, and which has implications for quantum computation. However, it isn't obvious at the moment that either of these are the case.


Typing of substitution in a bidirectional type system

One solution is indeed to restrict to substituting with synthesizing expressions. You can only hope to replace variables with terms of the same mode (i.e. inferrable terms), anything else just won't fit. It is not that restrictive in the sense that usually a checkable term together with a type annotation gives you an inferrable term. This embedding is typically called cut because well... this is what it is. This restriction is described (and deployed) in I Got Plenty o’ Nuttin’.

Alternatively (which is also mentioned in IGPoN) you can define hereditary substitution (a formalised account for STLC) whereby if you are about to form a redex because of the checkable you just plugged in, you fire it. And again. And again. And again. Until your substitution is not creating any new redexes.


Commutative matrix multiplication algorithms

In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is equivalent to the existence of an $O(n^c)$ commutative algorithm for matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit computing a bilinear map can be converted into a bilinear circuit at the expense of at most a factor of 2 in the size.


Lower bounds and impossibility results for distributed transactions

The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible.

To this end, it first decomposes SI into four properties:

  Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$

where,

$ACA$: avoiding cascading aborts; $SCONS = SCONSa \cap SCONSb$: strictly consistent snapshots; $MON$: snapshot monotonicity; and $WCF$: write-conflict freedom.

Then, it gives the following

  Impossibility theorem: None of SCONSa, SCONSb, and MON  is attainable in some asynchronous failure-free GPR system with obstruction-free updates (OFU) and wait-free queries (WFQ).

[1] Non-Monotonic Snapshot Isolation by Masoud Saeida et al@arXiv'2013


Cryptography protocols using graph problem instances

Number theory (along with neighboring "algebraic" areas like lattices and group theory) gets used for public-key crypto because the problems for which we know distributions on instances that (a) are hard and (b) have trapdoors are most naturally stated algebraically. This stands in contrast to the symmetric key setting: a much wider range of natural candidates for one-way functions (which don't require trapdoors) exist.

I imagine one can turn algebraic problems into graph-theoretic ones via the reductions which prove NP-completeness. But those transformations just make the representations more cumbersome -- they don't obviously provide any security advantages.

The eprint paper linked to by Sasho Nikolov in the comments is a good place to look for one of the very few combinatorial alternatives.


How does inheritance differ from subtyping?

[I haven't thought deeply about the issues of object-oriented type systems, but I will say what I know to get the discussion going.]

We say that $A$ is a subtype of $B$ if all $A$-typed values can be used in every context where $B$-typed values are expected.  Or, to put another way, $A$-typed values can "masquerade" as $B$-typed values.

If such masquerading poses no issues with type checking, i.e., plugging in $A$-typed values where $B$-typed values are needed continues to type check, we call it "structural subtyping".  If it cause no issues with behaviour, i.e., such plugging does not alter the behaviour expected, then we call it "behavioural subtyping".  (The "behaviour expected" will have to be formalised separately and many notions of behaviour are possible.)

Structural subtyping does not ensure behavioural subtyping because the structure of a type might match for accidental reasons.  However, defining the behaviour expected is not easy.  So, many programming languages use an intermediate point, where the user has to declare which type is a subtype of which.  This is referred to as "nominal subtyping".  See the question on Implicit vs explicit subtyping for a discussion of this issue.  The idea is that the programmer has to ensure behavioural subtyping for all declared subtypes using his own ingenuity.  The language cannot offer any help.  However, all declared subtypes must be at least structural subtypes.  Otherwise, the program would fail to type check.  The language can help ensure this.  (Some programming languages don't have good enough type systems to ensure this at compile-time.  If so, the type failure would be detected at run-time, or perhaps wrong results might be produced.  Such type holes are obviously undesirable.)

When one defines subclasses in object oriented programs, one typically adds publicly visible fields (or methods).  In most programming languages, such subclasses are regarded as nominal subtypes.  The question is whether they are also structural subtypes.  If they are not, i.e., the programming language allows one to declare nominal subtypes that are not structural subtypes, then there would be type holes in the programming language.

In simple cases, adding fields works fine.  The type of the superclass expects fewer fields than the type of the subclass.  So, if you plug in an instance of a subclass where an instance of the sueprclass is expected, the program will just ignore the additional fields provided and nothing goes wrong.

However, if the superclass or subclass has methods that take arguments of the same type as itself, or return results of the same type as itself, then problems arise.  Then the interface type of the subclass is not a structural subtype of that of the superclass.  Widely used type-safe programming languages such as Java do not allow such subclasses.  So, they restrict the language to obtain type safety.  The programming language Eiffel is said to have sacrificed type-safety to obtain flexibility instead.  If one designs a strong type system that retains flexibility, one must give up the principle that subclasses give rise to subtypes.  Hence the title of the paper "Inheritance is not subtyping".  The authors propose a different notion of higher-order subtyping which works instead.  Kim Bruce also has a closely related proposal called "matching" that achieves the same effect.  See this presentation.  Also helpful is a position paper of Andrew Black.

The semantics community is probably at fault for largely ignoring the problem.  We have traditionally regarded it as a practical type-system engineering issue that is of little theoretical interest.  If that is not the case and there is indeed some semantics work in the area, I hope the other people will mention them.


Strongly NP-complete variants of subset sum or partition problem

It's like cheating, but if you change the representation of the numbers in the input then the problem becomes strongly NPC:

SUBSET SUM OF FACTORIZED SEMIPRIMES "SUBSUMS"

Input: A list of $N+1$ integers: $q_0$ and $A = \{q_1, ..., q_N\}$ each one represented as a (sub)sum of factorized (semiprime) integers; i.e. $q_i$ is given as $p_{i,1} 2^{a_{i,1}} + ... + p_{i,m_i} 2^{a_{i,m_i}}$ where $p_{i,j} \geq 3$ is a prime and $a_{i,j}$ is its "shift" exponent (in other words the input is the list of integers $p_{1,1}, a_{1,1}, p_{1,2}, a_{1,2},  ..., p_{2,1}, a_{2,1}, p_{2,2}, a_{2,2}, ...$)

Output: Does there exist a subset of $A' \subseteq A$  such that $\sum_{q \in A'} q = q_0 $?

Easy reduction from the strongly NPC problem $X3C$.


Open or Interactive Constraint Satisfaction

I'm not altogether convinced by the previous work on open and interactive constraints.

An attempt to study the tractability questions was:

Martin J. Green and Christopher Jefferson, Structural Tractability of Propagated Constraints, CP 2008.
doi: 10.1007/978-3-540-85958-1_25

although this paper does leave several major questions unanswered.  The approach via propagators in this paper is closely related to existing constraint solver implementations.

I think work on SMT (satisfiability modulo theories) is also closely related to your question.  SMT theories are often motivated by problems from software and hardware verification, but there do exist theories with an AI flavour.  I look forward to more applications built with SMT as the core technology, and to more work in constraints applying ideas from SMT.


Counting reduction from #SAT to #HornSAT?

This post discusses #P-completeness of #Monotone-2SAT under weakly parsimonious reductions. If you negate all literals in a monotone 2-CNF formula $\phi$, you obtain a Horn 2-CNF formula $\psi$ with the same number of satisfying assignments.


Find a function that combines a set of integers and outputs an integer. This output can be used to deduce the absence of any integer in the set.

Well, is it only one missing event you want to detect? It you need to be able to detect the presence or absence of all 50 events, this means distinguishing between $2^{50}$ possibilities which obviously cannot be done with 32 bits. However if you wish to just detect a single missing event, here is a way that will work. Assume you have m events.

Assign each event a sequential number starting at 2.
Calculate $c = (m+1)! \mbox{mod}~p$, where p is some prime number greater than m+1 but less than $2^{32}$.
When registering the events, simply multiply the numbers corresponding to the events sequentially modulo p. Call this result r.
To determine if an event is missing, calculate $x = (c \times r^{-1}) \mbox{mod}~p$. If $x=1$ then no events are missing, otherwise $x$ is the label for the missing event.

UPDATE

A simpler solution (coming from Jukka's comment) is simply to do the following:

Assign each event a sequential number starting at 1.
Calculate $c = \sum_{j=1}^m j~ \mbox{mod}~2^{32} = \frac{j(j+1)}{2} \mbox{mod}~2^{32}$.
When registering the events, simply add the numbers corresponding to the events sequentially modulo $2^{32}$. Call this result r.
To determine if an event is missing, calculate $x = (c - r) \mbox{mod}~2^{32}$. If $x=0$ then no events are missing, otherwise $x$ is the label for the missing event.


$S^1_2$ is a theory of bounded arithmetic, that is, a weak axiomatic theory obtained by severely restricting the schema of induction of Peano arithmetic. It is one of the theories defined by Sam Buss in his thesis, other general references include Chapter V of Hájek and Pudlák’s Metamathematics of first-order arithmetic, Krajíček’s “Bounded arithmetic, propositional logic, and complexity theory”, Buss’s Chapter II of the Handbook of proof theory, and Cook and Nguyen’s Logical foundations of proof complexity.

You can think of $S^1_2$ as a theory of arithmetic which has induction only for polynomial-time predicates. In particular, the theory does not prove that exponentiation is a total function, the theory can prove to exist only objects of polynomial size (loosely speaking).

All known proofs of the Fermat Little Theorem utilize either exponential-size objects, or they rely on exact counting of sizes of bounded sets (which is probably not definable by a bounded formula, i.e., in the polynomial hierarchy, because of Toda’s theorem).

The result on FLT, $S^1_2$, and factoring stems from Krajíček and Pudlák’s paper Some consequences of cryptographical conjectures for $S^1_2$ and EF, and in my opinion it is fairly misleading. What Krajíček and Pudlák prove is that if factoring (actually, IIRC they state it for RSA instead of factoring, but it’s known that a similar argument works for factoring too) is hard for randomized polynomial time, then $S^1_2$ cannot prove the statement that every number $a$ coprime to a prime number $p$ has finite exponent modulo $p$, that is, there exists $k$ such that $a^k\equiv1\pmod p$.

It’s true that this is a consequence of FLT, but in fact it is a much, much weaker statement than FLT. In particular, this statement follows from the weak pigeonhole principle, which is known to be provable in a subsystem of bounded arithmetic (albeit a stronger one than $S^1_2$). Thus, Krajíček and Pudlák’s argument shows that $S^1_2$ does not prove the weak pigeonhole principle unless factoring is easy, and as such provides a conditional separation of $S^1_2$ from another level of the bounded arithmetical hierarchy, say $T^2_2$.

In contrast, the actual FLT does not even seem to be provable in full bounded arithmetic $S_2=T_2$, but this is not related to cryptography. You can find some relevant discussion in my paper Abelian groups and quadratic residues in weak arithmetic.


Counting the number of satisfying assignments in a POSITIVE CNF-SAT

This is still #P-complete [1]. This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph).

[1] Roth, Dan. "On the hardness of approximate reasoning." Artificial Intelligence 82.1-2 (1996): 273-302.


Is there fast algorithm for finding min vertex-disjoint path cover of DAG graph of poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v

So if I'm interpreting your question you have a set of points in the Euclidean plane and you want to find a decomposition of the points into as few monotone chains as possible? This is called the "layers of maxima" problem and it is easily solved in time O(n log n) by a plane sweep algorithm that sweeps over the points from left to right, using a binary search tree to maintain the set of intersection points of the monotone chains with the sweep line and assigning each point in sweep order greedily to the highest monotone chain that it can be assigned to. See e.g. Buchsbaum and Goodrich, "Three-Dimensional Layers of Maxima", Algorithmica 2004, for a three-dimensional version that can still be solved in O(n log n) and references to earlier work on the problem.


GHC's Data.Sequence's replicate function
 builds a fingertree in $O(\lg n)$ time and space, but this is enabled by knowing the elements that go on the right spine of the finger tree from the get-go. This library was written by the authors of the original paper on 2-3 finger trees.

If you want to build a finger tree by repeated concatenation, you might be able to reduce the transient space usage while building by changing the representation of the spines. The spines on 2-3 finger trees are cleverly stored as synchronized singly-linked lists. If, instead, you store the spines as deques, it may be possible to save space when concatenating trees. The idea is that concatenating two trees of the same height takes $O(1)$ space by reusing the spines of the trees. When concatenating 2-3 finger trees as originally described, the spines that are internal to the new tree can no longer be used as-is.

Kaplan and Tarjan's "Purely Functional Representations of Catenable Sorted Lists" describes a more complicated finger tree structure. This paper (in section 4) also discusses a construction similar to deque suggestion I made above. I believe the structure they describe can concatenate two trees of equal height in $O(1)$ time and space. For building finger trees, is this enough space saving for you?

NB: Their use of the word "bootstrapping" means something a bit different than your use above. They mean storing part of a data structure using a simpler version of the same structure.


Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?

To my knowledge this is the only reason and I am not sure whether everybody in the fields agrees with this.

The optimistic reasoning is: Since there has not been any progress in getting a larger lower bound, $4/3$ is the right bound. And once we know this for sure, we "only" need a polynomial time rounding algorithm.

More pessimistic people will view the $4/3$ only as a lower bound. To beat this,
you need an algorithm that does not "use" the Held-Karp relaxation, even not in a hidden way.

Even more pessimistic people would say that $3/2$ is the right bound, because nobody could improve Christofides algorithm (ignoring some of the recent progresses.)

Note that for metric ATSP, the integrality gap is at least $2 - \epsilon$
(Charikar, Goemans, Karloff, FOCS 2004)


This new version - where $K = K'$ - is decidable.

Let's show that the language $L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$ is a CFL.  Then the decidability follows from the decidability of the emptiness of a CFL.

We'll design a PDA to accept $L$.  On input $x$, this PDA will try to construct two factorizations of $x$, one using words of $A$, and the other using words of $B$.  It will use a counter on the stack to ensure these two factorizations are of the same length.  Conceptually I will refer to the $A$-factorization of $x$ so far as sitting on top of $x$ and the $B$-factorization as sitting on the bottom of $x$.  Then the stack will contain $n$ counters iff the absolute value of the difference of the number of words matched on the top, minus the number of words on the bottom, is $n$.  We need another state of the PDA to record what the appropriate sign is corresponding to $n$ (which tells us if the $A$-factorization is longer than the $B$-factorization, or vice versa).

As we scan the letters of $x$, we nondeterministically guess a word $t$ of $A$ and a word $u$ of $B$ to which this letter begins.  Once we guess, we are committed to matching the rest of $t$ and $u$ against $x$; if at any point our match fails, we halt in this nondeterministic choice.  So we also maintain, in the state of our PDA, the suffix of $t$ and $u$ that remains to match.

As we scan further letters, we continue matching until we hit the end of $t$ or the end of $u$ (or both).  When we hit the end of a word, we update the stack appropriately, and then guess a new word to match in either the top or bottom (or both).

We accept if the suffixes remaining to be matched are both empty in top and bottom, and the stack contains no counters.

We can construct this PDA effectively, so we can effectively decide if it accepts anything or not (for example, by converting effectively to a grammar $G$ and then using the usual method to see if G generates anything).

Edit: One can also turn this into an upper bound on how big $k$ can be, in the worst case.  I think it should give an upper bound of something roughly like $2^{O(l^2)}$, where $l$ is the sum of the lengths of the words in $A$ and $B$.

Edit: I see now that the requirement that $A$ and $B$ be finite sets can also be relaxed, to the requirement that $A$ and $B$ be regular (possibly infinite).  In this case, instead of maintaining the suffix remaining to be matched in "top" and "bottom", instead we maintain the states of the respective DFA we are in, after processing the prefix of a possible matched word.  If we hit a final state in either "top" or "bottom", we can nondeterministically choose to go back to the initial state for a new guessed word.


Is the problem of finding operators to satisfy a list of boolean variables NP complete?

With addition and subtraction, I think the Partition problem, which is NP-hard, reduces to your second problem.

Given a set $S = \{s_1, s_2, \ldots, s_n\}$ we create the problem

$s_1$ $op_1$ $s_2$ $op_2$ $s_3$ $op_3$ $\ldots op_{n-1}$ $s_n = 0$.

If a solution exists, we create two sets:

$S_1 = \{s_1\}\cup \{s_i | op_{i-1} = +\}$

$S_2 =  \{s_i | op_{i-1} = -\}$

These two sets have to have the same sum by the setup of our original problem, so the partition problem is solved.  This shows that not only is coming up with the actual solution to this problem hard, it's in fact NP hard to determine if a solution exists (at least for addition and subtraction).

For a set of operations that doesn't allow creation of negative integers, say multiplication and addition, it's not so clear.  Also, this only shows that the problem is weakly NP-hard; there may be a reduction that gives a stronger result than this.


Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

No, the opposite. This quote of Gandy's is not referring to Babbage, but to some intervening proposals for universal-style computing between Babbage and Turing. Gandy says those proposals did not have Babbage's recognition of the importance of branching and iteration to universal computation.

In "The Confluence of Ideas in 1936" by Gandy, as printed in the book "The Universal Turing Machine - A Half Century Survey", Section 2 is "Babbage and His Followers".

Here Gandy emphasizes that Babbage did understand and respect "conditional iteration" and "conditional transfer", e.g. end of p53 and top of p54

  Although Babbage mentions conditional transfer (67-68), he, with a natural respect for well-structured programming, uses only conditional iteration[....] He states conditional transfer explicitly (240), allowing that a 'go to' instruction may have to be executed by ringing a bell to summon the attendant; he gives an example of its use (241).

(Here Gandy refers to the article by Menabrea 1842 on Babbage's engine, but seems to attribute the ideas to Babbage himself.)

Gandy then quotes Babbage

  That the whole of the development and operations of analysis are now capable of being executed by machinery.

and writes

  Babbage, in his work on general algebra and functional equations, had shown
  his ability to think in abstract terms. If, then, one had led him to speculate (not
  difficult!) on what could be done with an abstract machine, free from limitations on
  its storage, he would surely have assented to a version (based on Sections 2.1.(1)-(5)) of Church's thesis.

Then Gandy goes on to Section 2.3, "Subsequent developments." He writes

  Other authors, concerned
  with more practical machines, referred to Babbage's work. Examples from Ran-
  dell 1982 are: M. d'Ocagne [1922], L. Couffignal [1933], V. Bush 1936, H.H. Aiken
  11964] (which is an unpublished memorandum of 1937). But the emphasis is on
  programming a fixed iterable sequence of arithmetical operations. The fundamental
  importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized, though the principles may be used in very particular contexts [....]

Finally, Gandy writes:

  Conclusions. Babbage asserted what was, in effect a version of Church's thesis. His work was never entirely forgotten, but its theoretical importance - its importance, so to speak, as software - was little recognized[....]


Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer points in the plane, with Euclidean distances) is NP-complete, because it hinges on an unsolved problem, the complexity of comparing sums of square roots. Some other geometric problems, such as the recognition of unit distance graphs (of some relevance as an abstraction of protein folding) are complete for the existential theory of the reals, which as far as we know is a different complexity class than NP.


Without knowing any further restrictions on the parameters, the problem is NP-hard.

Let $G = (V,E)$ be an undirected graph. For $v \in V$, define the set $S_v = \{ e \mid e \in E \mbox{ is incident to } v\}$. Then $| S_u \cap S_v | = 1$ if $u$ and $v$ are adjacent, and $|S_u \cap S_v| = 0$ otherwise. You can pad out each $S_v$ with distinct junk items until each set has the same size. Then an ordering of $\{ S_v \mid v \in V\}$ in which adjacent sets have "as large an intersection as possible" corresponds to a Hamiltonian path in $G$ (for sensible measures like maximizing $\sum_i |S_i \cap S_{i+1}|$ or maximizing $\min_i |S_i \cap S_{i+1}|$).

If you want adjacent sets to have "as small an intersection as possible", simply complement each of these sets and the same reduction also works.

Your question suggests that you think this problem can be done in $O(m^2)$, and now I'm curious why.


Constaint Satisfaction problem with exponentially many solutions

Without further assumption the bound on the number of solutions you give isn't going to help. The reason is that there is an easy transformation of an arbitrary CSP problem into one that either continues to have no solutions (if the original problem had no solutions) or that has an exponential number of solutions (if the original problem has at least one solution): just add a linear number of irrelevant and unconstrained variables. So if you could find a solution quickly when there are an exponential number, you could apply this method to the output of this transformation and use it to find a solution quickly even when there is only one.


Is finding the minimum regular expression an NP-complete problem?

Yes, it is NP-Hard.  Pitt and Warmuth showed that finding the smallest DFA consistent with a given sample cannot be approximated to within $OPT^k$ for any constant $k$, unless $P = NP$.

Regarding the learning question: Kearns and Valiant proved that you can encode RSA into a DFA.  So, even if the labeled examples come from the uniform distribution, being able to generalize to future examples (also even coming from the uniform distribution) would break RSA.  Hence, we think that in the worst case, having labeled examples does not help with learning a DFA (in the PAC model).  This is one of the classic cryptographic hardness results for learning.

Both of these issues are intertwined due to what we call the Occam's Razor Theorem.  It basically states that if we have a procedure for finding the smallest hypothesis from a given class that's consistent with a sample labeled by a hypothesis from the same class, then we can PAC learn that class.  So, given the RSA hardness result, we would expect that finding the smallest consistent DFA would be hard in general!

To add a positive learning result, Angluin showed that you can learn a DFA if you get to make up your own examples, but it requires the additional power being able to ask "is my current hypothesis correct?"  This was also a seminal paper in learning.

To answer your other question, this is all indeed related to Kolmogorov complexity, as the learning problem becomes easier when the canonical representation of the target DFA has low complexity.


Complexity of applying a permutation in-place

Option 0: Permuting In Place (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete $O(n \log n)$ time $O( \log^{2} n )$ space.

Option 1: Cheat by compressing your permutation to a succinct data structure, see Munro  http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Option 2:  Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat http://oeis.org/A186202

Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. $O(n^2)$ time, $O(\#\text{cycles} * \log n)$ space.

Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. $O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ time, $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$ space.

Option 5: From same paper by Munro as Option 0, For $i = 1 .. n$ rotate the cycle of $p(i)$ if $i$ is the largest index in that cycle. $O(n^2)$ time and $O(\log  n)$ space.


Real number $p$ such that a $p$-coin makes the undecidable decidable

I was also wondering how to solve this problem. Although the comments seem to suggest that the poster of the question has already solved the problem, I will write up a solution regardless in case anyone else is curious.

Some credit goes to Sidhanth Mohanty. He showed me this question because he was also interested in the solution, and he provided some crucial insights.

As discussed in the comments, we are considering probabilistic Turing machines, so we need only output the correct answer with probability, say, at least $2/3$.

Idea: Let $L$ be some undecidable language. Maybe we can encode the answers in the binary expansion of $p$. Establish a reasonable bijection $f \colon \mathbb{N} \to \{0,1\}^*$ and make the $i$-th bit in the binary expansion $p$ one if $f(i) \in L$ and zero if $f(i) \not\in L$. Now we hope to recover the binary expansion of $p$ by flipping the coin $t$ times, counting the number of heads $s$, and computing $s/t$.

Issue 1: This won't be polynomial time. Given some input $x \in \{0,1\}^*$, the index $f^{-1}(x)$ will be exponential in $|x|$, and determining the $f^{-1}(x)$-th bit of $p$ with high enough probability will take too long.

Fix: We get to choose what $L$ is, so we can make the elements in $L$ large in length.

Issue 2: At first it might seem like in order to determine the $i$-th bit of $p$, it's enough to read off the $i$-th bit of the binary expansion of $s/t$, hoping that $\vert s/t - p \vert < 2^{-i}$. However, this is not enough to guarantee that the $i$-th bit of $s/t$ is equal to the $i$-th bit of $p$. Suppose that $p$ is $0.1_2$ and that you're trying to determine the third bit of $p$. If $s/t$ is less than $p$ by any positive amount, which would occur roughly half the time, the third bit of $s/t$ could be a 1 rather than a 0. 1 Of course, we cannot actually have $p = 0.1_2$ since we’re assuming that $p$ is uncomputable by construction, but if $p$ were close to $0.1_2$ or any other value with a binary expansion that terminates, we would have a similar issue.

Fix: Note that if the $(j+1)$-th bit of $p$ is different from the $(j+2)$-th bit of $p$, then if we have $\vert s/t - p \vert < 2^{-(j+2)}$, the $i$-th bit of $s/t$ is indeed equal to the $i$-th bit of $p$ for all $1 \leq i \leq j$. This suggests that we can fix the issue by redefining $p$ to make lots of adjacent bits different in its binary expansion.

1Also, in this case, you would also have the issue that you couldn't distinguish $0.1_2$ and $0.0\overline{1}_2$.

Clean writeup:

Define $f\colon \mathbb{N} \to \{0, 1\}^*$ with $f(n)$ being $n$ written in binary with the leading $1$ removed. Let $H$ be your favorite undecidable language, e.g. let
$$
  H = \{x \in \{0,1\}^* : \text{ $x$ describes a Turing machine that halts on the empty string}\}.
$$
Then let $L$ be the undecidable language
$$
  L = \{1^{4^k} : f(k) \in H\}.
$$
Denote the binary expansion of $p$ as $0.p_1p_2p_3p_4p_5\ldots$. For every $i \in \mathbb{N}$, we choose
$$
  (p_{2i-1}, p_{2i}) =
  \begin{cases}
    (1, 0) & \text{if } f(i) \in H \\
    (0, 1) & \text{if } f(i) \not\in H.
  \end{cases}
$$

Our TM for deciding $L$ does the following on input $x \in \{0,1\}^*$:

If $x$ is not of the form $1^{4^k}$ for some $k \in \mathbb{N}$, reject. Otherwise, compute $k$.
Flip the coin $t = \lceil 3\cdot4^{2k+2}\ln(6)) \rceil$ times, counting the number of heads $s$.
Compute the $(2k-1)$-th bit of the binary expansion of $s/t$. Accept if it is one and reject if it is zero.

The runtime is $O(t) = O\left(\vert x \vert ^ 2 \right)$, which is polynomial time.

To prove correctness, note that $p_{2k-1}$ is one iff $1^{4^k} \in L$. Hence it is enough to prove that the $(2k-1)$-th bit of $s/t$ is equal to $p_{2k-1}$ with probability at least $2/3$. Since $p_{2k+1} \not= p_{2k+2}$, if $\lvert s/t - p \rvert < 2^{-2k-2}$, then for all $i \leq k$ we have that the $i$-th bit of $s/t$ is equal to $p_i$. In particular, if $\lvert s/t - p \rvert < 2^{-2k-2}$, then the algorithm outputs the correct answer.

The Chernoff bound in corollary 5 of this set of notes tells us that for any $\delta \in (0,1)$, we have
$$
  \operatorname{Pr}\left[\left\vert \frac{s}{t} - p \right\vert \geq \delta p \right] \leq 2\exp\left(-pt\delta^2/3\right).
$$
Setting $\delta$ to be $1/(2^{2k+2}p)$, we get
$$
\begin{align*}
  \operatorname{Pr}\left[\left\vert \frac{s}{t} - p \right\vert \geq \frac{1}{2^{2k+2}} \right]
  &\leq 2\exp\left(-\frac{t}{3 \cdot 4^{2k+2} p}\right) \\
  &\leq 2\exp\left(-\frac{3\cdot4^{2k+2}\ln(6)}{3 \cdot 4^{2k+2} p}\right) \\
  &= 2\exp\left(-\ln(6)/p\right) \\
  &< 2\exp\left(-\ln(6)\right) \\
  &= 1/3.
\end{align*}
$$
Thus $\operatorname{Pr}\left[\lvert s/t - p \rvert < 2^{-2k-2}\right] > 2/3$, so our algorithm is correct with probability at least $2/3$.


Landauer's principle internals - how it works

You're confused because the example didn't cover all possible cases, and you're extrapolating improperly.

Negation is the operation

  0 → 1,
    1 → 0.

This is reversible, and can theoretically be performed using an arbitrarily small amount of energy.

Restore to one is the operation

  0 → 1,
    1 → 1.

This is not reversible, and unavoidably  dissipates $k T \ln 2\;$ energy.


Given that you said it would be enough for the sequence to be unpredictable, here is a very simple solution.  The $i$th value in the sequence is given by

$$x_i = 2^{128} i + y_i$$

where $y_i$ is any pseudorandom sequence where you can efficiently find the $i$th value ($y_i$) and where each $y_i$ is 128 bits wide (i.e., $0 \le y_i < 2^{128}$).  For instance, you could use

$$y_i = F(K,i)$$

where $F$ is any pseudorandom function (e.g., AES) with a 128-bit output, and $K$ is a key (the seed from which the entire sequence is generated).


I will try to answer the question more generally so does not depend on the specific problem. Let $L$ be a language in $DTime(O(t(n))-DTime(o(t(n))$. Can we use padding to get a language in  $DTime(O(s(n))-DTime(o(s(n))$ where $s(n) \in \Omega(t(n))$ is an arbitrary (time constructible) function?

The answer is no:

  the complexity class separations using padding translate downwards but not upwards, see Why do equalities between complexity classes translate upwards and not downwards?.


Asymptotic density of ambiguous context-free grammars (CFGs)

The question depends on the exact encoding. However, it seems that in many reasonable encodings, as the length tends to infinity, the number of production rules $S\to a$ (for an appropriate interpretation of the starting symbol $S$ and the terminal $a$) will be more than one with high probability; here I literally mean the same terminal $a$. If we consider this as ambiguity, then I expect "most" grammars to be ambiguous. We can also concoct similar situations such as the rules $S\to S$ and $S\to a$ each appearing at least once.

Assuming this general hypothesis, that every (fixed) conceivable rule should appear with high probability as the length tends to infinity, we find that "most" grammars generate $\Sigma^*$ in an ambiguous manner.

As an example, consider the following encoding for grammars over $\Sigma = \{0,1\}$. The grammar alphabet consists of the symbols $\{0,1,;,.\}$. Non-terminals are indexed by binary strings of length at least 2. Rules are separated by full stops. Each rule is a sequence of binary strings separated by semicolons. The first binary string is the non-terminal on the left-hand side, and the rest (if any) constitute the right-hand side; if the first binary string is not a non-terminal (i.e., it is $\epsilon$,0,1), then the starting non-terminal is assumed. The starting non-terminal is always 00.

Under this encoding, every string in $\{0,1,;,.\}^*$ describes some grammar. A random grammar will with high probability contain many copies of $.00;00.$ and $.00;0.$, and in particular will be ambiguous.


Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem $\max wx$ such that $Ax \le b, x \in {0,1}^n$ where $A$ is a $m \times n$ non-negative matrix. The width of the program is $\min_{i,j} b_i/A_{i,j}$ (which we can assume is at least $1$). If $A$ is a $0,1$ matrix and $b$ is an integer vector then this captures packing problems where one allows repetitions up to $\min_i b_i$. Packing problems become easier as width increases. For Set Packing one can get an approximation of the form $d^{1/W}$ where $W$ is the width and $d$ is the maximum set size and this is more or less tight from hardness of maximum independent set. In particular when $W = \Omega(\log d)$ one gets a constant factor approximation.


Steiner tree problem for unweighted graphs

[Steiner tree] remains NP-complete if all edge weights are equal, even if $G$ is a bipartite graph having no edges joining two vertices in $C$ or two vertices in $V-C$.

— Garey and Johnson, Computers and Intractability, Freeman, 1979.  Citation is to private communication with E. R. Berlekamp.


You can create a table with the degrees-of-separation between every two users by doing a BFS or DFS from each node and recording the length of the shortest path to each node you reach as you get there (sometimes replacing a larger value with a shorter one through a different path you explored later). That's definitely polynomial time (O(|V|^2 + |V|*|E|)), but that's not to say it's cheap to do.


closure properties of IP(2pfa) and AM(2pfa)

You can take a look at the following paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers I: the power of interaction. J. ACM 39, 4 (Oct. 1992), 800-828. DOI= http://doi.acm.org/10.1145/146585.146599

or the related paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers II: zero knowledge. J. ACM 39, 4 (Oct. 1992), 829-858. DOI= http://doi.acm.org/10.1145/146585.146601


Sensitivity-Block sensitivity conjecture - Implications

Here is what Scott Aaronson has to say on the subject:

  What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of $f$, the certificate complexity of $f$, the randomized query complexity of $f$, the quantum query complexity of $f$, the degree of $f$ as a real polynomial, you name it.  So if, as is conjectured, sensitivity and block-sensitivity are polynomially related, then sensitivity—arguably the most basic of all Boolean function complexity measures—ceases to be an outlier and joins a large and happy flock.

Checking other relevant literature doesn't offer any other compelling implications:

Nisan and Szegedy describe the question but offer no motivation at all.
Kenyon and Kutin mention that is is a "natural open question".
Gotsman and Linial give a somewhat contrived equivalent problem (Conjecture 5.33 on page 18 of the following paper).
P. Hatami, Kulkarni and Pankratov, in their comprehensive survey on the problem, also offer no motivation, but they have several equivalent formulations. For example, the sensitivity conjecture is equivalent to the conjecture that the parity decision complexity of a function is polynomially bounded by the sensitivity. Conjecture 5.31 on page 17, due to Shi, is one reformulation that doesn't mention sensitivity at all.
Ambainis, Bavarian, Gao, Mao, Sun and Zao state that the conjecture "originates from the theory of complexity measures of Boolean functions and
decision tree complexity", and generally offer the same type of motivation as Scott Aaronson does. Their recent preprint is the last word on the conjecture (as of December 2014).


Union/find structure implemented by bitvectors

The concept is simpler than you think.

Assuming 8 bit words and a bitvector of only one word length,

1 = 00000001
3 = 00000100
6 = 00100000

The collection is the union of the three individual elements, which is to say 00100101.

Also, wikipedia: http://en.wikipedia.org/wiki/Bit_array


Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk: https://www.math.ucdavis.edu/research/seminars/?talk_id=6082


Why SHA-224 and SHA-256 use different initial values?

This We called Domain Separation, when we use same algorithm for different output size.
Separation is necessary because if i found two messages which have hash value (SH256), differs only in last octet and then i can publish the hash value as first 7 octet showing i used SHA224. since i already have two messages colliding on SHA224 which i can use later for forgery attack.
Using domain separation we can avoid such situation


Chernoff Bounds for settings with limited dependence

If $X_1, \cdots, X_n$ are $k$-wise independent random variables on $[0,1]$, then $$\text{Pr} \left[ \left| \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right| \geq n \cdot \varepsilon \right] \leq \left( \frac{k^2}{4 n \varepsilon^2} \right)^{\lfloor k/2 \rfloor}.$$
Note that this bound does not necessarily improve with greater $k$. So you may want to choose a smaller $k$ to get the best results.

Proof Sketch. W.L.O.G. $k$ is even. Consider the $k^\text{th}$ moment: $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] = \sum_{S \in [n]^k} \text{Ex} \left[ \prod_{i \in S} X_i - \text{Ex}[X_i] \right].$$
Each summand on the RHS is nonzero only if every $i$ appears at least twice in $S$. (Otherwise, since $\text{Ex}[X_i-\text{Ex}[X_i]]=0$ and the other terms are independent, the product is zero.) So each nonzero summand has at most $k/2$ different values of $i$. So there are at most ${n \choose k/2} (k/2)^k$ nonzero summands. Each summand is bounded by $1$. Thus $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] \leq {n \choose k/2} (k/2)^k \leq (n \cdot k^2 /4)^{k/2}.$$ Now apply Markov's inequality to obtain the result. Q.E.D. (Sorry the proof sketch is so brief. I can elaborate if you want.)

This appears as Prob. 3.8 p. 52 in Pseudorandomness by S. Vadhan.


Why can a Predictive Parser contain E' -> TE' | ε

... is not valid since we have "left recursion" (a variable that calls itself).

That's not what a left recursion is. That's simply recursion.

Direct left recursion is when a rule $A \to A\alpha$ exists for arbitrary $\alpha$.

Indirect left recursion exists when there's a rule $A \to^* A\alpha$ for arbitrary $\alpha$. Note the star, implying possibly many derivation steps (and if we're being precise, more than one, otherwise it's just direct left recursion).

Only left recursion (whether indirect or direct) is problematic for $\text{LL}(1)$. But your grammar doesn't contain left recursion, only right recursion. Right recursion has the form $A\to^* \alpha A$. See the difference?


Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

Ben-Or directly proved  $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model:

Element distinctness: Given an array of $n$ real numbers, are its elements distinct?
Set disjointness: Given two sets of $n$ real numbers, do they have an element in common?
Set equality: Given two sets of $n$ real numbers, is one array a permutation of the other?
Measure problem: Given $n$ real intervals, what is the total length of their union?
Set inclusion: Given two sets of real numbers, is one a subset of the other?
Permutation Parity: Given an permutation of the set $[n]$, is the permutation even or odd?

The first three are the ones most often used in computational geometry.


The answer is yes. To prove this, consider the complement language:
$$\{w: w\notin L(A) \vee \exists x: h(x)=h(w)\wedge x\notin L(B)\}$$

Now, we construct an NFA $C$ as follows. Given a word $w$, $C$ has $\overline{A}$ as a component, such that if $w\notin L(A)$ then $C$ accepts. It remains to check the rest.

Let $D$ be a DFA that recognizes $\overline{B}$.
In order to check if there exists a word $x$ as described, $C$ guesses (i.e. has a nondeterministic transition), for every letter $\sigma$ of $w$, a transition in $D$ that can be taken with a letter $\tau$ such that $h(\tau)=h(\sigma)$. The accepting states of this component are those of $D$.

It is not hard to prove that $C$ accepts the language above, and by complementing it you get an automaton for your desired language.


Avoiding overflow in finding a solution to $ax + by = c$

One way to solve this might be through an application of the Chinese remainder theorem and some kind of Hensel lifting.
Let's fix a constant $\alpha$ with the property that $2^\alpha 3^\alpha 5^\alpha > 2^{129}$ and $5^\alpha < 2^{64}$.  For instance, $\alpha=27$ would work fine.
Suppose $ax+by=c$ holds modulo $2^\alpha$, modulo $3^\alpha$, and modulo $5^\alpha$, i.e., $ax+by \equiv c \pmod{q}$ for $q=2^\alpha$, $q=3^\alpha$, and $q=5^\alpha$.  Then by the Chinese remainder theorem, it follows that $ax+by=c$ holds in the integers.  So, our goal will be to find $x,y$ that satisfy this equation modulo $2^\alpha$, modulo $3^\alpha$, and modulo $5^\alpha$.
Here are some observations that will help us find a solution that works modulo each of $2^\alpha$, $3^\alpha$, and $5^\alpha$:

Given a solution that is valid modulo $2^i$, $3^i$, and $5^i$, it is easy to find a solution that is valid modulo $2^{i+1}$, $3^{i+1}$, and $5^{i+1}$.  Here is how.  Given $(x,y)$ such that $ax+by \equiv c \pmod{q}$ (for $q\in \{2^i,3^i,5^i\}$), we consider the 3481 pairs $(x',y')$ such that $x' \in \{x,x+ d \cdot 2^i 3^i 5^i : |d| < 30, d \in \mathbb{Z}\}$ and $y' \in \{y,y+ d \cdot 2^i 3^i 5^i : |d| < 30, d \in \mathbb{Z}\}$.
One of these pairs will satisfy $ax+by \equiv c \pmod{q}$ (for $q\in \{2^{i+1}, 3^{i+1}, 5^{i+1}\}$) and will avoid overflow in $x',y'$ (i.e., we will have $0 \le x',y' < 2^{64}$).  So, you can check all 3481 candidates and find the one that you wanted.  Identifying the one you wanted is easy.  Given a candidate, it is easy to check for overflow and immediately rule out any $x',y'$ that trigger overflow or underflow in the expressions $x+ d \cdot 2^i 3^i 5^i,y+ d \cdot 2^i 3^ i5^i$.  Also, you can check whether $ax+by=c$ holds modulo $2^{i+1}$, $3^{i+1}$, and $5^{i+1}$ separately in 64-bit arithmetic without overflow, as long as each of $2^{i+1},3^{i+1},5^{i+1}$ is at most $2^{64}$.

It is also easy to find a solution that is valid modulo $2^0 3^0 5^0$: simply take $x=0,y=0$.

Given all of this background, we can now use induction to find a solution.  We start by forming a solution that works for $i=0$.  At each step, we increment $i$, until we reach $i=\alpha$.  Each step can be done in 64-bit arithmetic semi-efficiently (with a few thousand basic arithmetical operations), so the whole computation should be semi-efficient.

I feel like there ought to be some way to work modulo $2^i$, $3^j$, and $5^k$, and at each step separately increment either $i$, $j$, or $k$, but I haven't worked out the exact details of how to do that yet.  If you can make that work, the resulting scheme would be significantly more efficient.


Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph

This appears to be NP-complete by a reduction from Hamiltonian cycle in planar graphs of degree at most three. Hamiltonian cycle should still be hard in planar graphs of degree at most three that contain two adjacent degree-two nodes (this is the part I haven't checked very carefully). Embed the given planar graph into the grid in such a way that each vertex becomes a grid point, each edge becomes a grid path, and all edges have the same length $\ell$ (pad the shorter ones by zigzagging if necessary to achieve this). Let $s$ and $f$ be two adjacent degree-two nodes. Include walls in the initial placement of walls so that only the vertices and edges of the embedding remain available to connect $s$ to $f$. Let $n$ and $m$ be the numbers of vertices and edges in the original graph. Then, the original graph has a Hamiltonian cycle if and only if it is possible to place $m-(n-1)$ more walls in such a way that the new shortest path from $s$ to $f$ has length $(n-1)l+(n-2)$. A path of that length must be a Hamiltonian path in the original graph which together with the edge from $s$ to $f$ forms a Hamiltonian cycle, and conversely if the graph contains a Hamiltonian cycle then you can force the path from $s$ to $f$ to be that long by placing a wall in each other edge.


Is there a language with strong typed interfaces where types resolution are "delayed"?

What you are looking for are called "self types", and have been studied theoretically for ~20 years or so.

For example, see Safe Type Checking in a Statically-Typed Object-Oriented Programming Language by Kim B. Bruce, in the 1993 POPL (Principles of Programming Languages), pp. 285-298. Off the top of my head, John Mitchell and Kathleen Fisher have also worked on this, and they may also be described in Abadi and Cardelli's book A Theory of Objects.

Scala supports them, but I don't know if other mainstream OO languages do.


Algorithm for approximating convex bodies by a convex hull of ellipsoids

You may want to look into the "Crust" and "Power Crust" algorithms from Amenta, et al.  Rather than ellipsoids, it uses spheres, but I believe the concept is simliar as they are able to, at the limit, construct a water-tight body from an unorganized point-cloud.  In their case the desire was to mesh the original intended shape from the medial axis created between the delaunay and voroni spaces of the point-cloud rather than a convex hull of the points, but you may be able to glean some interesting ideas.

The associated papers can be found here:

A New Voronoi-Based Surface Reconstruction Algorithm

The Power Crust

The Power Crust, Unions of Balls, and the Medial Axis Transform


Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'

You can try reading more recent papers such as Worst-case to Average-case Reductions based on Gaussian Measures by Miccancio and Regev, or Regev's  lecture notes on the subject (you might want to read through the entire course).