Category-theoretic treatment of diffs, patches and merging?

As pointed by Martin, there is some work on the categorical representation of patches. Mimram and Di Giusto's "A Categorical Theory of Patches" being the most extensive categorical approach to edit-scripts as used by the UNIX diff.

In their sense, you have what you want. The objects are finite sequences of words over an alphabet $L$, seen as a mapping $A : [n] \rightarrow L$, where $[n]$ denotes the set with $n$ elements. An arrow between $A : [n] \rightarrow L$ and $B : [m] \rightarrow L$ is an injective partial increasing mapping $f : [n] \rightarrow [m]$. Injectivity and increasing are there to indicate that copies never cross over each other. You can find all the details on the paper.

Yes, merging is seen as the pushout on the free cocompletion of the above category.
We need the cocompletion to make sure we add merge conflicts to our construction.
It is not the case that a merge always exists.

Onto your second question, there is no categorical notion of minimal edit script for two main reasons.

Edit-scripts come in all shapes and forms. Some authors consider insertions, deletions and copies, some authors like to add substitutions as an operation too.
When you generalize from strings to trees, then, a plethora of other operations become
feasible.
More importantly, though, minimal-cost edit-scripts are not unique.
Take the file $ab$, and write a patch that transforms it into $ba$. What is the
minimal edit script that does this? There are two! Once again, when generalizing into
trees one can find even more situations where a notion of "minimality" is doubtful.

There has been a lot of work on generalizing edit scripts to trees. This has been split in two main bodies of work:

Untyped Trees: Think of s-expressions only. The tree-edit-distance between two
trees is the string-edit-distance between the preorder traversal of said trees. You can check some bibliography by Demaine et al. or Pawlik and Augsten, for example.
Typed Trees: Patches over Abstract Syntax Trees that are guaranteed to preserve
the well-typedness of the object, ie, applying a patch will always yield a valid AST.
Under the typed umbrella, there are less edit operations one can consider. Substitution, for example, doesn't make sense. Nevertheless, there exists a diff over the preorder traversal of the trees by Lempsink et al., which was later extended by Vassena. I am currently focusing on approaches that distance themselves from edit scripts for the very problems I pointed earlier, such as our latest work or some earlier work which tries to take advantage of the structure of the type of the values being "patched".

In either of those cases I have not seen a careful categorical interpretation of tree-structured patches.


OR-circuit complexity of a dense linear operator

This is a partial (affirmative) answer in the case when we have an upper bound on the number of zeros in every row or in every column.

A rectangle is a boolean matrix consisting of one all-1 submatrix and having zeros elsewhere.
An OR-rank $rk(A)$ of a boolean matrix is the smallest number $r$ of
rectangles such that $A$ can be written as a (componentwise) OR of these rectangles. That is, every 1-entry of $A$ is a 1-entry in at least one of the rectangles, and every 0-entry of $A$ is a 0-entry in all rectangles. Note that $\log rk(A)$ is exactly the nondeterministic communication complexity of the matrix $A$ (where Alice gets rows, and Bob columns).
 As OP wrote, every boolean $m\times n$ matrix $A=(a_{i,j})$ defines a mapping $y=Ax$, where  $y_i=\bigvee_{j=1}^na_{i,j}x_j$ for $i=1,\ldots,m$. That is, we take a matrix-vector product over the boolean semiring.

The following lemma is due to Pudlák and Rödl; see Proposition 10.1 in this paper
or Lemma 2.5 in this book for a direct construction.

Lemma 1: For every boolean $n\times n$ matrix $A$, the mapping $y=Ax$ can be computed by an unbounded fanin OR-circuit of depth-3 using at most $O(rk(A)\cdot n/\log n)$ wires.

We also have the following upper bound on the OR-rank of dense matrices.
 The argument is a simple variation of that used by Alon in this paper.

Lemma 2: If every column or every row of a boolean matrix $A$ contains at most $d$ zeros, then $rk(A)=O(d\ln|A|)$, where $|A|$ is the number of $1$s in $A$.

Proof:
Construct a random all-$1$ submatrix $R$ by picking each row independently with the same probability $p=1/(d+1)$. Let $I$ be the obtained random subset of rows. Then let $R=I\times J$, where $J$ is the set of all columns of $A$ that have no zeros in the rows in $I$.

A $1$-entry $(i,j)$ of $A$ is covered by $R$ if $i$ was chosen in
  $I$ and none of (at most $d$) rows with a $0$ in the $j$-th column
  was chosen in $I$. Hence, the entry $(i,j)$ is covered with probability at least $p(1-p)^{d}\geq pe^{-pd-p^2d}\geq p/e$.
  If we apply this procedure $r$ times to get $r$ rectangles,
  then the probability that $(i,j)$ is covered by none of these
  rectangles does not exceed $(1-p/e)^r\leq e^{-rp/e}$.  By the union bound, the
  probability that some $1$-entry of $A$ remains uncovered is at most
$|A|\cdot e^{-rp/e}$, which is smaller than $1$ for $r=O(d\ln|A|)$.
$\Box$

Corollary: If every column or every row of a boolean matrix $A$ contains at most $d$ zeros, then the mapping $y=Ax$ can be computed by an unbounded fanin OR-circuit of depth-3 using
$O(dn)$ wires.

I guess that a similar upper bound as in Lemma 2 should also hold when $d$ is the average number of $1$s in a column (or in a row). It would be interesting to show this.

Remark: (added 04.01.2018) An analogue $rk(A)=O(d^2\log n)$ of Lemma 2 also holds when $d$ is the maximum average number of zeros in a submatrix of $A$, where the average number of zeros in an $r\times s$ matrix is the total number of zeros divided by $s+r$.
This follows from  Theorem 2 in N. Eaton and V. Rödl;, Graphs of small dimension, Combinatorica 16(1) (1996) 59-85.
A slightly worse upper bound $rk(A)=O(d^2\ln^2 n)$ can be derived directly from Lemma 2 as follows.

Lemma 3: Let $d\geq 1$. If every spanning subgraph of a bipartite graph $G$ has average degree $\leq d$, then $G$ can be written as a union $G=G_1\cup G_2$, where the maximum left degree of $G_1$ and the maximum right degree of $G_2$ are $\leq d$.

Proof: Induction on the number $n$ of vertices. The base cases $n=1$ and $n=2$ are obvious. For the induction step, we will color the edges in blue and red so that the maximum degree in both blue and red subgraphs are $\leq d$. Take a vertex $u$ of degree $\leq d$; such a vertex must exists because also the average degree of the entire graph must be $\leq d$. If $u$ belongs to the left part, then color all edges incident to $u$ in blue, else color all these edges in red. If we remove the vertex $u$ then the average degree of the resulting graph $G$ is also at most $d$, and we can color the edges of this graph by the induction hypothesis. $\Box$

Lemma 4: Let $d\geq 1$. If the maximum average number of zeros in a boolean $n\times n$ matrix $A=(a_{i,j})$ is at most $d$, then $rk(A)=O(d^2\ln^2 n)$.

Proof: Consider the bipartite $n\times n$ graph $G$ with $(i,j)$ being an edge iff $a_{i,j}=0$. Then the maximum average degree of $G$ is at most $d$. By Lemma 3, we can write $G=G_1\cup G_2$, where
 the maximum degree of the vertices on the left part of $G_1$, and the maximum degree of the vertices on the right part of $G_2$ is $\leq d$.
Let $A_1$ and $A_2$ be the complements of the adjacency matrices of $G_1$ and $G_2$.
Hence, $A= A_1\land A_2$ is a componentwise AND of these matrices.
The maximum number of zeros in every row of $A_1$ and in every column of $A_2$ is at most $d$. Since $rk(A)\leq rk(A_1)\cdot rk(A_2)$, Lemma 2 yields $rk(A)=O(d^2\ln^2 n)$. $\Box$

N.B. The following simple example (pointed by Igor Sergeev) shows that my "guess" at the end of the answer was totally wrong: if we take $d=d(A)$ to be the average number of zeros in the entire matrix $A$ (not the maximum of averages over all submatrices), then Lemma 2 can badly fail.  Let $m=\sqrt{n}$, and put an identity $m\times m$ matrix in, say left upper corner of $A$, and fill the remaining entries by ones. Then $d(A)\leq m^2/2n < 1$ but $rk(A)\geq m$, which is exponentially larger than $\ln|A|$. Note, however, that the OR complexity of this matrix is very small, is $O(n)$. So, direct arguments (not via rank) can yield much better upper bounds on the OR complexity of dense matrices.


Streaming algorithms suitable for undergrad course

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following:

Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space.
Approximate bit counting on a sliding window - given a bit-stream, answer queries approximating the number of $1$'s in the last $N$ bits, and do so using $O(\log N)$ space.
Sampling from a sliding window (at any point, give a sample of $k$ elements uniformly chosen from the last $N$ elements of a stream).
Exact item counting - answer queries of the form "how many times did $x$ appear in the stream" such that the answer will be correct w.h.p. using only sublinear space (modern data structures are quite complex, but Count–min sketch seems to fit undergrad course).


The $O(5^kk^3n)$ is linear in $n$ as well and $O(n)$ for bounded $k$.
The Courcelle, Makowski, Rotics paper does not give explicit/good upper bounds for the contants hidden in the big-O.  If you want to make the dependency on $k$ explicit as in $O(f(k)n)$, then additional work is required.

See "Faster Algorithms on Clique and Branch Decompositions" by
Bodlaender et al (MFCS 2010)  for recent algorithms for domination-style algorithms.


Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

No, this is impossible for your parameters.  With $s$ bits of space, you can only visit at most $2^s$ vertices of the graph.  Now set $s = O((\log k)^d)$ and $k=(\log n)^2$ and it is clear that you cannot visit all of the graph, as $2^s = o(n)$.  Thus for any algorithm that uses only $O((\log k)^d)$ bits of space, there exist graphs where you fail to detect a $k$-cycle (e.g., because the $k$-cycle is in the unvisited part of the graph).

If $k=n^{\Theta(1)}$, and if your definition of a cycle allows repeated vertices to appear in the cycle, then an algorithm exists.  A simple approach is to guess a starting vertex $v_0$ and store it (which requires $\log n = O(\log k)$ bits); then, non-deterministically guess a path of length $k$, counting up to $k$ as you go (which requires $\log k$ bits), checking that none of the intermediate vertices are equal to $v_0$ and the final vertex is equal to $v_0$.
If $k=n^{\Theta(1)}$, and if your definition of a cycle does not allow repeated vertices to appear in the cycle, then I don't know whether an algorithm exists or not.


Problem in BPP but not known to be in RP or co-RP

Moved my comment here after Suresh's request.

An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP.

Reference: see the post How Many Sides to Your Error? (Dec 2, 2008) about the very same question on Lance Fortnow's blog and the comments below his post for a discussion about the naturalness of the problem.


Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were correct, since the proof applies to this case too. However, can we pinpoint the mistake? Here is, from a post on the lipton's blog, what seems to be the place where the proof fails:

The single error is one subtle point in the proof of Theorem 6, namely in Step 1, on page 31 (and also 33, where the dual case is discussed) - a seemingly obvious claim that $C'_g$ contains all the corresponding clauses contained in $CNF'(g)$ etc, seems wrong.

To explain this in more detail, we need to go into the proof and approximation method of Berg and Ulfberg, which restates the Razborov's original proof of the exponential monotone complexity for CLIQUE in terms of DNF/CNF switches. This is how I see it:

To every node/gate $g$ of a logic circuit $\beta$ (containing binary OR/AND gates only), a conjunctive normal form $CNF(g)$, a disjunctive normal form $DNF(g)$, and approximators $C^k_g$ and $D^r_g$ are attached. $CNF$ and $DNF$ are simply the corresponding disjunctive and conjunctive normal forms of the gate output. $D^r_g$ and $C^k_g$ are also disjunctive and conjunctive forms, but of some other functions, "approximating" the gate output. They are however required to have bounded number of variables in each monomial for $D^r_g$ (less than a constant r) and in each clause for $C^k_g$ (less than a constant k).

There is notion of an "error" introduced with this approximation. How is this error computed? We are only interested in some set T0 of inputs on which our total function takes value 0, and T1 of inputs on which our total function takes value 1 (a "promise") . Now at each gate, we look only at those inputs from T0 and T1, which are correctly computed (by both $DNF(g)$ and $CNF(g)$, which represent the same function - output of gate $g$ in $\beta$) at gate output, and look how many mistakes/errors are for $C^k_g$ and $D^r_g$, compared to that. If the gate is a conjunction, then the gate output might compute more inputs from T0 correctly (but the correctly computed inputs from T1 are possibly decreased). For $C^k_g$, which is defined as a simple conjunction, there are no new errors however on all of these inputs. Now, $D^r_g$ is defined as a CNF/DNF switch of $C^k_g$, so there might be a number of new errors on T0, coming from this switch. On T1 also, there are no new errors on $C^k_g$ - each error has to be present on either of gate inputs, and similarly on $D^r_g$, switch does not introduce new errors on T1. The analysis for OR gate is dual.

So the number of errors for the final approximators is bounded by number of gates in $\beta$, times the maximal possible number of errors introduced by a CNF/DNF switch (for T0), or by a DNF/CNF switch (for T1). But the total number of errors has to be "large" in at least one case (T0 or T1), since this is a property of positive conjunctive normal forms with clauses bounded by $k$, which was the key insight of Razborov's original proof (Lemma 5 in the Blum's paper).

So what did Blum do in order to deal with negations (which are pushed to the level of inputs, so the circuit $\beta$ is still containing only binary OR/AND gates)?

His idea is to preform CNF/DNF and DNF/CNF switches restrictively, only when all variables are positive. Then the switches would work EXACTLY like in the case of Berg and Ulfberg, introducing the same amount of errors. It turns out this is the only case which needs to be considered.

So, he follows along the lines of Berg and Ulfberg, with a few distinctions. Instead of attaching $CNF(g)$, $DNF(g)$, $C^k_g$ and $D^r_g$ to each gate $g$ of circuit $\beta$, he attaches his modifications, $CNF'(g)$, $DNF'(g)$, ${C'}^k_g$ and ${D'}^r_g$, i.e. the "reduced" disjunctive and conjunctive normal forms, which he defined to differ from $CNF(g)$ and $DNF(g)$ by "absorption rule", removing negated variables from all mixed monomials/clauses (he also uses for this purpose operation denoted by R, removing some monomials/clauses entirely; as we discussed before, his somewhat informal definition of R is not really the problem, R can be made precise so it is applied at each gate but what is removed depends not only on previous two inputs but on the whole of the circuit leading up to that gate), and their approximators ${C'}^r_g$ and ${D'}^r_g$, that he also introduced.

He concludes, in Theorem 5, that for a monotone function, reduced $CNF'$ and $DNF'$ will really compute 1 and 0 on sets T1 and T0, at root node $g_0$ (whose output is the output of the whole function in $\beta$). This theorem is, I believe, correct.

Now comes the counting of errors. I believe the errors at each node are meant to be computed by comparing reduced $CNF'(g)$ and $DNF'(g)$ (which are now possibly two different functions), to ${C'}^r_g$ and ${D'}^k_g$ as he defined them. The definitions of approximators parrot definitions of $CNF'$ and $DNF'$ (Step 1) when mixing variables with negated ones, but when he deals with positive variables, he uses the switch like in the case of Berg and Ulfberg (Step 2). And indeed, in Step 2 he will introduce the same number of possible errors like before (it is the same switch, and all the involved variables are positive).

But the proof is wrong in Step 1. I think Blum is confusing $\gamma_1$, $\gamma_2$, which really come, as he defined them, from previous approximators (for gates $h_1$, $h_2$), with positive parts of $CNF'_\beta(h_1)$ and $CNF'_\beta(h_2)$. There is a difference, and hence, the statement "$C_g'$ contains still all clauses contained in $CNF'_\beta(g)$ before the approximation of the gate g which use a clause in $\gamma_1'$ or $\gamma_2'$" seems to be wrong in general.


Are regular languages closed under addition?

Yes, they are.

First, consider the alphabet $\Sigma_i^3$ whose symbols are triples of digits (stacked one above each other into a pile of three digits). Over this alphabet, we can define a regular language $A'$ where the string formed by the topmost of the three digits belongs to $A$, a regular language $B'$ where the string formed by middle of the three digits belongs to $B$, and a regular language $C$ where the top two strings sum to the bottom one. $A'$ and $B'$ just use modified automata for $A$ and $B$, while $C$ uses the fact that you can do addition by scanning right-to-left while keeping only a single digit of carry as state.

Then $A'\cap B'\cap C$ is (by closure under intersection) a regular language that recognizes stacks of three strings, one in $A$, one in $B$, and the third in the sum. The homomorphism that strips off the top two digits from a stack leaving only the bottom one takes this to the language you want, and the result follows by closure under homomorphism.


Is the exponent in the rectangular matrix multiplication convex?

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?


Computing spanning trees with low crossing number using simplicial partitions

If I get it correctly, the result you need appears in Section 4 of this paper (a draft here). We also needed to join pieces of different papers, as the comments here tell.


Min Hamming distance of a given string from substrings of another string

Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:

Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.

Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$
Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then $$r(x,y) = \sum_{t,s} x^t y^s \left|\left\{ (i,j) \in [n]\times[k] : i+k-j=t \wedge v_i + m - u_j =s \right\}\right|. $$
In particular, for $k \leq t \leq n$, the coefficient of $x^{t} y^m$ in $r(x,y)$ is $$\left|\left\{ (i,j) \in [n]\times[k] : i=j+t-k \wedge v_i = u_j\right\}\right| = k-d_H(u,v[t-k+1,t]).$$
Thus, the coefficients of $r(x,y)$ provide a lookup table for $d_H(u,v[t-k+1,t])$ for $k \leq t \leq n$.
So, given the coefficients of $r(x,y)$, we can easily solve the problem by picking the $t$ such that $x^{t}y^m$ has the largest coefficient:

Output: $f(u,v)+k=\mathrm{arg}\max_{k \leq t \leq n} \mathrm{coefficient}_{r(x,y)}(x^{t}y^m)$

So how fast is this algorithm? I claim it can be implemented in $O(nm \log (nm))$ time (assuming arithmetic operations with $O(\log (nm))$ bits of precision take constant time) using the Fast Fourier Transform.

The core of the problem is computing $r(x,y)=p(x,y)q(x,y)$, where the degree of $p(x,y)$ is at most $n$ in $x$ and $m$ in $y$ and the degree of $q(x,y)$ is at most $k$ in $x$ and $m$ in $y$.

We can first reduce it to univariate polynomial multiplication by defining $$p'(z) = p(z^{m+1},z) \qquad \text{and} \qquad q'(z)=q(z^{m+1},z),$$ computing $r'(z)=p'(z)q'(z)$, and then extracting $r(x,y)$ from the identity $r'(z)=r(z^{m+1},z)$.

I won't go through the FFT algorithm (even though it's one of my favourite algorithms), but the general idea is:

Pick $\ell = O(nm)$ special points $w_1, \cdots, w_\ell \in \mathbb{C}$, namely $w_j=\exp(2\pi\sqrt{-1}j/\ell)$ and $\ell$ is a power of $2$ with $\ell > \mathrm{degree}(r'(z))=O(nm)$.
Evaluate $p'(w_j)$ and $q'(w_j)$ for all $j \in [\ell]$ in $O(\ell \log \ell)$-time using a divide and conquer algorithm.
Compute the values $r'(w_j)=p'(w_j)q'(w_j)$ for all $j$ in $O(\ell)$-time.
Interpolate the coefficients of $r'(z)$ from the values $r'(w_j)$ in $O(\ell \log \ell)$-time using essentially the same divide and conquer algorithm.

The observation that makes the divide and conquer algorithm work is that we can write $p'(z) = p'_\text{even}(z^2) + z \cdot p'_\text{odd}(z^2)$, where $p'_\text{even}$ and $p'_\text{odd}$ have half the degree of $p'$. It then suffices to recursively evaluate $p'_\text{even}(w_{2j})$ and $p'_\text{odd}(w_{2j})$ for $j \in [\ell/2]$.


question about concurrent ZK paper by Prabhakaran & Sahai

I'm one of the authors. Someone pointed me to this question. Based on a quick reading, here's an attempt at answering your concern.

What may not be very clear from this version of the description of the simulator (this was the first time I was describing a simulator, and admittedly it reads a bit too much like machine language) is that the view output by the simulator, after all the pushing and popping of the stack, corresponds to only the traversal through edges labeled with L1 and R1. So even if the verifier aborts somewhere else, it just get popped off, and the simulator continues.

I'd recommend the FOCS proceedings version (or a slightly expanded version that is available from my homepage) over this e-print version. In terms of the description in the proceedings version, the simulator's output corresponds to the "main thread" of the simulation, and doesn't include any aborts that may happen in the look-ahead blocks. (Just looking at the paper: see Figure 3 for an illustration.)

Hope that helps.

-Manoj


Worlds Relative to Which "Invulnerable Generators" Do Not Exist

If they were simply talking about (non-resource-bounded) Kolmogorov complexity, then $K$ would be uncomputable (otherwise you could use a machine computing $K$ to give short descriptions of the strings $x \in K$, since all you need to do is describe the machine and the length $n$ of $x$, and we have $K(x) = n$ yet $K(n) \leq \log n$), hence $B$ would be uncomputable as well.

However, the paper Abadi et al. reference (Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. FOCS 1983.) uses a resource-bounded version Kolmogorov complexity.  Let $U$ be an efficient universal Turing machine. Define $K_U[f(n), g(n)]$ to be the sets of strings $x$ such that there is a string $d$ of length $|d| \leq f(|x|)$ such that $x = U(d)$ and the computation of $U(d)$ takes at most $g(|x|)$ time. At the top of the second column on p. 444 of that paper, Hartmanis describes how to use this concept to construct a (computable) oracle relative to which $P \neq NP$.

Here is Hartmanis' idea, adapted to the Abadi et al. result.  Let $tow_3(1)=2$ and $tow_3(n+1)=2^{2^{2^{n}}}$ (which I believe is the function you described). By standard diagonalization (e.g. as in the time hierarchy theorem), construct a tally set $C$ such that $C \subseteq \{1^{tow_3(n)} : n \geq 1\}$ and $C \in TIME[n^{\log n}] - P$. Now place the first string of length $tow_3(n)$ from $K[\log n, n^{\log n}] - K[\log n, n^{\log \log n}]$ into $K$ iff $1^{tow_3(n)} \in C$. Since $C = \{1^n : (\exists x)[|x|=n \text{ and } x \in K]\}$, we have $C \in NP^{K}$.

We also have $C \notin P^{K}$, hence $P^K \neq NP^K$. Suppose for the sake of contradiction that $C \in P^{K}$. Then there is a poly-time oracle machine $M$ such that $C = L(M^K)$. I claim that this implies $C \in P$ (without the oracle!), contradicting the construction of $C$. Here's the poly-time algorithm: on input $x = 1^{tow_3(n_0)}$:

Compute all strings in $K$ of length strictly less than $|x|$. This can be done in polynomial time because all such strings have length at most $\log \log \log |x|$, and we just need to test the computation of $U(d)$ on even smaller strings $d$, for amounts of time that are still very small compared to $|x|$.
Run $M(x)$, simulating oracle queries to smaller strings with the results of (1). If $M(x)$ ever queries a string of length $|x|$, simulate that query with a "NO" answer.

The reason step (2) works it that, for sufficiently large input lengths, if there is a string $y \in K$ of that length, $M^K$ cannot query $y$, so we can simulate all such queries with a NO answer.  If it did query $y$, then we would have $y \in K[\log n, n^k]$ (where $n^k$ bounds the run-time of $M$), contradicting the fact that we chose $y$ to be not in $K[\log n, n^{\log \log n}]$.


The question you are asking is known as the separation problem for languages: Given two languages $K$ and $L$, is there a third language $M$ (a separator) that separates them, i.e. $K \subseteq M$ and $M \cap L = \emptyset$.

You are interested in the restricted case where $K$ and $L$ are finite, and in the size of a DFA for $M$.

In a 2013 paper, authors indicate:

  Although the separation problem frequently occurs, it has however not been systematically
  studied, even in the restricted, yet still challenging case of regular languages.

They however mention several special cases that have been solved, and that most certainly encompass the finite case.

You may also want to look at Craig interpolant, a similar problem on logical formulae.
Interpolation is used for instance in SAT-based model-checking, in a setting which I think is closer to what you are looking for (especially regarding finiteness of the input). This paper should be a good starting point.


About a pre-processing step for primal–dual weighted set cover problem

Call a set cheap if it has cost at most $\beta/n$.

Let $S_0$ be the collection of sets obtained by "scanning through the sets and adding any cheap sets". This wording is not quite right.  In this step one should only add cheap sets whose elements are not all covered by previously added cheap sets -- this ensures that the size of $S_0$ is at most $n$.  So, the total cost of sets in $S_0$ is at most $n\beta/n = \beta$, and these sets cover every element that is in any cheap set.

The intuition is that, if we're willing to give up a factor of two in the performance guarantee, we can go ahead and add the cheap sets, in $S_0$, up front, because these sets cost at most $\beta$, which is a lower bound on the optimal cost.  Once we've done this, all that remains is to cover the elements that are not covered by any cheap set.  If we can do this using sets that have cost $O(\log n)$ times the original optimal, the total cost (after adding in the cheap sets in $S_0$) will still be $O(\log n)$ times the original optimal.

In more detail: after committing to using the cheap sets in $S_0$, the remaining problem is to compute some collection $S'$ of sets that covers the remaining elements --- those that aren't in any cheap set.  And $S'$ should have cost $O(\log n)\cdot IP^*$.

This is the problem that the paper then shows how to solve.  To complete the details, suppose that we have some such set $S'$.  Obtain the complete solution by taking $S = S_0\cup S'$.

This $S$ then covers all the elements in $U$ (as $S_0$ covers the elements that are in any cheap set, while $S'$ covers the rest), and the cost of $S$ (the  cost of $S_0$ plus the cost of $S'$) is at most $\beta + O(\log n)\cdot IP^* = O(\log n)\cdot IP^*$.  So $S$ is an $O(\log n)$-approximate solution to the original problem.

A slightly subtle point is that, to compute $S'$, it is enough to compute take $S'$ to be any $O(\log n)$-approximate solution to the problem with universe restricted to the elements not covered by any cheap set.  This is because the optimal cost for the restricted problem is at most the optimal cost for the original problem.


It should be this one:

Church, A. (1941) The Calculi of Lambda-Conversion. Annals of Mathematics Studies
No. 6, Princeton University Press.


If the function is linear, then you can reduce to MaxSAT. Then there are some related formalisms like pseudo-boolean optimizatin (PBO) or integer linear programming (ILP).


Do dependent types give you everything subtyping does?

Subtyping and dependent types are orthogonal concepts.

Subtyping is typically equipped with a notion of subsumption, whereby an expression of one type can appear in place where a supertype is expected.

Subtyping is more likely to be decidable and is more simply to manage in implementation.

Dependent typing is vastly more expressive. But if you ever want to consider a group to also be a monoid, then you need a notion of subsumption to forget the extra structure. Often, such as when using Coq, a trivial proof obligation is generated to deal with this kind of coercion, so in practice subtyping may not add anything. What's more important is having ways of packaging together various theories to make them reusable, such as reusing the theory of monoids when talking about groups. Type classes in Coq are a recent innovation for doing such things. Modules are an older approach.

If you do a quick google of "subtyping dependent types" you find a bunch of work adding subtyping to dependent types, mostly from around the year 2000. I imagine that the meta-theory is really challenging, so no subtyping of dependent types appears in proof assistants.


Gröbner basis computation, while EXPSPACE-complete in general, are in PSPACE over Boolean rings. This has applications in model-checking to replace BDDs: Quoc-Nam Tran, "A PSPACE Algorithm for Groebner Bases Computation in Boolean Rings", Proc. WASET, Vol. 35, Nov. 2008, ISSN 2070-3740

[NOTE] The result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, see Mark van Hoeij, Gröbner basis in Boolean rings is not P-SPACE, arXiv:1502.07220, 2015.

[NOTE] The claim that the result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, is wrong. The author confuses PSPACE-computability with having a polynomial size. A PSPACE function may well have exponentially long output.


Majority function stability under deletion and addition of entries

$\newcommand{\bm}{\boldsymbol}$The two scenarios are not equal even when $s = t$. In the $s,t$ case you always re-sample the same number of bits, while in the $\delta$ case you get a binomial distribution in the number of bits flipped.

Let us define $\text{Maj}$ in a slightly different way than you might be used to, but assure yourself it is correct.

$$\text{Maj}(\bm{v}) := \left[\text{Sign}(\bm v) \geq 0\right]\\
\text{Sign}(\bm{v}) = \sum_i (-1)^{\bm v_i}$$
Now because $\bm v$ is a uniform random boolean vector, if we remove an element (say $v_i$) from it to from $\bm v'$ we can we can see that

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) - (-1)^{v_i}$$

but this is very similar to the expression we'd get when adding a new bit $u_i$:

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) + (-1)^{u_i}$$

Since $u_i$ is sampled from the uniform distribution of bits, we can replace it with random variable $u'_i = 1 - u_i$ which has an equivalent distribution, giving:

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) - (-1)^{u'_i}$$

In other words, removing a bit from the vector is not distinguishable from adding a new bit from the perspective of the majority function. Therefore we can just assume $k = s+t$ and only add $k$ bits to the original $n$ in $v$.

So what is the chance that when we add those bits our majority function doesn't change? If $\bm v$ contained $n$ bits originally, that question is equivalent (again using $\text{Sign}$ as insight) to starting a simple symmetric random walk on the unit line and asking what the chance is that we are at the same side of the origin after $n + k$ steps as we were at $n$ steps. If we let $X_n$ be our random walk at step $n$ this works out to (for the positive side):

$$\Pr[X_n \geq 0, X_{n+k} \geq 0] = \Pr[X_n \geq 0]\Pr[X_{n+k} \geq 0 \mid X_n \geq 0]$$

With $Y$ being an independent random walk (and thus identical to $X$), we can say due to a random walks lack of memory that:

$$\Pr[X_{n+k} \geq 0 \mid X_n \geq 0] =\\ \sum_{i = 0}^n\Pr[X_n + Y_k \geq 0 \mid X_n = i] =\\ \sum_{i = 0}^n\Pr[X_k \geq -i]\Pr[X_n = i]$$

And thus:

$$\Pr[X_n \geq 0, X_{n+k} \geq 0] = \Pr[X_n \geq 0]\sum_{i = 0}^n\Pr[X_k \geq -i]\Pr[X_n = i]$$

We can apply a similar series of steps to find $\Pr[X_n < 0, X_{n+k} < 0]$. Then finally

$$\Pr[\text{Maj}(\bm v') = \text{Maj}(\bm v)] = \Pr[X_n \geq 0, X_{n+k} \geq 0] + \Pr[X_n < 0, X_{n+k} < 0]$$

Now as an exercise to the reader, fill in $\Pr[X_n = q], \Pr[X_n \geq q]$ and $\Pr[X_n < q]$ and simplify. These probabilities for random symmetric walk $X$ are well-known (see any textbook on random walks).


Maximality and minimality: They are kinds of Pareto optimality.
Complexity: I think finding a minimum maximal solution is NP-hard.  I would reduce the independence domination problem (aka the minimum maximal independent set problem) in bipartite graphs.  This problem (more precisely its decision version) is known to be NP-complete (D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs.  Discrete Applied Mathematics 9 (1984) 27-39).  Since a bipartite graph is perfect, its independent set polytope is determined by the clique inequalities, and the number of cliques in a bipartite graph is polynomial.  Therefore, we can explicitly write down a system of linear inequalities Ax <= 1, x >= 0 for the independent set polytope.  The extreme solutions correspond to the independent sets, and the extreme maximal solutions correspond to the maximal independent sets.


As far as I know, dynamic programming does the trick

Klein's paper on TSP for planar graphs has the details for planar graphs with bounded tree-width.
If the graph is not planar, the dynamic program is slower (dependency on the tree-width is worse).

Philip N. Klein: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. SIAM J. Comput. 37(6): 1926-1952 (2008)
(PDF on Philip Klein's website)

Dynamic programming is also used to obtain a PTAS for bounded-genus and minor-free graphs (but as far as I remember the authors do not specify the details of the DP).

Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: Approximation algorithms via contraction decomposition. Combinatorica 30(5): 533-552 (2010)
(Paper on Erik Demaine's website)

Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: Contraction decomposition in H-minor-free graphs and algorithmic applications. STOC 2011: 441-450

For videos on these PTAS constructions, see Planar TSP and Minor-free TSP (again not focussing on the tree-width part).


The flaw in Bellare-Rogaway (1995) model on authenticated key exchange

The "protocol interference" attack:

From Fig 2 of http://seclab.cs.ucdavis.edu/papers/Rogaway/3pkd.pdf --

In Flow3A (resp. 3B), before the intended message is delivered, the adversary manages to obtain an encryption under $K_A$ (resp. $K_B$) of a different session key $\sigma'$ (through interacting with $S$ in a higher-level protocol) and sends this "forged" message to $A$ and $B$. This is a successful man-in-the-middle style attack.

Why the security definition should include TEST in the middle of execution:

If the interaction doesn't terminate immediately after TEST, then the forged session breaks security in a very obvious way. Namely, with probability 1/2, the TEST operation hands a key to the adversary; it becomes the "higher-level protocol" we're worried about with constant probability. If the adversary is not forced to immediately halt, then it can use this key to perform the man-in-the-middle attack above (at least in the BR95 scheme).

The security definition given in BR95 is, therefore, too weak as this is a plausible attack (Why would an adversary arbitrarily halt, especially after they've just extracted useful information?). That is, a protocol vulnerable to this attack is (wrongly) proven secure under the given definition.


Persistant bag/set with direct access to known elements

You can solve this with a dictionary, using myptr a = a.

You can get $O(\lg n)$ add and remove in an immutable data structure by using a balanced binary search tree. Enumerate will take $O(n)$ time, but the $i$th element can be made available in $O(i)$ time, so your enumerate result can keep up with any consumption of it.

"Confluently Persistent Tries for Efficient Version Control", by Erik D. Demaine, Stefan Langerman, and Eric Price provides a dictionary that is fully persistent, but not immutable. With it, you can get the same bound on enumerate, and a $O(\lg \lg n)$ bound on add and remove.


Generating interesting combinatorial optimization problems

One general approach to generating harder instances is as follows:

Start with a random problem instance.
Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.

For instance, for TSP, you could do something like the following.  Generate a random problem instance by picking a random $U(0,1)$ cost matrix.  Then, adjust the problem instance to hide a much-better solution in it: randomly select a tour that visits each vertex exactly once, and reduce the edge weights on that tour (e.g., generate it randomly from $U(0,c)$ where $c<1$; reduce the existing weight; or modify the existing edge with some fixed probability).  This adjustment procedure ensures that the optimal solution will, with high probability, be that special tour that you selected.  If you're lucky and you select a reasonable embedding, it will also not be so easy to recognize where you hid the special solution.

This approach is derived from general ideas in cryptography, where we want to create trapdoor one-way problems: where the problem is hard to solve without knowledge of the secret trapdoor, but with knowledge of the secret trapdoor, the problem becomes very easy.  There have been many attempts to embed secret trapdoors into a variety of hard problems (while still preserving the hardness of the problem even after the trapdoor has been added), with mixed degrees of success.  But this general approach seems like it might workable, for your purposes.

The resulting problem instances might be hard, but will they be interesting, from any practical perspective?  I don't know.  Beats me.  They look fairly artificial to me, but what do I know?

If your primary goal is to select problem instances that are practically relevant and representative of real-world applications of TSP, my suggestion would be take a totally different approach.  Instead, start by surveying real-world applications of TSP, then looking for representative instances of those problems, and convert them to their corresponding TSP problem instance -- so you are working with problem instances derived from a real world problem.


Complexity of finding the largest induced subgraph with all even degrees

The problem is NP-complete. We'll make a series of reductions from max-cut to show this.

Problem 0 (your problem): Given a graph $G$, does G have an induced subgraph with at least k vertices, such that all vertices have even degree within the subgraph?

Problem 1: Given a graph $G$ and subset $A$ of vertices, does $G$ have an induced subgraph with at least $k$ vertices in $A$, such that all vertices have even degree within the subgraph?

Problem 2: Given a graph $G$ and subsets $A, B$ of vertices, does $G$ have an induced subgraph with at least $k$ vertices in $A$, such that all vertices in $B$ have even degree within the subgraph?

Max-cut: Given a graph $G$, does there exist a cut $C \subset V$ of size $|\delta(C)|$ at least $k$? (where $\delta(C)$ is the set of edges in $E$ with exactly one endpoint in $C$)

We'll reduce max-cut to problem 2, problem 2 to problem 1, and finally problem 1 to problem 0, proving that your problem is NP-complete.

First we reduce the max-cut problem to problem 2. Given graph $G = (V, E)$ and $k$, we'll construct $G' = (V', E')$ and $A, B$ such that $G$ has a cut of size at least $k$ if and only if $G'$ has an induced subgraph with at least $k + |E|$ vertices in $A$, where every vertex in $B$ has even degree.

For every $v_{i} \in V$ we'll have a node $v_{i}'$ in $V'$. For every edge $e_{i} = (v_{x_{i}}, v_{y_{i}}) \in E$ we'll have nodes $e'_{i, 0}, e'_{i, 1}$ in $V'$, and edges $(e'_{i, 0}, e'_{i, 1}), (e'_{i, 0}, v'_{x_{i}}), (e'_{i, 0}, v'_{y_{i}}), (e'_{i, 1}, v'_{x_{i}}), (e'_{i, 1}, v'_{y_{i}})$. We'll set $A = B = \bigcup_{i = 1}^{|E|} \{e'_{i, 0}, e'_{i, 1}\}$.

Now, note that if we have exactly one of $v'_{x_{i}}$ or $v'_{y_{i}}$ in our subgraph, we can have both of $e'_{i, 0}$ and $e'_{i, 1}$. However, due to the degree constraint, if we have both or neither of $v'_{x_{i}}, v'_{y_{i}}$, we can have at most one of $e'_{i, 0}$ and $e'_{i, 1}$.

Take a cut $C \subset V$ in $G$ of size $k = |\delta(C)|$. We'll build $C' \subset V'$ s.t. $|C' \cap A| = |E| + k$, and every vertex in $B$ has even degree in the subgraph induced on $C'$. We set $v'_{i} \in C'$ iff $v_{i} \in C$, $e'_{i, 0} \in C'$ for all $i$, and $e'_{i, 1} \in C'$ for $e_{i} \in \delta(C)$. This construction has the claimed properties.

Next take $C' \subset V'$ s.t. $|C' \cap A| = |E| + k$, and and every vertex in $B$ has even degree in the subgraph induced on $C'$. Then we'll build a cut $C \subset V$ of size at least $k$. To do this, just set again $v_{i} \in C$ iff $v'_{i} \in C'$. Now since $|C' \cap A| = |E| + k$, there are at least $k$ edges $e_{i}$ s.t. both $e'_{i, 0}$ and $e'_{i, 1}$ are in $C'$. But for those $i$ we have $e_{i} \in \delta(C)$, hence $|\delta(C)| \geq k$ as desired.

Next we reduce problem 2 to problem 1. Given graph $G = (V, E), A, B$ and $k$, we'll construct $G' = (V', E')$ and $A'$ s.t. $G'$ has an induced subgraph with at least $2k$ vertices in $A'$ where every node has even degree in the induced subgraph if and only if $G$ has an induced subgraph with at least $k$ vertices in $A$ where every node in $B$ has even degree in the induced subgraph.

To build $G'$, We'll make two copies of $G$: for every node $v_{i} \in V$ we'll have nodes $v'_{i, 0}$ and $v'_{i, 1}$ in $G'$, and for every edge $e_{i} = (v_{x_{i}}, v_{y_{i}})$ in $E$ we'll have edges $e'_{i, 0} = (v'_{x_{i}, 0}, v'_{y_{i}, 0})$ and $e'_{i, 1} = (v'_{x_{i}, 1}, v'_{y_{i}, 1})$ in $E'$. Additionally, for every $v_{i} \in B^{c}$, we'll add a new vertex $m'_{i}$, and the edges $(v'_{i, 0}, m'_{i})$ and $(v'_{i, 1}, m'_{i})$. We set $A' = \{v'_{i, 0}, v'_{i, 1} \mid v_{i} \in A\}$.

Take a subgraph $C \subset V$ such that $|C \cap A| = k$ and vertices in $B$ have even degree in the graph induced on $C$. We'll build $C'$ s.t. $|C' \cap A'| = 2k$ and every vertex has even degree in the graph induced on $C'$. To do this, set $v'_{i, 0}, v'_{i, 1} \in C'$ if and only if $v_{i} \in C$. Then, for $v_{i} \in B^{c}$ with odd degree in the graph induced on $C$, we add $m'_{i}$ to $C'$. Now every vertex has even degree in the graph induced on $C'$, since vertices in $B$
have the same degree as in the graph induced on $C$ (hence even degree), we made vertices in $B^{c}$ have even degree, and since $C'$ is the same in both copies of the graph, every vertex $m'_{i}$ has degree $2$ or $0$. Clearly $|C' \cap A| = 2k$.

Now take any subgraph $C' \subset V'$ s.t. $|C' \cap A'| \geq 2k$, and every vertex has even degree in the graph induced on $C'$. We'll construct $C$ s.t. $|C \cap A| \geq k$, and every vertex in $B$ has even degree in the graph induced on $C$. To do this, we first build $C_{0}, C_{1}$, where $v_{i} \in C_{0}$ iff $v'_{i, 0} \in C'$, and $v_{i} \in C_{1}$ iff $v'_{i, 1} \in C'$. Note that $|C_{0} \cap A| + |C_{1} \cap A| = |C' \cap A'| \geq 2k$, hence WLOG $|C_{0} \cap A| \geq k$, and we set $C = C_{0}$. If some vertex $v_{i}$ in $B$ had odd degree in the graph induced on $C$, then $v'_{i, 0}$ would have odd degree in the graph induced on $C'$, hence $C$ has the claimed properties.

The reduction of problem 1 to problem 0 is by far the easiest, and I won't write a detailed proof here. The idea is to add for every vertex $v_{i}$ in $A^{c}$ the vertex $v'_{i}$ and the edge $(v_{i}, v'_{i})$, and finally subtract $|A^{c}|$ from $k$. Now every maximal solution includes one of $v_{i}$ and $v'_{i}$, but cannot include both, since then $v'_{i}$ would have odd degree, hence including $v_{i}$ no longer increases the size of the graph we're inducing on.


Orlicz norm of random variable and variance

The Kearns-Saul inequality states that if $X\sim Ber(p)$ then
$$ E[\exp(t(X-p))] = (1-p)e^{-tp}+pe^{t(1-p)} \le \exp\left(\frac{1-2p}{4\log((1-p)/p)}t^2\right).$$

The subgaussian constant $\frac{1-2p}{4\log((1-p)/p)}$ is optimal.
See http://ecp.ejpecp.org/article/view/2359 and especially the appendix in http://www.jmlr.org/papers/v16/berend15a.html for background and a slick proof.

The K-S inequality is a considerable improvement over Hoeffding and Bernstein for very small/large $p$.


Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

To me, your question seems analogous to saying "I've heard that non-Euclidean geometry requires me to give up Euclid's fifth axiom, which is very useful in many mathematical contexts." You don't have to give up the axiom in the sense of "personally agree, at a basic philosophical level, that it doesn't hold", you just have to think of it in terms like: "As a thought experiment, what sort of mathematics results if we assume it doesn't necessarily hold?"

Also, you might be interested in these blog posts by Andrej Bauer: "The Law of Excluded Middle" and "Proof of negation and proof by contradiction".


What are the main sub-areas of theoretical computer science?

Also I wonder if 'size' is the right metric. that tends to vary as subfields come in and out of fashion. For example, a visitor from the 1980s would be very puzzled as to where all the parallel algorithms disappeared to. Someone attending SoCG in the last five years would think that we should call it the Symposium on Computational Topology :).

Maybe the best thing to do is to let the student browse proceedings from theory conferences to get a sense of what's in vogue RIGHT NOW, and emphasize that this answer will change over time.


Competing against an optimal weighted majority in experts algorithm

If you don't mind randomization, then standard online learning algorithms in the "online convex optimization framework" give you essentially what you ask for, in expectation. The reason is that these algorithms are required to output a distribution $w \in \Delta([n])$ on experts at each time step, suffering an expected loss equal to the expectation of picking an expert from this distribution. And they have low expected regret compared to the best distribution on experts, i.e. $O(\sqrt{\ln n / T})$.

For example, you can take the classic multiplicative weights algorithm, which is just weighted majority but picking an expert to follow with probability proportional to its "weight". This is mentioned in Arora's survey (Theorem 6): https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf


Can you identify the sum of two permutations in polynomial time?

No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem $2$-Numerical Matching with target sums:

Input: Sequence of $a_1, a_2, \ldots a_n$ of positive integers, $\sum_{i=1}^n a_i = n(n+1)$, $1 \le a_i \le 2n$ for $1 \le i \le n$

Question: Are there two permutations $\psi_1$ and $\psi_2$ such that $\psi_1(i)+\psi_2(i)= a_i$ for $1\le i \le n$?

In the reference, a severely restricted variant of NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) was proven to be strongly NP-complete.

  RN3DM, Given a multiset $U = \{u_1, . . . , u_n\}$ of integers and an integer $e$ such that $\sum_{j=1}^n  u_j +
n(n + 1) = ne$ , do there exist two permutations $\lambda$ and $\mu$ such that
  $u_j + \lambda( j ) + \mu( j ) = e$, for $j = 1, . . . , n$?

There is an easy reduction from RN3DM to $2$-Numerical Matching with target sums problem:
Given an instance of RN3DM. We construct the corresponding instance by making $a_i= e-u_i$ for $1 \le i \le n$

W. Yu, H. Hoogeveen, and J. K. Lenstra.
Minimizing makespan in a two-machine flow shop with
delays and unit-time operations is NP-hard. Journal of
Scheduling, 7:333–348, 2004

EDIT Oct. 1st: Your problem is called PERMUTATION SUMS. It is listed since 1998 in OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION by Steve Hedetniemi.


Avoiding Cycles with Unification and Subtyping

From what I understand, it is likely that your subtyping constraints will always be of the form $\alpha \subseteq A$ or $A \subseteq \alpha$, where $\alpha$ is a unification variable. If that is the case, then one idea would be to follow a kind of occurs-check discipline. One thing that you can do to eliminate cycles is to maintain the invariant that there is a solution to your system. The solution that is the easiest to built (but the least general in some sense) is to set $\alpha := A$ for all constraints of the form $\alpha \subseteq A$, and to set $\alpha := \top$ for all constraints of the form $A \subseteq \alpha$ (and there is probably some work to do if $\alpha$ appears to the left/right of several constraints). For this solution to be valid, the simultaneous instantiation of all the unification variables should not induce a cycle in their definition. To do that, you can construct a form of dependency graph on unification variables, in which $\alpha$ depends on the unification variables of $A$ for each constraint $\alpha \subseteq A$. You then need to ensure that the obtained graph does not contain cycles.


What does "number of inputs to each neuron" mean in Neural Network terms?

You are bypassing the "hidden layer": A neural network consists of three layers: Input layer, hidden layer, and output layer:

You may also have more than one hidden layer:

(source: mu-sigma.com)

Though, in your case, since the number of hidden layers is not specified, it is safe to assume that there is just 1 hidden layer.

So, for example, in a 3:1 network, you have 1 output neuron, and 3 hidden neurons. The number of inputs shows the number of neurons in the input layer.


Possibility of hierarchy with $UP$ class?

Problem 2. answered in references

a. https://arxiv.org/pdf/cs/9907033.pdf

b. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&rep=rep1&type=pdf.


Complexity of hex with random turn order.

You might want to look at the paper "Random-Turn Hex and Other Selection Games," by Yuval Peres, Oded Schramm, Scott Sheffield, and David Wilson. From the introduction:

  "Random-Turn Hex is the same as
  ordinary Hex, except that instead of
  alternating turns, players toss a coin
  before each turn to decide who gets to
  place the next stone. Although
  ordinary Hex is famously difficult to
  analyze, the optimal strategy for
  Random-Turn Hex turns out to be very
  simple."

So indeed, your intuition was right: this will be in BPP (or maybe P).


What CS theories are absolutely paramount for someone new to TCS to understand?

(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella.
Apologies for the length.)

A small digression

You are asking for topics in TCS which

are "hot" in theoretical CS right now
are useful for innovative applications in software/hardware in the next future

From the way you pose the question, I am led to think that you believe that the two requirements above largely overlap, and/or that only bleeding edge research in TCS can have some impact in future technologies. If that is the case, I would instead argue that the overlap is instead much smaller.

First, CS theory is usually very far ahead most applications.
This is not unlike theory in other science disciplines. In the past, some great theoretical developments took much time to influence the industry.
A few examples:

Turing's vision of computers influenced automatic computers
Church's $\lambda$-calculus influenced programming languages
Higher order functional programming influenced Google's map/reduce
System F influenced generic types of Java (and C#, Scala, etc.)
System F$\omega$ influenced Scala higher kinds
Dependent types influenced Haskell GADTs
Church-style encodings of algebraic data types influenced the "visitor pattern" in OOP
Category theory influenced functional programming
Constructive/intuitionistic logic influenced type systems

These influences did not happen overnight. If history repeats, some new
technology tomorrow is more likely to draw from old-ish theory (relatively speaking) than bleeding edge discoveries.

Second, while some theoretical research is directed by some clear applications, sometimes research is driven by curiosity: when we discover a new approach and the first results appear to lead to an elegant theory, which reshapes our way of thinking about some topic, then we follow that direction. Often, even if we can't find a practical application right now, we still want to know how far we can go!

Third, some of the most powerful theory involves negative results. These, on the one hand do not tell us how to solve problems, but on the other hand tell us to avoid wasting resources trying to achieve the impossible.

For instance, computability theory tells us that we cannot precisely count the number of pages in a PostScript document (!), so we need to either move to better document formats or live with some approximate solution. Dually, we learn that if we design a new media format, we should try to avoid the same issues.

Another example: the so-called "free theorem", or parametricity property, can be used to prove the impossibility of writing a function with a certain polymorphic (or generic) type, in some languages.

Another: the Curry-Howard isomorphism can be used for a similar goal, proving the impossibility of a hypothetical program. (Shameless plug: I once used that to answer a Scala question on StackOverflow)

Some suggested "paramount" topics

(The following lists are not, by any means, complete. I only wrote the first topics that came to my mind.)

I would recommend the following topics as the bare minimum.

[Logic] Classical propositional logic. First order logic. Naive set theory.
[Computability] Decidable and semidecidable problems. Rice theorem. Many-one reduction.
[Computational complexity] P vs NP. Completeness / hardness. Polynomial reduction.
[Programming languages] $\lambda$ calculus: untyped & simply-typed. Church encodings (for untyped). Fixed points vs recursion.

These are more advanced. I would not recommend to study them all, albeit maybe one should know what these topics are about, at least. Having even a superficial understanding of these can help in keeping the mind open.

[Logic] Intuitionistic logic. ZFC set theory. Linear logic.
[Geometry] Basic topology.
[Domain theory] Posets. $\omega$CPOs. Complete lattices. Scott topology. Fixed point theorems (Tarski, Kleene). Induction  ($f(x)\sqsubseteq x \implies \mu f \sqsubseteq x$). Coinduction.
[Computability] Rice-shapiro.
[Type theory] Polymorphic types (System F). Dependent types and recursive/inductive types (Calculus of Constructions, Coq, Agda, etc.). Curry-Howard. Homotopy type theory (hot topic).
[Category theory] Products/coproducts. Functors. Natural transformations.
$F$-algebras/coalgebras.
[Programming languages] Imperative, functional, and logic programming. Formal semantics: operational (small and big step), denotational, axiomatic (Hoare logic). Continuations.
[Model checking] Temporal logics (modal $\mu$ calculus, CTL, LTL, etc.). SAT-solvers. SMT-solvers.
[Concurrency] Petri nets. Process algebras.

These are even more advanced or hotter topics.

[Programming languages]  Verification. Abstract interpretation. Gradual typing.
[Category theory] Cartesian closed categories. More "abstract nonsense" in general.
[Model checking] SAT-solvers. SMT-solvers.
[Type theory] Homotopy type theory (hot topic).
So. Many. Others.

And finally,

the topics mentioned in the digression above :-)

Most, if not all, these topics have had a deep influence on the design of modern programming languages. Some of these can also affect the way we think rather deeply. Here's a few examples from my experience.

When stuck in writing a correct while loop, one might stop and try to think about the loop invariants, and solve the issue. Of course, this only happens if one has seen Hoare logic before.

Remembering certain programming techniques can be hard. Sometimes, theory can help to quickly recall / reconstruct such techniques. For instance, above I mentioned the visitor pattern. Its definition can be recovered remembering that recursive types are interpreted as initial $F$-algebras, so by initiality, we immediately obtain an associated type
$$
\mu F \to \forall \alpha.\ (F\alpha \to \alpha) \to \alpha
$$
So, in OOP, we would take the object (of recursive type $\mu F$), the visitor (of type $F \alpha \to \alpha$), and must return the result of the visitor ($\alpha$). Translating this into OOP, say Java, is routine.

This might look as gibberish before studying these topics, but I believe one
can see that, in this way, a one-line theoretical description can summarize a complex technique like the visitor pattern.

Concluding, I hope I managed to show that the topics above have had an impact on software, and probably will have more in the future. I also hope this does not feel too overwhelming, especially since it's only about the PL part of TCS! :-)


Site with collection of exercises in TCS?

100 exercises in the theory of automata and formal languages

https://algomuse.net/
It's a kind of competition but problems are from research papers.

Here http://www.openproblemgarden.org/
Some problems have hints.

https://a3nm.net/work/research/questions/#other-lists-of-open-problems

In this book, each chapter have some exercise:
https://files.boazbarak.org/introtcs/lnotes_book.pdf


Perhaps one must consider the parent of the node to be inserted as having weight 2. Then the "find the lowest in-density ancestor" is equivalent to "find the least amount of rebuilding needed to maintain the invariants".

edit:

In the physical world, density is defined as mass divided by volume. This corresponds to the density notion in these cache-oblivious B-trees if we view each "item" as having mass 1 and each location in $\mathcal{T'}$ (the static binary tree) as having volume 1.

Before inserting an item, we want to make sure that once it is in the tree it is in a subtree that is within its prescribed density bounds. We therefore imagine that it is already there in the tree, but taking up no space yet. The reason why we might imagine that it presently takes up no space is that, well, there might not be any space for it to take up right now, as in your example.

To make sure that the tree the new item will be in is within bounds, we need to find its closest ancestor that we actually can rebalance (without increasing the height) and insert the item into while still remaining within the density boundaries. To do so, we find the nearest ancestor that will be within the density boundaries, which means using its current "volume" and its soon-to-be-correct "mass". To get the latter, we must include an extra unit of mass for the item we are about to insert.


Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?

Paterson and Stockmeyer show that for most $n$-tuples of rational numbers $(a_1, \dotsc, a_n)$, evaluating $\prod_{i=1}^{n} (x - a_i)$ requires $\Omega(\sqrt{n})$ arithmetic operations, and this is tight.

The following polynomials get within a logarithmic factor of the $\sqrt{n}$ bound, by results of Strassen, Schnorr, and Heintz & Sieveking: $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$, $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$, $\sum_{i=1}^{n} i^{r} x^{i}$ (for $r$ a rational that is not an integer), etc.  For exact references and for more on this, see pp. 324-325 of von zur Gathen's survey.


Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?

I'd like to offer some pointers.

  Is there any research that goes along these lines and perhaps formalizes this intuition?

Parametricity by analysis of the shape of (simply-typed) normal forms preceded by a normalisation argument was proposed by Girard, Scedrov, and Scott [1]. This connects parametricity, cut-elimination in logic, and a proof technique for coherence in category theory. Here, parametricity is understood as a property of dinaturality, originally proposed for system F in [2].

  Is this idea correct and strong enough to prove (by case analysis on the normal forms of the terms) 'free theorems' or more general parametricity results?

In [1], it is noted that this includes the so-called "free theorems" as a special case. But the argument does not extend to all of system F, and dinaturality fails to capture relational parametricity (see e.g. [3]). On the other hand, a work by Paolo Pistone shows that one indeed thus obtains a syntactic characterisation of parametricity for a class of types a bit larger than the simple types including your examples [4]:

  Our results imply that, for positive second order types, realizability, parametricity, dinaturality and typability are equivalent properties of closed normal lambda-terms.

So there is indeed an elementary technique based on looking at shapes of normal forms, which provides a syntactic characterisation of some parametricity results including the "free theorems", that also hints at a connection with categorical coherence.

[1]: Girard, J.-Y.; Scedrov, A. & Scott, P. J. Normal Forms and Cut-Free Proofs as Natural Transformations. Logic From Computer Science, Mathematical Science Research Institute Publications 21, Springer-Verlag, 1992, 217-241.
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.811

[2]: Bainbridge, E. S.; Freyd, P. J.; Scedrov, A. & Scott, P. J. Functorial polymorphism. Theoretical computer science, Elsevier, 1990, 70, 35-64.
https://core.ac.uk/display/82270459

[3]: De Lataillade, J. Dinatural Terms in System F. Logic in Computer Science, 24th Annual IEEE Symposium, 267-276, 2009. https://www.irif.fr/~delatail/dinat.pdf

[4]: Pistone, P. On completeness and parametricity in the realizability semantics of System F. https://arxiv.org/abs/1802.05143


Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?

One approach is described by

Georgios Fourtounis and Nikolaos S. Papaspyrou. 2013. Supporting Separate Compilation in a Defunctionalizing Compiler. SLATE 2013.

As @gasche mentions:

  A different approach at the problem would be to consider that each module can define its own "defunctionalized functions" type and dispatcher/handler.

You can "link" those types and handlers with a specialized linker.
Unlike using open datatypes, you concatenate the list of constructors and the case functions.
But the linker must add cases for partial application: Without whole-program analysis, you cannot predict which partial applications can be used for which function, so you add all cases. An $n$-ary function can be partially applied to $i$ arguments (with $0< i < n$) and produce a function of arity $n-i$, which can be partially applied again.


Another beautiful example of the price of abstraction: network coding. It's known that in multicast settings, the max-flow-min-cut relation is not one of equality (the primal and dual don't match). However, the traditional models assume flow that's merely passed on and not "processed" in any way. With network coding, you can beat this limit by cleverly combining flows. This example was a great motivator for the study of network coding in the first place.


Linear ordering from weighted directed graph (kittens)

Sorry for the brevity, maybe I can come back and expand later. There is work in voting and modeling voters that should be relevant. For example, take a model, i.e. in Mallows model, if A is truly cuter than B, then with probability $p > 0.5$ I rank $A$ ahead of $B$ and otherwise I rank B ahead of A. All rankings are made independently.

Then the corresponding voting rule is to compute the MLE underlying "true" ranking that generates the votes we've seen. For this particular model it is the Kemeny rule and it's NP-hard, but there are other models too.

...

(expansion) Condorcet in the 1700s first used the MLE idea. Say that every voter produces a ranking, and in that ranking any given pair of candidates are in the "correct" order with probability $p > 0.5$. Then, given a bunch of people's votes, we want to compute the single linear order that had the highest probability of generating those votes, the MLE. Young showed that the solution of this is the Kemeny voting rule, which minimizes the average bubblesort distance to all the rankings we are given.

Conitzer and Sandholm ('05) extended this idea to other voting rules, with other noise models (e.g. I put the best candidate in the $n$th place with probability $2^{-n}$).

Since then there's been work, e.g. by Xia and Conitzer (09), on extending these ideas to when people don't see the whole list of alternatives, but just get to see some of the alternatives (submit partial orders). This should be relevant to your setting, I think. There is also at least some empirical-type work in this vein. I am thinking specifically of Pfeiffer et al (12). The setting is basically the same as yours. They have some sort of adaptive strategy of which kitten pair (or whatever they used) to show to the next voter. The goal was to get a good ranking with fewer pairwise comparisons (i.e. not asking every voter to rank all the kittens).

That's what I know of the theoretical and AI work. There's also a lot of statistics that I know less about. Probably the stats will be most helpful if you want to actually implement something that aggregates partial rankings/observations.

I know that some of the most popular statistical models for these things are the Mallows model, Bradley-Terry, and Plackett-Luce. All of these are noise models for how voters randomly generate a ranking given the true underlying "correct" ranking. In fact, there is so much work about this going on in statistics that I might suggest you post on stats.se, because I am woefully ignorant but I think they (or perhaps the machine learning community as well) have a lot of work on algorithms for (approximately) finding solutions (e.g. the MLE) given a bunch of rankings and assuming that they were generated using one of these models. At least, I hope these keywords help you in your search!


What are some good references for mathematical optimization for the layman?

This is a very vast topic. For nonlinear optimization the book by Bertsekas is a standard reference. For convex optimization you should look at Boyd and Vandenberghe. For linear programming, the book by Schrijver is a reasonable (but dense) source.

But you should also look at course material. Each of the authors mentioned above also has course material/lecture slides that might be useful.


Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

Yes.

I took the four screenshots  0,1,2,3  of this answer in case is doesn't render correctly.

Alexey did not specify that the outputs are bounded-length (that was edited in by Kaveh),

so I do not assume that.    Note that  L $\subseteq$ NL $\subseteq$ NC2 $\subseteq$ DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$ .

In this answer, "strings" without further clarification may continue infinitely to the right.

The part of this answer between here and the at-symbol applies

to all probabilistic automata with at most $C$ configurations;

even those with, for example, irrational transition probabilities.

Consider any positive integer $j$. $\;\;\;$ Since probabilities are non-negative and add to one,

there are less than $j$ $x$s such that $\: 1/j < \operatorname{Pr}[\text{Automaton outputs }x] \;$. $\;\;\;$ Consider any such $x$.

For strings $s$, say a configuration is bad for $s$ if the probability of the automaton outputting $s$

from the configuration is at most $1/j$, and good for $s$ otherwise. $\:$ Say a configuration

is good if the configuration is good for at least one suffix of $x$, and bad otherwise.

$\operatorname{Pr}[\text{Automaton outputs }x \;\; | \;\; \text{Automaton reaches a bad configuration}]$
$\leq$
$1/j \: < \: \operatorname{Pr}[\text{Automaton outputs }x] \;\;\;$,

so it's possible for the automaton to output $x$ without reaching any bad configuration.

Probabilities are non-negative and add to one, so any given configuration is good

for less than $j$ strings. $\;\;\;$ The automaton has at most $C$ configurations, so there are

less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ strings for which there exists a configuration which is good for the string.

Since it's possible for the automaton to output $x$ while remaining in

good configurations, $x$ has less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ distinct non-empty suffixes.

Thus, either $x$'s length is less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ or $\big[x$ is eventually-periodic and the length

of [the pre-periodic part concatenated with the initial period] is less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \hspace{.02 in}\big]$.

Regard the former case as having period zero, so both of those cases are

covered by "pre-periodic part and initial period, each with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$".

Now, choose a family $H$ of hash functions with short output and domain equal to

$\big[$the set of strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \hspace{.02 in}\big]$, $\:$ such that for all distinct equal-length

elements $x_0$ and $y$ of their domain, if  $y\neq x$  then $\;\;\; \operatorname{Pr}_{h\leftarrow H'}[h(\hspace{.03 in}y) = h(x_0)] \: \leq \: 1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in}) \:\:\:\:$.

Let $x_0$ and $x_1$ be the pre-periodic part and initial period respectively of $x$.

For all strings $y_0$ and $y_1$ whose lengths are at most the lengths of $x_0$ and $x_1$ respectively,

$\operatorname{Pr}_{h\leftarrow H}\hspace{-0.06 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle\big]$
$\leq$
$\operatorname{Pr}_{h\leftarrow H}[\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle]$
$\leq$
$1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$

.   Since doing so will correspond to taking a weighted average, that will still apply when

$y_0$ and $y_1$ are chosen from a distribution independently of $h$.  In particular, it will still apply when

$\langle \hspace{.03 in}y_0,\hspace{-0.03 in}y_1\rangle \:$ is chosen according to the automaton's outputs so that $y_0$ is the first up-to-length($x_0$)

bits of the output and $y_1$ is the next up-to-length($x_1$) bits of the output.  Since the random

choice of $h$ from $H$ also corresponds to a weighted average, there is an $h$ from $H$ such that

$\operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}\hspace{-0.05 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle\big]$
$\leq$
$1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$

.   Let $h_0$ be such an $h$.

$1/j \: < \: \operatorname{Pr}[\text{Automaton outputs } x] \;\; \leq \;\; \operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}[\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.02 in}x_1\rangle]$
$=$
$\operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}\hspace{-0.05 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h_0(\hspace{.03 in}y_0),h_0(\hspace{.03 in}y_1)\rangle = \langle h_0(x_0),h_0(x_1)\rangle\big]$

,   so the probability of $\: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.03 in}x_1\rangle \:$ conditioned on

$\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \; \langle h_0(\hspace{.03 in}y_0),h_0(\hspace{.03 in}y_1)\rangle = \langle h_0(x_0),h_0(x_1)\rangle$

is greater than $2/3$.  In particular, for each element $i$ of

$\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, conditioned on the same event,

$2/3$$<$
$\operatorname{Prob}[\text{Automaton gives more than } i \text{ bits of output and}$

$\text{the }i\text{-th bit of the output equals the }i\text{-th bit of } x_0$||$x_1]$

.     Multiplying the number of states by  $4\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j$  lets the automata track $i$ and

for hard-coded $i_0$ from $\{0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, record the $i_0$-th output.

Now, for efficiency's sake, we must turn back to the hash family $H$.  Let $p$ be the

smallest prime that is not less than  $2\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}$ ,  and then use wikipedia's string hashing method.

For input length of at most one block, collisions are simply impossible.    Otherwise,

$\text{maximum_collision_probability} \leq \text{degree}\hspace{.02 in}/p \; = \; ((\text{number_of_blocks})\hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; \leq \; (\lceil (\text{input_length})/(\text{block_size})\rceil\hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; \leq \; (\lceil (\text{input_length})/1\rceil \hspace{-0.04 in}-\hspace{-0.04 in}1)/p \; = \;$

$(\lceil \text{input_length}\rceil \hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; < \; (\text{input_length})/p < (C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)/p \leq (C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)/(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}) \; = \; 1/(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)$

.     Thus wikipedia' string hashing method has small enough collision probability for this answer.

By Bertrand's postulate, $p$ will be less than  $4\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}$ ,  so for $j$ given in unary, logspace can find $p$

by trial division and do the arithmetic operations mod $p$.    In particular, NC2 can do the same.  Observe that wikipedia's string hashing method takes the input as a stream, so

(for $j$ given in unary) NC2 can find a deterministic finite automata for each hash in the $p$ family.

Thus, by a product construction, NC2 can get automata which will use any given

hash in the $p$ family to test both parts of the underlying automata's output -

If the underlying automaton would halt without having produced output or finish a part

not matching the target hash values, then the resulting automaton will enter a reject state;

if the underlying automaton gives enough output without either of those happening,

then the resulting automaton goes to Finalize0 or Finalize1,

determined by the value of the bit the underlying automaton was recording.

By the conditional probability I went over earlier, there is an $h_0$ is the $p$ family such that,

when that's done with $\operatorname{length}(x_0)$ and $\operatorname{length}(x_1)$ and $h_0(x_0)$ and $h_0(x_1)$, for each element $i_0$$\{0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, the probability of the resulting automaton finalizing the $i_0$-th bit of  $x_0$||$x_1$  is more than twice its probability of finalizing the other bit.    Clearly, for each such automaton, there is at most one pair  $\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle$  of $\big[$strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j\big]$ satisfying the previous sentence's condition.    Furthermore, the $p$ family and its outputs

are given by integers mod $p$ and the lengths are restricted to being less than  $C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j$ ,

so for $j$ in unary, NC2 can output a list of all such automata.
@
Now, assume that all probabilistic transitions are coin-flips, i.e.,

equal probability of going to each of 2 possible next-states:

There are only polynomially many possibilities for the workspace's contents, so the automata's sizes are polynomial.    Each transition probability is in {0,1/2,1}, so by Lemma 6.1, (for $j$ given

in unary) NC2 can determine whether there is a pair of $\big[$strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j\big]$ satisfying the condition in the paragraph just-before the at-symbol, and if so, find that pair.

There's almost certainly a simpler method, but as a brute-force for determining whether-or-not

the strings represented by such pairs are equal, NC2 can build the deterministic finite automata from those representations which give one output per step, construct their product, and check

whether-or-not that product automata reaches a state from which [exactly one halts or they

give different outputs].  Thus NC2 can (for $j$ given in unary) output a list of pairs such that

[each string which the Turing machine has probability greater than $1/j$ of outputting]

is the eventually-periodic string encoded in the obvious way by exactly one of the pairs in the list.

Now it's time to show that NC2 can find the probabilities of those strings being outputted.

We start by dealing with no-further-output scenarios.  Non-deterministic logspace can check whether-or-not there is a sequence of random bits which will cause further output from a given configuration, so NC2 can replace entering those configurations with entering the halt state.

The remaining configurations all have some way of giving output.  Since loops can be removed from any such way, it must be that for each non-halt configuration, there's a way to give output with at most number_of_configurations transitions.  Since non-zero transition probabilities are at least 1/2, one will have that for each non-halt configuration, the probability of giving output from there in

at most most number_of_configurations transitions is at least 1/(2^(number_of_configurations)).

That remains the case as long as it stays in configurations which weren't replaced with halt,

so for all positive integers t, the probability of it doing so for t steps without giving output

is at most (1-(1/(2^(number_of_configurations))))^(floor(t/(number_of_configurations)))

That goes to zero as t goes to infinity, so for each time and configuration-at-that-time, the probability of [giving no further output but not halting] is zero.  By countable additivity, the previous sentence remains true when "for each time and configuration-at-that-time," is removed, so the probability of [the total output being finite without the automata ever entering its halt state] is 0.

For infinite eventually-periodic strings, apply the previous paragraph, then further modify

the automaton to have it track its output's location in    the pre-periodic part  /  the period  ,

as applicable, and halt if it would output something other than the eventually-periodic

string's next bit.        The only other way for it to not output the whole eventually-periodic string

is its output being finite, so by the previous paragraph, the probability of it outputting the

eventually-periodic string is one minus the probability of it reaching the halt configuration.

For finite strings, apply 2 paragraphs ago then further modify the automaton

to track [the amount of output it has given, up to the string's length, inclusive],

enter an accept state if has outputted the whole string and would halt (for a reason other than

the following part of this sentence), and halt if it [hasn't finished outputting the string and

would output something other than the next bit] or would output more than the string.

By two paragraphs ago, its probability of outputting the string without entering the accept state is zero, so its probability of outputting the string equals its probability of entering the accept state.

By Lemma 6.1, given $j$ in unary, NC2 can compute those probabilities.  NC2 can also

compare those probabilities to $1/j$, so can strip out the pairs with probability at most $1/j$.

In summary, given $j$ in unary and an automaton whose probabilistic transitions

are coin-flips, NC2 can output a list of triples  $\langle \text{prob},\hspace{-0.02 in}x_0,\hspace{-0.02 in}x_1\rangle$  such that

the pairs formed by taking the right two entries from distinct triples

represent distinct eventually-periodic strings
and
for each such eventually-periodic string, the left entry of its triple

is the probability of the automaton outputting that string
and
each of those probabilities is greater than $1/j$
and
for each string x, if the probability of the automaton outputting $x$ is greater than $1/j$ then

$x$ is eventually-periodic and represented by the right two entries of one of the triples

.  (In light of this paper, I suspect Lemma 6.1 can be improved to put its problem in TC1.

If so, then TC1 can also do everything relevant to this answer that NC2 can do.)

Applying that to the OP's problem:

NC2 can round the probabilities down to fractions with denominator $j$ and remove the denominators.  Since $j$ is in unary, logspace can reduce mod $j$, and thus sample "as close to uniformly as possible" from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$.     Note that  $2\hspace{-0.05 in}\cdot \hspace{-0.05 in}\lceil \log_2(\hspace{.05 in}j)\rceil$  random bits are enough to make the error less than $1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$.    For the same reason, logspace can use the list of [triples with integer left entries] and the element from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$ to add the integers, stopping if/when the sum exceeds the element, and then [if that happened then output the eventually-periodic string indicated by the most recent triple's other two elements, else output $\bot$].

Thus NC2 can do those things after it computes the list, so DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$

can also do the same things.    That means DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$ can use

at most  $2\hspace{-0.05 in}\cdot \hspace{-0.05 in}\lceil \log_2(\hspace{.05 in}j)\rceil$  random bits to sample from a distribution such that, other than $\bot$,

the probabilities for each output are less than $3/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$ away from the original probabilities, and whenever the latter is greater than $1/j$, the resulting probability will be greater than $1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$.

Now, plugging in  $j = 2^k$  and [using just $k$ random bits] and $\big[$using the actual input machine's structure as a Turing machine to simulate reading from a $\left(\hspace{-0.04 in}O(S)\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^S\right)$-state automata whose probabilistic transitions are all coin-flips$\big]$ gives a  $O\hspace{-0.04 in}\left(\hspace{-0.03 in}(S\hspace{-0.04 in}+\hspace{-0.04 in}k)^{\hspace{.02 in}2}\hspace{-0.03 in}\right)\hspace{-0.02 in}$-space algorithm that uses $2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k$ random bits to sample from a distribution such that, other than $\bot$, the probabilities for each output are less than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$ away from the original probabilities, and whenever the latter is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$, the resulting probability will be at least $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$.    (Since $2^k$ is a power of two,

$k$ random bits is enough to choose the element from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$ perfectly uniformly.)

That achieves what you're after.


I am not sure there is any general characterization for equivalence, but the following papers by Hopcroft, and Hunt and Rosenkrantz resp. might be a good start:

John E. Hopcroft, On the equivalence and containment problems for context-free languages, Theory of Computing Systems 3(2):119-124,  doi:10.1007/BF01746517;
Harry B. Hunt, III and Daniel J. Rosenkrantz, On Equivalence and Containment Problems for Formal Languages, Journal of the ACM 24(3):387--396, 1977, doi:10.1145/322017.322020.

Hopcroft shows in particular that, if $M$ is regular, then $L(G)=M$ is decidable iff $M$ is bounded, i.e. there exist $n$ words $w_1,w_2,\ldots,w_n$ s.t. $M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$.


Running Simon's algorithm on D-wave machine

Short answer: No.

There are really two separate issues to unpack here:

Even if it worked exactly as advertised (which, as you might have heard, is somewhat disputed at present... :-) ), D-Wave's machine, by the company's own account, is only for adiabatic optimization.  There's no particular reason to think that it could implement (e.g.) Shor's factoring algorithm, or other algorithms in the usual quantum circuit model.
Even if you had a standard, universal quantum computer---so, not any of D-Wave's current or planned devices, but a "gate model" QC capable of running Shor's factoring algorithm and so forth---even then, Simon's algorithm in particular requires that the QC make quantum queries to a hypothetical black box.  So in order to run Simon's algorithm, you need some explicitly-computable function that "instantiates" the black box.  Right now, however, no one has a very clear idea whether there exist such explicitly-computable functions that satisfy the Simon promise, for which a classical algorithm couldn't also use the explicit descriptions to solve Simon's problem efficiently.  Note that Shor's and Simon's algorithms are very similar at some level.  The main advantage of Shor's over Simon's is that, with the former, we do know an explicitly-computable function---namely, the modular exponentiation function---that "instantiates" the abstract periodic black box (and that, moreover, has some practical importance...).


How to prove that Supremum preorder coincides with Hoare preorder?

I’m going to use normal notation, as the square symbols are a pain to typeset.

Proposition: Let $L$ be a complete lattice, and $B$ its set of completely join-irreducible elements. If every element of $L$ is a join of a subset of $B$, then the following are equivalent:

$\bigvee X\le\bigvee Y\implies \forall x\in X\,\exists y\in Y\,x\le y$ for all $X,Y\subseteq B$.

All $x\in B$ are completely join-prime, i.e., $x\le\bigvee Y\implies\exists y\in Y\,x\le y$ for all $Y\subseteq L$.

$L$ satisfies the infinitary distributive law $x\land\bigvee_{i\in I}y_i=\bigvee_{i\in I}(x\land y_i)$.

Note that condition 3 is not equivalent to its dual, and it is weaker than full complete distributivity.
Proof:
1 → 2: By the assumption on $L$, $\bigvee Y=\bigvee\{u\in B:\exists y\in Y\,u\le y\}$. Thus, if $x\le\bigvee Y$, then $\bigvee\{x\}\le\bigvee\{u\in B:\exists y\in Y\,u\le y\}$, hence by 1, there exists $u\in B$ and $y\in Y$ such that $x\le u\le y$.
2 → 1: For any $x\in X$, $x\le\bigvee X\le\bigvee Y$, hence $x\le y$ for some $y\in Y$ as $x$ is completely join-prime.
3 → 2: If $x$ is completely join-irreducible and $x\le\bigvee Y$, then $x=\bigvee\{x\land y:y\in Y\}$ by 3, hence $x=x\land y$ (i.e., $x\le y$) for some $y\in Y$ by complete irreducibility.
2 → 3: $x\land\bigvee_{i\in I}y_i\ge\bigvee_{i\in I}(x\land y_i)$ always holds. For the other inequality, since the left-hand side is a join of a subset of $B$ by assumption, it suffices to show that
$$u\le x\land\bigvee_{i\in I}y_i\implies u\le\bigvee_{i\in I}(x\land y_i)$$
for all $u\in B$. The premise implies $u\le x$, and since $u$ is completely join-prime by 2, there exists $i\in I$ such that $u\le y_i$. Then $u\le x\land y_i\le\bigvee_{i\in I}(x\land y_i)$.


Fast algorithm to distribute points evenly in a 2D grid

The optimal centroidal Voronoi tessellation for the infinite 2D grid is a hexagon tiling.

You can get one of these by placing points at even coordinates on even rows and odd coordinates for odd rows. Depends on the number of points you need.

Start with that then run Lloyd's algorithm for a few iterations to tidy up the corners and edges.

I would compute it offline on a unit square to good precision, then dilate it to your chosen rectangle with a simple linear transformation.


What is the computational complexity of the PageRank problem?

As pointed out on the wikipedia page you cite, PageRank is simply computing the eigenvector corresponding to the maximum eigenvalue of the (modified) adjacency matrix of the web graph.  Since this is simple linear algebra, it should definitely be in FP, if not much smaller classes.

Part of the issue with Google's implementation is that the web is so large that its adjacency matrix doesn't fit into the memory of any single (or even any 10,000) computers.  So although the complexity of PageRank is technically in FP, the scale at which Google is doing it doesn't really fit into the realm of traditional single-processor complexity.  To discuss the complexity of actually computing PageRank on a graph as large as the whole web, you'd at the very least have to consider some sort of distributed computation model.


Such a bound is not possible. Consider the case where $f$ is the distribution that is uniform over some set $S$ of size $2^{\delta \cdot n}$, and let $\tilde{f}$ be the distribution that with probability $\delta$ outputs a uniformly distributed element of $S$, and otherwise outputs a uniformly distributed string.

It is not hard to see that you can get from $f$ to $\tilde{f}$ you only need noise of at most $(1-\delta) \cdot 2^{-\delta \cdot n}$.  However, $H(f)= \delta \cdot n$ while $H(\tilde{f}) \approx (1 - \delta + \delta^2) \cdot n$. Thus, you get a difference of $(1 - \delta)^2 \cdot n$ for arbitrarily small $\delta$ for an extremely low noise.

In particular, you can set $\delta = \frac{\log(1/\varepsilon)}{n}$, and obtain noise $\varepsilon$ and entropy difference $\approx n - 2\log(1/\varepsilon)$.


Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)


Reducing factoring prime products to factoring integer products (in average-case)

This is not really an answer, yet it sheds some light on the difficulty of demonstrating such reductions.

The problem can be summarized as follows:
Let $\mathcal{A}$ be an algorithm which solves the INTEGER-MULT problem with non-negligible probability. Let this probability be at least $n^{-c}$, for some constant $c \in \mathbb{N}$ (when the size of input is $n$). Prove that there exists a PPT (probabilistic polynomial-time) algorithm $\mathcal{A}'$ which, uses $\mathcal{A}$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

Consider an algorithm $\mathcal{A}^*$ which solves the INTEGER-MULT problem if and only if the input $N$ has the special from $N = PQR$, where $P$ and $Q$ are primes of size $n/4$ and $R$ is a prime of size $n/2$, and otherwise fails. Moreover, on input an integer $N$ of the above form, it outputs $PQ$ and $R$. We first show that $\mathcal{A}^*$ has a non-negligible probability of solving the INTEGER-MULT problem. To this end, it suffices to find the fraction of $n$-bit integers of the special form, as this fraction bounds the success probability of $\mathcal{A}^*$ from below.

By prime number theorem, the number of primes whose size is $k$-bits is:

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

Therefore, the fraction of $n$-bit integers of the special form is:

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

which is non-negligible in $n$.

Therefore, one should be able to prove the existence of a PPT algorithm $\mathcal{A}'$ which, uses $\mathcal{A}^*$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

IMHO, this seems a very difficult task, since $\mathcal{A}^*$ only (partially) decomposes integers of the special form, and there does not seem to be a way to use it to decompose integers of the form $PQ$.


How to find the first $k$ points of high enough level using a priority search tree?

The tree is binary and has depth $O(\log(n))$ and the properties that:

for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent.
for any node $v$, all descendants in the left subtree have x-coordinate smaller than $v$, and all descendants in the right subtree have x-coordinate larger than $v$.

This means that your solution set from which you choose $k$ elements is actually a subtree one side (in the left/right sense) of what remains when a path is deleted, and can be traversed with DFS in $(\log(n)+k)$ time.  Note that the priority search tree may require dummy points at which you root subtrees to keep the depth low.

This paper may give some clarification: http://people.scs.carleton.ca/~michiel/MinMaxPST.pdf


How to compute K and n? [Item-based Collaborative Filtering]

My guess is that these are free parameters of the algorithm that you must set somehow.  For instance, you might evaluate different choices of these parameters on a set of training data to see which performs the best.  You could also use cross-validation or other techniques to evaluate different settings of these parameters.

Note that p.46 of the thesis says "This threshold value is based on the predicted ratings that are achieved after running the item-based collaborative filtering algorithm."  That sounds consistent with my interpretation above.

In general, I would recommend reading the original, published, peer-reviewed research papers on algorithms for this problem.  I would expect them to generally be of relatively high quality, and to be more likely to explain the algorithm and methodology in full (or cite a source that does).


Quadratic relationship between nondeterministic and deterministic space?

In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that if $G_k (n)$ is the number of distinct languages accepted by NFA's with $n$ states over a $k$-letter alphabet, and $g_k (n)$ is similarly the number of distinct languages accepted by DFA's, then for fixed $k \geq 2$

(i) $\log g_k (n)$ is, up to smaller order terms, asymptotically $kn\log n$

(ii) $\log G_k (n)$ is, up to smaller order terms, asymptotically between $(k-1)n^2$ and $kn^2$.


Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure?

It seems to me that the problem can be solved in constant space.

We perform a recursive procedure, and store only the parity of the number of negation gates seen on the path from the root to the current node.

At a leaf, if we have a variable and have seen an even number of negation gates, we set the variable to be true. Otherwise, if we have seen an odd number of negation gates, we set the variable to be false.

As before, at an AND or OR gate we first call recusively to the left, and then to the right if the value has not been determined.

Now if there exists a satisfying assignment, then the assignment defined above will satisfy the formula.