What graphs on $\mathbb{N}$ can be encoded as regular languages?

$\beta(E_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma.
If we assume that the language is regular, the pumping lemma tells us that there must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular.
A similar argument also demonstrates that $\beta(E_2)$ is not regular, and more generally demonstrates that for a graph to be regular, for any $(n, m)$ in the graph with $n$ greater than some finite cutoff $p$, there must be infinitely many $n'$ such that $(n', m)$ is in the graph.
Since both $E_1$ and $E_2$ fail this condition, they are not regular.


So people keep nagging me to post this even though it only solves a simplified
version of the problem.  Okay then :)

At the end of this, I will put some of what I learned from the paper of Ibarra and Trân, and why that method breaks down on our general problem, but perhaps still gives some useful information.

But first, we'll look at the simpler problem of trying to decide the set

$L = \{ 2^n \mid $ the ternary and binary representations of $2^n$ have both even length or odd length$\}$

Note how this has $2^n$ rather than $n$ as in the original problem.  In particular if the input number is not a power of 2, we want to reject it rather than attempt to calculate its length in any base.

This greatly simplifies matters: If the original number is written prime factorized as $2^{v_2} 3^{v_3} 5^{v_5} 7^{v_7} ...$, then for all the $v_i$ except $v_2$ we just need to check that they are all $0$.

This allows us to solve this simplified problem by using a wrapper around the old method (by Minsky I assume) of encoding the state of a $k$-counter automaton in the exponents of the prime factorization of the single variable of a multiplication/division automaton, which as noted in the OP above is pretty much equivalent to a 2-counter automaton.

First, we need a $k$-counter automaton to wrap.  We will use 3 counters, named $v_2$, $v_3$ and $v_5$.

The automaton will accept iff for the initial counter values, the ternary and binary representations of $2^{v_2}$ have both even length or odd length, and both $v_3$ and $v_5$ are zero.  When it accepts it will first zero all its counters.

Here is some code for that, in an assembly format similar to the OP (I've just added variables to the instructions).  I haven't actually tested it, since I have nothing to run it with, but I consider this a formality: 3-counter automata are well known to be Turing-complete, and to be able to construct any computable function of one of their initial values.

// Check that v3 and v5 are both zero.
                JZ v3, check5
                GOTO reject
check5:         JZ v5, init3
                GOTO reject
// Decrement v2 until it is zero, constructing 2^n in the process.  If 2^n
// was even, we will then pass to even2 with 2^n in v3; If 2^n was odd, we
// will pass to odd2 with 2^n in v5.
init3:          INC v3          // Set v3 to 1 = 2^0 to start with.
even1:          // We have decremented v2 an even number of times so far.
                // 2^decremented amount is in v3.
                JZ v2, odd2
                DEC v2
dup3to5:        JZ v3, odd1
                DEC v3
                INC v5
                INC v5
                GOTO dup3to5
odd1:           // We have decremented v2 an odd number of times so far.
                // 2^decremented amount is in v5.
                JZ v2, even2
                DEC v2
dup5to3:        JZ v5, even1
                DEC v5
                INC v3
                INC v3
                GOTO dup5to3
// The second part checks the ternary length of 2^n, which starts out in v3
// or v5 according to whether the *binary* length of 2^n (i.e. n+1) was odd
// or even.
odd2:           // v3 needs to have odd ternary length to accept.
                // It is simplest to consider 0 to have even length in both
                // binary and ternary.  This works out as long as we're
                // consistent.
                JZ v3, reject
trisect3to5:    DEC v3
                DEC v3
                JZ v3, even2
                DEC v3
                INC v5
                GOTO trisect3to5
even2:          // v5 needs to have even ternary length to accept
                JZ v5, accept
trisect5to3:    DEC v5
                DEC v5
                JZ v5, odd2
                DEC v5
                INC v3
                GOTO trisect5to3
accept:         HALT Accept
reject:         HALT Reject

The next step is then to re-encode the above in the exponents of a single variable automaton.  As the result is pretty long, I'll just describe the general method, but a full version (slightly "optimized" in spots) is on my website.

                JZ vp, label
                DEC vp
next:           ...

becomes (basically divide by p, and then do cleanup to undo if the division wasn't even):

                DIV p, next, ..., newlabel.fp-1
newlabel.f1:    MUL p
                GOTO newlabel.i1
...
newlabel.fp-1:  MUL p
                INC
newlabel.ip-2:  INC
...
newlabel.i1:    INC
                GOTO label
next:           ...

INC vp becomes MUL p. Individual JZ and DEC can first be changed into the combined form.  GOTO label and HALT Reject are unchanged.

HALT Accept would be unchanged, except that in our case we still have one final check to do: we need to ensure that there are no prime factors in the number other than 2,3 and 5.  Since our particular 3-counter automaton zeros the counters it uses when it accepts, this is simple: just test that the final variable is 1, which can be done by jumping to the code

                DEC     // BTW it cannot be zero before this.
                JZ accept
                HALT Reject
accept:         HALT Accept

The code on my website also has an initial check that the number isn't zero, which I've just realized is redundant with the v3, v5 zero checks, oh well.

As I mentioned, the above method works for the simplified problem, but it really has no chance of working for the general one, because:  In the general problem the precise value of every prime's exponent counts for deciding its general size and thus which lengths it has in various bases.  This means that:

We have no "free" primes to use for counters.
Even if we did have free primes for counters, we don't really have a way to extract all the necessary information from the infinitely many other primes whose exponent values do matter.

So let's end with an explanation of the gist of the general method from the above linked paper by Ibarra and Trân (freely downloadable version) for how to prove that certain problems aren't solvable by a 2CA, and how it annoyingly breaks down in our case.

First, they modify every 2CA into a "normal form", in which the two counters switch in "phases" between one only increasing and the other only decreasing until it reaches zero.  The number of states $s$ of this normalized automaton plays an important role in the estimates.

Then, they analyze this automaton to conclude that they can construct certain arithmetic sequences of numbers whose behavior are linked.  To be precise (Some of this is not stated as theorems, but is implicit in the proof of both of their two main examples):

If a number x is accepted by the automaton, without the size $v^x_i$ of the nonzero counter at the beginning of a phase $i$ ever going $\leq s$, then there exists an integer $D>0$ such that all the numbers $x + n D$, $n\geq 0$ are accepted.
If a set $X$ contains at least $s^2+1$ accepted numbers such that for each number $x\in X$ there is a phase $i$ such that $v^x_i\leq s$, then we can find $p, r\in X$, and integers $K_1,K_2$ such that

For every integer $n\geq 0$, either $p + n K_1$ and $r + n K_2$ are both accepted by the automaton, or both are rejected.

(Thoughts:

They require $x>s$ for $x\in X$ but I think this is actually unnecessary.  Actually so is that they are accepted.
Most of this should also hold for rejected numbers, as long as the rejection is by explicit halting rather than nontermination.)

For their own examples they also frequently use the fact that $D,K_1,K_2$ have no prime factors $>s$.  To prove impossibility, they then derive contradictions by showing that such arithmetical sequences cannot exist.

In our problem, getting a contradiction from this breaks down with the second case.  If we have $K_1 = K_2 = 6^k$, where $k$ is large enough that no number between $p$ and $r$ is divisible by either $2^k$ or $3^k$, then there will also be no powers of 2 or 3 between $p + 6^k n$ and $q + 6^k n$, so they are either both accepted or both rejected.

Point 1 can still be shown to be impossible, because powers of 2 and 3 mostly grow further and further apart.  And I believe I can show the second case impossible if $K_1\neq K_2$ (I've emailed @MarzioDeBiasi the argument).  So perhaps someone could use this information to restrict the form of the automaton further, and finally derive a contradiction from that.


Can we efficiently distinguish between P and BPP?

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if
there exists a language $L \in BPP$ such that for all $A \in PTM$,
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A.$$

Here as I understand it $L_A$ is the language accepted by $A$, $\langle A\rangle$ is a code for $A$, and $D$ takes such a code and outputs a string that may or may not be in $L$ or in $L_A$.

One particular way this could happen is if $D(\langle A)=\langle A\rangle$ for all $A$, or to write it more succinctly, $D(e)=e$ for all $e$. Instead of $L_A$ we may write $\phi_e$.

Then the condition is
$$e\in L\leftrightarrow e\not\in\phi_e,$$
or, if we consider a set to be identified with its characteristic function,
$$ L(e)\ne \phi_e(e).$$
This now starts to look like saying that $L$ is a diagonally non-computable (DNC) function as studied in computability theory.
There, we have two facts:

There is no noncomputable oracle $A$ such that with positive probability, a random oracle $B$ can compute $A$; and
with probability 1, a random oracle $B$ can compute a DNC function.
with probability 1, a random oracle $B$ cannot compute a DNC function taking values in $\{0,1\}$.

Here (1) is analogous to BPP=P which we don't know whether holds.
And (3) is analogous to the statement that, assuming BPP$\ne$P, a random oracle cannot produce a $D$ as you suggest.

To conclude, I don't have an answer to your question, but

  by a loose analogy with computability theory it seems somewhat implausible that such a function $D$ should exist even if BPP$\ne$P.


Dichotomy of the spectra of directed graphs

The answer to “alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component” is YES (though I don’t understand what is “alternative” about this statement, as it does not in any way disprove the conjecture).

As I already wrote in a comment, it is a not very difficult exercise to show that if $f\in\mathbb Z[x]$ is a monic polynomial, there exists a directed graph $G$ on $O(\deg(f)+\|f\|_1)$ vertices whose eigenvalues include all roots of $f$. This implies the statement above modulo the fact that such polynomials may have roots with exponentially small imaginary part, which I assumed to be easy to find in the literature on minimal root separation. However, I realized that such bounds are actually not as readily found as I expected, so I decided to write it as a proper answer for the record.

Several examples of polynomials with exponentially small root separation are listed by Schönhage [1], in particular the family of polynomials
$$x^n-2(cx-1)^2\qquad(n\ge3,c\ge2)$$
attributed to Mignotte [2] (which I cannot verify as I have no access to it at the moment). Now, these polynomials have each a pair of real roots near $1/c$ in distance $<2/c^{1+n/2}$, whereas we need a pair of complex roots. This is, however, easily accomplished by modifying the polynomial slightly: let
$$f(x)=x^n\mathbin{\color{red}+}(2x-1)^2=x^n+4x^2-4x+1.$$
Clearly, this polynomial has no positive real root (and no negative real root either if $n$ is even). Moreover, it is easy to show that it still has a pair of (necessarily non-real) roots in exponentially small distance to $1/2$; if I didn’t mess up the computation, these roots are approximately
$$z_\pm=\frac12\pm i2^{-1-\frac n2}+O(n2^{-n}).$$
Now, $f(x)$ can be written as the determinant of e.g. the $n\times n$ matrix
$$\begin{pmatrix}
x&-1\\
&x&-1\\
&&x&-1\\
&&&\ddots\\
&&&&x&-1\\
1&-4&4&&&x
\end{pmatrix}$$
and therefore as the characteristic polynomial of the adjacency matrix of the weighted directed graph $G_0$ on $n$ vertices $\{0,\dots,n-1\}$ with edges $i\to i+1$ of weight $1$ for $i=0,\dots,n-2$; $n-1\to0$ of weight $-1$; $n-1\to1$ of weight $4$; and $n-1\to2$ of weight $-4$. The eigenvalues of $G_0$ are thus exactly the roots of $f$, including $z_\pm$.

Finally, the eigenvalues of $G_0$ are included among eigenvalues of the unweighted directed graph $G_1$ on $2n+6$ vertices
$$0_+,0_-,\dots,(n-2)_+,(n-2)_-,(n-1)_+^0,\dots,(n-1)_+^3,(n-1)_-^0,\dots,(n-1)_-^3$$
with edges $i_+\to(i+1)_+$ and $i_-\to(i+1)_-$ for $i=0,\dots,n-3$; $(n-2)_+\to(n-1)_+^j$ and $(n-2)_-\to(n-1)_-^j$ for $j=0,\dots,3$; $(n-1)_+^0\to0_-$, $(n-1)_-^0\to0_+$; and $(n-1)_+^j\to1_+$, $(n-1)_+^j\to2_-$, $(n-1)_-^j\to1_-$, $(n-1)_-^j\to2_+$ for $j=0,\dots,3$.

References:

[1] A. Schönhage, Polynomial root separation examples, Journal of Symbolic Computation 41 (2006), no. 10, pp. 1080–1090, doi:10.1016/j.jsc.2006.06.003.

[2] M. Mignotte, Some useful bounds, in: Buchberger, Collins, Loos (eds.), Computer Algebra: Symbolic and Algebraic Computation, 2nd ed., Springer-Verlag, 1983, pp. 259–263, doi:10.1007/978-3-7091-7551-4_16.


How hard is it to find a "well-distributed" subset of models of a propositional formula?

Well, I don't know what the exact complexity class is, but the problem is hard: a polynomial-time algorithm for this problem would imply P=NP.  Just take $k=0$; then the answer to your problem is yes if and only if $\phi$ is unsatisfiable.  Therefore, any polynomial-time algorithm for your problem would imply P=NP.

If you don't like relying on the special case $k=0$, here's a related construction.  Let $\psi$ be a boolean formula on $n$ variables $x_1,\dots,x_n$.  Introduce $n+1$ new variables $y_0,\dots,y_n$.  Define the formula

$$\phi := (\psi \land y_0 \land \dots \land y_n) \lor (\neg y_0 \land \dots \neg y_n).$$

Set $k=1$ and $\alpha=n$.  If $\psi$ is satisfiable, the answer to your problem is no.  If $\psi$ is not satisfiable, the answer to your problem is yes.


What is the advantage of a transformation matrix in perspective projection?

One advantage of transformation matrices over direct calculations is that you can compose transformations simply by multiplying matrices. E.g. you might have different transformations for basic motions such as rolling, panning, or dollying the camera and doing similar things to the objects in the scene. Keeping track of all this in a direct calculation becomes an unmaintainable mess.


What are some examples of secret sharing schemes actually being used in real-world applications?

(Almost) Every modern HSM (hardware secure module, for cryptographic applications) uses Shamir secret sharing. So, no, secret sharing use is wide spread.


Lower bounds for linear satisfiability problem

I strongly suggest reading the more recent followup paper by Ailon and Chazelle, which avoids the whole infinitesimal issue entirely.  If you want to stick with my paper, please read the journal version (Chicago J Theoretical Computer Science 1999).  The SODA version has a major bug in Section 5, and (I think) the journal version explains the main proof much more clearly.


Connectivity of a random regular graph of degree $d$

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed that a random $d$-regular graph has nearly optimal spectral gap, with high probability.


Is infinitary logic a logic in the sense of Gurevich?

First question: A set $M$ is decidable if there is a Turing Machine which halts on all inputs and accepts all inputs $x$ with $x \in M$.

We try to encode $\bigwedge_{\phi \in X} \phi$ for arbitrary sets of $\mathsf{FO}[\tau]$-formulars $X$. Since, $\mathcal{P}(X)$ is uncountable there can be no code with finite alphabet. Hence, there can be no Turing Machine recognizing $\mathcal{L}_{\infty\omega}[\tau]$ for each $\tau$ (even for empty $\tau$). Hence, the syntax is undecidable.

Second question: Given a code which translates a Deterministic Turing Machine (DTM) $T$ into a $\tau$-Structure $\mathcal{T}$. We can write a $\mathsf{FO}$-formular $\varphi_k$ with

$$ \mathcal{T} \models \varphi_k \Leftrightarrow \textrm{ The DTM $T$ holds after $k$ steps on $\varepsilon$.}$$

If we reassign variables (forgot the previous states of the Turing Machine) we can modell this $\varphi_k$ with constant, finite number $m$ of variables which does not depend on $k$.

Hence,

$$ T \in H_\varepsilon \Leftrightarrow \mathcal{T} \models \bigvee_{k \in \omega} \varphi_k \in \mathcal{L}_{\infty \omega}^m.$$

Where $H_\varepsilon$ is the special Halting Problem. Consequently, the Model Checking Problem for $\mathcal{L}_{\infty \omega}^m$ is undecidable for sufficiently large $m$.


(More a comment than answer:)

Finite projective planes exist for values of n which are powers of a prime, and there are infinitely many values of n which are ruled out by a theorem of R.H. Bruck and H. Ryser, which was generalized to block designs by Chowla:

http://en.wikipedia.org/wiki/Bruck%E2%80%93Chowla%E2%80%93Ryser_theorem

n = 10, as was stated, was solved (no plane exists) by a computer search so the first value of n not ruled out by Bruck-Ryser is n = 12. However, the computer work did not seem to give new insights as to whether or not there are only the prime power planes. What seems to be needed are new mathematical methods for insight into the commonly made conjecture that only the prime power planes exist.


Dynamic Upper Envelope of lines in the plane

"someone" is right.  Timothy Chan's paper "Dynamic Planar Convex Hull Operations in
Near-Logarithmic Amortized Time" appears to solve the problem with insertions/deletions taking $O(\log ^{1+\epsilon}n)$ amortized time, and queries taking $O(\log n)$ time.  He solves your problem which is dual to the convex hull problem.


The edge sets whose deletion leaves a cluster graph can easily be described as a formula with one free variable (the edge set) in monadic second-order graph logic. Therefore, by an optimization version of Courcelle's theorem, the minimum cardinality set can be found in linear time for graphs of bounded treewidth, which obviously include the 2-trees.

See e.g. Arnborg, Lagergren, and Seese, "Easy problems for tree-decomposable graphs", J. Algorithms 1991.


Since I was myself somewhat confused, I begin by clarifying a few concepts in the question.

Collection. I see no reason to spend time rigorously defining what "collection" means when we can simply ask what happens for data structures in general. A data structure occupies a piece of memory and has some operations that may access that memory and that may be invoked by users. These users may be distinct processors or just different threads, it does not concern us. All that matters is that they may execute operations in parallel.

Lock-free. Herlihy and Boss say that a data structure is lock-free when a crashing user does not prevent further uses of the data structure. For example, imagine one pours water on a processor that is in the midst of inserting a node in a sorted set. Well, if other processors try later to insert into that sorted set, they should succeed. (Edit: According to this definition, it is the case that if a data structure uses locks then it is not lock-free, but it is not the case that if a data structure does not use locks then it is lock-free.)

With these definition, I think Herlihy and Boss basically say that the answer is to turn critical regions into transactions.

But, you may ask, does this have the same complexity? I'm not sure the question makes sense. Consider push(x) { lock(); stack[size++] = x; unlock(); }. Is this a constant time operation? If you ignore the locking operation and hence other users then you can answer YES. If you do not wish to ignore other users, then there really is no way to say whether push will run in constant time. If you go one level up and see how the stack is used by some particular algorithm, then you might be able to say that push will always take constant time (measured now in terms of whatever happens to be the input of your parallel algorithm). But that really is a property of your algorithm, so it doesn't make sense to say that push is a constant time operation.

In summary, if you ignore how much a user executing an operation waits for other users, then using transactions instead of critical regions answers your question affirmatively. If you don't ignore the waiting time, then you need to look at how the data structure is used.


What is the recognition complexity of k-uniform k-partite hypergraphs?

The problem is NP-hard for $k=3$ already.

Indeed, testing if a graph is tripartite (i.e., there exists a partition $V_1 \sqcup V_2 \sqcup V_3$ of its vertex set $V$ such that each edge is between two different subsets) is cleary NP-hard, as it is exactly equivalent to $3$-coloring.

Now, I reduce the problem of the question to that problem. Given a graph $G$, construct the 3-uniform hypergraph $H$ by adding to each edge $e = \{v_1, v_2\}$ a fresh vertex $v_e$. I claim that $H$ is tripartite iff $G$ is. Indeed, a tripartition of $H$ clearly gives a tripartition of $G$. Conversely, given a tripartition of $G$, we can construct a tripartition of $H$ by assigning each fresh vertex $v_e$ to the one available class of the partition. The reduction is obviously PTIME.


Circuits with oracles vs. Turing Machines with oracles

The best reference for relativized circuits is Chris Wilson's paper "Relativized NC"  http://www.springerlink.com/content/u727654246wu8662/

The second condition you have (downward closure of O_n) is not needed to get the equivalence say between P^O and uniform poly-size circuits with oracle O. Also your third condition should be thrown away, the size of the circuit will prevent access to O_m for m larger than the circuit size.


How to design an online algorithm for secretary problem with multiple players?

Per @usul's suggestion, consider the following online greedy algorithm $A$.  When bin $i$ is revealed, $A$ considers all subsets $S$ of not-yet assigned balls such that all balls in $S$ can fit together in bin $i$.  It chooses any largest such set, say $A_i$, then assigns all balls in $A_i$ to bin $i$.

The post asks for an algorithm that each ball can use independently.  To achieve this, just have each ball independently simulate $A$, and decide to join a given bin only if $A$ says it should.

Lemma 1. This greedy algorithm is 0.5-competitive.

Proof. Let $A^* = \bigcup_{i} A_i$ denote the set of balls assigned by $A$.  Let $O_i$ denote the set of balls assigned by OPT to bin $i$.  Let $O^* = \bigcup_i O_i$ be the set of all balls assigned by OPT.

The set $O_i \setminus A^*$ is one possible set that $A$ could have assigned to bin $i$.  Set $A_i$ is at least as large as this set, so $|O_i \setminus A^*| \le |A_i|$.  Summing over $i$ gives $|O^*\setminus A^*| \le |A^*|$.  That is, the number of balls assigned by OPT but not $A$ is at most the number assigned by $A$.  This implies the desired bound.  Specifically, as $O^* \subseteq A^* \cup (O^*\setminus A^*)$, it follows that
$$|O^*| \le |A^*| + |O^*\setminus A^*| \le |A^*| + |A^*| = 2|A^*|.~~~~~~~~\Box$$

If you want a polynomial-time algorithm, you can modify $A$ to choose each set $A_i$ so that it is within a factor of $1-\epsilon$ of the largest possible.  (E.g., to achieve $\epsilon=1/2$ just order the not-yet-assigned balls by increasing $w_{ij}$, and take as many as will fit in bin $i$.  Or use a PTAS at each step to achieve any fixed $\epsilon>0$.)  Then $|O_i \setminus A^*| \le |A_i|/(1-\epsilon)$ and the algorithm will be $(1-\epsilon)/(2-\epsilon)$-competitive.  (E.g. $1/3$-competitive for $\epsilon=1/2$.)

And just for the record, per OP's comment:

Lemma 2. No deterministic online algorithm has competitive ratio more than 0.5.

Proof. Consider the instance with two balls and two capacity-1 bins, where each ball has weight 1 for bin 1, but only the ball put by the online algorithm in bin 1 can fit in bin 2.$~~~\Box$


A sketch of a possible reduction to prove that it is NP-complete.

Informally it starts from a modified 3SAT formula used to show that 3SAT is ASP-complete (Another Solution Problem), and "follows" the standard chain of reductions 3SAT=>DIRECTED HAMCYCLE => UNDIRECTED HAMCYCLE => TSP

Start with a 3SAT formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ caluses $C_1,...,C_m$;
Trasform it to a new formula $\varphi'$ adding a new variable $t$ ...;
... and expanding each clause $(x_{i_1} \lor x_{i_2} \lor x_{i_3})$ to $(x_{i_1} \lor x_{i_2} \lor x_{i_3} \lor t)$;
From $\varphi'$ build the diamonds structure graph $G = \{V,E\}$ used to prove that DIRECTED HAMILTONIAN CYCLE is NP-Complete; suppose that each clause $C_j$ correspond to node $N_j$ in $G$;
Modify $G$ into graph $G' = \{V',E'\}$ replacing each node $u$ with three linked nodes $u_1, u_2, u_3$  and modify the edges according to the standard reduction used to prove the NP-completeness of UNDIRECTED HAMILTONIAN CYCLE from DIRECTED HAMILTONIAN CYCLE i.e. $u_1$ is the node used for incoming edges, $u_3$ is the node used for outgoing edges;
Convert the UNDIRECTED HAMILTONIAN CYCLE instance on $G'$ to a TSP instance $T$ in which all edges of $G'$ has weight $w = 1$, except the (unique) edge in the diamond going to the "positive" assignment of $t$ which has weight $w = 2$ (red edge in the figure below); finally the edges added to make $G'$ complete have weight $w = 3$.

Clearly the TSP instance $T$ has a simple cycle that visits all nodes which corresponds to the satisfying assignment of  $\varphi'$ in which $t = true$ (and this tour can be easily constructed in polynomial time), but it has total weight $|V'|+1$ (because it uses the edge that correspond to the assignment $t = true$ that has weight 2). $T$ has another simple cycle that visits all nodes with a lower total weight $|V'|$ if and only if the edge of weight $2$ that corresponds to the assignment $t = true$ is not used; or equivalently if and only if there is another satisfying assignment of $\varphi'$ in which
$t = false$ ; but this can be true if and only if the original formula $\varphi$ is satisfiable.

I'll think more about it, and I'll write a formal proof (if it doesn't turn out to be wrong :-).
Let me know if you need further details about one or more of the above passages.

As noted by domotorp an interesting consequence is that the following problem is NP-complete: Given a graph $G$ and an Hamiltonian path in it, does $G$ have an Hamiltonian cycle?


Your parameter "naive treewidth" is known as tree-partition-width in the literature.
It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-width. See [Wood 2009].

Note that your example in the update actually has pathwidth 2.

[Wood 2009] David R. Wood. On tree-partition-width. European Journal of Combinatorics 30 (2009) 1245-1253. https://doi.org/10.1016/j.ejc.2008.11.010
(also on arXiv https://arxiv.org/abs/math/0602507)


Is this "subgroup packing" polytope integral?

Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups.

On the positive side.

Theorem:
For cyclic groups with order $p^kq$, where $p$ and $q$ are primes and $k\in \mathbb{N}$, the incidence matrix of elements and subgroups is totally unimodular.

This is because the family of subgroups is a union of two laminar families.

Hence, this shows the smallest counterexample for cyclic groups must have order at least $2\times 3\times 5 =30$. This actually explains why no small counterexample was found.

Andrew ran some computations, and found a counterexample for cyclic group of order $30$.

Counterexample: $x_0=1/2$, $x_2=\frac{30}{2}-\frac{1}{2}=29/2$, $x_3=\frac{30}{3}-\frac{1}{2}=19/2$, $x_5=\frac{30}{5}-\frac{1}{2}=11/2$, and $0$ everywhere else.
It's not hard to check the point is feasible. Here I rephrase Andrew's proof that this is actually a vertex.
There are $30$ tight constraints. The whole group constraint, the three
subgroups generated by $2,3$ and $5$ respectively, and non-negativity constraints. Because we have $30$ variables, $x$ is a vertex.

One might wonder if the polytope for $\mathbb{F}_2^n$ is integral for all $n$. Unfortunately, Andrew also found a non-integral of the polytope for $\mathbb{F}_2^4$.


The most natural ways to represent knots are either to embed them piecewise linearly in $\mathbb{R}^3$ (just store the coordinates of the vertices and where you want to put segments) (any tame knot can be embedded piecewise linearly) or with a knot diagram, i.e. storing a projection on $\mathbb{R}^2$ as a graph where at every crossing you specify which strand is above.

As Suresh pointed out, checking knot equivalence is highly non-trivial (not known to be in P) but experimental results for unknot recognition are polynomial-like -- knot equivalence looks much harder though. If you are looking for software, peek at Regina .


How to map random cardesian points in a 2d array

This is impossible in general.

The reason is that the grid-distance is symmetric while being closest neighbors is not a symmetric relation.

If you have many points ($\geq 9$) close to the origin and then a point at, say, $(M,0)$ for some large $M$.

The point at $(M,0)$ has a its closest neighbors as some of the points which are closest to the origin, but these points consider it as the farthest point from them.


Preserving termination when rewriting recursive programs

The standard presentation of program transformation ideas is unsound, quite unfortunately.  They usually think of program transformation as forward deduction.  Using equational reasoning, you can deduce new facts from the old program, and lo and behold, it gives a better program!  While the new facts are quite clearly facts, nothing guarantees that they constitute a program.  The problem you have spotted is this naive presentation of the program transformation ideas.

However, it is possible to think of very much the same process as a backward deduction.  We think of the old program as a specification, and derive a new program that satisfies the specification.  Since equational reasoning is often bidirectional, you would see very similar steps in deriving the new program.  However, the meaning of these steps is opposite to what the naive methods imply.  When you use this "correct" method, you reason about termination while introducing recursion, and always derive a correct program.

For a paper describing the technique, see Deductive and inductive synthesis of equational programs (PDF).  This was done for first-order "equational" programs, but very similar ideas should be applicable to terminating functional programs.  If you are interested in non-terminating programs, I think you could use coinduction techniques (an off-the-cuff intuition).  However, my efforts to apply domain theory techniques to do these kinds of transformations did not bear fruit.  It might still be possible, but I haven't seen anything written on it.


I assume that your graph is undirected.

If you allow $k/2$ without integer division,
then you can reduce your problem to computing the maximum mean weight cycle. Replace every undirected edge by two directed egdes. Every edge leaving a node $A_i$ gets value $B(i)$. Compute a cycle of maximum mean weight (i.e., with maximum average edge weight).
You condition is violated if and only if the maxium mean weight is $> 1/2$.

The maximum mean weight cycle as well as the minimum mean weight cycle can be computed
in polynomial time by Karp's algorithm, see Cormen, Leiserson, Rivest, Stein.

If you insist on integer division, things get more delicate, since there could be several
maximum mean weight cycles and a longer one can satisfy the bound but a shorter one need not. You can slightly reduce the weights (by a constant $\epsilon$ which is negligble
compared to your edge weights). This will favour shorter cycles and you might get away with this.


A square with entries whose adjacencies never repeat

An extended version of my comment:

Let $p = n+1$ be a prime number. Then we can construct an $n \times n$ square from the multiplication table of integers modulo $p$. For example, if $p = 5$, we have

1234
2413
3142
4321

Now each pair $ab$ with $a \ne b$ occurs exactly once. Similarly, each pair $a$-above-$b$ with $a \ne b$ occurs exactly once.

Hence this is a valid construction; alphabet size $n$ and an $n \times n$ square.

Moreover, it is optimal. In an $n \times n$ square there are $n(n-1)$ horizontal pairs, and each of them must be different. If we had an alphabet of size $n-1$, we could only construct $(n-1)^2 < n(n-1)$ different horizontal pairs.


The problem of deciding whether a given CNF formula has a satisfying assignment other than a given one is easily shown to be NP-complete by transforming a CNF formula to add one trivial solution.  This problem is called the “Another Solution Problem (ASP) of SAT” in [YS03], where it is used to give a systematic proof that (the decision versions of) the ASPs of many other problems are also NP-complete.

The problem of deciding whether a given CNF formula has a unique satisfying assignment or not (so you have to answer “no” if the formula has no satisfying assignments or more than one satisfying assignment) is US-complete.  US contains both UP and coNP.

References

[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.

Edit: An earlier version (revision 1) of this answer contained a confusion between the decision version and the search version.  It has been fixed.


Deciding emptiness of intersection of regular languages in subquadratic time

Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted.

We will prove a stronger theorem and then the simple answer will follow.

Theorem: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time, then any problem that's non-deterministically solvable using only n bits of memory is deterministically solvable in $poly(n)\cdot2^{(\delta n/2)}$ time.

Justification: Suppose that we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time.  Let a non-deterministic Turing machine M with a read only input tape and a read/write binary work tape be given.  Let an input string x of length n be given.  Suppose that M doesn't access more than n bits of memory on the binary work tape.

A computation of M on input x can be represented by a finite list of configurations.  Each configuration consists of a state, a position on the input tape, a position on the work tape, and up to n bits of memory that represent the work tape.

Now, consider that the work tape was split in half.  In other words, we have a left section of $\frac{n}{2}$ cells and a right section of $\frac{n}{2}$ cells.  Each configuration can be broken up into a left piece and a right piece.  The left piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the left section.  The right piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the right section.

Now, we build a DFA $D_1$ whose states are left pieces and a DFA $D_2$ whose states are right pieces.  The alphabet characters are instructions that say which state to go to, how the tape heads should move, and how the work tape's active cell should be manipulated.

The idea is that $D_1$ and $D_2$ read in a list of instructions corresponding to a computation of M on input x and together verify that it is valid and accepting.  Both $D_1$ and $D_2$ will always agree on where the tape heads are because that information is included in their input characters.  Therefore, we can have $D_1$ verify that the instruction is appropriate when the work tape position is in the left piece and $D_2$ verify when in the right piece.

In total, there are at most $poly(n) \cdot 2^{n/2}$ states for each DFA and at most $poly(n)$ distinct alphabet characters.

By the initial assumption, it follows that we can solve intersection non-emptiness for the two DFA's in $poly(n) \cdot 2^{(\delta n /2)}$ time.

You might find this helpful: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

CNF-SAT is solvable using $k+O(\log(n))$ bits of memory where k is the number of variables.  The preceding construction can be used to show that if we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time, then we can solve CNF-SAT in $poly(n) \cdot 2^{(\delta k/2)}$ time.  Therefore, the simple answer holds.

Comments, corrections, suggestions, and questions are welcomed.  :)


Is finding an optimal solution to this Knapsack-like problem NP-hard?

NOTE: My original reduction didn't work. Fixed now.

Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are proportional to the weights, so
$p_i = \beta w_i$ with $\beta < 1$.

Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a profit of
$$
\sum_{i \in S} w_i + \sum_{i \not\in S} p_i = W + \beta \left(\sum_i w_i -W\right) = (1-\beta)W + \beta \sum_i w_i,$$ which is optimal. If there's not such a set of weights, then we can't.


Is there a general theory for why certain algorithms are inefficient in high-level languages?

There is no deeper reason other than quality of compilers and interpreters.

Some languages are not designed with speed of execution in mind. For example, the design goals of Python did not include speed of execution at the very top. In such cases you should not wonder where speed has gone.

Some languages are intended to run fast but it takes time for people to produce good compilers and runtime environments. Typical examples are the so-called "high-level" languages. For example, early variants of ML were memory hogs that ran sort of fast until the garbage collector kicked in. Nowadays, 25 years later, a modern variant of ML, such as Ocaml, runs with speeds comparable to those of C and C++, and in most cases you don't even notice that there is a garbage collector.

Why is it harder to compile high-level languages to fast code? Well, because they are high level. Programs written in such languages operate directly with concepts that are far removed from the underlying hardware. In contrast, low level languages such as C, C++ and java are essentially glorified assembly languages and there is very little that the compiler actually needs to do.

Also, there are languages out there whose design is essentially screwed up in such a way that efficient compiled code is hard to obtain. Typically such languages have no or little compile-time type checking or unreasonable amounts of reflection, i.e., eval <string>, and an operational semantics which relies heavily on string replacement and manipulation of source code. Bourne shell comes to mind, TeX/LaTeX as well, and maybe Python to an extent. As long as such "features" are deliberate design choices that is ok, but there also seem to be languages out there whose design was based on ignorance of programming language theory.


Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron

Via Rubin:

There is a sequence of polytopes $\{ P_k\}_k$ each defined by two variables and one constraint (plus two nonnegativity constraints) such that the integer hull of $P_k$ has $k+3$ vertices and $k+3$ facets.

$P_k=\{ (x,y)\in \mathbb{R}^2_+ ~|~f_{2k} x + f_{2k+1}y \le f^2_{2k+1}-1\}$

Here, $f_j$ is the $j$-th Fibonacci number.

This shows that the number of facets of the integer hull $P_I$ cannot be bounded above in terms of the number variables and constraints of $P$.

Schrijver provides a nice collection of these kind of results in his Theory of Linear and Integer Programming.


Lattice generation inside d-dimensional unit ball

In general, even telling whether any such point exists is hard; it is equivalent to the Shortest Vector Problem (SVP), and it is conjectured that there is no polynomial-time algorithm for this problem.


Uniform derandomisation of circuit complexity classes

The class uniform-RNC has been studied a lot.
It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and polylogarithmic running time (see the Handbook of Theoretical Computer Science Vol. A). So the question is whether every efficient randomised parallel algorihm can be derandomized.

Since symbolic determinant identity testing is in uniform-RNC, derandomizing RNC implies circuit lower bounds by the results of Kabanets & Impagliazzo (Computational Complexity, 13(1-2), pages 1-46, 2004).

An important special case is the question whether we can compute perfect matchings in uniform-NC. There are several randomized parallel algorithms known, but we do not know whether there is a deterministic one. Recently,
Fenner, Gurjar and Thierauf (STOC 2016) have shown that we can compute perfect matchings in bipartite graphs by uniform circuits of polylogarithmic depth and quasipolynomial size.


Both statements seem to be false.

Consider all Boolean formulas $\Phi$ in 3-CNF. The objective value of an $n$-variable formula $\Phi$ is $1/n$ if $\Phi$ is satisfiable, and is $1$ if $\Phi$ is not satisfiable. The corresponding minimization problem has an asymptotic PTAS (it is easy to come within an additive $+1$), but is not in APX (as this would allow you to solve 3-SAT).
Consider all undirected graphs. The objective value of a graph $G$ is its edge-chromatic number $\chi'(G)$. Holyer has proved that deciding $\chi'(G)=3$ is NP-hard. The corresponding minimization problem is APX-hard (there is no approximation algorithm with worst case ratio better than $4/3$), but the problem has an asymptotic PTAS (Vizing's theorem tells us that $\chi'(G)$ is between the max-degree and the max-degree plus 1).


In their basic form, type classes are somewhat similar to object interfaces. However, in many respects, they are much more general.

Dispatch is on types, not values. No value is required to perform it. For example, it is possible to do dispatch on the result type of function, as with Haskell's Read class:

class Read a where
  readsPrec :: Int -> String -> [(a, String)]
  ...

Such dispatch is clearly impossible in conventional OO.
Type classes naturally extend to multiple dispatch, simply by providing multiple parameters:

class Mul a b c where
  (*) :: a -> b -> c

instance Mul Int Int Int where ...
instance Mul Int Vec Vec where ...
instance Mul Vec Vec Int where ...

Instance definitions are independent from both class and type definitions, which makes them more modular. A type T from module A can be retrofitted to a class C from module M2 without modifying the definition of either, simply by providing an instance in module M3. In OO, this requires more esoteric (and less OO-ish) language features like extension methods.
Type classes are based on parametric polymorphism, not subtyping. That enables more accurate typing. Consider e.g.

pick :: Enum a => a -> a -> a
pick x y = if fromEnum x == 0 then y else x

vs.

pick(x : Enum, y : Enum) : Enum = if x.fromEnum() == 0 then y else x

In the former case, applying pick '\0' 'x' has type Char, whereas in the latter case, all you'd know about the result would be that it's an Enum. (This is also the reason why most OO languages these days integrate parametric polymorphism.)
Closely related is the issue of binary methods. They are completely natural with type classes:

class Ord a where
  (<) :: a -> a -> Bool
  ...

min :: Ord a => a -> a -> a
min x y = if x < y then x else y

With subtyping alone, the Ord interface is impossible to express. You need a more complicated, recursive form or parametric polymorphism called "F-bounded quantification" to do it accurately. Compare Java's Comparable and its use:

interface Comparable<T> {
  int compareTo(T y);
};

<T extends Comparable<T>> T min(T x, T y) {
  if (x.compareTo(y) < 0)
    return x;
  else
    return y;
}

On the other hand, subtyping-based interfaces naturally allow the formation of heterogeneous collections, e.g. a list of type List<C> can contain members that have various subtypes of C (although it is not possible to recover their exact type, except by using downcasts). To do the same based on type classes, you need existential types as an additional feature.


Colouring achieving simple discrepancy bound?

I assume you mean a deterministic algorithm. The best discrepancy bound is in fact $O(\sqrt{n\log (m/n)})$ which is $O(\sqrt{n})$ when $m = O(n)$. This the famous Six Standard Deviations Suffice bound of Spencer (1985 TAMS). A coloring achieving this bound can be found in deterministic polynomial time, using a recent result by Bansal and Spencer.

Achieving the random coloring bound of $\sqrt{2n \ln (2m)}$ can be done with simple classic derandomization methods. You can use the method of conditional expectations or variants of the multiplicative weights method. You can even achieve the stronger $\sqrt{2|e|\ln(2m)}$ bound for each edge $e$. See Section 1.1. of Chazelle's book.

For completeness, let me reproduce the multiplicative weights argument, because it's nice and simple. Identify the vertices of $H$ with $[n]$. We will pick $\chi(i)$ for $i = 1, \ldots, n$ greedily. Define $D(e, k) = \sum_{i \in e, i \leq k}{\chi(i)}$ to be the discrepancy of $e$ up to $k$. Let $p(e, k) = \frac{1}{2}e^{\alpha D(e, k)} +\frac{1}{2}e^{-\alpha D(e, k)}$ for $\alpha = \sqrt{2\ln (2m)/n}$, and the potential function $P(k) = \sum_e{p(e, k)}$. Define also $p(e, 0) = 1$ and $P(0) = m$. You can verify that for a random choice of $\chi(k+1)$, $\mathbb{E}P(k+1) \leq P(k)e^{\alpha^2/2}$. So you can just pick each $\chi(k)$ to minimize $P(k)$, and after the final step you have
$$
\frac{1}{2} e^{\alpha |D(e, n)|} \leq \max_e p(e, n) \leq P(n) \leq me^{n\alpha^2/2}.
$$

Simple algebra gives the bound.


Can a measurement commuting with the stabilizer of a state disturb the state?

The quoted claim from the book is true. It is not true that $Z_1$ must always commute with all stabilizers of $\lvert \psi \rangle$. For example, if $X_1X_2$ stabilizes $\lvert \psi \rangle$ (e.g., if $\lvert \psi \rangle$ was an EPR pair) then $Z_1$ does not commute with $X_1X_2$ and $Z_1$ is not a stabilizer of $\lvert \psi \rangle$.


What is this matrix column-selection problem, and how hard is it to approximate?

After more thought, I found a simple approximation-preserving reduction from independent set, showing that this problem is hard to approximate better than $n^{0.5}$. Here it is.

Consider a graph $G=(V,E)$ with n vertices. Construct the following matrices, with columns indexing the vertices.

For each vertex $v$, construct a matrix with the top row containing a 1 in column v, and a 0 elsewhere. All remaining rows are filled with $-\infty$.
For each edge $e=(u,v) \in E$, construct a matrix with the first row with $-\infty$ at $u$ and $0$ elsewhere, and the second row with $-\infty$ at $v$ and $0$ elsewhere. All remaining rows are filled with $-\infty$.

The matrices corresponding to edges penalize choosing two adjacent vertices in the graph by $-\infty$, essentially enforcing that the selected set of columns is an independent set of vertices. The matrices corresponding to vertices add one to the objective value for each column selected (i.e. for each vertex included in the independent set). Consequently, $val(S)$ is $-\infty$ for all non-independent sets S, and |S| for all independent sets S.

This shows that the maximum of val(S) is as hard to approximate as the maximum cardinality of an independent set, as needed.


What is the difference between System F and Hindley-Milner type system?

Yes, In Hindley-Milner universal quantifiers are allowed only at the outside of a type (and therefore omitted). For example, in HM you can have the type $\forall \alpha.(\alpha\to\alpha) \to (\alpha\to\alpha)$ usually abbreviated as $(\alpha\to\alpha)\to(\alpha\to\alpha)$, but you cannot have $(\forall \alpha.\alpha\to\alpha) \to (\forall \alpha.\alpha\to\alpha)$.

A special feature of HM (that does not make sense for system F) is the distinction between let-bindings and beta reducts. In a let-binding the type of the bound variable may be polymorphic in the sense that its free type variables are quantified separately. For example,

let f = λ x . x in λ x . f f x

can be typed in HM and in system F (by giving f the polymorphic type $\forall \alpha.\alpha\rightarrow\alpha$), but

(λ f . λ x. f f x) (λ x . x)

cannot be typed in HM, only in Sytem F.

The advantage of these restrictions is that type inference for HM
is decidable and rather efficiently so whereas it is undecidable
for F.


Type-based memory safety without manual memory manage or runtime garbage collection?

Roughly speaking, there are two main strategies for safe manual memory management.

The first approach is to use some substructural logic like linear logic to control resource usage. This idea has floated around basically since linear logic's inception, and basically works on the observation that by banning the structural rule of contraction, every variable is used at most once, and so there is no aliasing. As a result, the difference between in-place update and re-allocation is invisible to the program, and so you can implement your language with manual memory management.

This is what Rust does (it uses an affine type system). If you are interested in the theory of Rust-style languages, one of the best papers to read is Ahmed et al's L3: A Linear Language with Locations. As an aside, the LFPL calculus Damiano Mazza mentioned is also linear,  has a full language derived from it in the RAML language.

If you are interested in Idris-style verification, you should look at Xi et al's ATS language, which is a Rust/L3 style language with support for verification based on Haskell-style indexed types, only made proof-irrelevant and linear to give more control over performance.

An even more aggressively dependent approach is the F-star language developed at Microsoft Research, which is a full dependent type theory. This language has a monadic interface with pre- and post-conditions in the spirit of Nanevski et al's Hoare Type Theory (or even my own  Integrating Linear and Dependent Types), and has a defined subset which can be compiled to low-level C code -- in fact, they are shipping verified crypto code as part of Firefox already!

To be clear, neither  F-star nor HTT are linearly-typed languages, but the index language for their monads are usually based on Reynold and O'Hearn's separation logic, which is a substructural logic related to linear logic that has seen great success as the assertion language for Hoare logics for pointer programs.
The second approach is to simply specify what assembly (or whatever low level IR you want) does, and then use some form of linear or separation logic to reason about its behaviour in a proof assistant directly. Essentially, you can use the proof assistant or dependently-typed language as a very fancy macro assembler that only generates correct programs.

Jensen et al's High-level separation logic for low-level code is a particularly pure example of this -- it builds separation logic for x86 assembly! However, there are many projects in this vein, like the Verified Software Toolchain at Princeton and the CertiKOS project at Yale.

All of these approaches will "feel" like a bit like Rust, since tracking ownership by restricting the usage of variables is key to them all.


Nonterminal descriptional complexity of regular languages

Lemma 1. Consider $L = (ab)^* + (ba)^*$:

There exists CFG with two variables which generates $L$
There exist no CFG with one variable which generates $L$

For proving (1) we may just consider the following CFG $$ S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$
The second proposition is a bit more tricky. Suppose that there exists CFG $G = (\{S\}, \{a, b\}, P, S)$ such that $L = L(G)$. Every production is $S \rightarrow \alpha$ for some $\alpha \in \{a, b, S\}^*$. Say, $\alpha = w_1 S w_2 S \ldots w_k S w_{k+1}$. Then $$u_1, \ldots u_k \in L \Rightarrow w_1 u_1 w_2 u_2 \ldots w_k u_k w_{k+1} \in L,$$ because as $L$ is generated by $G$, one can derive this word by using $S \rightarrow w_1 S w_2 S \ldots w_k S w_{k+1}$ and then deriving every $u_i$ from $S$'s. By using that we can prove that in right-hand side of every production $S$ can't be followed immediately by any symbol:

if $S$ is followed by $a$, we have subword $Sa$ in $\alpha$, then we can derive $ba$ from $S$, thus we can derive the word which contains two $a$'s in the row, which obviously doesn't lie in $L$;
if $S$ is followed by $b$, having subsword $Sb$ of $\alpha$ we can derive $ab$ from $S$ and thus obtain the word which contains two $b$'s in the row;
if we have subword $SS$ of $\alpha$, we can derive $ab$ from the first $S$ and $ba$ from the second.

Also $S$ can't follow neither letter nor $S$ in right-hand side of every production for the same reason. So $G$ can only have productions of sort $S \rightarrow S$ and $S \rightarrow w$ for $w \in L$. Thus $L(G)$ is finite, which is contradiction. $\Box$
I'd also like to suggest the following
Lemma 2. Let $w_1, \ldots w_n$ be some words. The language $w_1^* + \ldots + w_n^*$ is generated by CFG with one variable iff words $w_1, \ldots w_n$ commute pairwise, i. e. $w_i w_j = w_j w_i$ for every $i,j$.


Relation between Kleene star, union and difference in relation algebra


Not exactly what you're looking for, but Dinur and Safra, in their celebrated paper on the hardness of vertex cover, prove that the following promise problem is NP-hard for every fixed $r,\epsilon > 0$ (using the PCP theorem and Raz's parallel repetition theorem).

Instance: A graph $G$ whose vertex set is composed of $m$ sets $V_1,\ldots,V_m$ of size $r$, each of them forming an $r$-clique.

Problem: Distinguish between the following two cases:

YES case: $G$ has an independent set of size $m$.
NO case: Every set $A \subseteq V$ containing more than $\epsilon m$ vertices contains a clique of size $h = \lfloor \epsilon r^{1/c} \rfloor$ (where $c$ is some universal constant).

More explicitly, for any NP language $L$ there is a polytime $f$ mapping instances of $L$ to instances of this promise problem, in such a way that if $x \in L$ then $f(x)$ is a YES instance, and if $x \notin L$ then $f(x)$ is a NO instance.


I don't know if this is an "explanation", but hopefully it is a useful "description".

More generally than projective measurements, one always measures an operator. (A projector is a special case of this.) So what does it mean to "measure an operator"?

Well, operators often correspond to 'observable' physical quantities. The most important in quantum mechanics, for instance, is energy; but one can also (sometimes indirectly) measure other quantities, such as angular momentum, z-components of magnetic fields, etc. What is being measured always gives real-valued results --- in principle, some definite result (e.g. an electron is in the  'spin +1/2' state as opposed to 'spin −1/2', or in the first excited energy level as opposed to the ground-state in a hydrogen atom, etc.), albeit each a priori possible result is realized with some probability.

We assign each of the real-valued outcomes of a measurement to a subspace. The way we do this is to describe a Hermitian operator --- i.e. an operator which associates a real eigenvalue to different subspaces, with the subspaces summing up to the whole Hilbert space. A projector is such an operator, where the real values are 0 and 1; i.e. describing that a vector belongs to a designated subspace (yielding a value of 1), or its orthocomplement (yielding a value of 0). These Hermitian operators are observables, and the eigenspaces are those for which the observable has a "definite" value.

But what about those vectors which are not eigenvectors, and do not have "definite" values for these observables? Here is the non-explaining part of the description: we project them into one of the eigenspaces, to obtain an eigenvector with a well-defined value. Which projection we apply is determined at random. The probability distribution is given by the familiar Born rule:

$$ \Pr\limits_{|\psi\rangle}\bigl( E = c \bigr) \;=\; \langle \psi | \Pi_c | \psi \rangle \;, $$

where $\Pi_c$ is the projector onto the c-eigenspace of an 'observable quantity' E (represented by a Hermitian operator $A = \sum_c \; c \cdot \Pi_c$). The post-measured state is some projection of the state $|\psi\rangle$ onto some eigenspace of the observable A. And so if $| \psi_0 \rangle$ is the pre-measurement state, $| \psi_1 \rangle$ is the post-measurement state, and $\Pi_c$ is the 'actual result' measured (i.e. the eigenspace onto which the pre-measurement state was actually projected), we have the proportionality result

$$ | \psi_1 \rangle \;\propto\; \Pi_c | \psi_0 \rangle $$

by the projection rule just described. This is why there is the projector in your formula.

In general, the vector $| \psi'_1 \rangle = \Pi_c | \psi_0 \rangle$ is not a unit vector; because we wish to describe the post-measurement state by another unit vector, we must rescale it by

$$ \|\;|\psi'_1\rangle\;\| = \sqrt{\langle \psi'_1 | \psi'_1 \rangle} = \sqrt{\langle \psi_0 | \Pi_c | \psi_0 \rangle} \;,$$

which is the square-root of the probability with which the result would occur a priori. And so, we recover the formula in your question,

$$ | \psi_1 \rangle \;=\; \frac{\Pi_c | \psi_0 \rangle}{ \sqrt{ \langle \psi_0 | \Pi_c | \psi_0 \rangle }} \;.$$

(If this formula seems slightly clumsy, take heart that it looks and feels a little bit better if you represent quantum states by density operators.)

Edited to add: the above should not be construed as a description of POVMs. A "positive operator valued measurement" is better seen as describing the expectation value of various measurable observables Ec in a collection { Ec }c ∈ C .


I'm interested in but not familiar with this topic. Searching for "Average case complexity theory", I found a thesis written by Tomoyuki Yamakami:

  Average Case Computational Complexity Theory, Tomoyuki Yamakami, 1997.

Section 3.5.1 seems relevant, a space-analog notion similar to the average-time complexity is defined. Hopefully with a deeper reading we'll find some problems that has been analysed :)

Also in the paper

  On the Theory of Average Case Complexity, Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, 1989.

Average log-space complexity is defined in Section 7.


If you allow me to give an answer that uses "technical" terminology: the output of a finite state transducer on any given regular language is again a regular language. The sort of regular $(ab)^*$ equals non-regular $\{ a^nb^n \mid n\ge 0\}$. Thus that cannot be performed by a FST.

(added) The fact that regular languages are closed under FST is a consequence of Nivat's Theorem. Every FST $T$ can be decomposed into a regular language $R$, and morphisms $g,h$ such that $T(L) = g(h^{-1}(L) \cap R)$. In short $R$ consists of "letters" of the form $(a,b)$ where $a,b$ are from the input and output alphabets respectively (or empty), and $h,g$ select  the input/ output components from those pairs.


Math talk: Theorem about git revision control system?

Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and  arose in the context of the DARCS version control system. It can be seen as an abstract theory of branching and merging. Recently patch theory has been given HoTT [ 6 ] and categorical [ 7 ] treatments.

Patch theory is work in progress, and doesn't cover all aspects of version control, but contains a lot of theorems that you could look at. It is a clear example of theory that's applicable to the 'real world' -- not surprising, for patch theory is an abstraction / simplification of something very concrete. At the same time it connects with cutting-edge maths like HoTT.

J. Dagit, Type-Correct Changes - A Safe Approach to Version Control Implementation.
G. Sittampalam, Some properties of darcs patch theory.
I. Lynagh, Camp Path Theory.
D. Roundy, Implementing the darcs patch formalism ... and verifying it.
J. Jacobson, A Formalization Of Darcs Patch Theory Using Inverse Semigroups.
C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.
S. Mimram, C. Di Giusto, A Categorical Theory of Patches.


Shortest simple path with minimum edge cost minus node reward

As we discussed earlier, this can be solved by transforming your weighted edges-and-nodes graph to a normal weighted-edges graph: simply make the edge-weights in the new graph equal to the edge-weights in the old graph minus the reward of the node they point to.  This may lead to a graph with negative-cycles; and finding a simple path on such a graph is NP-Hard.

Unfortunately, the two problems are equivalent.  The transformation in the other direction is easy - given a directed weighted graph with negative cycles, you can turn it into a directed weighted-edges-and-nodes graph with no negative edges simply by setting the "reward" of each node to the lowest incoming edge, and subtracting that amount from all incoming edges.

Thus, your problem NP-Hard in the general case.  However, the sub-cases where the transformation in the first paragraph would generate a graph with no negative edge-cycles (ex. if, for instance, the node's reward is <= the least weight of an incoming edge) are in P.


Consequences of existence of a strongly polynomial algorithm for linear programming?

This would show that parity and mean-payoff games are in P. See Sven Schewe. From Parity and Payoff Games to Linear Programming. MFCS 2009.


Benefits for syntactic and semantic classes

Here are a couple of advantages.

Syntactic classes give you time hierarchies. Zak's proof of the nondeterministic time hierarchy works for any syntactic class. For semantic classes (like UPTIME($n^3$)?$=$UTPIME($n^2$)) these are open questions.
It's easier to create oracles that separate syntactic classes since you only need to diagonalize infinitely often and you don't care what happens on the other input lengths. Conversely it's easier to collapse semantic classes since you can eliminate machines that don't fulfill the promise.


I'm assuming that you mean the Flood Set algorithm for solving the agreement problem in Section 6.2 of [1]. The Flood Set algorithm proceeds in rounds and requires every process $u$ to forward all received values, which it stores in a set $W$; initially $W$ contains $u$'s input value. We assume that $f$ processes can be faulty. After $f+1$ rounds, every alive process $u$ checks if its set $W$ is a singleton. If so, $u$ decides on the singleton value, otherwise $u$ decides on a default value $x$. It can easily be shown that after $f+1$ rounds, all correct processes have the same set $W$.

For a general graph, the answer is obviously no: Suppose that the network is cut by a faulty process $u$ into parts $C_0$ and $C_1$ and processes in $C_0$ start with $0$ whereas processes in $C_1$ start with $1$. If $u$ crashes initially, the following happens in round $f+1$: all processes in $C_0$ will decide on $0$ and all processes in $C_1$ will decide on $1$.

Note that this impossibility argument holds for any agreement algorithm.

[1] Nancy Lynch. Distributed Computing. Publisher: Morgan Kaufmann


Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

The answer to Question (1) is no.  The answer to Question (2) is yes.  Here are the details.
I'll work with the following equivalent problem formulations.  For the input, we are given $n$ pairs of values $(v_1, w_1), (v_2, w_2), \ldots, (v_n, w_n)$ in $\mathbb R^2_+$.
Problem A. Find $\max\big\{ \sum_{i\not\in S} v_i : S\subseteq [n],\, \sum_{i\not\in S} w_i \le \sum_{i=1}^n v_i\big\}$.
Problem B. Find $\min\big\{ \sum_{i\in S} v_i : S\subseteq [n],\, \sum_{i\in S} w_i \ge \sum_{i=1}^n w_i-v_i\big\}$.
(By calculation, these problems are equivalent to those in the post. Note that the first is a special case of the standard KNAPSACK problem.  As discussed further in the proof of Theorem 2 below, the second is a special case of a sort of inverse of KNAPSACK.)
Theorem 1. The answer to Question 1 is no.  Specifically, for any $\epsilon>0$, there is a polynomial-time $(1+\epsilon)$-approximation algorithm for Problem A that has infinite approximation ratio for Problem B.
Theorem 2. The answer to Question 2 is yes.  Specifically, there is  polynomial-time $2$-approximation algorithm for Problem B.
Proof of Theorem 1.  First consider the instance $I=((0,\epsilon), (\epsilon, \epsilon), (1, 1))$.  The optimal solution is $S^*=\{1\}$, giving value $1+\epsilon$ for Problem A and $0$ for Problem B.  The solution $S=\{1,2\}$ gives value $1$ for Problem A and $\epsilon$ for Problem B.  So $S$ is a $(1+\epsilon)$-approximate solution for Problem A, but has ratio $\epsilon/0=\infty$ for Problem B.  Now consider an algorithm that, given this instance $I$, returns $S$, and given any other instance $I'$, returns a $(1+\epsilon)$-approximation solution for that instance $I'$, computed using the standard PTAS for KNAPSACK (thinking of $I'$ as an instance of Problem $A$, which is a special case of KNAPSACK). This is the desired algorithm. $~~~\Box$
Proof sketch for Theorem 2. Remark: The algorithm is similar to a greedy algorithm for Knapsack, and its analysis is similar to the analysis of that algorithm.
We give a 2-approximation algorithm for a slightly more general "inverse knapsack" problem:

Given $(v_1, w_1), \ldots, (v_n, w_n)$ and target $W$, find $\min\big\{\sum_{i\in S} v_i : S\subseteq [n],\, \sum_{i\in S} w_i \ge W\big\}$.

Given input $I=(((v_1, w_1), \ldots, (v_n, w_n)), W)$:

if $W\le 0$: return $\emptyset$

let $h = \arg\min_i \frac{v_i}{\min(W, w_i)}$

let $I'$ be the residual instance obtained from $I$ by deleting $(v_i, w_i)$ and replacing $W$ by $W'=W-w_i$.

recursively compute a solution $S'$ for $I'$

return $\{h\} \cup S'$

By a standard inductive argument, the algorithm returns a valid solution.  To finish we sketch a proof that the solution value is at most twice the optimal.  Consider any execution of the algorithm.  If $W\le 0$ the solution is optimal, so assume $W>0$.
Assume WLOG (by reordering $I$) that the final solution $S$ is $S=[m]=\{1,2,\ldots, m\}$, with each index $i\in S$ being chosen in the $i$th of the $m+1$ calls.  Define instances $I_1$ and $I_2$ as follows.  $I_1$ is obtained from $I$ by replacing $W$ by $W_1=w_1+w_2+\ldots+w_{m-1}$, while $I_2$ is obtained from $I$ by replacing $W$ by $W_2=W-W_1$ and deleting the pairs $(v_1, w_1), \ldots, (v_{m-1}, w_{m-1})$ (this is the instance passed into the final second-to-last recursive call).  Then:

$S_1=[m-1]$ is an optimal solution for $I_1$. (Note that $v_i/w_i \le v_j / w_j$ for all $i\in [m-1]$ and $j\not\in[m-1]$, and $w_1+w_2+\ldots+w_{m-1}=W_1$.  Using this, we can show by a standard greedy perturbation argument that $S_1$ is an optimal solution for the fractional relaxation of the instance $I_1$, where a fractional amount $x_i\in[0,1]$ of each item $i$ can be chosen.  So $S_1$ is also optimal for $I_1$.)

$S_2=\{m\}$ is an optimal solution for $I_2$. (This follows by a similar argument, along with the observation that replacing each $w_i$ in $I_2$ by $w'_i=\min(w_i, W)$ doesn't change the optimal value.)

The optimal value for $I_1$ is at most the optimal value for $I$. (This follows from the definition of $I_1$, as any solution for $I$ gives a solution for $I_1$.)

The optimal value for $I_2$ is at most the optimal value for $I$. (Consider the instance $I''$ obtained from $I$ by replacing each $v_i$ with $i\in[m-1]$ by $v'_i=0$.  Clearly the optimal value for $I''$ is a lower bound on the optimal value for $I$.  There is an optimal solution for $I''$ that includes all the indices in $[m-1]$.  The remaining part of that solution gives a solution for $I_2$ of the same value.)

From the preceding four observations, it follows that the cost of the final solution $S=S_1\cup S_2$ is at most twice the optimal value for $I$.$~~~\Box$


Reference for fast algorithm for bottleneck shortest paths

P. M. Camerini (1978), The min-max spanning tree problem and some extensions, Information Processing Letters 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3


Difference between Stencil -structures and Cellular Automata Category-theoretically?

Judging from the source you provided, there appear to be two key differences:
(1) stencils have numeric values in each cell and update the cells with functions defined numerically (typically using continuous functions) while cellular automata typically have only a finite set of values per cell and use functions that in general do not arise from numerical methods, and (2) stencils are updated by a sweep across the grid while in cellular automata generally all cells are updated simultaneously.


Fully dynamic algorithms for strong components of a directed graph

I know it is an older question but this research paper has a relatively straight forward O(m^(3/2)) algorithm for incrementally maintaining them: https://arxiv.org/pdf/1105.2397.pdf
Here is one with O(m) algorithm for decrementally maintaining them: https://arxiv.org/pdf/1901.03615.pdf (from 2019 and it improves on the O(m*sqrt(n)) algorithm of https://u.cs.biu.ac.il/~liamr/scc-new.pdf)
I am not sure there is anything better for doing both operations.  Part of the issue is the data structure used for maintaining them.  Incremental algorithms are typically using Tarjan's Union-Find for fast partitioning of disjoint sets.  While decremental algorithms are using an Even-Shiloach(ES)-tree, as the breadth-first-search representation matches the problem.
As for a unified data structure which efficiently can be used for a fully online SCC maintenance, that would be progress we hope to see soon.


How to constrain a finite automaton (NFA and DFA) to a tree?

I think the easiest way of enforcing tree shape is the set of conditions

$q_0$ is not in the image of $\delta$,
$\delta$ is injective, and
$M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable.

Then we can prove (by induction) that for any state $q$ there is a unique path from $q_0$ to $q$.


You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. There's a classic No-Free-Lunch result in PAC learning which says that you cannot learn the concept class of all boolean functions on the integers in a distribution-free fashion. Meaning: there is no function $m=m(\epsilon,\delta)$ such that if you request $m$ or more iid labeled examples from any unknown distribution, you'll be able to guarantee an $\epsilon$-accurate classifier with $\delta$-confidence. The proof proceeds by taking a uniform distribution over a large enough support size -- big enough to thwart any given purported sample complexity $m(\epsilon,\delta)$. A shorthand for saying this might be "take the uniform distribution over the integers". Now we all know that's absurd, and the explanation above is the only way I know to make sense out of it (and also jibes with the No-Free-Lunch context).


Church-Rosser property for dependently typed lambda calculus?

It might be useful to quickly give the counter-example to CR in typed calculi with $\beta$ and $\eta$:

$$ t=\lambda x:A.(\lambda y:B.\ y)\ x$$

And we have
$$ t\rightarrow_\beta \lambda x: A.x$$
and
$$ t\rightarrow_\eta \lambda y:B.y$$

It is immediate that if $A\equiv B$, then the two resulting terms are, in fact, $\alpha$ equivalent, but there is no reason for this to be the case, on untyped terms.

On typed terms, it's pretty clear that $A$ has to be equal to $B$ for the resulting term $t$ to be well-typed. The big difficulty that occurs is this:

  For dependently typed systems, confluence needs to be proven before type preservation!

This is because you need the property of $\Pi$-injectivity
$$ \Pi x:A.B=_{\beta\eta}\Pi x:A'.B'\ \Leftrightarrow\ A=_{\beta\eta}A'\wedge B=_{\beta\eta} B'$$
in order to prove inversion, which is required to prove preservation/subject reduction.

So you can't even prove that $\beta\eta$-reductions preserve types without confluence, but confluence doesn't even hold on untyped/ill-typed terms!

Breaking out of this vicious circle requires some technical tricks, which are hard to summarize here, but arguably the simplest to understand is to simply stop being interested in $\eta$-reductions, but instead concentrate on $\eta$-expansions: $t\rightarrow_{\eta*}\lambda x:A.t\ x$

Of course, you need to restrict this rule to non-$\lambda$ and non-applied terms to even hope to get termination, but with these restrictions it seems that the reduction behavior is much better behaved, and the meta-theory works out without too many problems. A good reference seems to be Neil Ghani, Eta-Expansions in Dependent Type Theory.

A different, and recently quite popular approach, is described by Abel, Untyped Algorithmic Equality for Martin-Löf's Logical Framework with Surjective Pairs.


Is there a gap between weak learning and PAC-learning?

I think you're confusing two notions of hardness: computational and statistical.

In Q1, you point out, essentially, that boosting produces an improper learner. I think what you're asking then, is: Is there a concept class which is (computationally) hard to learn properly but can be efficiently learned via boosting? I believe there should be such examples, but can't think of one off-hand.

In Q2, please note that SQDim refers to hardness in a statistical sense -- i.e., the minimal number of statistical queries required. (We don't have any unconditional computational hardness results but plenty of statistical ones.)


Lower bounds for nonuniform circuits and oracles separating complexity classes

Yes, yes, and yes.

The basic idea is to consider the characteristic function of a language $L$
(the oracle you're constructing) at length $n$ as a string of length $2^n$
that will be an input to a ("big") circuit.
An OR gate in that circuit will correspond to
a polynomially-bounded existential quantifier, and
an AND gate to a polynomially-bounded universal quantifier.

Consider Furst-Saxe-Sipser as an example of
how this can be used to build oracles:
If the language $L$ is constructed so that
the characteristic function of $L \cap \Sigma^n$ is an input
whose parity differs from an $\mathsf{AC}^0$ function
(which exists, by Furst-Saxe-Sipser),
then you've just successfully diagonalized against
the language in $\mathsf{PH}$ corresponding to that $\mathsf{AC}^0$ function.
Doing this over all $\mathsf{AC}^0$ diagonalizes against all of $\mathsf{PH}$, and thus builds an oracle $L$ such that $\mathsf{PH}^L \neq \mathsf{PSPACE}^L$
(since the latter includes the language corresponding to
the "big" parity circuit).

For more discussion and examples of this general theme see the following survey :

Ker-I Ko, "Constructing Oracles by Lower Bound Techniques for Circuits", 1989.


Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits.
Indeed, by $\sigma$-additivity of the probabilistic measure, for any input $x$, there exists $n$ such that with probability $>1/2$, the algorithm computes the right answer within $n$ steps. Thus, we can find the answer deterministically as follows: for $n=1,2,3,\dots$, we simulate the algorithm for $n$ steps using all possible sequences of random bits (necessarily of length $\le n$) to count the probability that it halts with any particular answer; sooner or later, we find an $n$ and an answer that’s output with probability $>1/2$ within $n$ steps, and then we declare the winner.


Longest edge length of the greedy spanner on uniformly distributed pointsets in $[0,1]^d$

In our paper Distribution-Sensitive Construction of the Greedy Spanner (accepted for ESA 2014) we prove the following (combining Theorem 4 and Lemma 6):

  There exists $c_t$ dependent only on $t$ such that for every $c > 0$, if $P$ is a set of points uniformly and independently distributed at random in a $\sqrt{n} \times \sqrt{n}$ square and $n$ is large enough, then with probability at least $1 - n^c$, the greedy $t$-spanner on $P$ does not have edges longer than $c \cdot c_t \log n$.

Our bound on $c_t$ is fairly large, but we have experimental evidence that the 'right' bound is $\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$.


Computation space of Nisan's generator for space bounded machines

Yes, I believe that is correct. See, for example, these lecture notes.


Algorithm to Bulk Delete nodes from a Treap

Section 2 of the original treaps paper ("Randomized Search Trees" by Aradon and Seidel), as well as the journal version of the same paper (also called "Randomized Search Trees"), explains how to split and join treaps without affecting the validity of the randomized balancing. That's all you need to bulk delete.

  In order to split a treap storing $X$ according to some $a$, simply insert an item with key $a$ and "infinite" priority.
  By the heap-order property the newly inserted item will be at the root of the new treap.
  By the in-order property the left subtree of the root will be a treap for $X_1$ and the right subtree will be a treap for $X_2$.
  In order to join the treaps of two sets $X_1$ and $X_2$ as above, simply create a dummy root whose left subtree is a treap for $X_1$ and whose right subtree is a treap for $X_2$, and perform a delete operation on the dummy root.


It depends what you count as "the GCT program."

Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant and permanent to resolve the strong permanent versus determinant conjecture (i.e., that the permanent is not in the orbit closure of any polynomially larger determinant). In this case, it is possible that even if the conjecture is true, that this is not reflected in the vanishing/nonvanishing of multiplicities of irreps supported on these orbit closures. It is even possible that the conjecture is not reflected in the appropriate inequality of multiplicities. I should note that there are various forms of evidence that this shouldn't happen, but it has not yet been formally ruled out.

Note, however, that if instead of multiplicities you merely want a separating module, then the strong perm v det conjecture is true if and only if there exists a separating module.

If your goal is the original permanent versus determinant conjecture, there is an earlier step in GCT, namely (as pointed out by chazisop) moving to the strong perm v det conjecture by considering the orbit closures. It is conceivable that the original permanent versus determinant conjecture is true but the strong version is false. However, this seems highly unlikely to me. Also, if this is the situation, then none of our current methods can even come close to resolving the perm v det conjecture, since they all currently work for the "strong"/"approximative"/"border-"/Zariski-closed version of whatever algebraic complexity statement they are proving.
If your goal is not perm v det but Boolean $\mathsf{NP} \not\subseteq \mathsf{P/poly}$, there are additional claimed steps in GCT that have yet to be published. It is possible that one of these unpublished steps could fail as well, but obviously it is hard to comment on the details of mathematics one hasn't seen...
[Potential failures of lower bounds in general, not specific to GCT.] GCT is currently aimed at nonuniform lower bounds; that is, even in the GCT approach to Boolean lower bounds, it is aimed at showing $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. But of course, it is consistent with current theorems that $\mathsf{P} \neq \mathsf{NP}$ yet $\mathsf{NP} \subseteq \mathsf{P/poly}$. Of course, it's also technically possible that $\mathsf{P} = \mathsf{NP}$ and the perm v det conjecture is false!

However, let me point out that the GCT program as it currently exists still seems to me like the first thing to try. If it turns out that any one of (1)-(3) above actually doesn't work, it will mean that the perm v det conjecture (and hence, $\mathsf{P}$ versus $\mathsf{NP}$) is almost unimaginably harder than we currently think it is. (It may be worth noting that this statement is coming from someone who already thinks that the following analogy may be roughly correct, if not inadequate: $\mathsf{P} \neq \mathsf{NP}$ is to our current state of knowledge as the Classification of Finite Simple Groups is to Fermat's Little Theorem). And even if that is the case, understanding the exact way in which the failure occurs will likely be important to making further progress.


What requirements should a denotational semantics for a programming language satisfy to be correct?

What I am writing is essentially contained in babou's answer.
But I wanted to express it a bit differently
emphasizing the point of defining formal semantics.

A formal semantics is a mapping from one class of mathematical structures $P$
(e.g. programs in a programming language)
to another class of mathematical structure $S$ (e.g. domains):
$[[ \cdot]] : P \to S$.

Different conditions required from the mapping give different kinds of semantics.

What conditions should we require from the mapping?
That depends on what we want to do with the semantics.
The required denotational properties depend on
what your intention is in extending the language,
a formal semantics might be wrong or right depending on that intention.

Let's step back for a second and look more generally why we define formal semantics.

  The point of formal semantics is that
  we take the class of mathematical structures that we want to study and
  map it to another class of mathematical structures that we already know something about, and we use that knowledge to study the original class of structures.

If you don't know what denotational properties you require from your denotational semantics of your language and have no use for it,
what is the point of to providing a denotational semantics?
It will not add any confidence that your extended language will behave as you want.

On the other hand,
if you know how the denotational semantics should be
based on your intuitive informal semantics and your intention in extending the language,
then you can use that to formally check that
your programming language matches your intuitive semantics and
will work as you intended
(w.r.t. the requirements you had for your denotational semantics).


How can you state how abstract interpretation gets around Rice's Theorem succinctly?

To be as clear and concise as possible, I'd try saying this

  Abstract interpretation may only over-approximate properties of programs: the most precise abstract value of a program $P$ may be $a$, but any algorithm for computing an abstract value will in general compute some value $a'\geq a$ for $P$ (possibly $\top$ in the worst case).


First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number of vertices.

The solution is a refinement of the idea suggested in the other answer.

First part

Claim: Given a $k$-regular graph $G$ with even number of vertices, one can compute a graph $H$ which is $(k+1)$-regular, and $H$ is Hamiltonian iff $G$ is Hamiltonian.

Proof:
Take two copies of the $k$-regular graph $G$, let call them $G_1$ and $G_2$. For a vertex $v \in V(G)$, let $v_1$ and $v_2$ be the corresponding copies. Create a clique with $k+2$ vertices for $v$. Pick two vertices $v'$ and $v''$ in this clique, and remove the edge between them. Next, connect $v_1$ to $v'$ and $v_2$ to $v''$. Let $C(v)$ denote this component for $v$.

Repeat this for all the vertices of $G$, and let $H$ denote the resulting graph.

Clearly, the graph $H$ is $k+1$ regular. We claim that $H$ is Hamiltonian if and only if $G$ is Hamiltonian.

One direction is clear. Given a Hambiltonian cycle in $G$, we can translate it into a cycle in $H$. Indeed, whenever the cycle visits a vertex $v$, we interpret it as moving from $v_1$ to $v_2$ (or vice versa) while visiting all the vertices in $C(v)$.
As such, this results in a Hamiltonian cycle in $H$. (Note, that this is where we are using the fact that the original number of vertices is even - if the cycle is odd this breaks down.)

As for the other direction, consider a Hamiltonian cycle in $H$. It must be that $C(v)$ is visited by a portion of the cycle that starts in $v_1$, visits all the vertices of $C(v)$ and leaves from $v_2$ (or the symmetric option). Indeed, the Hamiltonian cycle can not enter and leave from the same $v_i$. As such, a Hamiltonian cycle in $H$ as a natural interpretation as a Hamiltonian cycle in $G$.
QED.

Second part

As noted below  by Tsuyoshi any 3-regular graph has even number of vertices. As such, the problem is hard for a $3$-regular graph with even number of vertices. Namely, the above reduction shows the problem is hard for any $k$-regular graph, although the resulting graph has an even number of vertices.

We observe, that this implies that the following problem is NP-hard.

Problem A: Deciding if a k-regular graph $G$ with even number of vertices has an Hamiltonian cycle going through a specific edge $e$.

However, if $k$ is even then given an instance $(G, e)$ we can reduce it to desired problem. Indeed, we replace the edge $e$ by a clique of $k+1$ vertices, as before deleting one edge in the clique, and connecting its two endpoints to the endpoints of $e$, and removing $e$ from the graph. Clearly, for the new graph $H$:

$H$ is $k$-regular.
$H$ is Hamiltonian iff $G$ is Hamiltonian with a cycle using $e$.
$H$ has $|V(G)| + k+1$ vertices => $H$ has odd number of vertices.

Note,  that a $k$-regular graph, for $k$ odd, must have an even number of vertices (just count the edges), As such, there are no $k$-regular graphs with odd number of vertices, with $k$ being odd.

Result

It is NP-Hard to decide if a $k$-regular graph has a Hamiltonian cycle for $k\geq 3$. The problem remains NP-Hard even if the graph has an odd number of vertices.

Of course, it is always possible I made some stupid mistake...

Exercise

If we want to go from a graph that is $k$-regular to a graph that is (say) $2k$-regular then the graph resulting from applying the above reduction repeatedly results in a graph with a size that depends exponentially on $k$. Show, that given a $k$-regular graph $G$,  and $i >2$, one can construct a graph $H$ that is $(k+i)$-regular and its size is polynomial in $k,i$ and $n$, where $n$ is the number of vertices of $G$. Furthermore, $G$ is Hamiltonian if and only if $H$ is Hamiltonian.

(I am posting this as an exercise, not a question, since I know how to solve this.)


The logic in derivation of virtual welfare

I think I've gotten part of the answer. The above statement actually says that for any truthful mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for truthful mechanisms only, then by the Myerson's Lemma the payment rule must be in that form.


Maximum number of geometrically disjoint paths - is the complexity known?

The following paper establishes NP-hardness of essentially all non-trivial questions in this direction:

  Jan Kratochvíl, Anna Lubiw, Jaroslav Nesetril:
  Noncrossing Subgraphs in Topological Layouts. SIAM J. Discrete Math. 4(2): 223-244 (1991)


First of all I think you mean a maximum clique, not all cliques (and even not maximal cliques). As otherwise e.g in $K_n$ there are $2^n−1$ cliques.

If the question is the one that I said, then there is no polynomial time online algorithm for update (unless P=NP). If there is such an algorithm $A$, given a graph $G$, we can find a maximum clique of $G$ in polynomial time. Just start from a graph on $n$ vertex without any edge and add edges of $G$ one by one and update information in each step by $A$. After adding all edges we have a maximum clique. Note that if we use exponential memory at some steps we can do this, but to write on exponential memory we need exponential time as well.

Maybe there are some heuristics.


Monomial decomposition as product of smaller monomials

For the moment, let's restrict to counting these factorizations, rather than listing them.  Warming up with the one-variable case, integer partitions give the answer, as you point out.  You can compute the number $p(n)$ of partitions of $n$ using the generating function
$$\sum_n p(n)x^n = \prod_{i>0} \frac{1}{1-x^i}.$$
This generalizes easily to two variables.  If $p(m,n)$ is the number of "partitions" of the 2-long vector $(m,n)$ (i.e. representations of $(m,n)$ as a sum of positive integral multiples of vectors of the form $(i,j)$ with $i,j\ge0$ and $i+j>0$), then
$$\sum_{m,n} p(m,n)x^m y^n = \prod_{i,j\ge0;\ i+j>0} \frac{1}{1-x^i y^j}.$$
The sequence $p(m,n)$ appears as A054225 in the OEIS.

If you want to list the factorizations rather than count them, look instead at
$$\prod_{i,j\ge0;\ i+j>0} \frac{1}{1-u_{i,j}\ x^i y^j}.$$
For example, the coefficient of $x^2 y^2$ here is
$$u_{2,2} + u_{2,1}u_{0,1} + u_{2,0}u_{0,2} + u_{2,0}u_{0,1}^2 + u_{1,2}u_{1,0} +
  u_{1,1}^2 + u_{1,1}u_{1,0}u_{0,1} + u_{1,0}^2u_{0,2} + u_{1,0}^2 u_{0,1}^2,$$
corresponding to the 9 factorizations of the monomial $x^2 y^2$.

In principle you could write down a two-dimensional recurrence for $p(m,n)$ which is analogous to the recurrence for the ordinary partition numbers.  However, for it to be algorithmically useful (e.g. more efficient than computing the series expansion above), one would need a closed form for the coefficient of $x^m y^n$ in the product
$$\prod_{i,j\ge0;\ i+j>0} (1-x^i y^j).$$


Does the 0-1 principle apply to merge networks?

$\def\et{\mathbin\&}$Yes, and this holds much more generally. Note that a comparator can be thought of as a pair of gates, one of which computes $\min\{x,y\}$, and the other $\max\{x,y\}$. A linearly ordered set is a distributive lattice with $x\land y=\min\{x,y\}$ and $x\lor y=\max\{x,y\}$. We have the following 0–1 principle:

Let $C$ be a circuit with $\land$ and $\lor$ gates, and $\phi(u_1,\dots,u_n)$ a property of values of nodes of $C$ expressible as a conjunction of quasi-identities in the language of lattices (i.e., implications of the form $t_1=s_1\et\dots\et t_k=s_k\to t_0=s_0$, where $t_i$ and $s_i$ are terms using $\land$, $\lor$, and the variables $u_j$).
If $\phi(u_1,\dots,u_n)$ holds whenever $C$ is evaluated in the $\{0,1\}$ lattice, then it holds whenever $C$ is evaluated in an arbitrary distributive lattice.

This is an immediate consequence of the facts that the $2$-element lattice generates the quasivariety of distributive lattices (i.e., every distributive lattice can be embedded in a direct product of $2$-element lattices), and that values of nodes of $C$ are lattice terms in values of the input variables.
Note that $t\le s$ is equivalent to $t\land s=t$, hence we can freely use inequalities instead of equalities in the statement above.
Now, if $C$ is a comparator network with inputs $x_1,\dots,x_n,y_1,\dots,y_n$ and outputs $z_1,\dots,z_{2n}$, it automatically computes a permutation of the inputs, hence the property that it correctly merges sorted lists can be expressed by the conjunction of the quasi-identities
$$x_1\le x_2\et\dots\et x_{n-1}\le x_n\et y_1\le y_2\et\dots\et y_{n-1}\le y_n\to z_i\le z_{i+1}$$
for $i=1,\dots,2n-1$, hence if it works for $0$–$1$ inputs, it also works over arbitrary linearly ordered sets.


Sampling distinct values with probability proportional to their frequency

If the problem is well-defined, I suspect it should be achievable using the following method.  Pick a $m$ values uniformly at random from the stream.  For each value, the expected value of the number of times it is included in the sample will be proportion to its frequency in the stream.  If the frequency of every item is small compared to $1/m$, the probability that an item appears in the sample will be approximately proportional to its frequency in the stream.

If some items appear more often than that, use a sketch (e.g., a CountMin sketch) to estimate the frequency of frequently-occurring items.  You don't need to estimate the frequency of all items, only those whose frequency is higher than $1/(1000m)$ (say), so the sketch can be very efficient.  Then, you select $m$ values uniformly at random from the stream, removing duplicates; if any of the selected values is in the CountMin sketch and has probability close to $1/m$ or larger, then you fix things up (e.g., by dropping it with some probability, as needed).  I'll let you work out the exact arithmetic for how to make the probabilities work out however you want (as it's not clear to me exactly what you want to have happen), but this should work and be very efficient, as the sketch only needs to track frequencies for a small number of items.


Where can I find an elementary small-step structural operational semantics for closures?

Is chapter 29 of Bob Harper's book what you are looking for?


Relation between fixed parameter and approximation algorithm

There are several connections between parameterized complexity and approximation algorithms.

First, consider the so-called standard parameterization of a problem. Here, the parameter is what you would optimize in the optimization version of the problem (the size of the vertex cover for the Vertex Cover problem, the width of the tree decomposition for the Treewidth problem, etc.). Let us concretely look at Vertex Cover. Any kernel with a linear number of vertices for Vertex Cover implies a constant factor polynomial-time approximation algorithm: into the approximate solution, put all the vertices that have been forced into the solution by the kernelization algorithm, and all the vertices of the kernelized instance. On the other hand, lower bounds on the approximation factor imply lower bounds on the size of a kernel. For example, under the Unique Games Conjecture, Khot and Regev (JCSS 2008) rule out approximation algorithms for Vertex Cover with a ratio of any $c<2$, which rules out a kernel for Vertex Cover with at most $ck$ vertices, $c<2$, as well.

EDIT: The argumentation for the kernel lower bound in the previous paragraph is very informal, and to the best of my knowledge it is open whether such lower bounds on the kernel size can be proven, even for Vertex Cover. As @Falk points out in the comments, the argument holds for most (all?) known kernels. However, I don't see how one could exclude the existence of kernelization algorithms where a feasible solution of the kernelized instance has a different approximation ratio than the corresponding solution in the initial instance.

Then, there is the issue of PTAS versus FPTAS. If we want to find a solution within $(1+\epsilon)$ from optimal, we can parameterize by $1/\epsilon$. Then, a PTAS corresponds to an XP-algorithm in the parameterized setting, whereas an FPTAS corresponds to an FPT-algorithm. For an approximation lower bound, we may not expect an EPTAS for any problem whose standard parameterization is W[1]-hard: running the EPTAS with $\epsilon=1/(k+1)$ would solve the problem exactly in FPT time.

Finally, an FPT approximation algorithm is an algorithm with FPT running time and an approximation ratio which may depend on the parameter. For example, the standard parameterization of the Cliquewidth problem has an FPT approximation algorithm with approximation ratio $(2^{3k+2}-1)/k$ (Oum, WG 2005), whereas the standard parameterization of Independent Dominating Set has no FPT approximation algorithm with performance ratio $g(k)$ for any computable function $g$, unless FPT=W[2] (Downey et al., IWPEC 2006). See (Marx, The Computer Journal 2008) for a survey on FPT approximation.


Are there any heuristic-free NP complete problems?

See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. According to that answer, under some natural cryptographic assumptions, for every co-NP-complete problem there is an infinite subset $\Phi$ of instances such that membership in $\Phi$ is polynomial time, and the decision problem restricted to $\Phi$ is trivial (answer always no).

This can be formalized by stating that no co-NP-complete set is P-immune. It is also known (again under cryptographic assumptions) that no NP-complete set is P-immune. So there is another infinite subset $\Phi'$ such that membership in $\Phi'$ is polynomial-time testable and the decision problem restricted to $\Phi'$ always has answer yes. See e.g. Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, doi:10.1137/S009753970444421X.