Problem Clarifications

There's a few things worth mentioning about the problem you asked.

First of all, we need to make sure that the expression you are maximizing is well defined, so the denominator must be non-zero. Simply adding the constraint that $\sum_{j=1}^Mx_j \ge 1$ is enough.

Second, I'd rather not get into the problem of talking about whether an optimization problem is NP-hard, so I'm going to explicitly state a decision version of the problem and then the rest of this answer will talk about that.

For the decision problem, the following are the inputs (note: variables follow the naming scheme from the question except $G$ which I introduce here and stands for "goal"):

Two positive integers $N$ and $M$
A collection of values $R_{ij}\in\{0,1\}$ specified for every pair of $i$ and $j$ with $1 \le i \le N$ and $1 \le j \le M$
A positive integer $T$
A value $G$

And the output is yes if and only if there exists an assignment of values to the variables $x_j$ for $1 \le j \le M$ such that

for all $1 \le j \le M$, $x_j \in \{0,1\}$ and
$1 \le \sum_{j=1}^Mx_j \le T$ and
$\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$

This problem is NP-hard

Reduction

We prove this by reduction from dominating set. The dominating set problem asks for a given graph and number $k$ whether some choice of $k$ vertices has the property that every vertex in the graph is either chosen or next to a chosen vertex.

Suppose we are given an instance of dominating set consisting of a graph $G = (V, E)$ and a number $k$.

For convenience, label the vertices of $G$ as $v_1, v_2, ..., v_{|V|}$.

Then we construct an instance of the problem in question as follows:

$N = M = |V|$
$R_{ij} = 1$ if and only if $(v_i, v_j) \in E$ or $i=j$
$T = k$
$G = 0$

Polynomial Time

Very little needs to be done in the reduction to construct the instance, so this reduction is clearly polynomial time.

Answer preserving

Every instance generated by this reduction has $G = 0$. Therefore the condition that $\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$ is equivalent to the condition that for every $i$ with $1 \le i \le N$, $\sum_{j=1}^Mx_jR_{ij} \ne 0$. That in turn is equivalent to the condition that for all $i =1, ..., N$, there exists some $j \in \{1, ..., M\}$ such that $x_j = R_{ij} = 1$.

In other words, once we work in the fact that $N = M = |V|$ and $T = k$, we see that the instance is a yes instance if and only if there exists an assignment of zeros and ones to the variables $x_j$ such that

at least one and at most $k$ values of $j$ have $x_j = 1$ and
for all $i =1, ..., |V|$, there exists some $j \in \{1, ..., |V|\}$ such that $x_j = R_{ij} = 1$

That in turn is equivalent to choosing between $1$ and $k$ indices (the ones for which $x_j = 1$) such that for all $i =1, ..., |V|$, some one of the chosen indices $j$ has $R_{ij} = 1$.

But $R_{ij} = 1$ if and only if $i = j$ or $(v_i, v_j) \in E$. Thus solving the instance is equivalent to choosing between $1$ and $k$ indices from $1$ to $|V|$ such that for every $i$, either $i$ is chosen or $v_i$ is adjacent in $G$ to some $v_j$ with j chosen.

Restating this one last time, the answer to the instance generated by the reduction is the same as the answer to the following question: is it possible to choose between $1$ and $k$ vertices in $G$ such that each vertex is either chosen or adjacent to a chosen vertex. This is the original dominating set instance.

We have shown that the reduction is answer preserving, so this concludes the proof that the decision problem in question is NP-hard.


Approximating Independent Dominating set on bipartite graphs

After a bit more searching, it appears that what I'm looking for is unlikely to exist.
In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when restricted to bipartite graph (this is the part I missed when I first came across this paper).
[1] Halldórsson, Magnús M., Approximating the minimum maximal independence number, Inf. Process. Lett. 46, No. 4, 169-172 (1993). ZBL0778.68041.


Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

If $M$ is an infinite monoid that has no nontrivial finite quotient, then the only recognizable subsets of $M$ are $\varnothing$ and $M$ itself, whereas there are many more rational subsets.

As a special case, this holds if $M$ is any infinite simple group. (Monoid morphisms map inverse elements to inverse elements: $f(x)f(x^{-1})=f(x^{-1})f(x)=f(1)=1$. Thus, surjective monoid morphisms map groups to groups, and are group morphisms.)


What is complexity of this max-edge subgraph problem?

The generalized problem (such that each vertex $v$ has degree at most $b_v$) is called the $b$-matching problem. Chapter 31 of Schrijver's book is devoted to the subject. It can be solved in strongly polynomial time.

The case that $b_v=2$ for every vertex $v$ has been studied, particularly for providing lower bounds for the traveling salesman problem.


Splay tree potential function: why sum the logs of the sizes?

How to come up with sum-of-logs potential

Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. So $s(a)$ and $s'(a)$ may differ iff $a \in P$.

Moreover, $A$ only rearranges constantly many elements in the search path at any moment. Let's call this type of algorithm "local" algorithm. For example, splay tree is local. It rearranges only at most 3 elements at a time by zig, zigzig and zigzag.

Now, any local algorithm that creates "many" leaves in the after-tree, like splay tree, has the following nice property.

  We can create a mapping $f: P \rightarrow P$ such that

  There are linearly many $a \in P$,  where $s'(f(a)) \le s(a)/2$.
  There are constantly many $a \in P$, where  $s'(f(a))$ can be large but trivially at most $n$.
  Other elements $a \in P$, $s'(f(a)) \le s(a)$.

We can see this by unfolding the change of search path. The mapping is actually quite natural. This paper, A Global Geometric View of Splaying, precisely shows the details how to see the above observation.

After knowing this fact, it is very natural to choose sum-of-logs potential.
Because we can use the potential change of the type-1 elements to pay for the whole rearrangement. Moreover, for other-type elements, we have to pay for the potential change by at most logarithmic.
Hence, we can derive logarithm amortized cost.

I think the reason why people think this is "black magic" is that the previous analysis do not "unfold" the overall change of the search path, and see what really happens in one step.
Instead, they show the change in potential for each "local transformation", and then show that these potential changes
can be magically telescoped.

P.S. The paper even shows some limitation of sum-of-logs potential.
That is, one can prove satisfiability of access lemma via sum-of-logs potential to only the local algorithm.

Interpretation of sum-of-logs potential

There is another way to define the potential of BST in Georgakopoulos and McClurkin's paper which is essentially the same as sum-of-logs potential in Sleator Tarjan's paper. But this gives good intuition to me.

Now I switch to the notation of the paper. We assign a weight $w(u)$ to every node $u$. Let $W(u)$ be the sum of the weight of $u$'s subtree. (This is just the size of $u$'s subtree when the weight of every node is one.)

Now, instead of defining the rank on the nodes, we define the rank to the edges, which they called progress factor.

$$pf(e)=\log(W(u)/W(v)).$$

And the potential of tree $S$ is

$$\Phi(S) = \sum_{e\in S} pf(e).$$

  This potential has a natural interpretation: if during a search we traverse an edge $(u,v)$ we reduce the search space from the descendants of $u$ to the descendants of $v$, a frantional reduction of $W(u)/W(v)$. Our progress factor is a logarithmic measure of this 'progress', hence its name. [From Section 2.4]

Observe that this is almost equal Sleator Tarjan's potential, and it is additive on paths.

edit: It turns out that this alternative definition and the intuition behind it was described long ago by Kurt Mehlhorn. See his book "Data Structures and Algorithms" Volume I, Section III. 6.1.2 Splay Trees,  pages 263 - 274.


Does P = NP imply NP being a strict subset of PSPACE?

No.  It is possible (as far as we know) that $\textbf{P} = \textbf{NP} = \textbf{PSPACE}$.

If $\textbf{P} = \textbf{NP}$, the polynomial hierarchy collapses, i.e., $\textbf{P} = \textbf{PH}$.  See also Can one amplify P=NP beyond P=PH? for an attempt to understand the limits of the implications of $\textbf{P} = \textbf{NP}$, and see Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? for information about why it seems hard to derive the implication $\textbf{P} = \textbf{PSPACE}$.


Does Conway's PRIMEGAME generate all prime powers of 2?

Yes, PRIMEGAME outputs $2^k$ if and only if $k$ is prime.

Conway's original paper is well worth reading if you can track it down.  You can also find a very clear exposition in Richard Guy's paper Conway's prime producing machine (Mathematics Magazine 56(1):26–33, 1983), including the wonderful cartoon below. (Yes, that's Conway with the Alexander horns, referring to a famous drawing by Simon Fraser.)  Conway himself posted a concise proof on the math-fun mailing list.  There's also a brief explanation at the OEIS blog.


How to deal with concept classes with exponential value of VC dimension

One approach would be to stratify your concept class by VC-complexity. For example, suppose that $C$ is the set of all functions $f:\{0,1\}^n\to\{0,1\}$; its VC-dim is $2^n$.
However, you can decompose $C$ in any number of ways. Say, $C_k$ is the collection of all functions whose (minimal) binary tree has depth $k$ or less. Or, $C_k$ is the set of all functions whose Fourier expansion puts no weight on XORs of more than $k$ bits.
Then $C_1\subset C_2 \subset \ldots \subset C_n$, and selecting the appropriate $C_k$ is the problem of model selection. Machine learning theory offers a principled way of doings this via Structural Risk Minimization; here is a good start:
http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=705570&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel4%2F18%2F15247%2F00705570.pdf%3Farnumber%3D705570


Lower bound for orienting an asynchronous ring?

Edit: The answer below was written assuming that the ring is synchronous.

Note that if node ids are chosen from some countable set and you don't care about time complexity, the $\Omega(n\log n)$ messages lower bound for electing a leader in a synchronous ring does not apply.

In that case, there's an $O(n)$ messages algorithm that solves your problem: First, elect a leader using the $O(n)$ time-slicing algorithm of [1], and then, as mentioned in your comment, use the leader to orient the ring. Moreover, $\Omega(n)$ seems to be a trivial lower bound: If $o(n)$ messages are being sent, then there is a segment of $2$ neighboring nodes that do not send/receive any messages throughout the run. By an indistinguishability argument, you can show that there is a run where you get conflicting orientations.

[1] Greg N. Frederickson, Nancy A. Lynch: Electing a leader in a synchronous ring. J. ACM 34(1): 98-115 (1987)


"Divide and conquer" data stream algorithms

Guha et al. '03 give an approximation algorithm for k-median clustering in the streaming model.  Their algorithm divides the data into disjoint pieces, finds O(k) centers for each disjoint piece, and then combines the results to get the k centers.  This seems to be the type of algorithm you're looking for.


If you have an exact and simple formula like $O(n2^n)$ I would go with that. It is more precise than $O((2+\epsilon)^n)$ because it tells you what the epsilon really is. For the same reason I would generally prefer $O(2^{n/2})$ (but with a slashed fraction not a vertical one in the exponent) to $O(1.42^n)$, although in some cases you might want to give the numerical value (or both forms) to show more clearly how a bound compares to previous bounds for the same problem.

If the formula is more complicated ($c^n$ where $c$ is the largest real root of a higher-degree polynomial, say) it can be helpful to replace $c$ by a numeric value. In this case $c$ should always be rounded up, not down, and lower-order terms like the factor of $n$ in the first formula should be omitted (because they are covered by the rounding of $c$).


Complexity of the Hamiltonian Subcycle problem

Some standard terminology:

A set of cycles that spans all nodes is called a cycle cover (or "vertex-disjoint cycle cover").
Cycle covers and perfect matchings are special cases of graph factors: cycle covers are 2-factors (spanning 2-regular subgraphs) and perfect matchings are 1-factors (spanning 1-regular subgraphs).

Polynomial-time algorithms:

As Tsuyoshi pointed out, finding a cycle cover in a given graph can be reduced to the problem of finding a perfect matching in a bipartite graph.
More generally, Tutte (1954) shows the following: for any graph $G$ and any integer $f$ it is possible to construct a graph $G'$ such that $G'$ has a 1-factor (perfect matching) if and only if $G$ has an $f$-factor.

As is well known, there are polynomial-time algorithms for perfect matchings.


Is perfect matching for bipartite graph with no cycles unique?

If the graph is acyclic, which implies that it is also bipartite, then the perfect matching is unique by the following algorithm:

While the graph is not empty, pick a leaf vertex $u$ (which exists because the graph is acyclic) add the edge between $u$ and its unique neighbor $v$ to the matching and then remove $u$ and $v$. If at some point graphs without incident edges are produced, then there is no perfect matching.

This is probably folklore knowledge which would mean that there is no citable source.


I've come to the conclusion that the definition of the complement as I've written doesn't make sense for POVMs. It assumes that the product of two elements is a simultaneous event which is false.

What I found is, because I'm dealing with probabilities and for me this was a "fail" event, I just switch my notion to 1 - "success" and I don't have to use any complements.


What is the computational complexity of sin and cos for floating point inputs?

$\def\tc{\mathrm{TC}^0}\DeclareMathOperator\len{len}$Since there were no other takers, let me expand the comments above.
The fundamental fact here is that approximations of basic arithmetic operations, and trigonometric and cyclometric functions like $\sin x$, $\cos x$, $\arctan x$, are computable in uniform $\tc$ (and therefore in logarithmic space) for fixed-point rational inputs. See e.g. Reif, Reif and Tate, Maciel and Thérien for the basic arguments, however, the most crucial result for the uniform version is the proof that integer division and iterated multiplication are in uniform $\tc$ by Hesse, Allender, and Barrington. This is optimal in that all such functions (except addition and subtraction) are $\tc$-complete.
(These results are typically stated for approximation of functions on a bounded domain, but they apply to arbitrary fixed-point inputs all the same, the point being that as long as there is only a linear number of bits before the binary point, we can reduce the input modulo $2\pi$ by just computing an approximation of $2\pi$ with a sufficent accuracy, followed by a division.)
This has several consequences.
First, $\sin(x2^y)$ and $\cos(x2^y)$ can also be approximated in uniform $\tc$ when $y$ is negative, by converting the input to fixed-point notation up to the desired accuracy. Thus, from now on I will only consider the case with $y\ge0$. We can as well also assume $x\ge0$, as this only affects the sign of sin.
Second, the problem is not really about trigonometric functions, as all the complexity is in reducing the input to a bounded domain. More precisely, we have:

Proposition 1: The following search problems are equivalent up to uniform $\tc$ (and a fortiori log-space) bounded-query Turing reductions:

Given $x,y$, approximate $\sin(x2^y)$ and $\cos(x2^y)$ to $\len(x)$ bits of accuracy.

Given $x,y$, approximate $\sin(x2^y)$ to $\len(x)$ bits of accuracy.

Given $x,y$, approximate $x2^y\bmod 2\pi$ to $\len(x)$ bits of accuracy.

Given $y$ and unary $n$, approximate $2^y\bmod \pi$ to $n$ bits of accuracy.

Here, approximation of $z\bmod2\pi$ is defined so that when $z$ is very close to an integer multiple of $2\pi$, numbers close to $0$ and close to $2\pi$ are both considered valid outputs.
Proof: For $1\le2$, use the identity $\cos z=1-2\sin^2(z/2)$. For $1\le3$, $\sin$ and $\cos$ are $2\pi$-periodic, and computable on $[0,2\pi]$ in $\tc$. For $3\le1$, we can compute $z\bmod2\pi$ from $u=\cos z$ and $v=\sin z$ in $\tc$ using $\arctan(v/u)$ and a little fiddling with quadrants. For $3\le4$, compute $2^y\bmod2\pi$ to $2\len(x)+O(1)$ bits of accuracy, and use $x2^y\bmod2\pi=x(2^y\bmod2\pi)\bmod2\pi$, which holds as $x$ is an integer. QED
Curiously, the argument above gives a reduction of $\cos(x2^y)$ to $\sin(x2^y)$—or actually to $|\sin(x2^y)|$—and conversely we can reduce $|\sin(x2^y)|$ to $\cos(x2^y)$ using the identity $\sin z=\pm\sqrt{1-\cos^2z}$, but I don’t know how to reduce $\sin(x2^y)$ itself to $\cos(x2^y)$.
Third, exponentially scaled uniform $\tc$ circuits can be evaluated with $O(1)$ alternations of existential and universal nondeterminism, and counting. That is,

Proposition 2: The problems from Proposition 1 are computable in the counting hierarchy FCH, and therefore in polynomial space.

(Notice that the trivial algorithm that expands $x2^y$ in full followed by a computation of $\sin,\cos$ only gives an exponential-time upper bound, so this is an improvement.)
The level of CH the problem lands in corresponds to the depth of the uniform $\tc$ circuits, up to small differences depending on the exact definitions of the levels and the circuit model. The recent paper by Allender, Balaji, and Datta tries to optimize the level for some of the basic ingredients (division, iterated multiplication). They do not mention trigonometric functions, so this would need further work, however it is a safe guess that the argument should give something in the vicinity of the 3rd–5th level of CH.


Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution?

There certainly is significance -- and there is a lot that is known about the subject.
If you are willing to make reasonable assumptions, such as the security of cryptographic primitive, then it is straightforward to achieve such a ratio: any secure encryption scheme will provide one example.  Encrypting takes polynomial time if you know the key, while recovering the key if you don't know it takes super-polynomial time (assuming the encryption scheme is secure), so their ratio tends to 0 as the security parameter goes to infinity.
If you want to avoid making any unproven assumptions, then I believe it is an open problem to find such a problem.  In particular, it is an open problem to prove that give an explicit example of a function on $n$ bits such that it takes a circuit of size more than $5n$ to compute the circuit.  See e.g., Is there a better than linear lower bound for factoring and discrete log?.  This corresponds to a constant (strictly greater than zero) ratio.  So, I don't think it is known how to exhibit a problem such that it provably has a ratio that goes to zero in the limit.


Algorithms and structural complexity theory

For many lower bounds in algebraic complexity, I do not know of a natural interpretation in terms of efficient algorithms. For example:

the partial derivatives technique of Nisan and Wigderson
the rank-of-Hessian technique of Mignon and Ressayre (giving the currently best known lower bound on permanent versus determinant)
the degree bound of Strassen (and Baur-Strassen)
the connected components technique of Ben-Or.

In all the above results, they really seem to be using a property of the functions involved, where that property itself seems unrelated to the existence of any particular algorithm (let alone an effective one).

For non-algebraic results, here are a couple of thoughts:

The standard counting argument for the $n \log n$ sorting lower bound does not appear to have an interpretation in terms of efficient algorithms. However, there is an adversarial version of this lower bound [1], in which there is an algorithm which, given any decision tree that uses too few comparisons, efficiently constructs a list that the decision tree sorts incorrectly. But the adversarial version, while not difficult, is significantly more difficult than the counting proof. (Note that this is quite a bit stronger than what one gets by applying the adversary lower bound technique, e.g. as in these notes, since in [1] the adversary itself is efficient.)
I think I've changed my mind about PARITY not in $AC^0$ (even the original proof, let alone the Razborov-Smolensky proof, as pointed out by @RobinKothari). Although the Switching Lemma can be viewed as a randomized (or deterministic) algorithm that lets you swap two rows of a circuit without a big blow-up in size, I think this really has a different flavor than many results in complexity, and specifically the ones you cite. For example, Williams's proof that $ACC \neq NEXP$ is based crucially on the existence of a good algorithm for a particular problem. In contrast, if one could prove something like the Switching Lemma nonconstructively, it would be just as good for proving PARITY not in $AC^0$.

Because of these last two examples - especially sorting, where the standard proof is nonconstructive - it seems to me that the question may not just be about natural interpretations in terms of efficient algorithms, but also somehow about the constructiveness / effectiveness of the proofs of various complexity results (depending on what the OP had in mind). That is, the standard sorting lower bound is not constructive or algorithmic, but there is a constructive, algorithmic proof of the same result.

[1] Atallah, M. J. and Kosaraju, S. R. An adversary-based lower bound for sorting. Inform. Proc. Lett. 13(2):55-57, 1981.


How to evaluate and compare the performance of algorithms in practice?

I believe what you're looking for is the field of Experimental Algorithmics. There is a text by McGeoch, an ACM Journal, and a previous question on this site that provides a reading list for the field.


Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$

The satisfiability problem for these circuits  (i.e., given a circuit $C$ and $u\in[0,1]$, decide whether there is an input $x$ such that $C(x)\ge u$) is in NP, and therefore NP-complete by Neal Young’s comment and Peter Shor’s answer.

We can construct a nondeterministic reduction of the problem to linear programming in the following way. Let $\{a_i:i<m\}$ be all nodes of $C$ that are min or max gates (here $m\le n$, where $n$ is the size of the circuit), and let $b_i$ and $c_i$ be the input nodes of gate $a_i$. For every $i<m$, choose one of the two additional constraints $b_i\le c_i$ or $c_i\le b_i$ (there are $2^m$ possible choices in total). When such a choice is fixed, we can simplify the circuit by replacing each $a_i$ with $b_i$ or $c_i$ as appropriate, and the resulting circuit can be described by a system of $n$ linear equations whose variables are the original input variables of the circuit, and additional variables corresponding to nodes of the circuit.

We also include $m$ inequalities stating that the extra constraints are satisfied, inequalities bounding the original input variables to $[0,1]$, and an inequality stating that the output node has value $\ge u$. Then this is a linear program of size $O(n)$ depending on the choice of the extra constraints, and the circuit attains value $\ge u$ iff there exists a choice of the constraints such that the associated linear program has a solution. Since linear programming is in P, this shows that the problem is in NP.

Also note that the optimum value of a linear program is attained at a vertex of the polytope. This means that the denominator of the optimal solution can be expressed as a determinant of a square matrix of dimension $O(n)$ whose entries are constant-size integers, and there are only $O(1)$ nonzero entries in each row, and as such it is bounded by $2^{O(n)}$.

Reductions of this kind are often useful to give upper bounds on the complexity of satisfiability in propositional fuzzy logics (such as Łukasiewicz logic) and related systems. (In fact, the original problem is a minor variant of satisfiability in Łukasiewicz, which would correspond to circuits with $\min(1,x+y)$ instead of $(x+y)/2$.) An overview of related results can be found in Chapter X of the Handbook of Mathematical Fuzzy Logic, Vol. II.


Why are these two definitions of PPAD equivalent?

For issues with the cited paper, (and hence this answer) see Does PPAD really capture the notion of finding another unbalanced vertex?

Yes. These two problems are equivalent and hence PPAD-complete. The reduction is given on page 505 of Papadimitriou's original 1994 paper (pdf) introducing End of the Line. This is valid even if the degree of the graph is exponential, provided we are given an "edge-recognition algorithm" and a "pairing function". This is also mentioned on the same page. The reduction is given for PPA (the undirected version of PPAD). It can be extended to PPAD as well.


Is it enough for linear program constraints to be satisfied in expectation?

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution."

For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual is infeasible in some of these cases, but that's fine.)

So the expected value of the primal over all runs of the algorithm is $E[f(X)]$. But $E[X]$ is a dual-feasible solution, so there exists a dual solution of value $\frac{e}{e-1}f(E[X])$. The key trick is that $f(X)$ is linear in the dual variables $X$: In fact, here the dual variables are $\alpha_i$ and $\beta_j$, and each matching of vertex $i$ to $j$ adds a total of $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ to the primal objective. So $E[f(X)] = f(E[X])$ and the conclusion follows.

(As a side note, I feel that, as this point is one of the main focuses of their paper (according to the abstract), it would have been nicer if they had explained this point! It doesn't seem at all obvious to me, and I would like to find out when it's true more generally.)


Is there any efficient algorithm for computing all semigroups of order n?

You asked the same question here
and I answered it. Jean-Eric's algorithm is for computing the elements (among other things) of a semigroup defined by a generating set, and is not related to your question.


No, the variant is in P:

for each element $x_i \in X$
find the set $A_{x_i}$ of triples "reachable" from $x_i$:

start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$
iteratively add to $A_{x_i}$ all triples that share at least one element with all triples already in $A$

check if $E \setminus A_{x_i}$ is a solution and also for each triple $(x,y,z) \in E$ check if $E \setminus (A_{x_i} \setminus \{ (x,y,z) \})$ is a solution (remove at most one triple from $A_{x_i}$); if it's not a solution proceed with the next $x_i$ (step 1.)
if no solution is found, repeat the same algorithm 2–3 above "scanning" $y_i \in Y$ and checking $A_{y_i}$
if no solution is found, repeat the same algorithm 2–3 above "scanning" $z_i \in Z$ and checking $A_{z_i}$

To prove that  it is correct note that each $A_{x_i}$ contains at most one element of the solution $M$ of the 3DM:

by your variation constrait $E \setminus M$ is contained in at least one of the $A_{x_i},A_{y_i},A_{z_i}$, suppose $A_{x_i}$: $E \setminus M \subseteq A_{x_i}$;
furthermore $M \cap A_{x_i}$ must contain at most one triple from $A_{x_i}$, otherwise the 3DM constraint “covers each element of $X$, $Y$ and $Z$ exactly once” would be violated


how to formalize the class(?) of computational models and their equivalence

I recommend that you look at realizability theory. In realizability computational models are known as partial combinatory algebras (PCA). They cover a wide range of computational models. There is a 2-category of PCAs in which we can speak not only of equivlence, but also about general morphisms from one computational model to another.

Some references:

Jaap van Oosten's book on realizability.
John Longley's Ph.D. thesis.

John's Ph.D. is probably the best source to read about comparison of PCAs. An abridged version can be found in my Ph.D. thesis.

I should point out that realizability theory is just one way of organizing and structuring the world of computational models in a mathematically precise way. Nevertheless, it is a very sophisticated machinery which shows what can be done.


What is the application of combinatorial game theory

I think Kaveh's comment is the correct answer: applications? We don't need no applications.

But despite all that, combinatorial game theory does appear to have some applications in error correcting codes. See Conway and Sloane, "Lexicographic codes: Error-correcting codes from game theory", IEEE Trans. Inf. Th. 1986.

More simply, if you are willing to think of nim-addition (bitwise exclusive or) as something that came out of combinatorial game theory, then there are plenty of applications, for instance in tabulation hashing, or as one of the components of Schieber and Vishkin's lowest common ancestors data structure, or as one of the components of some block cipher systems.


Cut-elimination for calculus with nats or other inductive datatype?

How about Ulrich Berger's work? For example Strong normalization for applied lambda calculi. The "recursively defined constants" part gets you inductive types, more or less. And don't be put off by the word "untyped", he gets results for typed systems too.


Data structure for getting all matches of a prefix from a large list of strings

For a fixed-length prefix, store them in a hash table.  For a variable-length prefix, use a trie.

If you have a static list and don't need to support insertions or deletions into the list, storing them in sorted order by lexicographic order also works, as you can use binary search to find the matches (they will all be consecutive).


What exactly does "semantically observable" side-effect mean?

A semantics of a program is a model of its behavior which, like any scientific model, ignores aspects that you don't want to study.

An extremely detailed model of the execution of a program would model the physical behavior of the computer that executes it, including the execution time, power consumption, electromagnetic radiation, etc. Such aspects are very rarely taken into account because they are very rarely relevant. Nonetheless they do matter sometimes: a useful model of an airplane autopilot needs to include runtime information, a useful model of a credit card's security needs to include electromagnetic radiation, ...

In typical semantics, side effects such as timing and power consumption are ignored. Even if in a mundane setting where you type an expression at a Haskell interpreter prompt, the printing of the result is a side effect (if you try to print out an infinite object, it matters). If the Haskell interpreter runs out of memory, this is also an observable side effect in a “real-world” model, but not in an idealized model of Haskell that effectively allows unbounded computations.

An observable side effect is one which is modeled in the semantics. In typical models of programming languages, memory consumption is not modeled, so a computation that requires 1TB of storage can be pure, even though if you try to run it on your PC it would observably fail.

Another kind of non-observable side effect is one that is internal to the function. This is, I think, what most semanticists would think of when talking about non-observable side effects. Consider a computation that uses mutable data internally, but does not share this mutable data with any other part of the program. For example, a list sorting function which builds an array with the same elements as the list, sorts the array in place, and returns a list containing the elements as the array in their final order: a semantic model of subexpressions of this function exhibits side effects (modifications of the array), but the function itself has no external side effect, so it is pure.

For a more subtle example, consider a function that writes some data to a temporary file and cleans up after itself. In a semantics where there is always enough room for temporary files and programs do not share temporary files, the function has no side effect; the temporary file acts as extra memory used by the function. In a semantics which takes filesystem full conditions into account, the function has a side effect — it may fail due to external circumstances. In a semantics that allows the machine to crash, the function has a side effect: if there is a crash during the execution of the function, the temporary file may be left behind. In a semantics that allows concurrently executed programs to see and maybe modify the temporary file, the function has a side effect.


Is it hard to find optimal addition chains?

The problem is mentioned as being open in Eric Lehman's PhD thesis "Approximation algorithms for grammar-based data compression" in 2002. From p35 of the thesis:

"Nevertheless, an exact solution to the addition chain problem remains strangely elusive. The M-ary method runs in time polylog(n) and gives a 1 + o(1) approximation. However, even if exponentially more time is allowed, poly(n), no exact algorithm is known."


Lee's algorithm for synthesis of ranking functions in size-change termination proofs

The complexity is acceptable in current verifiers, and has been implemented in at least the AProVE termination analysis tool for term rewrite systems.

They describe their implementation in Lazy Abstraction for Size-Change Termination, by Codish, Fuhs, Giesl & Schneider-Kamp, basing their implementation on the papers you refer to. Performance is good both from an expressiveness point of view and a run-time perspective.

The additional (clever!) trick is to pre-process the search for an appropriate abstraction and ranking function into a SAT problem (along with other search procedures for termination analysis) and having a SAT solver try to simultaneously find an instance. This trick is common in the termination analysis community.


Algorithms for finding all cliques of a given degree in a graph

This maybe: https://papers-gamma.link/paper/32
With an open source implementation here: https://github.com/maxdan94/kClist


Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm

The multi-terminal cut problem (which is also known as the multiway cut problem) has many important applications. In the more general setting, each edge $e$ has a cost $c_e \ge 0$. The goal is to remove a minimum cost set of edges such that in the resulting graph there is no path between any two vertices in $T$. Here is an application in distributed computing.

Each vertex represents an object, and an edge $e$ of cost $c_e$ between them represents the cost of communication between the objects. The objects have to be partitioned to reside on $k$ different machines, with special object $s_i$ residing on the $i^{th}$ machine. The goal is to partition the objects residing on the $k$ machines in such a way that the communication cost between the machines is minimized.


Algebraic topology for termination proofs

As someone somewhat familiar with termination analysis, I'd say that the techniques are only as ad-hoc as the programs they aim to prove termination of, which is to say very ad-hoc indeed.
The crucial approach to scaling such analyses is modularity which allows decomposing the problem into sub-problems. Indeed this usually consists in identifying cycle-like things, typically either cycles in the control flow graph or the call graph, and decomposing it along it's strongly connected components (SCCs). We have very efficient algorithms to do this. No algebraic topology really required here AFAIK.
This is the easy part. The hard part is then identifying variants for each SCC. Here again you can do things in a modular manner, but it's more subtle. The most relevant fields as far as I can tell are constraint solving, and in particular linear programing and general combinatorial principles often related to Ramsey theory. Again, I'm not sure whether algebraic topology really has a role to play.

I will mention a connection between algebraic topology and rewrite theory though, if that can sate your curiosity: there is a strong analogy between homological algebra and confluence of rewrite systems. In particular, there is a connection between simply connected spaces, and (nice) rewrite systems in which every critical pair is closed (which implies confluence).
Here's some nice notes by Yves Guiraud, Eric Hoffbeck, and Philippe Malbos.
And Here's some really nice slides by Gershom Bazerman. Following the links to those papers should get you somewhere.


Do Delaunay triangulations on the sphere maximize the minimum angle?

FIRST ARGUMENT: This was my first answer. Note that this argument is wrong. See my second argument below.

I don't think it's true. The reason that it works in the plane is that in a circle, the inscribed angle subtended by a chord is one half the corresponding central angle. Thus, if we have a triangle with a small angle, any points that would make a larger angle with the opposite edge are inside the empty Delaunay circle, and so aren't one of the points in the configuration we are finding a triangulation of.

Now, suppose you have a Delaunay triangulation on the sphere. Place a point at the center of the sphere, and project all the pionts onto a plane. The edges of the triangles (great circles on the sphere) are all taken to line segments. But the circles giving the empty ball property are taken to ellipses, and so if there's a point outside the projected ellipse but inside the circumcircle of the triangle, this point would make a larger angle with the edge.

EDIT:

Wait a minute. This answer is completely wrong, because the central projection does not preserve angles. I still think the conjecture is wrong, because I have a much more complicated argument that the theorem about inscribed angles does not hold on the sphere. Here's the argument:

SECOND ARGUMENT:

The reason this holds in the plane is that the inscribed angle subtended by a chord is one half the corresponding central angle. That holds because, in the diagram below, we have
$$ CYX_2 = \frac{1}{2} (\pi - X_2 C Y)$$ and $$C Y X_1 = \frac{1}{2} (\pi - X_1 C Y).$$ Subtracting, we get $$ X_1 Y X_2 = \frac{1}{2} X_1 C X_2.$$

Now, in spherical geometry, we get
$$CYX_2 = \frac{1}{2} ( \pi - X_2CY + A(X_2CY) \,) $$
and
$$CYX_1 = \frac{1}{2} ( \pi - X_1CY + A(X_1CY) \,), $$
where $A(XYZ)$ means the area of triangle XYZ.
Subtracting, we get
$$ X_1 Y X_2 = \frac{1}{2} (X_1 C X_2 + A(X_2CY) - A(X_1CY)\,).$$

For the locus of points $Y$ making a constant angle $X_1YX_2$ to be a circle, we thus need that the difference of areas $A(X_2CY) - A(X_1CY)$ depends only on the arclength $X_1X_2$. However, this is incompatible with the observation that $A(XCY)$ is $0$ for $X$ diametrically opposite $Y$ and for $X=Y$, but grows to some maximum size in between.

Thus, the locus of points $Y$ with constant angle $X_1YX_2$ is not a circle. This means that for some triangle $X_1YX_2$ we can find a point $Y'$ outside the circumcircle of $X_1YX_2$ so the angle $X_1YX_2 < X_1 Y' X_2$. We can then use this to build a counterexample to the conjecture that Delaunay triangulations on the sphere maximize the minimum angle.


Low-depth arithmetic complexity of the product of $k$ matrices

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of exhaustivity):

Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication.
Suryajith Chillara, Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach.
Suman K. Bera, Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication.


What is the best place to get BibTeX entries for ICLR and other machine learning papers?

For NeurIPS (previously NIPS), the NeurIPS website itself is a good source: look for a paper, go to its page, and click on the "BibTex" link. Here is a random sample (!):

ICML, COLT, and JMLR appear to have similar BibTex-ready websites: see http://proceedings.mlr.press/. For instance, going to the abstract of a randomly chosen paper from ICML'15:

ICLR does not seem to have this in place; for instance, even checking on Google Scholar, the paper you point out is cited a lot (~4k times), but always as the arXiv version. For conferences or workshops using OpenReview, such as ICLR'18 (I believe it was the first time for this conference), you can get some BibTex entry by clicking on a specific paper, and selecting "Show BibTex":

However, it is unclear to me the resulting citation is better that the ArXiv one.


Dark Integers: General Purpose Computations on Internet Routers

This can be helpful:

Parasitic computing is an example of a potential technology that could be viewed simultaneously as a threat or healthy addition to the online universe. On the Internet, reliable communication is guaranteed by a standard set of protocols, used by all computers. These protocols can be exploited to compute with the communication infrastructure, transforming the Internet into a distributed computer in which servers unwittingly perform computation on behalf of a remote node. In this model, one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication.

In the parasitic computing site you can detailed information on how you can solve a 3-SAT problem using the checksum of TCP packets.

Other useful links:

Seminar report on parasitic computing by K.K.Maharana
Nature's article on parasitic computing (Aug 2001)


reduction of maximum independet set to minimum distance of code

For the benefit of the others, the minimum code distance problem for codes over $\mathbb{F}_2$ is: given a matrix $H$ ($m$ by $n$, with elements from $\mathbb{F}_2$) and a positive integer $w$, does there exist a vector $x$ such that $Hx = 0$ and the hamming weight (number of 1's) of $x$ is at most $w$.

Since both max ind set and the minimum distance of a linear code are NP complete, there are many-one reductions in either direction. However, it doesn't seem that any of the reductions in the literature that I have seen are directly from max independent set. Actually it seems that the known reductions are from other problems related to coding. Alexander Vardy proved the NP-hardness of computing the min distance by reducing from the max-likelihood decoding problem: given a matrix $H$ over $\mathbb{F}_2$, a vector $s$ and a positive integer $w$, does there exist a vector $x$ such that $Hx = s$ and the weight of $x$ is at most $w$. This problem was shown to be NP-hard by Berlekamp and others by reduction from 3-dimensional matching (which is one of the Karp problems and can be reduced to from 3SAT). If you want to reduce max independent set to 3SAT and piece together all these reductions, I guess you can get what you want...

There is a line of work that looks at hardness of approximating the min distance problem. However, reductions there are also from other coding problems. For example, Dumer and others show a hardness of approximation result for the min distance problem by reducing from the nearest codeword problem (given a message find the nearest codeword in hamming distance). A hardness of approximation result for the latter problem was proved by Arora and others, as far as I can tell using two methods: reducing from set cover, or reducing from label cover.


Reaching the double exponential upper bound in Fourier-Motzkin elimination

I think this upper bound is tight. As an example, consider the following system

\begin{align*}
+x_0 & +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
+x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
+x_0 & +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
+x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
-x_0 & +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
-x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
-x_0 & -\frac{3}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
-x_0 & -\frac{3}{2} x_1 -\frac{7}{4} x_2  \le 0 \\
\end{align*}

It has 8 inequalities. Though some of them are identical, it is not a problem since we do not remove redundant constraints. One can also add dummy variables to make them different. Reducing $x_0$, we obtain system with 16 inequalities. Then, reducing $x_1$, we obtain system with $64$ inequalities.

More generally, let $S_{n}^k$ denote the following system of inequalities over $x_0, x_1, \ldots, x_{k - 1}$. Here we assume that $k \le n, n\ge 2$. There will be $2^n$ inequalities in $S_{n}^ k$. Take any $m \in\{1, 2, \ldots, 2^n\}$.  Let $m^{th}$ inequality of $S_{n}^ k$ be
$$\alpha^m_0 x_0 + \ldots + \alpha^m_{k - 1} x_{k - 1} \le 0,$$
where
$$\alpha^m_i = \begin{cases} 2^{-i} & \mbox{if $m \le 2^n - 2^{n - i - 1}$}, \\ -2 + 2^{-i} & \mbox{otherwise.} \end{cases}$$

Here we use a restriction mentioned above : provided $k\le n$, we have that $2^{n - i - 1}$ is an integer.

For example, system above is $S_{3}^3$. It is easy to verify that if we eliminate $x_0$ from $S_{n} ^k$, we obtain $S_{2n - 2} ^{k - 1}$. Indeed, when we eliminate $x_0$, we add up all the inequalities from the first half with all the inequalities from the second half.  Thus we get $2^{n - 1} \cdot 2^{n - 1} = 2^{2n - 2}$ inequalities. What happens with $x_i$ for $i > 0$? In the first $$2^{n - 1} \cdot (2^{n - 1} - 2^{n - i - 1}) = 2^{2n - 2} - 2^{2n - 2 - i} = 2^{2n - 2} - 2^{(2n - 2) - (i - 1) - 1}$$ inequalities a coefficient before $x_i$ will be $2^{-i} + 2^{-i} = 2^{-(i - 1)}$. In the last $2^{-i} + (-2 + 2^{-i}) =  2^{(2n - 2) - (i - 1) - 1}$ inequalities a coefficient before $x_i$ will be $2^{-i} + (-2 + 2^{-i}) = -2 + 2^{-(i - 1)}$. This is $S_{2n - 2}^{k - 1}$, but over variables $x_1, \ldots, x_{k - 1}$. Since, $2n - 2 \ge n - 1 \ge k - 1$, a restriction on the number of variables is also preserved.

Further, if we eliminate $x_1$, we obtain $S_{4n - 6}^{k - 2}$, and so on. After $d$ steps we will have $S^{k - d}_{2^d n - (2^{d + 1} - 2)}$. The latter has exactly
$$2^{2^d n - (2^{d + 1} - 2)} = N^{2^d}/ 2^{2^{d + 1} - 2}$$
inequalities, where $N = 2^n$ is the number of inequalities of the initial system.


Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

Well, the problem is in $P$ after all.
I'll keep the previous answer as it also works for the directed case (which is NPC, as answered on the other question), and shows it is $FPT$ with respect to $l$.

In the undirected case, it is solvable, deterministically via minimum cost flow (this might not work on the scales you are referring to in the question, but its better than exponential algorithm.

The following procedure will decide whether some edge $e=(u,v)\in E$ should be a part of the output graph. In order to answer the original problem just loop over all edges.

In order to create the flow network, do as follows:

Step 1:
Expand $e$ to have a vertex $x_e$ and replace $e$ with the edges $(u,x_e),$$(x_e,u),(v,x_e),(x_e,v)$  (they are directed as a part of the flow network), set their cost to 0.

Step 2: replace every vertex $t$, except for $x_e$ by two vertices $t^-$ and $t^+$, and add an edge $(t^-,t^+)$. Set the cost of these edges to 1.

Step 3: Replace of every edge $\{a,b\}\in E$ with the edges $(a^+,b^-),(b^+,a^-)$. Set the cost of these edges to 0.

Step 4: Add a new vertex $y_e$ and add the edges $(s,y_e),(t,y_e)$ with cost 0.

Step 5: set all capacities to 1.

Now run the min cost flow algorithm, searching for a flow of value 2 from $x_e$ to $y_e$.

Analysis:

Every 2-valued flow from $x_e$ to $y_e$ is a union of a path $x_e\leadsto s\to y_e$ and a path $x_e\leadsto t\to y_e$.
The paths are disjoint, since for every vertex $t$ there's only 1 capacity in the $(t^-,t^+)$ arc.
The returned paths are the two paths whose sum of distances is minimal, and that's also the cost of the found flow. This allows us to add $e$ to the output graph or delete otherwise.


The "probabilistic" element in probabilistic model checking is that the system being checked is probabilistic, not that we add probabilities to an existing deterministic or non-deterministic system.
Thus, what you are checking is whether a probabilistic system satisfies some property. For example "is it true that with probability at least 0.5, the system will reach an error state?"

Now, a probabilistic system is given by a set of states, and transitions between the states. However, this does not give a concrete definition of such systems. Specifically, there are two aspects to be considered:

Are the transitions dependent on an action (e.g. user input, or some environment interaction)
Is time discrete or continuous?

For property 1, if there is no user input, then the system just progresses with time, and is called a Markov Chain (assuming it's behaviour is independent of time). Otherwise, it is called a Markov Decision Process (MDP), where in each step an action is "played", and that determines the probabilities of moving to the next steps.

Now for property 2 - if time is discrete, then at every time point the system progresses. This gives rise to Discrete time Markov chains (DTMC, or often called just MC). If time is continuous, then (after modelling specifically what is meant by that), you get Continuous time Markov chains (CTMC).

You could also speak of continuous time MDPS, although this model is slightly less common. I'm not sure if PRISM supports it.

Different models are used for different settings. For example, CTMCs are common in modelling asynchronous protocols, or chemical reactions, whereas DTMCs are useful for synchronous probabilistic systems.


Finding a simple dual of a simple graph in some surface

For 3-regular graphs, having a simple dual is the same thing as having a polyhedral embedding (an embedding in which each face is a simple cycle and every two faces intersect in an empty set, a vertex, or an edge). But testing for the existence of a polyhedral embedding is known to be NP-complete: see B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf

I'm not sure whether polyhedral embeddability is known to remain NP-complete when restricted to 3-regular graphs — it doesn't seem to be in Mohar's paper — but it seems very likely to be true.


Fourier decomposition in terms of another basis

As pointed out in the comments if $u\in \{\pm 1\}$ then $x=x(u) \in \{0,1\}$ where $$x(u)=\frac{1-u}{2},$$ with $x(-1)=1,$ and $x(1)=0.$ This will then yield
$$f(x)=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ and if we denote the $\{0,1\}$ valued version of $f$ as $\tilde{f},$
$$\frac{1-\tilde{f}(x)}{2}=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ leading to
$$\frac{\tilde{f}(x)}{2}=\frac{1}{2}\left[1+ \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i\right]-2^{n-1}f(0),$$
or
$$\tilde{f}(x)=1-2^{n}f(0)+\sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$
if I haven't made any errors along the way.


Dependent eliminator for empty type in intensional Martin-Löf type theory

$\text{absurd} : (A : \text{U}) \to 0 \to A$ and $\text{elim} : (A : 0 \to \text{U}) \to (x : 0) \to A\,x$ are equivalent. To go right, use $\text{absurd}\,(A\,x)\,x$. To go left, use $\text{elim}\,(\lambda\,x.\,A)\,x$. Also, both types are propositions because of the $0$-s in domains. There's not much reason to assume or use $\text{elim}$ instead of $\text{absurd}$.


There are some relatively recent papers by Emanuele Viola et al., which deal with the complexity of sampling distributions. They focus on restricted model of computations, like bounded depth decision trees or bounded depth circuits.

Unfortunately they don't discuss reversible gates. On the contrary there is often loss in the output length. Nevertheless these papers may be a good starting point.

Bounded-Depth Circuits Cannot Sample Good Codes

The complexity of Distributions


Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

No, it's not true. Consider this game where the row player's actions are A,B,C and column's are D,E (shown are the row player's payoffs):

    D     E
A   1     0
B   0     1
C  0.6   0.6

I think that in any equilibrium, the row player plays only C.

But now if the column player uses a no-regret algorithm, every sample will either be action D or E, and the row player's best response will always be either A or B. So the row player will never play C in the entire empirical history.


The answer to both questions is yes.
The standard reduction from 3-SAT to 3DM – as used by Garey and Johnson, for example – is not parsimonious, but there is a sequence of parsimonious reductions that goes:
3-SAT → 1-IN-3-SAT → MONOTONE-1-IN-3-SAT → 3DM
Moreover, these reductions can be done in a way that preserves planarity. The details can be found in [1, 2]. The key reduction MONOTONE-1-IN-3-SAT → 3DM is from [1]. It is shown to be parsimonious by [2], which also shows how to do the other reductions in a parsimonious way. The reduction from 3-SAT to PLANAR-3-SAT is done using the crossover gadget from [3], which [2] also shows to be parsimonious.
[1] M.E Dyer, A.M Frieze, Planar 3DM is NP-complete, Journal of Algorithms, Volume 7, Issue 2 (June 1986), Pages 174-184. PDF
[2] Harry B. Hunt, III, Madhav V. Marathe, Venkatesh Radhakrishnan, and Richard E. Stearns. The Complexity of Planar Counting Problems. SIAM J. Comput. 27, 4 (August 1998), 1142-1167. arXiv:cs/9809017
[3] David Lichtenstein. Planar Formulae and Their Uses, SIAM Journal on Computing 11:2 (1982), 329-343. doi:10.1137/0211025


How are new probabilities computed when simulating measurement on a set of qubits?

Let
$$P(0) = |a|^2 + |c|^2 + |e|^3 + |g|^2.$$
This is the probability of observing $0$.

Then
\begin{eqnarray*}
w &=& a \big/ \sqrt{P(0)}, \\
x &=& c \big/ \sqrt{P(0)}, \\
y &=& e \big/ \sqrt{P(0)}, \\
z &=& g \big/ \sqrt{P(0)}.
\end{eqnarray*}


Here are some interesting anecdotes about TCS giants. Some of them are dark, quite possibly the opposite of 'fun', but you also might get something you're looking for. This also might work best as a community wiki.

Kurt Gödel:

Gödel was concerned with developing a mathematical framework for describing the effectively computable. Both he and Alonzo Church developed candidate frameworks (Recursion and Lambda Calculus respectively), but neither satisfied him. In fact, Gödel acted very much as the ultimate skeptic - no proposal which satisfied all of his contemporaries seemed to satisfy him. He involuntarily became the de facto litmus test for effective computation. Alan Turing's A-Machines (we later began to call these Turing Machines...) were the first idea to satisfy Gödel, and this launched a lot of the original interest in Turing's paper. Curiously, Gödel later wished to revoke his support but things were already set in motion.
Gödel was a good friend of Einstein. In fact, they purportedly walked together often when they were both at Princeton. Supposedly Einstein once made a comment to a colleague implying his work meant very little to him; that the reason he chose to stay at Princeton was for his walks with Gödel.
He purported to have a proof that God exists.
Gödel was a very suspicious individual. His own work in Physics and Philosophy convinced him that work of Leibniz was suppressed by a conspiracy against him despite a lack of any solid evidence. In his later years he became increasingly frightened of being poisoned to death and would only eat food his wife taste-tested for him. At one point his wife became hospitalized for an elongated period, during which time he was afraid to eat anything and starved himself to death. It's interesting, but perhaps not fruitful, to speculate about Turing's suicide by poison and what role this may have played in Gödel's conspiracy theory.

Alan Turing:

The "Father of Computer Science". Turing's original work involved describing mathematically what we should think of as effective computation. Right before publication, having just learned of the lambda calculus of Alonzo Church, he scrawled down a proof which showed equivalence between his machines and Church's calculus.
Turing was a student of Bertrand Russel and also a Philosophy student of Wittgenstein. I believe I have heard Turing became very frustrated at his inability to penetrate Wittgenstein's philosophy and eventually retreated from the subject.
He is considered a war hero. Turing's machines, and in particular his modifications to the Bombe, helped the Bletchey Park code breaking effort in WWII to crack the German Enigma machines.
Because Turing was a homosexual and also likely because of his once high security clearance, the British Government striped him of his status and forced him to undergo extreme hormone treatment. Due to this persecution and other factors Turing commit suicide, by consuming an apple he had laced with cyanide. There is speculation as to why Turing chose to commit suicide this way. The British Government just recently released a formal apology for their actions, 70 years later.

John Von Neumann:

With influences well beyond Computer Science, Von Neumann may have been the last well known poly-mathematician. His work helped to develop quantum physics, game theory, theoretical computer science, PDEs, microscopy, systems architecture, functional analysis and more.
Von Neumann was entirely unimpressed by John Nash's seminal contributions to Game Theory. Von Neumann is reported to have shrugged and said, "[Nash Equilibrium] is just a fixed point theorem."
Von Neumann was known for his terrible driving. Supposedly the cause of many of his car accidents was the fact he insisted on reading at the wheel.
Unlike many other scientists in the Manhattan Project, including Einstein, who would later come to regret their involvement in the project and actively protested nuclear programs/stockpiling, John Von Neumann never had any regrets. He continued to work on the nuclear proliferation of the United States for some time.


Complexity of finding a consistent hyperplane

Second version, hopefully correct.

I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.

Let us first reduce the strict feasibility problem $\exists? x: Ax < b$ to finding a linear separator. Towards this, notice that you can reduce to the special case $b=0$: just transform the constraints to
$$
Ax + tb < 0, \\
t < 0
$$
If $Ax < b$ is feasible for some $x$, then $(x, -1)$ is feasible for the problem above. Conversely, if $(x, t)$ is feasible for the problem above, then $\tilde{x} = -x/t$ is feasible for $A\tilde{x} < b$.
This reduction just adds a row and a column to $A$, and a new variable $t$.

Assume then that you are given the problem $Ax < 0$.
Create a data set which has one point labeled red for every row of $A$, and is equal to that row. It also contains the origin $0$, labeled blue. Any hyperplane $H$ separating the red-labeled points from the blue-labeled origin gives a solution to $Ax < 0$: just take the normal of $H$ in the direction of the origin to be $x$.

The final step is to reduce the feasibility problem $Ax \le b$ to the strict feasibility problem $Ax < b$. We argue that given an oracle for the strict feasibility problem, we can solve the feasibility problem. Let $S$ be an inclusion-maximal set of constraints such that the system $\forall i \in S: (Ax)_i < b_i$ is feasible: we can find $S$ in at most $m$ calls to the oracle (assuming $A$ is $m\times n$). If $S$ contains all constraints, we are done. Otherwise, it is not hard to see that, if $Ax \le b$ is feasible, then for any $i \not \in S$ the constraint $(Ax)_i \le b_i$ must be satisfied with equality for all feasible $x$. Use one (or more) of these constraints to eliminate one (or more) of the variables, and recurse on the remaining variables.

This equivalence between finding a linear separator and linear programming is surely well-known, but I do not know what the right reference is. For example, I have seen something like the final reduction above attributed to Chvatal.


Extensions of beta-theory of lambda calculus

Yes. There is for example beta + the rule {s = t | s and t are closed unsolvable terms}. This is as far as I remember not equal to beta-eta, and is consistent. See mathgate for a short description and reference to Barendregt.


Does every greedy algorithm have matroid structure?

Actually, the complete and general description of a problem that can be solved by a greedy algorithm is a matroid embedding, which generalizes both the concept of a matroid and that of a greedoid. The answer is no—a problem solvable by a greedy algorithm need not have a matroid structure, but it will have the structure of a matroid embedding (which is, alas, much more complicated).

A mental model for some of this could be finding minimum spanning trees. The structure used by Kruskal's algorithm is a matroid, but that used by Prim's algorithm (which requires a start node) is not. (It is, however, a greedoid—and a matroid embedding.)

Helman et al. (1993), in their paper An Exact Characterization of Greedy Structures define their notion of a greedy algorithm in terms of set systems, which is the same formalism that is used for matroids and greedoids. A set system $(S,\mathcal{C})$ consists of a set $S$ and a collection $\mathcal{C}$ of subsets of $S$, the so-called feasible sets. A basis for the set system is a maximal feasible set, that is, a set that is feasible but not contained in any other feasible set. An objective function $f:2^S\rightarrow\mathbb{R}$ associates each subset of $S$ with a value. An optimization problem, in this formalism, consists in finding a basis of maximum objective value for a given set system and objective function.

The greedy algorithm, defined in terms of this formalism, is quite simple: You start with the empty set, and successively add a single element until you reach a basis, always ensuring that (i) your set is feasible at each step, and (ii) the element you add maximizes the objective function of the resulting result, wrt. all the alternative elements you could have added. (That is, conceptually, you try adding all feasible alternatives, and choose the one yielding the highest objective value.)

You could, perhaps, argue that there might be other forms of greedy algorithm, but there are several textbooks on algorithms and combinatorial optimization that describe this set-system based algorithm as the greedy algorithm. That doesn't prevent you from describing something that doesn't fit, but could still be called greedy, I suppose. (Still, this does cover anything that could potentially have a matroid structure, for example, though it is much more general.)

What Helman et al. do is that they describe when this algorithm will work. More specifically:

They show that for linear objective functions (where the objective value is the sum of element weights), the greedy algorithm will work exactly on the structure they define as a matroid embedding;
They give a similar characterization for so-called bottleneck objectives (where the objective value of a set is equal to the minimum over the individual element weights); and
They give an exact characterization of which objective functions (beyond linear ones) are optimized by the greedy algorithm on matroid embeddings.


Finding largest subgraph that contains a given edge and admits a cycle cover

Deterministically, you can do it as follows: Give your edge $e$ the weight $n+1$ and add a self-loop of weight zero to each node that does not have one so far. Existing edges get weight one. By removing the weight zero loops,
a maximum weight cycle cover in the new graphs induces a partial cycle cover in the old graph that (1) contains your edge $e$ and (2) has a maximum number of edges. The vertices of the partial cycle cover induce the graph you are looking for. If the cycle cover in the new graph does not contain $e$ at all, then
there is no such subgraph.

You can compute a maximum weight cycle cover by reducing it to maximum weight perfect matching.


Self-intersecting walk in expander graphs

I think only knowing the graph is an expander does not fix the value you are asking. If you are doing random walk naively then when the graph has bounded degree there is constant probability that the walk will reach the same vertex after just 2 steps, and therefore the expected number of steps is constant.

I guess you want to exclude that case by saying the random walk cannot take the same edge in two consecutive steps. But still there are different cases here: if we take the union of a degree 4 expander graph and a grid, it will still be an expander (with worse parameters), but there is constant probability that the walk return to the same position in 4 steps, and therefore the expected number of steps is again constant. On the other hand, if we take a random graph, since the girth is high the expected number (or in fact the minimum) of steps for any vertex to be revisited will be super-constant.

$\sqrt{n}\log n$ is definitely a safe upperbound because of the birthday paradox argument. I guess the answer for random graphs might be $\sqrt{n}$, because if you take a random walk of length significantly smaller than $\sqrt{n}$, with good probability the induced subgraph will be just the path and do not have more edges. In general if the induced graph on the set of visited vertices has a lot of edges outside the path, it means the walk "had many chances" to visit some vertex twice.

I understand this may not answer your question completely but I couldn't figure out how to leave a comment like Suresh Venkat did.


The relationship between degree of vertex and size of dominating set

If all vertices have degree at least $d$ then there is always a dominating set of size $\frac{n \ln n}{d} + 1$. Pick a random set $S$ of size $\frac{n \ln n}{d}$. For a particular vertex $v$, the probability that $v$ is not dominated by $S$ is upper bounded by $(1 - \frac{d}{n})^{\frac{n\ln n}{d}} \leq e^{-\ln n} = \frac{1}{n}$. Introduce an indicator variable for every vertex that is $1$ if it is not dominated by $S$ and $0$ otherwise. The number of undominated vertices is the sum of indicator variables, so the expected number of undominated vertices is at most $n \cdot \frac{1}{n} = 1$. Hence there exists a set of size $\frac{n \ln n}{d}$ that leaves at most one vertex undominated, add this vertex to the dominating set.

For your question it means that if all vertices have degree at least $n^k$ then there is a dominating set of size $n^{1-k}\log n + 1$. Would be nice to see if one can get rid of the $\log n$ or not.


Formalization of dependent record types/kinds in MLTT or variant thereof?

I do not know how much of the paper it covers but we do have a module based on it in the standard library:

https://agda.github.io/agda-stdlib/Data.Record.html


Algorithms for Nash equilibrium computation.

Perhaps the 2008 paper presented at the Symposium on Algorithmic Game Theory
by Hémon, Rougemont, and Santha, "Approximate Nash Equilibria for Multi-player Games" could help?
They "exhibit polynomial-time algorithms for additive approximation" for $n$-player games.


Defining finite sets inductively in a proof assistant?

There are many variants of finite sets in constructive mathematics. One that can be defined using just inductive definitions, and is therefore amenable to formalization in type theory, is the Notherian finiteness by Thierry Coquand and Arnaud Spiwack. The idea is to define a set or a type $A$ to be finite if the following holds: every sequence $a : \mathbb{N} \to A$ contains a duplicate. The trick is to express an equivalent condition using inductive definitions, so that we get an induction principle for reasoning about such sets.

The definition of Notherian finiteness from section 2.3 of the linked paper can be translated to Coq like this:

(* [occurs x l] states that x appears in the list l *)
Inductive occurs {A : Type} : A -> list A -> Type :=
  | occurs_head : forall x k, occurs x (cons x k)
  | occurs_tail : forall x y k, occurs x k -> occurs x (cons y k).

(* [has_duplicates l] states that [l] has a duplicate, i.e., that an element appears in it twice. *)
Inductive has_duplicates {A : Type} : list A -> Type :=
  | has_duplicates_head : forall x l, occurs x l -> has_duplicates (cons x l)
  | has_duplicates_tail : forall x l, has_duplicates l -> has_duplicates (cons x l).

(* An auxiliary definition: a list `l` is said to be `notherian` if it contains a duplicate, or if every extension of `l` by one element is `notherian`. *)
Inductive notherian (A : Type) : list A -> Type :=
  | N_duplicates : forall l, has_duplicates l -> notherian A l
  | N_step : forall l, (forall a, notherian A (cons a l)) -> notherian A l.

Definition NotherianFinite A := notherian A nil.

If you're willing to use quotient types or the higher inductive types from homotopy type theory, then you can have a look at the defintion of finite sets Finite in the HoTT library. It says that a type X is finite if there is a number n such that X is merely equivalent to the standard finite set {0, 1, ..., n-1}. The word "merely" here means that we truncate the existence, i.e.,
$$\textstyle\mathsf{Finite}\, X \mathrel{{:}{=}}
\sum_{n : \mathbb{N}} \left\| X \simeq \mathsf{Fin}\,n\right\|$$
where $\mathsf{Fin}\,n$ is the standard finite set $\sum_{k : \mathbb{N}} (k < n)$.


Difference between PRAM and machine model in dynamic multithreading

Dynamic multithreading (like Cilk) does not involve processors working synchronously (in lockstep), for instance. PRAM is (sort of) SIMD, while DM is (sort of) MIMD. Notice that there are async PRAM models, but none seem to have gathered enough pull. Notice also that DM assumes logical parallelism, while PRAM is very much explicit parallelism, and that PREM machines (unlile DM) don't really exist beyond the lab.


What are the morphisms of Adj(C,T) - the category whose objects are the adjunctions of a given monad?

The definition of morphism of adjunctions may be found in MacLane's book. Let $F:\mathcal C\rightarrow\mathcal D$, $G:\mathcal D\rightarrow\mathcal C$, $F':\mathcal C'\rightarrow\mathcal D'$, $G':\mathcal D'\rightarrow\mathcal C'$, and let $(F,G,\eta,\varepsilon)$, $(F',G',\eta',\varepsilon')$ be adjunctions. A map of adjunctions from the first to the second is a pair of functors $L:\mathcal C\rightarrow\mathcal C'$, $K:\mathcal D\rightarrow\mathcal D'$ such that $KF=F'L$, $LG=G'K$ and $L\eta=\eta'L$ (or, equivalently, $\varepsilon K=K\varepsilon'$).

In the case of the category of adjunctions of a monad, the category $\mathcal C$ on which the endofunctor of the monad acts is fixed, so $\mathcal C'=\mathcal C$ and one considers the above definition only in case $L=Id_{\mathcal C}$.


Given a subset of of the hypercube and an affine transform of it, find the affine map

From D.W.'s comment, we see that your problem is equivalent to the same problem with $s=0$ (and with $d$ only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem over $\mathbb{F}_2$, just phrased slightly differently. (Usually CodeEq is phrased as "you have two $d \times n$ generator matrices of linear codes, is there a permutation of the $n$ columns which makes the two generator matrices have the same row-span?" In your case, the action by $GL(d,2)$ is the action which preserves the row-span, and the fact that you are only interested in a set of vectors means you essentially have an action of $S_n$ on the columns.)

Here's what's known about its complexity:

This problem is at least as hard as Graph Isomorphism (essentially goes back to Luks '93 "Permutation groups and polynomial-time computation", see Miyazaki, though it is often cited to Petrank-Roth '97)
As with GI, it is in $\mathsf{NP} \cap \mathsf{coAM} \cap \mathsf{SZK}$, by essentially the same proof as for GI.
It's no harder than Tensor Isomorphism [GQ19]
The best known worst-case upper bound is $2^{O(n)}$ (due to Babai, cf. [BCGQ11])
There is an algorithm by Sendrier 2000 that may work well in practice, depending on what kinds of codes you are looking at.


On the complexity of Bandwidth Minimization

The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper.

On the other hand, it is also known that for any $k$, whether a given graph has bandwidth at most $k$ can be decided in $O(f(k)n^{k+1})$ time. This implies that the bandwidth problem is in $XP$. See the another paper by Saxe.


Universal Approximation Theorem — Neural Networks

Cybenko's result is fairly intuitive, as I hope to convey below; what makes things more tricky is he was aiming both for generality, as well as a minimal number of hidden layers.  Kolmogorov's result (mentioned by vzn) in fact achieves a stronger guarantee, but is somewhat less relevant to machine learning (in particular, it does not build a standard neural net, since the nodes are heterogeneous); this result in turn is daunting since on the surface it is just 3 pages  recording some limits and continuous functions, but in reality it is constructing a set of fractals.  While Cybenko's result is unusual and very interesting due to the exact techniques he uses, results of that flavor are very widely used in machine learning (and I can point you to others).

Here is a high-level summary of why Cybenko's result should hold.

A continuous function on a compact set can be approximated by a piecewise constant function.
A piecewise constant function can be represented as a neural net as follows.  For each region where the function is constant, use a neural net as an indicator function for that region.  Then build a final layer with a single node, whose input linear combination is the sum of all the indicators, with a weight equal to the constant value of the corresponding region in the original piecewise constant function.

Regarding the first point above, this can be taken as the statement "a continuous function over a compact set is uniformly continuous".  What this means to us is you can take your continuous function over $[0,1]^d$, and some target error $\epsilon>0$, then you can grid $[0,1]^d$ at scale $\tau>0$ (ending up with roughly $(1/\tau)^d$ subcubes) so that a function which is constant over each subcube is within $\epsilon$ of the target function.

Now, a neural net can not precisely represent an indicator, but you can get very close.  Suppose the "transfer function" is a sigmoid.  (Transfer function is the continuous function you apply to a linear combination of inputs in order to get the value of the neural net node.)  Then by making the weights huge, you output something close to 0 or close to 1 for more inputs.  This is consistent with Cybenko's development: notice he needs the functions involved to equal 0 or 1 in the limit: by definition of limit, you get exactly what I'm saying, meaning you push things arbitrarily close to 0 or 1.

(I ignored the transfer function in the final layer; if it's there, and it's continuous, then we can fit anything mapping to $[0,1]$ by replacing the constant weights with the something in the inverse image of that constant according to the transfer function.)

Notice that the above may seem to take a couple layers: say, 2 to build the indicators on cubes, and then a final output layer.  Cybenko was trying for two points of generality: minimal number of hidden layers, and flexibility in the choice of transfer function.  I've already described how he works out flexibility in transfer function.

To get the minimum number of layers, he avoids the construction above, and instead uses functional analysis to develop a contradiction.
Here's a sketch of the argument.

The final node computes a linear combination of the elements of the layer below it, and applies a transfer function to it.  This linear combination  is a linear combination of functions, and as such, is itself a function, a function within some subspace of functions, spanned by the possible nodes in the hidden layer.
A subspace of functions is just like an ordinary finite-dimensional subspace, with the main difference that it is potentially not a closed set; that's why cybenko's arguments all take the closure of that subspace.  We are trying to prove that this closure contains all continuous functions; that will mean we are arbitrarily close to all continuous functions.
If the function space were simple (a Hilbert space), we could argue as follows.  Pick some target continuous function which is contradictorily supposed to not lie in the subspace, and project it onto the orthogonal complement of the subspace.  This residual must be nonzero.  But since our subspace can represent things like those little cubes above, we can find some region of this residual, fit a little cube to it (as above), and thereby move closer to our target function.  This is a contradiction since projections choose minimal elements.  (Note, I am leaving something out here: Cybenko's argument doesn't build any little cubes, he handles this in generality too; this is where he uses a form of the Riesz representation theorem, and properties of the transfer functions (if I remember correctly, there is a separate lemma for this step, and it is longer than the main theorem).)
We aren't in a Hilbert space, but we can use the Hahn-Banach theorem to replace the projection step above (note, proving Hahn-Banach uses the axiom of choice).

Now I'd like to say a few things about Kolmogorov's result.  While this result does not apparently need the sort of background of Cybenko's, I personally think it is much more intimidating.

Here is why.  Cybenko's result is an approximation guarantee: it does not say we can exactly represent anything.  On the other hand, Kolmogorov's result is provides an equality.  More ridiculously, it says the size of the net: you need just $\mathcal O(d^2)$ nodes.  To achieve this strengthening, there is a catch of course, the one I mentioned above: the network is heteregeneous, by which I mean all the transfer functions are not the same.

Okay, so with all that, how can this thing possible work?!

Let's go back to our cubes above.  Notice that we had to bake in a level of precision: for every $\epsilon>0$, we have to go back and pick a more refined $\tau >0$.  Since we are working with (finite) linear combinations of indicators, we are never exactly representing anything.  (things only get worse if you include the approximating effects of sigmoids.)

So what's the solution?  Well, how about we handle all scales simultaneously?  I'm not making this up: Kolmogorov's proof is effectively constructing the hidden layer as a set of fractals.  Said another way, they are basically space filling curves which map $[0,1]$ to $[0,1]^d$; this way, even though we have a combination of univariate functions, we can fit any multivariate function.  In fact, you can heuristically reason that $\mathcal O(d^2)$ is "correct" via a ridiculous counting argument: we are writing a continuous function from $\mathbb{R}^d$ to $\mathbb R$ via univariate continuous functions, and therefore, to capture all inter-coordinate interactions, we need $\mathcal O(d^2)$ functions...

Note that Cybenko's result, due to using only one type of transfer function, is more relevant to machine learning.  Theorems of this type are very common in machine learning (vzn suggested this in his answer, however he referred to Kolmogorov's result, which is less applicable due to the custom transfer functions; this is weakened in some more fancy versions of Kolmogorov's result (produced by other authors), but those still involve fractals, and at least two transfer functions).

I have some slides on these topics, which I could post if you are interested (hopefully less rambly than the above, and have some pictures; I wrote them before I was adept with Hahn-Banach, however).  I think both proofs are very, very nice.  (Also, I have another answer here on these topics, but I wrote it before I had grokked Kolmogorov's result.)


First thing to say that the minimality here is subset-minimality (as opposed to cardinality-minimality). Observe that minimality is not actually needed. The main objective is to block the assignment A, which led to the conflict. However minimality is beneficial because like this you block other "bad" assignments as well.

Similarly, multiple MUCs are not a problem. All we need is to block the  assignment A so picking an arbitrary MUC is sufficient. Note also that the number of MUCs can be exponential, so going through all of them might not even be feasible and typically is not done in this context.

To compute an MUC there're various algorithms. The easiest is to go through each literal L in the set and remove it. If the set is still UNSAT, then move onto the next literal. If the set is SAT, put the literal L back (it's needed).  If I may shamelessly plug in my paper, here's more algorithms [1].

[1] Minimal Sets over Monotone Predicates in Boolean Formulae. J Marques-Silva, M Janota, A Belov. CAV13


Pseudorandom generator for finite automata

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known.

But if $d$ is very small, say a constant, then you can do better and achieve logarithmic seed length -- I think, this is something I thought about years ago but never wrote down.  The trick is to use Nisan's result RL $\subseteq$ SC.  Basically, he shows that if you are given a branching program then you can find a logarithmic-seed distribution that fools it.  His result extends to a small number of branching programs.  So if $d$ is a constant then you can enumerate over all possible finite-state automata, and find a distribution that fools all of them.  This should still work as long as the number of programs is polynomial in $n$.


Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory

In fact there is known a regular graph $G$ for which zero-error capacity  $\Theta(G)$ is less than the Lov$\acute{a}$sz bound $\vartheta(G)$. W. Haemers in $[1]$ has proved that for the complement of Schl$\ddot{a}$fli graph $G$ the following holds: $\Theta(G)\leqslant7<\vartheta(G)=9$.

In $[2]$ it is noted that "The best known upper bounds on $\Theta(C_m)$ and $\Theta(\overline{C}_m)$ for $m$ odd and greater than $5$ are given by the Lovasz theta function ...". From this I conclude that that the answer to your last question is no (since then I don't know any results improving on this.).

Finding Shannon capacity even for $C_7$ would be a major breakthrough for this hard problem. Additionally, it can be noticed that

  "it is not known if the problem of deciding whether the Shannon capacity of a given input graph exceeds a given value is decidable".

W. Haemers, “On some problems of Lov$\acute{a}$sz concerning the Shannon capacity of a graph,” IEEE Trans. on Information Theory, vol. 25, no. 2, pp. 231–232, Mar. 1979.
T. Bohman, "A limit theorem for the Shannon capacities of odd cycles. II," Proceedings of the American Mathematical Society, 2005.
N. Alon, "Combinatorial Reasoning in Information Theory".


Inspirational talk for final year high school pupils

There is a neat way to introduce zero-knowledge proofs to students, which I think is originally due to Oded Goldreich (please correct me if I'm wrong).

You have a red ball and a green ball, which poor colorblind Charlie believes are the same color. You want to convince Charlie that you can tell the difference between the red ball and green ball, and you want to do this in a way that Charlie does not learn which is red and which is green. (You want to prove something is true, in such a way that no one else can turn around and claim a proof of that something as their own.) How can you do this? Or is it impossible?

One protocol is the following. Charlie puts a ball in each hand, then chooses to either switch the two balls behind him, or not. Then he presents the two balls again. If you can always detect whether he switched the two balls or not, then Charlie is increasingly convinced that you can tell the difference between them. If Charlie does this shuffle at random and you really can't tell the difference between the colors, then you will only guess correctly with probability $1/2$. After $k$ trials, Charlie should be convinced that you can tell the difference with probability at least $1-1/2^k$.

Now while Charlie becomes increasingly convinced that you can tell the difference, he frustratingly never learns which ball is red and which one is green.


Would polynomial solution for #P-complete problem mean polynomial solution for PSPACE problem?

We know that #P is included in FPSPACE (the class of function problems corresponding to PSPACE), but we currently do not know if this inclusion is proper or not. Therefore, a polynomial time algorithm for #P-complete problems does not necessarily imply a polynomial time algorithm for all problems in PSPACE.


Dynamic all-pairs shortest paths - O(1) query

theory results:

exact:

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

approximate:

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

implementation for road networks:

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato Fonseca F. Werneck: Customizable Route Planning. SEA 2011: 376-387

(updates only to cost of edges, might be possible to extend to addition and deletion of edges)

comment

none of the methods above achieves O(1) query time

note that if you use lots of space for a data structure, it probably means that you will need significant time to update the data structure in case the graph changes
(low query time at the cost of high update time)

if updates are rare, it might be worth it.
what is the application?


Is there a notion of computability on sets other than the natural numbers?

This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.

There is an entire area of theoretical computer science which studies computability in analysis, algebra and topology. Of central importance is the notion of computability for real numbers. In fact Turing's original paper on Turing machines starts with the following sentence:

  The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.

Sometimes it pays to go back to the source.

There are several ways to set up computability on general sets, of which one of the most general ones is realizability theory. The idea of realizability theory goes back to Kleene's paper On the Interpretation of Intuitionistic Number Theory from 1945, but has since been generalized and developed into a mini-branch of computability, with a good mix of category theory, see for instance Jaap van Oosten's book "Realizability: an introduction to its categorical side" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Let me describe the idea of realizability very briefly, and discuss your "coordinate free" requirement later. Start with a model of computation, such as Turing machines, the $\lambda$-calculus, a programming language, or any other partial combinatory algebra (you can even take certain topological spaces to be "models of computation", this stuff is general). For concreteness, let us consider Turing machines. We code Turing machines by natural numbers, but note that I could have taken some other model of computation, so you should not assume that the use of $\mathbb{N}$ is in any way essential here. (Other possibilities include: the powerset of natural numbers, infinite sequences of natural numbers, the syntax of the untyped $\lambda$-calculus, certain categories of games, etc.)

A computability structure on a set $X$ is given by a relation $\Vdash_X$ between $\mathbb{N}$ and $X$, called the realizability relation, such that for every $x \in X$ there $n \in \mathbb{N}$ such that $n \Vdash_X x$. We call such structures assemblies. This definition directly corresponds to the intuitive idea that some piece of data $n$ respresents, or realizes, an element $x \in X$. (For instance, certain sequences of bits represent finite lists of pairs of strings of characters.)

Given two assemblies $(X, {\Vdash_X})$ and $(Y, {\Vdash_Y})$, a map $f : X \to Y$ is realized (or "computable") if there is a Turing machine $T$, such that, whenever $n \Vdash_X x$ then $T(n)$ terminates and $T(n) \Vdash_Y f(x)$. Again, this is a direct transliteration of what it means informally to "program" an abstract function $f$: the corresponding Turing machine does to representing data whatever $f$ does to the corresponding elements.

Assemblies may be extended to a realizability topos. A topos is a model of higher-order intuitionistic mathematics. This tells us that every realizability topos (there is one for each model of computation) contains lots of interesting objects. For instance, it contains an object of real numbers, which thus gives us computability on reals. But it also contains many other objects, such as Hilbert spaces, Banach spaces, spaces of smooth maps, etc. You asked for some other computable structure, but you got something much better: entire mathematical worlds of computability.

Since category theory and toposes can be scary and require some amount of technical proficiency in computability theory, category theory, and logic, we could also work in just one concrete topos, but we express everything in concrete non-abstract ways. A particularly good world of computation arises from Kleene's function realizability, and goes under the name of computable analysis.

Let me comment on the "coordinate free" requirement:

Switching between models of computation gives different kinds of computable worlds. This is a bit like switching between different fields giving different kinds of linear algebra.
A set $X$ may be equipped with many computability structures $\Vdash_X$, just like a set of vectors has many bases. However, while all bases are equivalent, not all computability structures on $X$ are computably equivalent.
If we work concretely with computability structures $(X, {\Vdash_X})$, that is a bit like working with matrices in linear algebra. It can be very useful, but is not abstract.
To work in a "coordinate-free" fashion, we work in a realizability topos and harness the power of category theory (yes, it's a cliché but it works).
We can even work in a "world-free" fashion: develop mathematics in intuitionistic logic, and then interpret the results in realizability toposes.


Gentle introduction to graph isomorphism for bounded valance graphs

The algorithm for bounded-degree graph isomorphism is so closely tied to (permutation) group theory that I doubt there is an introduction that uses groups "only gently." However, you might consult Paolo Codenotti's Ph.D. thesis for more complete background. He doesn't cover bounded-degree graph isomorphism exactly, but covers the tools needed for it (and the rest of the thesis is about bounded-rank hypergraphs, extending the best known algorithm for general graph isomorphism to the bounded-rank hypergraph case).

You may also find the book Group-Theoretic Algorithms and Graph Isomorphism useful, as it covers most of the background necessary (Chapter 2, "Basic Concepts", is 47 pages) and is a much more leisurely exposition than most of the published papers on the topic.


Lower bounds on alternative models of multiparty communication complexity

The "number in hand" model is the one I was thinking of, and there is quite a bit of literature about it. In particular I found this paper of Jeff Phillips, Elad Verbin, and Qin Zhang from SODA 2012 [1]. In particular they prove lower bounds on the problem I was interested in using, the undirected graph connectivity problem, of $\Omega(nk / \log^2(k))$. Here $k$ is the number of edges provided to each player and $n$ is the number of vertices in the graph.

[1] http://arxiv.org/abs/1107.2559


What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

A working algorithm that I described in a comment above is the following:

First start by bringing a random element with probability $1/n$ in position $n$: swap positions 1 and 2 with proba $1/2$, then 2 and 3 with proba $2/3$, ... then $n-1$ and $n$ with proba $(n-1)/n$.
Apply the same procedure to bring a random element in position $n-1$: swap positions 1 and 2 with prob $1/2$ ... then positions $n-2$ and $n-1$ with proba $(n-2)/(n-1)$.
Etc

The number of gates required by this algorithm is $(n-1)+(n-2)+ \cdots + 2+1 = n(n-1)/2 = O(n^2)$.


Can a term on normal form prove an illogical assertion?

I'll turn my comments into an answer: In general, if you do not have any axioms or "stuck" terms, you cannot have a normal proof of $\mathrm{False}\simeq\forall X:*,X$ in a system like the CoC (or extensions of it). The (classical) proof I outlined here applies, crucially using inversion in several places.

I believe it's not hard to have a normal proof of $\mathrm{True}\rightarrow\mathrm{False}$ in an inconsistent system, however, by "blocking" some of the redexes with a variable. Applying this proof to any closed term of type $\mathrm{True}$ would then lead to non-termination.

This leads to a pretty natural question, which I will also outline here: is it possible to reason correctly about programs in an inconsistent language, as long as every "proof-like" term is normalized?

The answer to this seems to be mostly affirmative, though the meta-theory is quite finicky: it's easy to lose even type preservation if one is not careful!

The most comprehensive exploration of this idea to my knowledge is the PhD dissertation of Vilhelm Sjöberg: A Dependently Typed Language with Nontermination.


Proof that circuit upper bounds for $E$ imply $P \neq NP$

I don't think the paper in the other answer contains an answer to your question. Indeed I am not really sure a proof has been published, because the result follows from other well known results.

The proof of the statement you want is as follows:

$\Sigma_3 E$ contains a function of maximum possible circuit complexity on every input length, by simply defining a function which proves itself (using alternation) to be different from all functions with non-maximum circuit complexity. This is standard and the proof idea can be found in sources such as Arora and Barak's textbook.
If $P = NP$ then $\Sigma_3 E = E$, by padding and the collapse of the polynomial time hierarchy to $P $.
Therefore if $P = NP$ then there is a language in $E$ with maximum circuit complexity. This is the contrapositive of what you want to prove.


Origins and applications of Theory A vs Theory B?

It comes from the handbook on theoretical computer science, which had two volumes: A was for algorithms and complexity, and B was for logic and semantics.

Jukka, did ICALP predate this ? Or was it in response to this ?

As for benefits, I think there's always some utility in taxonomizing areas based on topics of interest, and forms of study. However, as with all taxonomizations, the problem comes when you forget to "go back up the tree and down the other side" :).

EDIT: as ICALP explicitly states, this division comes from the Elsevier journal Theoretical Computer Science, which itself predates the handbook, so I think that's a more accurate source.

EDIT ++: From the history of the EATCS comes this snippet about TCS, the journal:

  Since that time M. Nivat, who is still
  Editor-in-Chief has reported regularly
  to council and general assembly and
  occasionally in the Bulletin - e.g.
  when the split into sections A
  (automata, algebra und algorithms) and
  B (logic, semantics and related
  topics) was decided upon (Bulletin no.
  45, p.2,3, October 1991);

which yields 1991 as when this first started happening at the journal. However, the Handbook was first published in September 1990 !


Embedding a n-tree into a b-dimensional space

This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v_r$. On the other hand, the distance between every two leaves is greater than $h$. Since there are $N = b^h$ leaves, we get that

  there are $N$ points in a ball of radius $h$ such that all the pairwise distances between the points are greater than $h$

We must have that $m = \Omega(\log N) = \Omega(h \log b)$.