Using ϵ -unification and Knuth-Bendix completion to automatically proof theorems about groups

This is going to be a somewhat incomplete answer, since you are asking some pretty broad questions about the applications of the techniques.

First let me start by saying that while the research in the field of equational logic and completion hasn't seen a complete revolution since 1980 (as compared to, say SMT) there have been substantial improvements, so bear in mind that techniques and tools have changed. My first recommendation would be to take a look at Term Rewriting and All That by Baader and Nipkow, which is slightly more up to date (but still almost 20 years old!). You might also want to check CiME as an implementation of some of these techniques.

The canonical set from the first example of the appendix is actually

$\begin{eqnarray}R1 &:& 0+X\rightarrow X\\R2&:&I(X)+X\rightarrow 0\\R3&:&(X+Y)+Z\rightarrow X+(Y+Z)\\R8&:&I(0)\rightarrow 0\\R11&:&X+0\rightarrow X\\R12&:&I(I(X))\rightarrow X\\R13&:&X+I(X)\rightarrow 0\\R14&:&X+(I(X)+Y)\rightarrow Y\\R17&:&I(X+Y)\rightarrow I(Y)+I(X)\end{eqnarray}$

For the life of me I can't understand why they adopted additive notation for non-commutative groups.

Note that the set $\{R1,R2,R3\}$ is not canonical, since e.g. $X+0$ does not reduce to $0$ (but $X+0=0$ is derivable in the equationnal system).

The canonical system was derived from the first 3 rules by application of Kuth-Bendix completion, and nothing else, $\varepsilon$-unification is not needed in this case. There are many papers that expand on this example, including, I think, the original paper which is sadly tough to find online. The wikipedia page is a good place to fish for references.

I'm not sure what advice to recommend for using these techniques in practice. I gave a reference to an existing tool, there are many others in various states of maintenance, see e.g. here.

I would also suggest taking a look at first-order theorem provers with equality and equality logic provers, e.g. Otter & Mace since they integrate these kinds of techniques and might be more suited to your needs, if you're trying to prove basic theorems in some algebraic theory.

I really suspect you might want some more specialized tools for Gröbner bases if you're trying to prove theorems about fields, since these are much more specialized (and much more powerful). Perhaps some people more familiar with computer algebra can point you in the right direction for this.


What are the problems in EXPSPACE \ EXPTIME?

Your argument proves that $\mathsf{NEXPTIME}\subseteq\mathsf{EXPSPACE}$, since if a TM terminates in (nondeterministic) exponential time it cannot write to more than an exponential number of tape cells.

On the contrary, if a TM uses exponential space it can still run in doubly-exponential time, e.g. a TM that increments a binary counter of $2^n$ bits until wrapping uses exponential space but runs in $\mathcal{O}(2^{2^n})$ steps.

So the problems that you’re looking for are those that require at most exponential space but whose running time cannot be bounded by an exponential (even though it can be bounded by a double exponential since $\mathsf{EXPSPACE} \subseteq 2 \mathsf{EXPTIME}$). I don’t have a specific example problem in mind though.


Complexity of counting maximum number of co-linear points in Euclidean plane

First, my understanding is that the paper you linked to does not show that 3sum is incorrect. It just shows that the 3sum conjecture is false in a model of computation that is not realistic (i.e., we do not have currently a truly subquadratic algorithm for 3sum).

As for your question, if you are looking for a line containing more than $k$ points, and $k$ is sufficiently large (at least say $10\log^2 n$), then it is not hard to get a subquadratic number of candidate lines such that one of them with high probability is the desired line. Then using standard trade-offs between space and query time for range searching, you would get something subquadratic. The question is of course what to do in the in-between range, when the heaviest line has between $3$ and polylog n points on it. (For ref, see http://sarielhp.org/p/04/depth/depth.pdf).

I think the interesting open question, is whether one can get $O(n^2/k^2)$ (the above would get you at best $O(n^2/k^2 * polylog n)$ [but its probably slower than that]).


What is the benefit of Krivine's notation?

I'm assuming you mean Krivine's notation from Lambda Calculus: Types and Models.

This notation, used as a data representation, makes many algorithms on lambda-terms simpler to implement and prove correct. That is, given a  lambda term $f\; e_1\; e_2\; \ldots\; e_n$, you want to view it as a head $f$, together with a list of arguments $[e_1,  e_2, \ldots, e_n]$.

For example, suppose you want to compare two terms $f\;e_1\;\ldots\; e_n$ with $g\;t_1\;\ldots\;t_n$. It is often most natural to compare the heads $f$ and $g$ first, and not even look at the $(e_i, t_i)$ pairs unless that comparison succeeds. (This often comes up in implementations of higher-order unification.)

See Cervesato and Pfenning's paper A Linear Spine Calculus for a formalization of this idea.


How to play the following game? (placing balls into bins)

I think $x_1 = \dots = x_{\ell-1} = 0, x_{\ell} = y_1 = \dots = y_{\ell} = n$ is better.  You are guaranteed to choose red in all bins except for bin $\ell$, and bin $\ell$ has $n$ red balls and $n$ blue balls, so your overall odds of success are $1/2 > 1/e$.


Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$.
We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case variance, as follows. We interpret the shared randomness as a uniformly random point $(s,t)$ from the disk with radius $1/2$ and center $(1/2,0)$. The sender sends a $1$ if $x > s$ and a $0$ otherwise, while the receiver takes $\hat{x} = 1/2 + \frac{\pi}{8}\sqrt{s/(1-s)}$ if they receive a $1$, and $\hat{x} = 1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}$ if they receive a $0$. To see that this is unbiased, note that $s$ has probability density function $\frac{8}{\pi}\sqrt{s(1-s)}$, so the expected value of $\hat{x}$ is
$$\int_0^x \Big(1/2 + \frac{\pi}{8}\sqrt{s/(1-s)}\Big)\frac{8}{\pi}\sqrt{s(1-s)}\ ds + \int_x^1 \Big(1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}\Big)\frac{8}{\pi}\sqrt{s(1-s)}\ ds\\
= \int_0^1 \frac{4}{\pi}\sqrt{s(1-s)} + s\ ds - \int_x^1 1\ ds
= x.$$
To see that this is optimal for the average-case variance, let's first make a framework to describe the most general possible algorithm. For every possible value of the shared randomness $h$, the receiver will estimate $\hat{x}$ as one value $a(h)$ if they receive a $0$ bit, and will estimate $\hat{x}$ as a different value $b(h)$ if they receive a $1$ bit. We may as well assume that $a(h) \le b(h)$ for all $h$.
On the sender's side, imagine that the functions $a, b$ are fixed and $x$ is known, but that the sender hasn't yet peeked at the randomness $h$. The sender has to divide the possible values of $h$ into disjoint sets $A(x)$ and $B(x)$, with the plan of sending a $0$ bit if $h \in A(x)$ and sending a $1$ bit if $h \in B(x)$, subject to the constraint
$\mathbb{E}_h[a(h)\cdot\mathbf{1}_{h \in A(x)} + b(h)\cdot\mathbf{1}_{h \in B(x)}] = x$,
such that the variance of the random variable $a(h)\cdot\mathbf{1}_{h \in A(x)} + b(h)\cdot\mathbf{1}_{h \in B(x)}$ is minimized. Since the mean is fixed, minimizing the variance is equivalent to minimizing the second moment
$\mathbb{E}_h[a(h)^2\cdot\mathbf{1}_{h \in A(x)} + b(h)^2\cdot\mathbf{1}_{h \in B(x)}]$.
Since $\frac{b^2 - a^2}{b - a} = a+b$, and since we assumed that $a(h) \le b(h)$ for all $h$, the optimal strategy for the sender is to greedily set
$A(x) = \{h \mid a(h) + b(h) > t(x)\}, B(x) = \{h \mid a(h) + b(h) < t(x)\}$
for some threshold $t(x)$ which is chosen to satisfy the constraint on the mean:
$\mathbb{E}_h[a(h)\cdot\mathbf{1}_{a(h) + b(h) > t(x)} + b(h)\cdot\mathbf{1}_{a(h) + b(h) < t(x)}] = x.$
(If $a(h) + b(h) = t(x)$ with positive probability, then we divide the set of $h$s with $a(h) + b(h) = t(x)$ in any way we like to make the constraint on the mean work out.)
By rearranging the internals of the algorithm, we may now assume that $a(h) + b(h)$ is an increasing function of the random variable $h$, so the sender's strategy can be expressed as: send $0$ if $x < s(h)$ and send $1$ if $x > s(h)$, where $s$ is another threshold function, which satisfies
$\mathbb{E}_h[a(h)\cdot \mathbf{1}_{x < s(h)} + b(h)\cdot \mathbf{1}_{x > s(h)}] = x$.
From this, we can deduce that
$\mathbb{E}_h[a(h)s(h)^n + b(h)(1-s(h)^n)] = \mathbb{E}_{x,h}[a(h)\cdot nx^{n-1}\mathbf{1}_{x < s(h)} + b(h)\cdot nx^{n-1} \mathbf{1}_{x > s(h)}] = \mathbb{E}_x[nx^n] = \frac{n}{n+1}$
for every $n$, and that $b(h) - a(h) = s'(h)$.
Using the above identities, we can check that the expected variance is
$$\mathbb{E}_{x,h}[a(h)^2\cdot \mathbf{1}_{x < s(h)} + b(h)^2\cdot \mathbf{1}_{x > s(h)} - x^2]\\
= \mathbb{E}_{h}[a(h)^2s(h) + b(h)^2(1-s(h)) - 1/3]\\
= \mathbb{E}_h[(a(h)s(h) + b(h)(1-s(h)) - 1/2)^2 + (b(h) - a(h))^2s(h)(1-s(h)) - 1/12]\\
\ge \mathbb{E}_h[(b(h) - a(h))^2s(h)(1-s(h)) - 1/12].$$
By Cauchy-Schwarz, we have
$$\mathbb{E}_h[(b(h) - a(h))^2s(h)(1-s(h))]\\
\ge \mathbb{E}_h[(b(h) - a(h))\sqrt{s(h)(1-s(h))}]^2\\
= \mathbb{E}_h[s'(h)\sqrt{s(h)(1-s(h))}]^2\\
= \Big(\int_0^1 \sqrt{s\cdot (1-s)}\ ds\Big)^2 = \frac{\pi^2}{64},$$
which finishes the proof.
Edit: We can actually combine the disk-based example algorithm above (with the least possible average variance) and the subtractive dithering algorithm to create a dithering algorithm which has variance strictly less than $1/12$ for every $x$. The main idea is that the set of functions
$x \mapsto \operatorname{Var}[\hat{x}]$
coming from unbiased dithering algorithms is a convex set: given any pair of dithering algorithms, we can use shared randomness to randomly choose between them. Our plan is to first perturb the subtractive dithering algorithm in a way which keeps its average variance (for $x$ uniformly in $[0,1]$) approximately the same but which makes the variance lower for $x$ closer to $0$ and $1$ and higher for $x$ close to $1/2$, and then to take a weighted combination of this perturbed subtractive dithering algorithm with the disk-based example algorithm described above.
To perturb the subtractive dithering algorithm, we will stick with the choice of threshold $s(h) = h$, but we will perturb the functions $a(h), b(h)$. The perturbed functions will be given by
$$a(h) = h - 1/2 + \delta'(h)\\ b(h) = h + 1/2 + \delta'(h)$$
for some small function $\delta(h)$ - as long as $\delta(1) - \delta(0) = \mathbb{E}_h[\delta'(h)] = 0$, this perturbed algorithm will be unbiased. The variance of the perturbed subtractive dithering algorithm is then given by
$$\operatorname{Var}[\hat{x}] = \mathbb{E}_h[a(h)^2\cdot \mathbf{1}_{x < h} + b(h)^2\cdot \mathbf{1}_{x > h} - x^2]\\
= \tfrac{1}{12} + \mathbb{E}_h[(2h-1)\delta'(h)\cdot \mathbf{1}_{x < h} + (2h+1)\delta'(h)\cdot\mathbf{1}_{x > h} + \delta'(h)^2]\\
= \tfrac{1}{12} + 2\delta(x) - 2\int_0^1 \delta(h)\ dh + \int_0^1 \delta'(h)^2\ dh.$$
As you can see, the average value of $\operatorname{Var}[\hat{x}]$ increases by only $\int_0^1 \delta'(h)^2\ dh$, so by taking $\delta(x)$ a sufficiently small multiple of the difference of the two variance functions for the two algorithms in question, we get the perturbation we need. (While the resulting combination of the perturbed dithering algorithm and the disk-based algorithm outperforms subtractive dithering for all $x$, it is almost certainly not optimal, so I won't work out the gory details.)


Who introduced nondeterministic M-automata, and proved that the finite ones recognize the rational sets over M?

According to J. Sakarovich, Elements of Automata Theory, p. 372,

  It seems that the result appears for the first time in [1]; hidden in a footnote of this seminal but difficult article, it was then given many statements, usually in special cases.

[1] C. C. Elgot and J. E. Mezei, On relations defined by generalized finite automata, IBM J. Res. and Develop., vol. 9 (1965), 47–68.

A full proof was also given in S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974.


You can indeed see linear regression as arising from a fixed point computation, but it is better to think of it as related to transitive closure computations than to folds or unfolds.
Regression is about minimising the mean squared error. A regression model has a vector of inputs (i.e., the design matrix) $X$, a vector of outputs $Y$ and a set of coefficients $\beta$, with a model
$$
   Y = X\beta + e
$$
where $e$ is a vector of errors. If we view $e$ as a function of $\beta$, we can write:
$$
   e(\beta) = Y - X\beta
$$
Then, the squared error (as a function of the coefficients $\beta$) will be given by the dot product
$$
   SE(\beta) = e^T e
$$
Then a bit of vector calculus will tell you that $\beta$ gets minimised when
$$
\beta = (x^T x)^{-1} x^T y
$$
The matrix inversion in the equation above is secretly a fixed point calculation. To get an intuition for why, you need to recall two facts.

First, the star in Kleene algebra (i.e., models of regular expressions) corresponds to iteration. You can see this in the characterizing equation:
$$A^\ast = I + A A^\ast$$

Next, square matrices with elements valued in a Kleene algebra form a Kleene algebra. So if you think of the equation above in terms of linear algebra, you can sort of see this as saying:
$$\begin{array}{lcl}
    A^\ast &=& I + A A^\ast \\
    A^\ast - A A^\ast & = & I \\
    A^\ast (I - A) & = & I \\
    A^\ast &=& (I-A)^{-1} \\
   \end{array}$$
So matrix inversion has a fundamental connection to the asteration operation in Kleene algebra.

As another source of intuition, if you think of a square Boolean matrix as representing the edge relation in a graph, the Kleene star of the graph represents reachability in the graph -- and graph reachability is very obviously a fixed point property.
This is all quite handwavy, but these ideas have been developed  rigorously. They were first (I think) introduced to computer science by Roland Backhouse and B.A. Carré, and were developed by Robert Tarjan in his 1979 paper A Unified Approach to Path Problems. (Tarjan also points out this means that many graph algorithms can be seen as sparse matrix computations!)


Determinant of a generalized Vandermonde matrix

In general, there is a theoretical $O(n^{2.376})$ time algorithm for finding the LU decomposition of an arbitrary matrix using the Coppersmith–Winograd algorithm, which then obviously yields the determinant (adding $O(n)$ time).  There is a problem however that the Coppersmith–Winograd algorithm isn't considered usable in practice.  Afaik, people mostly use the $O(n^{2.807})$ time Strassen algorithm.  Doesn't Boost UBLAS's lu_factorize use this?

In you case, the Moore matrix should admit considerable optimizations because basically any Gaussian elimination like procedure like LU decomposition can be done abstractly.  Indeed, you'll find a nice $O(n)$ formula for computing the Moore determinant referenced by wikipedia, which presumably one proves by simply working out the LU decomposition in general.


Rabin shows the one-wayness of (x^2 mod N=pq) without the factorization of N by a reduction showing that if you can take square roots module N=pq then you can factor N.


Most general setting for fine-grained exponential-time complexity classes?

(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few.

Might it be the case that a RAM program can solve general CNF-SAT in exponential time with a base less than 2, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base at least 2 and (a slightly-weakened version of) SETH is true in the TM model only?

SETH is generally stated in the word RAM model (in particular, with $O(\log t)$ word size, where the running time is $t$). This is mainly because most (if not all?) algorithmists don't care about or work in the multi-tape Turing machine model, but rather a random-access style model. It is true that in general we do not know how to simulate such time-t RAMs with multi-tape Turing machines super-efficiently, and (more importantly) we do not know how to simulate such RAMs in less than $O(t^2)$ gates with a Boolean circuit. But see the answer to the next question.

Is there a variant of SETH where only subexponential space algorithms are considered in order to make it applicable to more models? Or is there some reason I'm not understanding that no generality is lost without this assumption?

Note there is a very simple time-space tradeoff one can obtain, if SETH is false. Suppose we have a $2^{\beta n}$ time algorithm $A$ for k-SAT on $n$ variables, using $\Theta(2^{\beta n})$ space, where $\beta < 1$. Consider the following algorithm $A_{\alpha}$ parameterized by some parameter $\alpha \in (0,1)$:
On $k$-SAT formula $F$, enumerate all assignments $a$ to the first $n-\alpha n$ variables of $F$, plug $a$ into $F$ and run $A$ on the resulting $\alpha n$-variable formula. Stop and output a SAT assignment if it's found.
Note the above $A_{\alpha}$ runs in $O(2^{n-\alpha n}\cdot 2^{\beta \alpha n}) \leq O(2^{n-(1-\beta)\alpha n})$ time and uses only $\Theta(2^{\beta \alpha n}+\alpha n)$ space.
Corollary: If $k$-SAT has a $2^{\beta n}$ time algorithm, then for every $\epsilon \in (0,\beta)$ there is a $\delta > 0$ such that $k$-SAT can be solved in $O(2^{\epsilon n})$ space and $O(2^{(1-\delta)n})$ time.
Proof: Let $k$-SAT have a $2^{\beta n}$ time algorithm. For any given $\epsilon \in (0,\beta)$, set $\alpha = \epsilon/\beta < 1$. Applying the above reduction, we can solve $k$-SAT in $O(2^{\epsilon n})$ space and $2^{n-(1-\beta)\alpha n}$ time, so $\delta = (1-\beta)\alpha$ suffices. QED
However, note the time-space product of the resulting algorithm is not very favorable...
I do think that the "polynomial-space SETH" (which I believe I have seen in the literature, but am blanking on a reference) that only rules out polynomial-space faster-than-$2^n$ time for $k$-SAT, is a much more plausible hypothesis than SETH itself.


List of TCS conferences along with important dates

I'm maintaining such a list here:
https://sites.google.com/site/yixincaoresearch/conferences.

Thanks due to  Anupam Gupta and Iftah Gamzu.


Hardness of approximation assuming NP != coNP

Here's a straightforward observation. If you assume $NP \neq coNP$, then it is pretty easy to see there are $NP$ optimization problems which do not even have good nondeterministic approximation algorithms, in some sense.

For example, the PCP theorem says that you can translate SAT into the problem of distinguishing whether $1-\varepsilon$ of the clauses are satisfied and all of the clauses are satisfied, for some $\varepsilon > 0$. Suppose there is a nondeterministic algorithm which can distinguish between these two cases, in the sense that the nondeterministic algorithm can report in each computation path either "all satisfied" or "at most $1-\varepsilon$", and it says "at most $1-\varepsilon$" in some path if at most $1-\varepsilon$ can be satisfied, otherwise it says "all satisfied" in every computation path if all equations can be satisfied. This is enough to decide SAT in $coNP$, so $NP=coNP$. It seems clear that the existence of such a nondeterministic algorithm has no bearing on whether $P = NP$.

It's quite plausible that a more "natural" scenario exists: an optimization problem which is hard to approximate in deterministic polynomial time under $NP \neq coNP$ but not known to be hard under $P \neq NP$. (This is probably what you really wanted to ask.) Many hardness of approximation results are first proven under some stronger assumption (e.g. $NP$ not in subexponential time, or $NP$ not in $BPP$). In some cases, later improvements weaken the necessary assumption, sometimes down to $P \neq NP$. So there is hope that there's a slightly more satisfactory answer to your question than this one. It is hard to wonder how there could be a problem that cannot be proved hard to approximate in deterministic polytime under $P \neq NP$, but it can be proved hard under $NP \neq coNP$. That would mean that $NP \neq coNP$ tells us something about deterministic computations that $P \neq NP$ doesn't already say; intuitively, this is hard to grasp.


What are the relationships between Functional Reactive Programming, Automatic Differentiation, Self-Adjusting Computation and Partial Evaluation?

I essentially agree with Dave's comment: these are lots of different things (and I only feel remotely competent to talk about three of them).

However, from the perspective of a consumer of functional programming research, the three things I know something about probably feel related, because they all are ways of making functional programs deal with inputs that change over time. For instance:

Functional reactive programming - consider this when you want to write a program as if you're taking, as input, list of all the user events that's ever happened, but you still want the program to behave reasonably as you feed it inputs over time. An underlying assumption is therefore that the data about past events won't change, and that the only changes to the input will be the addition of new events that happened after all the old events.
Partial evaluation - consider this when your program neatly cleaves into two parts, and you want to recompute, over and over, part 2 based on the outcome of part 1. This assumes your code has the property that the difference between "part 1" and "part 2" are known when you write the code, so an underlying assumption is that the data that stays the same (the data part 1 computes with) and the data that changes (the data part 2 computes with) are known in advance.
Self-adjusting computation - consider this when your program's execution flow is not neatly divided into parts, but involves a lot of decisions based on data. Self-adjusting computation is designed to react to small changes in inputs by only redoing computation that was based on modified data. Therefore, an underlying assumption is that the particular changes can't be anticipated in advance.

[Update] In practice, the challenges associated with each of these three things are different: it doesn't necessarily make sense to talk about any of them as special cases of the others. However, as Jake points out below, there are (slightly restricted) libraries of functional reactive programming that are implemented on top of self-adjusting computation primitives. Similarly, it might be possible to effectively implement something like partial evaluation on top of self-adjusting computation, since SAC makes the very few a priori assumptions about its input data.


Holographic Algorithms - Equivalence of Bases

Tensors (in this sense) are just arrays of numbers, so I don't think you'll find tensor free surveys unless they're completely free of calculations.

The "$T^{\otimes k}$" operation formalizes both the operations of changing basis and attaching gadgets to each output node (in fact I like to think of a change of basis as a sort of gadget operation). Let $\Gamma$ be a generator matchgate with standard signature $M_{i_1i_2\cdots i_k}=u(\Gamma)$. This an array of $2^k$ numbers. The signature in a new basis is given by

$(T^{\otimes k}M)_{i_1i_2\cdots i_k}:=\sum_{i_1',\cdots,i_k'} T_{i_1i_1'} \cdots T_{i_ki_k'} M_{i_1'i_2'\cdots i_k'}$

where $T$ is some two-by-two matrix descring the new basis.

Let $\Gamma'$ be the matchgate formed by adding $k$ new vertices to $\Gamma$, taking these to be the new outputs, and connecting them to the old outputs by an edge of weight $x$. Then the new signature is $C^{\otimes k}M$ where $C_{ij}$ is the matrix $\begin{pmatrix}0&x\\1&0\end{pmatrix}$. If you then perform the change of basis $TC^{-1}$ you get the signature $T^{\otimes k}M$.


Lower bound for testing closeness in $L_2$ norm?

It appears that $O(1/\epsilon^2)$ samples — as usul showed below — is enough for testing, so that the sample complexity is exactly $\Theta(1/\epsilon^2)$; actually, it turns out this number of samples us even enough for learning $D$ up to an additive $\epsilon$ wrt the $L_2$ norm.

Let $\hat{D}$ be the empirical density function obtained by drawing $m$ i.i.d. samples $s_1,\dots, s_m\sim D$ and setting
$$
\hat{D}(k) \stackrel{\rm{}def}{=} \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}},\qquad k\in[n]
$$
Then
$$
\begin{align*}
\lVert D - \hat{D} \rVert_2^2 &= \sum_{k=1}^n \left( \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - D(k) \right)^2 = \frac{1}{m^2}\sum_{k=1}^n \left( \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - mD(k) \right)^2 \\
&= \frac{1}{m^2}\sum_{k=1}^n \left( X_k - \mathbb{E} X_k \right)^2
\end{align*}
$$
where $X_k\stackrel{\rm{}def}{=} \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}}\sim\operatorname{Bin}( m, D(k) )$. The $X_k$'s (for $k\in[n]$) are not independent, but we can write
$$
\begin{align*}
\mathbb{E}\lVert D - \hat{D} \rVert_2^2 &= \frac{1}{m^2}\sum_{k=1}^n \mathbb{E}\left[ \left( X_k - \mathbb{E} X_k \right)^2 \right]
= \frac{1}{m^2}\sum_{k=1}^n \operatorname{Var} X_k \\
 &= \frac{1}{m^2}\sum_{k=1}^n mD(k)\left( 1- D(k) \right) \leq \frac{1}{m}\sum_{k=1}^n D(k) \\
&= \frac{1}{m}
\end{align*}
$$
so that for $m\geq \frac{3}{\epsilon^2}$,
\begin{equation}
\mathbb{E}\lVert D - \hat{D} \rVert_2^2 \leq \frac{\epsilon^2}{3}
\end{equation}
and applying Markov's inequality
\begin{equation}
\mathbb{P}\left\{ \lVert D - \hat{D} \rVert_2 \geq \epsilon \right\} \leq \frac{1}{3}.
\end{equation}


Langton's ant highway conjecture and undecidability

From the comment: the undecidable questions are related to initial configurations with infinite support, whereas the conjecture refers to the behaviour of the ant when starting from a configuration with finite support (all but a finite number of cells are in the same initial state). If the conjecture is true then there are no undecidable problems starting from a finite support: just stop when the ant starts building the highway towards empty space.


Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph.
https://doi.org/10.1007/BF02760024


For a random oracle R, does BPP equal the set of computable languages in P^R?

Yes.

First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$, and the result you allude to is $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$. If I've understood correctly, you are asking if $Pr_R(\forall L\, L \in \mathsf{P}^R \cap \mathsf{COMP} \iff L \in \mathsf{BPP}) = Pr_R(\mathsf{P}^R \cap \mathsf{COMP} = \mathsf{BPP}) = 1$.

Consider

$p := 1-Pr_R(\mathsf{P}^R\cap \mathsf{COMP} = \mathsf{BPP}) = Pr_R(\exists L \in \mathsf{P}^R \cap \mathsf{COMP} \backslash \mathsf{BPP})$.

By the union bound, the $p$ is upper-bounded by $\sum_{L \in \mathsf{COMP}} Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP})$. (Note that the latter sum is countable.) Now, by the 0-1 law - which applies since all the relevant statements do not change if we change $R$ finitely much - each individual probability in this sum is either 0 or 1. If the answer to your question is no, then $p=1$, so there must be some $L \in \mathsf{COMP}$ such that $Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$. But this contradicts the fact that $\mathsf{AlmostP} = \mathsf{BPP}$.

Update Oct 10, 2014: As pointed out in the comment by Emil Jeřábek, the same argument applies to $\mathsf{AM}$ vs. $\mathsf{NP}^R$, since we also know that $\mathsf{AlmostNP} = \mathsf{AM}$.

He also points out that we didn't use anything about $\mathsf{COMP}$ other than that it is a countable class that contains $\mathsf{BPP}$ (resp., $\mathsf{AM}$). So the "interesting conclusion" in the OQ actually applies to any countable class of languages $\mathcal{C}$ that contains $\mathsf{AM}$: if $\mathsf{P} = \mathsf{NP}$, the "only" languages that witness the oracle separation $\mathsf{P}^R \neq \mathsf{NP}^R$ are outside of $\mathcal{C}$. But the latter statement feels somewhat misleading to me (it makes it sound like, for any $L_0$ we could consider $\mathcal{C} = \mathsf{AM} \cup \{L_0\}$, and thereby "show" that no $L_0$ realizes $\mathsf{NP}^R \neq \mathsf{P}^R$, contradicting the well-known theorem). Rather, writing it out symbolically, we've shown:

If $\mathsf{P} = \mathsf{NP}$, then $\forall \text{countable } \mathcal{C} \supseteq \mathsf{AM}\, Pr_R(\mathsf{NP}^R \neq \mathsf{P}^R \text{ and } \mathsf{NP}^R \cap \mathcal{C} = \mathsf{P}^R \cap \mathcal{C}) = 1$.

Note that, crucially, probability 1 is not the same thing as all $R$, and which full-measure set of $R$ satisfy the argument to $Pr_R$ can depend on $\mathcal{C}$. So if we try to alter $\mathcal{C}$ to $\mathcal{C} \cup \{L_0\}$, it at most removes a measure 0 set of $R$ that satisfy this statement.


Scoring set of points based on clustering

For the one dimensional case, you can use the variance.

For the higher dimensions, you can generalize the variance by first computing a mean point and then computing the sum of the square of the distance between each point and the mean squared followed by a division the sum by the number of points. This division by the number of points (which also happens in the variance) is the difference between the solution you have suggested and what I am recommending.  This division allows for a fair comparison of clustering between sets of points of different sizes.

For $n$ points with mean point $m$, the computation is $\frac{1}{n} \sum_{i=1}^n \operatorname{dist}(m, p_i)^2$.


What is the complexity of this weighted b-edge matching problem?

Assuming $x(e)=1$ in Condition 2, the problem is NP-complete.

Clearly it is in NP.  We show NP-hardness by reduction from Subset Sum:

Lemma 1. The problem is NP-hard.

Proof. The proof is by the following reduction from Subset Sum.  Given a Subset-Sum input $(y, T)$, where $y=(y_1, y_2, \ldots, y_n)$ is a sequence of integers, and $T$ is the target, the reduction outputs the following instance of the problem defined by OP.

For each given integer $y_i$, create two new vertices $v_i$ and $v'_i$, and add two copies of edge $e_i=(v_i, v'_i)$, each with weight $w(e_i) = y_i$.  Put one copy of $e_i$ in $E_1$ and the other in $E_2$, and make $b_\ell(v_i) = b_u(v_i) = b_\ell(v'_i) = b_u(v'_i) = 1$.  Finally, take $r_1 = T$ and $r_2 = (\sum_i y_i) - T$.  This completes the reduction.

Given any subsequence of $y$ that sums to $T$, there is a corresponding solution $(E'_1, E'_2)$ to the created instance, where, for each $i$, if $y_i$ is in the subsequence we put the copy of $e_i$ that is in $E_1$ in $E'_1$, and otherwise we put the copy of $e_i$ that is in $E_2$ in $E'_2$.  Then each vertex has one chosen edge incident to it, the total weight of edges in $E'_1$ is $T$, and the total weight of edges in $E'_2$ is $(\sum_i y_i) - T$, as required.

Conversely, consider any solution $(E'_1, E'_2)$ to the created instance.  Form a corresponding solution to the Subset-Sum instance by choosing the elements $y_i$ of $y$ such that $e_i$ is in $E'_1$.  It sums to at least $T$ by Condition 1. And it sums to at most $T$ because, for each edge $e_i$ that is not in $E'_1$, it must be that $e_i$ is in $E'_2$ (by Condition 2), and the total weight of such edges must be at least $(\sum_i y_i) - T$ (by Condition 1).  $~~\Box$


The f_equal tactic does not do anything because what you are trying to prove is not true. You assumed that the first components (VN_value) of m and n are equal, but what about the second components (VN_prop), how do you intend to prove they are equal?

Also note that we cannot decompose the equation

{| VN_value := m_value; VN_prop := m_prop |} =
 {| VN_value := n_value; VN_prop := n_prop |}

into

m_value = n_value

and

m_prop = n_prop

because the second equation is not well typed: the left-hand side has type valid m_value = true and the right-hand side valid n_value = true. Instead, we need to transport m_prop from the type valid m = true to the type valid n = true.

So, you need transport and you need an extra assumption. Here is how you can do it:

Fixpoint valid (n: nat) : bool :=
  match n with
    | 0 => true
    | 1 => false
    | S (S p) => valid p
  end.

Record valid_nat : Type :=
  { VN_value : nat ;
    VN_prop  : valid VN_value = true }.

Definition transport {A : Type} (B : A -> Type) {a b : A}: a = b -> B a -> B b.
Proof.
  intros [] ?; assumption.
Defined.

Lemma valid_nat_unique (m n : valid_nat) (p : VN_value m = VN_value n):
  transport (fun k => valid k = true) p (VN_prop m) = VN_prop n ->
  m = n.
Proof.
  destruct m; destruct n.
  simpl in * |- *.
  destruct p.
  intros [].
  reflexivity.
Qed.


Place of tree-adjoining grammars in the hierarchy of tree grammars

Actually I've found the answer. Here is quote from unpublished work (lecture notes?) of M. Kanazawa:

  The class of tree languages of tree-adjoining grammars is included in
  the class of tree languages generated by monadic simple context-free
  tree grammars.


(perfect fractional) matching in regular hypergraphs

You are asking many things in the question, and I can only answer part of it:

  necessary and/or sufficient conditions for existence perfect matchings

It is unlikely that a nice necessary and sufficient characterization is known, because deciding whether a given 3-regular hypergraph has a perfect matching or not is NP-complete.  Indeed, it is equivalent to the monotone 1-in-3 SAT problem, which is proved to be NP-complete by Schaefer [Sch78].  (In [Sch78], the same problem is called “ONE-IN-THREE SATISFIABILITY” without the word “monotone.”)  To see this equivalence, interpret each hyperedge as a variable and each vertex as a clause.

[Sch78] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 216–226, May 1978.  DOI: 10.1145/800133.804350.


Oracular separations between poly- and log-depth quantum circuits

I apologize; I was too glib when I wrote that.  While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it.  Maybe your post will help motivate me to finally kill this problem off!


Is there a 'process algebra' to describe ACID transactions on a database?

There is a paper by Van Beek called An Algebraic Approach to Transactional Processes which describes adding transactions to process algebra:

(a :~ 0 . a:~ a + 2) II (a:~ 1 a:~ a X 2) ((a :~ 0 . a:~ a + 2)) II ((a:~ 1 a:~ a X 2))

This paper even delves into isolation levels.

The author describes how in Communicating Sequential Processes (CSP), if you have a write blocked on a read, you can get into a deadlock scenario.

The author references another paper J.A. Bergstra, A. Ponse, and J.J. van Warne. Process algebra with backtracking which allows for rollback of a failed CSP operation.

There is discussion on the nature of transactions in K.P. Eswaran, J .N. Gray, R.A. Lorie, and 1.1. Traiger. On the notions of consistency and  predicate locks in a data base system. Communications of the ACM, 19(11)

The properties of transactions are described in ] J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques.

The acid properties of transactions are described in J. Gray. The transaction concept: Virtues and limitations and in T. Haerder and A. Reuter. Principles of transaction-oriented database recovery


Can we efficiently convert from NFA to smallest equivalent DFA?

See here:
https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings
"checking whether an NFA accepts all strings is PSPACE-complete".
In particular, if an NFA accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.


Is there a standard format for Dependent QBF?

There is a standard format proposed. At QBFEVAL’18 there is a DQBF-track, which uses DQDIMACS from a paper by Föhlich et al on IDQ.


What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976).  Since an ER random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.


What was the significance of Leslie Valiant's, "A Theory of the Learnable?"

I think that "there is a natural limit to what computers can learn", while definitely true, is not one of the main takeaways of Valiant's paper, for two reasons. One is that I could not find any discussion of lower bounds or no-free-lunch results in this paper. Two is that surely statisticians had been aware of such fundamental limitations on learnability prior to Valiant, if only as folklore.

I'd say the reason that paper has had such an impact is that it formalized an intuitively appealing learning model (what came to be known as PAC), which turned out to have a rich and satisfying mathematical structure, as well as numerous generalizations and extensions. Of course, finite-sample bounds had been obtained by Vapnik and Chervonenkis previously, but Valiant placed learning in an algorithmic setting by (among other things) emphasizing the importance of representation. In particular, he argued that DNFs are a natural human-interpretable representation and wondered whether these can be efficiently PAC-learned. (We now know that properly PAC-learning 3-term DNFs in polytime would imply NP=RP, but the agnostic case is still an active area of research and a major open question, as far as I know).

In summary: by Valiant's own admission, the statistical contributions of the paper are minor. He doesn't even need the full power of VC theory, since he mostly (exclusively) deals with discrete function classes, for which cardinality bounds + Chernoff do just fine. The reason that this paper has had such an impact on CS -- and indeed, probably the main reason why machine learning, by default, resides in CS departments -- has mainly to do with the computational aspects.


Chernoff-type Inequality for pair-wise independent random variables

Pairwise independence is not enough for a Chernoff-type bound on the expectation.

This follows from the fact that there are $poly(n)$-size sample spaces on $n$ 0-1 random variables, where all the variables are pairwise independent, and each is variable is uniform (it is $1$ with probability $1/2$). So the expected value of their sum is $n/2$. But because there are only $poly(n)$ possible events in the sample space, even the probability that a sum is exactly a particular value $v$ is at least $1/poly(n)$ (hence, it can't be at most $1/exp(n)$).

For a reference to this sample space construction, see pages 11-12 in this survey.


Extending EAL with recursion makes it incompatible with the abstract algorithm?

The term that you gave does have one duplication, i.e.: ones is used in the body and returned in form of a free variable. The following example illustrates the same effect but is smaller:

loop = λ_. loop

To make the graph structure clear, let's make sure that each identifier is used exactly twice (_ represents connected erasing node):

C[loop, loop_rec] = λ[_, loop_rec]

EAL gives you termination proof if you can stratify all the terms. I don't see how you can stratify this one.
If the level of loop_rec is $n$ then the level of whole λ is also $n$. And after the contraction the level of both loop and loop_rec should be $n-1$ which gives you contradiction.

On the other hand you are right that this copy can't escape the definition (assuming 1 and cons are closed), so it is equal to an actual infinite list. Yet I don't see how to generalize this into an argument about arbitrary recursive let statements.


NP-hardness of a graph partition problem?

I've found that this problem is NP-hard, even restricted to trees.
The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it.


Even if you have a one-player game there is no computable equilibrium. Consider nature putting probability $1/2^i$ on program $i$. Any computable strategy will achieve some value strictly less than one or you could use it to solve the halting problem. But you can achieve any value less than one by the strategy that for some fixed sufficiently large $t$, simulates nature's program $j$ for $t$ steps and outputs the number of steps it takes program $j$ to halt if $j$ halts in $t$ steps, infinity otherwise.


Yes, of course you could do that.  Whether it is useful will depend on the task.  I'd suggest spending some quality time on tutorials/classes on neural networks, and then spend some time experimenting with different network architectures to see how the choice of feature vector affects the performance of the network.


Motivation for Developing Shortest Path Simplex Algorithms

A major open problem in mathematical programming is designing a strongly polynomial time linear programming algorithm. A related problem is whether any variant of the simplex algorithm runs in strongly polynomial time. It makes sense to first prove strong polynomial time bounds for variants of simplex applied to problems for which we already know strong polynomial time algorithms exist.


Satisfiability problems with restricted (not bounded) number of occurrences per variable

Theorem: The special case of 1-in-3-SAT where each variable
  appears an even number of times is NP-hard.

Proof: Consider an instance $I$ of 1-in-3-SAT, and let $a_1,\ldots,a_n$
be an enumeration of the variables in $I$.
Assume that variables $a_1,\ldots,a_m$ occur an odd number of times,
whereas $a_{m+1},\ldots,a_n$ occur an even number of times.
Without loss of generality $m$ is an even number (and otherwise,
add a new dummy clause with three newly created dummy variables).

From instance $I$, we create a new instance $I'$ of 1-in-3-SAT
in which every variable occurs an even number of times.
Furthermore, $I$ is satisfiable if and only if $I'$ is satisfiable:

Instance $I'$ contains all variables and all clauses of $I$.
For every variable $a_i$, instance $I'$ contains a (new)
corresponding variable $b_i$.
Furthermore, $I'$ contains a (new) variable $c$.
For every clause $a_i,a_j,a_k$ in $I$, instance $I'$ contains a new clause $\lnot b_i, \lnot b_j,\lnot b_k$.
For $i=1,\ldots,m$, instance $I'$ contains a new clause $a_i,b_i,c$.

It is easy to check that every variable in $I'$ occurs in an even
number of clauses. If $I'$ is satisfiable, then this induces a
satisfying assignment for $I$.

Finally consider a satisfying assignment for $I$.
Use truth values $b_i:=\lnot a_i$ for $1\le i\le n$ and $c:=$FALSE.
The resulting assignment satisfies all clauses in $I'$.


Independent iterations in Las Vegas algorithms

Rapid restarts in SAT solving are one area where the sequence introduced in Luby,Sinclair,Zuckerman is used. See for example Section 2.1 in http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf for some references.


Can we verify satisfiability of first order statements via saturation in sub-exponential time?

I am assuming by saturation you mean saturation-based reasoning as used by a resolution theorem prover e.g. where we negate and attempt to find a contradiction by saturation if we saturate we can conclude there is no contradiction assuming certain properties were preserved during proof search.

Given this setting, it is the part in bold that kills any attempt to do what you are hoping for. To be able to conclude that a saturated set was produced using a complete proof search procedure means checking every inference not made during proof search to make sure this was allowed. In practice this means looking at selected literals of every given clause and all reductions or deletions.

As far as I'm aware, so far there has been no effort to make theorem provers record the necessary information to check these things. But such information could be exponentially larger than the saturated set.


In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.

I think I finally understood what is going on here and why we seem to have two conflicting answers: one saying that we can simply apply the directed, vertex version of Menger's theorem / max-flow min-cut, and the other one saying that the problem of finding a separating set of vertices in directed graphs is NP-hard. Obviously I'm no expert on this kind of things, but let's see if I can get these right...

Let $G = (V,E)$ be a directed graph. Let $p, q \in V$ be two distinct nodes. In what follows, $X \subseteq V \setminus \{ p,q \}$ is a subset of nodes that doesn't contain $p$ or $q$. Let $G-X$ be the subgraph of $G$ induced by $V \setminus X$.

Now let's define two (non-standard) terms:

$X$ is a one-way separator if $G-X$ doesn't have any directed path from $p$ to $q$.
$X$ is a two-way separator if $G-X$ doesn't have any directed path from $p$ to $q$ or from $q$ to $p$.

Now I think the situation is as follows:

It's possible to find a minimum-size one-way separator in polynomial time.
However, finding a minimum-size two-way separator is NP-hard.

Some explanations and references:

One-way separators: There is a directed vertex version of Menger's theorem: the maximum number of pairwise internally-disjoint directed paths from $p$ to $q$ = the minimum size a one-way separator. See, for example, p. 205 and Theorem 11.6 of Bondy and Murty's Graph Theory with Applications (1976). (Of course Menger's theorem is an existential result, but a typical proof seems to reduce the problem to max-flow min-cut, which gives a poly-time algorithm. Anyway, the statement of Menger's theorem is already enough to place the problem in NP${}\cap{}$co-NP.)
Two-way separators: These seem to be equal to "node multiway cuts in directed graphs, for $k = 2$ and weights = 1" in this paper that András mentioned. Theorem 1 claims that finding an optimal solution is NP-hard.

(Obviously, we could find a 2-approximation of two-way separators by simply taking the union of two one-way separators. But this isn't necessarily optimal.)

Now if we get back to the original question: isn't it enough to just find a one-way separator, to break the strong connectivity? So isn't the original problem in P?


Complexity of recognizing vertex-transitive graphs

I don't have a complete answer, but I think both problems are open.

The paper by Jajcay, Malnič, Marušič [3] is related to your first question.
They provide some tools to test vertex-transitivity. They say in the introduction that:

  For a given finite graph $\Gamma$,
  it is decidedly hard to determine whether $\Gamma$ is vertex-transitive,
  and the ultimate answer comes usually only after a substantial part of
  the full automorphism group of $\Gamma$ has been determined.

Note that vertex-transitivity test can be done by testing graph isomorphism $n−1$ times.
Make two copies $G$ and $G'$ of your graph,
with special anchors (like paths of length $n+1$) at $u \in V(G)$ and $v \in V(G')$.
There is an isomorphism between $G$ and $G'$ if and only if
the original graph has an automorphism mapping $u$ to $v$.
Thus you can test vertex-tansitivity by fixing a vertex $x$,
and checking that there are automorphisms mapping $x$ to all the other vertices.

Also note that if vertex-transitivity test can be done in polynomial time,
then so is isomorphism test for vertex-transitive graphs.
This is because two vertex-transitive graphs are isomorphic if and only if
their disjoint union is vertex-transitive.
I believe that complexity of graph isomorphism for vertex-transitive graphs is not known.

For the 2nd question, I found a partial result.
A circulant graph is a Cayley graph on a cyclic group.
Evdokimov and Ponomarenko [2] show that recognition of
circulant graphs can be done in polynomial time.
Also the book chapter by Alspach [1, Chapter 6: Cayley graphs, Section 6.2: Recognition]
would be interesting for you, although it says that:

  We shall ignore the computational problem of recognizing whether an
  arbitrary graph is a Cayley graph. Instead, we always assume that
  Cayley graphs have been described in terms of the groups on which they
  are built, together with the connection sets. For most problems this
  is not a drawback.

Beineke, Wilson, Cameron. Topics in Algebraic Graph Theory. Cambridge University Press, 2004.
Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835. doi:10.1090/S1061-0022-04-00833-7
Jajcay, Malnič, Marušič. On the number of closed walks in vertex-transitive graphs. Discrete Math. 307 (2007) 484-493. doi:10.1016/j.disc.2005.09.039


VC dimension for balanced binary decision trees

It is shown here (slide 10) that if $H_{d,k}$ is the number of depth-$k$ decision trees over $d$ input bits, then
$$v:=\log_2(H_{d,k})=
(2^k-1)(1+\log_2(d))+1
.
$$
So $v$ is an upper bound on the VC-dimension of your class. I don't know how tight it is, since you have the additional constraint of the trees being balanced.


How can one ACTUALLY minimize a regular expression?

Finding the answer to your question is not overly difficult, if one is used to proving PSPACE upper bounds. But I think one cannot find an answer to your question in the literature, so here it is:

Given a regular expression r of alphabetic width n, i.e. with n alphabetic letters, you can enumerate all regular expressions of alphabetic width 1,2,3, one by one (see the paper by Gruber et al. 2012), and test for each such candidate expression c whether L(c) = L(r). The first expression where the test succeeds is clearly of minimum alphabetic width.

Apart from the test for language equivalence, this can be implemented using "only" linear space (and using exponential time).

The regular expression equivalence test can be done by converting r and c each to a nondeterministic finite automaton, and check if these automata are equivalent. The latter can be done in PSPACE as follows (this algorithm is mentioned in the paper by Bonchi and Pous 2013): For each word $w$ of length at most $2^n$, test whether $w \in L(r)$ if and only if $w \in L(s)$. If all these $2^{n+1}-1$ tests are successful, then $L(r)=L(s)$.

Notes

The paper by Gruber et al. (2012) also covers the computation of the number of regular languages whose minimal regular expression is of size n for small values of n. This actually uses an implementation of regular expression minimization. The test for language equivalence is not done in polynomial space as described above, but by computing the minimal DFA. This requires exponential space in the worst case. But there are more practical ways (all practical approaches seem to use exponential space) for testing the equivalence of NFAs, see
http://languageinclusion.org/

References

Hermann Gruber, Jonathan Lee, Jeffrey Shallit: Enumerating regular expressions and their languages, arXiv:1204.4982 [cs.FL]
Filippo Bonchi, Damien Pous: Checking NFA equivalence with bisimulations up to congruence. POPL 2013.


Existence of equilibria in infinite two players zero sum extensive form games with perfect information

By the Ky Fan minimax theorem, if you can identify the strategy spaces of the two players with convex compact subsets of a locally convex topological vector space, and the payoff function $M(x, y)$ is convex and continuous in $y$ for any $x$, and also concave and continuous in $x$ for any $y$, then the minimax theorem holds.


Computing integer points on the circumference of a given circle

If $a=b=0$ and $r=pq$ where $p$ and $q$ are primes congruent to 1 mod 4, then from the $O(1)$ integer points on the circle one could determine the factorization of $r$. So the problem is not going to be easier than factorization.


How to find the exact period of Blum-Blum-Shub random number generator?

You can determine the period reasonably easily if you know the factorization of $M$ as $pq$, the factorization of $(p-1)\cdot (q-1)$ and the factorization of $\ell-1$ for any prime $\ell$ that divides $(p-1)\cdot (q-1)$.

This requires two steps, first find the order of $x_0$ modulo $M$. Since this divides $(p-1)\cdot (q-1)$ whose factorization is known, this is standard. Let $L$ denote this order, the period of BBS is the order of $2$ modulo $L$ and you can compute it in the same way as we computed $L$.


Is minimax problem NP-Hard when the inner problem is NP-Hard ?

The answer to your question is "no", although for natural problems that you might be thinking about, it may be a good heuristic that if the inner problem is NP hard, the whole problem is probably hard as well. But you can come up with the following contrived counterexample.

Let $X = \{0,1\}$ and $U = \{0,1\}^n$, and let $\phi$ and $\theta$ be two 3SAT instances with the promise that exactly one of them is satisfiable. Let $f(0,u) = \phi(u)$ and let $f(1,u) = \theta(u)$. Then the minmax value is always 0, so computing it is in P, but for any fixed $x$, the problem is 3SAT and is NP hard.


Two valued variant of subset sum problem

Your problem $P$: given a multiset $S = \{a_1, \dots, a_m\}$ of some $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $k \in \mathbb{N}$, what is the $k$-partition $S_1, \dots, S_k$ which maximizes $\min_i \sum_{a_j \in S_i} a_j$.
Definition A "disjoint collection" of subsets of $S$ is a collection of subsets of $S$ that are disjoint. A "disjoint $k$-collection" is a disjoint collection with $k$ subsets.
Consider problem $P'$: given a multiset $S$ of $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $T \in \mathbb{Z}^+$, what is the maximally sized disjoint collection of subsets of $S$ which has the property that each subset's sum is $\ge T$?
Claim 1 if we can solve $P'$ in poly-time we can solve $P$ in poly-time.
Proof of Claim 1: We reduce $P$ to $P'$ using binary search. Let $A'$ denote the assumed poly-time algorithm for $P'$.
So we have $S$ and some $k$ as input from $P$. Let $T^*$ denote the optimal minimum-set-sum (the value we're trying to find to answer $P$).
We will call $A'$ with the same $S$ and various $T$s as input.
Let $\tilde{T}$ be the maximal $T \in \mathbb{Z}^+$ for which $A'$ returns a collection of size at least $k$.
We claim that $\tilde{T} = T^*$.
First, let's show $\tilde{T} \le T^*$: to see this, by definition of $\tilde{T}$, note that $A'$ produces a set of at least $k$ subsets each of whom has sum $\ge \tilde{T}$; add the "leftover" elements outside to any subset in the collection; now we have a $k$-partition with each subset having sum $\ge \tilde{T}$. But $T^*$ is the maximal $T$ with this property: so $T^* \ge \tilde{T}$.
Next, let's show $\tilde{T} \ge T^*$: by definition of $T^*$, there is some $k$-partition of $S$ all of whose subsets sum to $\ge T^*$. So if we feed $S$, $T^*$ as input to $A'$, $A'$ will return a collection of size at least $k$. But $\tilde{T}$ is the maximal such $T$, so $\tilde{T} \ge T^*$.
We know that $\tilde{T} = T^*$ lies between $T=1$ and $T=\lfloor (\sum_{a_i \in S} a_i) / k \rfloor \le m_1a + m_2b$.
So to find $\tilde{T}$, we need only $O(\log(m_1a + m_2b))$ calls to $A'$ with binary search: any $T$ for which we get a collection of size $\ge k$ from $A'$ is $\le \tilde{T}$; any $T$ for which we get a collection of size $< k$ from $A'$ is $> \tilde{T}$. $\square$
Now we show (or *claim to show*) that $P'$ can be solved in poly-time:

Problem $P'$: given a multiset $S$ of $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $T \in \mathbb{Z}^+$, what is the maximally sized disjoint collection of subsets of $S$ which has the property that each subset's sum is $\ge T$?
Claim 2 we can solve $P'$ in poly-time.
Let $\ell^*$ denote the size maximal size disjoint collection (we are looking for $\ell^*$ and a disjoint collection that achieves this maximum).
First some definitions:
Definition call multisets consisting of only $a$'s and $b$'s, "$(a, b)$-multisets". Any such multiset can be identified by an ordered pair $(i, j)$ where $i$ denotes the number of $a$'s and $j$ denotes the number of $b$'s.
Definition "$(a,b,T)$-minimal multisets" $(i, j)$ are those $(a,b)$-multisets for which removing any element would bring you to a sum below $T$: i.e. $ai + bj \ge T$, but $a(i-1) + bj < T$ and $ai + b(j-1) < T$. For example, if $a=2$ and $b=5$ and $T=20$, the minimal multisets would be $(10, 0)$, $(8, 1)$, $(5, 2)$, $(3, 3)$ and $(0, 4)$.
Observation: Without loss of generality,  we can assume that the optimal collection of $\ell^*$ subsets of $S$ consists of only $(a, b,T)$-minimal multisets. To see why this is without loss of generality, consider any collection of $\ell^*$ subsets of $S$, each with sum $\ge T$: remove as many elements as you can from each of these subsets, while maintaining the invariant that each must have sum $\ge T$. Once you cannot remove any more, you have a collection of $\ell^*$ $(a,b,T)$-minimal subsets. So indeed it is fine to look only for collections of $(a,b,T)$-minimal multisets.
Note that there are not so many "minimal" $(a,b,T)$-multisets that can be subsets of $S$: we can crudely bound by $\min(m_1, m_2)+1$ (since no two minimal multisets can have either coordinate equal).
Call the actual number of these minimal multisets that are also subsets of $S$ as $M$. Order these $M$ subsets in say lexicographically decreasing order (like we did above), and call them $(i_1, j_1), (i_2, j_2), \dots, (i_p, j_p),\dots, (i_M, j_M)$.
We claim to solve $P'$ in poly-time with a dynamic programming approach (where we'll construct the optimal $\ell^*$ minimal multisets in lexicographically decreasing order):
Our overall problem is to compute the maximum number of disjoint $(i_p, j_p)$s we can find among the base set $S = (m_1, m_2)$.
Let $F(M', m_1', m_2')$ be defined as the maximally sized disjoint collection of $(m_1', m_2')$ you can find, where all the subsets must be one of the lexicographically smallest $M'$ subsets of the $M$ $(a,b,T)$-minimal subsets we identified, i.e. $(i_{M-M'+1}, j_{M-M'+1}), (i_{M-M'+2}, j_{M-M'+2}) ..., (i_M, j_M)$.
We want to find $F(M, m_1, m_2)$.
We have the recurrence $$F(M, m_1, m_2) = 1 + \max_{p=1, 2, \dots, M} F(M-p+1, m_1-i_p, m_2-j_p)$$ and similarly $$F(M', m_1', m_2') = 1 + \max_{p=M-M'+1, \dots, M} F(M-p+1, m'_1-i_p, m'_2-j_p).$$ In each subproblem none of the 3 coordinates ever increase, and always either $m_1'$ or $m_2'$ decreases.
The running time of this dynamic programming is bounded by $O(M (Mm_1m_2)) = O((m_1+m_2)^4)$, as we wanted (strictly, the DP only gives the value of $\ell^*$ and not an achieving disjoint $\ell^*$-collection, but I think an actual optimal solution should be able to be constructed from the DP table as well). $\square$.


Is there an analogy of a vertex separator for hypergraphs?

heres an example

PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING
APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS KAYAASLAN et al

(there is also some research on hypergraph edge separators used in SAT solvers & other edge separators but not incl it because you asked for vertex separators although there is possibly/presumably some connection.)


Claim: If $M$ is a 2-way NFA (without endmarkers) with $n$ states
which acceptes a unary language $L\not=\emptyset$ then there is a word $w \in L$ of
length at most $3n+5$.

Proof sketch:
Let $v\in L$ be some word of some length $N>3n+5$ and let $\rho$ be
an accepting run for $v$. Let $v=v_1 v_2$, where $v_2$ is the suffix
of $v$ of length $n+1$. Let $\rho=\rho_1\rho_2$, where $\rho_1$ is
the prefix of $\rho$ that ends when the head moves from the last
position of $v_1$ to the right, for the last time. Let $q$ be the last
state of $\rho_1$.

Before we manipulate $\rho_1$, we first prepare a "way out" for $M$ by
showing that we can pump up (!) $\rho_2$.

For each of the $n+1$ positions $i$ of $v_2$ let $p_i$ be the first
state in which this position is visited in $\rho_2$. Clearly, there
must be positions $i<j$ with $p_i=p_j$ and thus we can pump up
$\rho_2$ by strings whose length are multiples of $j-i$, if we like. (This will not affect
$\rho_1$ and the subrun $\rho'_1$ that will be described below).

However, the main part of the construction is to transform $\rho_1$
into a subrun $\rho'_1$ on the string $u$ of length $2n+3$. The idea is to
center $\rho'_1$ around position $n+2$ and neither let it get to
position 1 nor to position $2n+3$. The construction will make sure
that $\rho'_1$ ends in state $q$ at some position (between 2 and 2n+2). It
can then be completed to an accepting run by adding a suitably pumped
version of $\rho_2$ that makes sure that the overall string $uv'_2$
has length at least $2n+2$ (but at most $3n+4$).

Let $\rho_0$ be the prefix of $\rho_1$ until position $n+2$ is reached
for the first time. The prefix of $\rho_1'$ is then just $\rho_0$.

Let us assume that the next step of $M$ is to the left. We follow the next
steps of $\rho_1$ until either it comes back to position $n+2$ or
until it attempts to step at position 1. If the former happens, this
part of $\rho_1$ is just copied to $\rho'_1$. In the latter case, we
consider for each position $1,\ldots,n-1$ the state $r_i$ in which it
is visited for the first time in the current subrun. Clearly, there must
be $i<j$ with $r_i=r_j$ and we just remove the part of the subrun between
$(j,r_j)$ and $(i,r_i)$. The consideration of the thus shortened run
goes on in this way until position $n+2$ is reached again.

When $M$ moves to the right of $n+2$, a similar procedure is applied with
positions $n+3,\ldots,2n+3$ in place of $1,\ldots,n+1$.

It is easy to see (but a bit tedious to formally denote) that the resulting subrun
$\rho'_1$ is valid for $M$, remains in the interval $[2,\ldots,2n+2]$
and eventually reaches state $q$ at some position $k$. It is then
extended to an accepting run as described above.


How to find interesting research problems

I strongly disagree with the "find a list of open problems" approach. Usually open problems are quite hard to make progress on, and I'm thoroughly unconvinced that good research is done by tackling some hard but uninteresting problem in a technical area.

That being said, of course solving an open problem is really good for academic credentials. But that's not what you are asking.

Research is a process designed to generate understanding at a high level. Solving technical problems is a means to that end: often the problem and its solution illuminate the structure or behavior of some scientific phenomenon (a mathematical structure, a programing language practice, etc).

So my first suggestion is: find a problem that you want to understand. Research is fundamentally about confusion. Are there some specific topics you are interested in, but that you feel you have a fundamentally incomplete comprehension of, or that seem technically clear, but that you lack any good intuition for? Those are good starting points. Follow Terry Tao's advice ask yourself dumb questions! A lot of good research comes out of these considerations. In fact, this whole page contains a lot of good advice. Note that if you are looking at a well-explored problem or field, it's unlikely you'll get original insights right away, so it's important to read up on literature concurrently with your own explorations.

Second, don't discount communicating with your Professors. Ask them about their own research, not necessarily about projects they want to give you. Engage in a conversation! This helps you find out what you are interested in, but also what the research landscape looks like in their field. Research doesn't happen in a vacuum, so you should speak to your fellow students, PhDs in your department, go to talks and workshops at your university, etc. You'll find that being immersed in a research environment helps you do research a lot more than finding a list or specific problem and locking yourself in your office.

Finally, I would suggest working on something small. Research is bottom-up much more than it is top down, and it's rare that a very simple task (writing a proof or a program) turns out to be as simple as you expected it to. Doing several small projects that are not research-scale (expanding on homework, writing up an explanation of something you learned) often build up into genuine research level stuff. It's common to try to "go big" at the beginning, but that's just now how our brains work.


Number of Maximum Overlap in n-Dimensions

This is a well-known variant of Klee's measure problem.  The best algorithm known, due to Timothy Chan, runs in roughly $O(n^{d/2})$ time, ignoring polylogarithmic factors.  Faster algorithms are known for the special cases of fat boxes and boxes with one or more fixed coordinates; see recent work by Karl Bringmann and Hakan Yıldız, respectively.


Are Turing machines still useful as model of computation?

I think the issue is that, you're misunderstanding the purpose of the Turing Machine model.

Turing Machines are not meant to be programmed in.  If you're writing code, you absolutely should not be thinking of how it would run on a Turing Machine.

However, Turing Machines are excellent for reasoning about. In Theoretical Computer Science, we're interested in proofs. We want to be able to say "there exists an algorithm with this property" or "for all algorithms, this statement holds". And we need an operational definition of what an algorithm is.

This is exactly where Turing Machines come in handy. First, the definition of a Turing Machine is precise: it's an exact mathematical object, whose behaviour is fully specified. Secondly, it's small: it contains finite states, and transitions between states that affect the tape.

If you wanted to rigorously prove something about a smartphone model, you would have to reason about all the different bits in memory, possibly even about hardware and transistor states. But to prove something about a Turing Machine, there's one simple state-space, and a simple memory model. This is how we've been able to build up theories of decidability, computational complexity, etc. They work because they're based on a model that's simple enough to write proofs about, but powerful enough that it reflects the capabilities of actual computers.

For example, say you create a new programming language. You want to show that every problem that can be solved, can be solved in your language. Now, you could show that you can simulate an entire smartphone's circuitry in your language, each gate and transistor and byte. But that's huge. Instead, you can achieve the same thing by showing that you can simulate an arbitrary Turing Machine in your language, which is much simpler to write.

Now, it's worth mentioning that Turing Machine's are not the only model of computation. There are two main competitors. First, any time we're discussing  fine-grained complexity, you will likely use a RAM model instead of a Turing Machine, so that you can model the speed of algorithms without having to traverse the entire tape to access a particular part of memory. Secondly, the Lambda Calculus and its various derivatives are equivalent in power to a Turing Machine. While they don't model hardware, their semantics closely match how we think of programming language as behaving, and there's an entire field (Programming Languages Theory) build around such models. They're not as minimal as Turing Machines, but they're more compositional i.e. it's easier to build programs by combining small building blocks. and their behavior is predicable based on those combinations.


PARITY $\notin$ $AC^0$ with bounded fanout: easy proof?

I might miss something, but isn't $AC^0_{bf}$ the same as a Formula? Since every input bit can have an effect on at most a bounded number of gates, we can simply suppose that every gate has only one output (after possibly duplicating a few things) and we can push down not gates as well. We know that the formula size of parity is n^2 (see Troy J. Lee, "The formula size of PARITY", 2007) and since on every level of our circuit we can only have O(n) gates, this shows that parity is not in $AC^0_{bf}$.


PTAS for a variant of multiple knapsack?

If I'm not mistaken, in the introduction of Bansal and Sviridenko, they mention that your special case - where children value items equally aka jobs take the same time on all machines - was the topic of Woeginger (1994) and shown to have a PTAS. Woeginger also points out that the problem is strongly NP-hard and hence does not permit an FPTAS unless P=NP.

Note however that if the number of bins $m$ is fixed rather than being part of the input, then the usual discretization method used for Knapsack and others, where items are rounded to powers of $(1+\epsilon/n)$, seems to yield an FPTAS.


Uses of algebraic structures in theoretical computer science

My impression is that, by and large, traditional algebra is rather too specific for use in Computer Science.  So Computer Scientists either use weaker (and, hence, more general) structures, or generalize the traditional structures so that they can fit them to their needs.  We also use category theory a lot, which mathematicians don't think of as being part of algebra, but we don't see why not.  We find the regimentation of traditional mathematics into "algebra" and "topology" as separate branches inconvenient, even pointless, because algebra is generally first-order whereas topology has a chance of dealing with higher-order aspects.  So, the structures used in Computer Science have algebra and topology mixed in.  In fact, I would say they tend more towards topology than algebra.  Regimentation of reasoning into "algebra" and "logic" is another pointless division from our point of view, because algebra deals with equational properties whereas logic deals with all other kinds of properties as well.

Coming back to your question, semigroups and monoids are used quite intensely in automata theory.  Eilenberg has written a 2-volume collection, the second of which is almost entirely algebra.  I am told that he was planning four volumes but his age did not allow the project to be finished.  Jean-Eric Pin has a modernized version of a lot of this content in an online book.  Automata are "monoid modules" (also called monoid actions or "acts"), which are at the right level of generality for Computer Science.  Traditional ring modules are probably too specific.

Lattice theory was a major force in the development of denotational semantics.  Topology was mixed into lattice theory when Computer Scientists, jointly with mathematicians, developed continuous lattices and then generalized them to domains.  I would say that domain theory is Computer Scientists' own mathematics, which traditional mathematics has no knowledge of.

Universal algebra is used for defining algebraic specifications of data types.  Having gotten there, Computer Scientists immediately found the need to deal with more general properties: conditional equations (also called equational Horn clauses) and first-order logic properties, still using the same ideas of universal algebra.  As you would note, algebra now merges into model theory.

Category theory is the foundation for type theory.  As Computer Scientists keep inventing new structures to deal with various computational phenomena, category theory is a very comforting framework in which to place all these ideas.  We also use structures that are enabled by category theory, which don't have existence in "traditional" mathematics, such as functor categories.  Also, algebra comes back into the picture from a categorical point of view in the use of monads and algebraic theories of effects.  Coalgebras, which are the duals of algebras, also find a lot of application.

So, there is a wide-ranging application of "algebra" in Computer Science, but it is not the kind of algebra found in traditional algebra textbooks.

Additional note: There is a concrete sense in which category theory is algebra.  Monoid is a fundamental structure in algebra.  It consists of a binary "multiplication" operator that is associative and has an identity.  Category theory generalizes this by associating "types" to the elements of the monoid, $a : X \rightarrow Y$.  You can "multiply" the elements only when the types match: if $a : X \rightarrow Y$ and $b : Y \to Z$ then $ab : X \to Z$.  For example, $n \times n$ matrices have a multiplication operation making them a monoid.  However, $m \times n$ matrices (where $m$ and $n$ could be different) form a category.  Monoids are thus special cases of categories that have a single type.  Rings are special cases of additive categories that have a single type.  Modules are special cases of functors where the source and target categories have a single type.  So on.  Category theory is typed algebra whose types make it infinitely more applicable than traditional algebra.


Scott Aaronson gives an oracle where $\oplus$P = PEXP which implies the oracle you want. http://eccc.hpi-web.de/report/2005/040/download/ (Theorem 12 in the appendix)


Why is Bayesian filtering better than Neural Networks when classifying spam?

It would be interesting to know what litterature you have read.

As far as I know, Bayesian filters were working very well. That's because the learning is based on the words used, and a Bayesian filter is quick to understand that an email containt "Viagra" is likely spam.

But spammers are not so stupid, and they quickly introduced mispelled word. "VI4GRA" has never been seen in any spam before. In a word: it's easy to work around a Bayesian filter.

Neural Networks can be good at classifying. But there are two difficulties: the choice of measures ; the training data.


How to determine whether there is exactly one simple path between two nodes in a graph

Ok, now that you've revealed the motivation: there is exactly one simple path between two nodes iff there is a path in which every edge is a bridge of the graph. So find all the bridges (standard linear time by depth first search) and compute the connected components of the subgraph they form. Two vertices have a unique simple path iff they belong to the same component.


I think one surprising fact is that in this model Savitch's theorem doesn't "obviously" relativize. That is, one can see that $PSPACE^P=EXPTIME$ and $NPSPACE^P=NEXPTIME$ in this model, and we don't currently know that $EXPTIME=NEXPTIME$ (and Savitch's theorem in this context does not seem to give it).  I'd be interested in whether this can be pushed to "provably" non-relativizing.

One can also observe that $NL^{NL}=NL^L=NP$ in this model.

However, I think that this model is at least worth thinking about, with respect to issues of relativization in the space hierarchy theorem.  Also, in some sense, I want $L^A$ to make poly-sized queries to $A$.


What is the state of the art in theory of "Software transformations preserving behavior"?

I think what you are looking for, in the context of verified transformations in a proof assistant, is known as "refinement", wherein a very-high level, inefficient implementation of some algorithm is gradually refined down into an efficient, low-level implementation, proving that the transformations preserve certain properties along the way.  Various tools have been developed to help the user do this without being overcome by tedious book keeping.

In terms of the state of the art, I think Lammich's tool in Isabelle/HOL has been used successfully in at least two significant developments (a verification of Hopcroft's algorithm by Lammich and Tuerk, and a verified implementation of an LTL model checker by Esparza, Lammich et al).  Ironically, I was also reading this paper this morning, about a similar tool, newly developed, in Coq, courtesy of the dependent_types subreddit on Reddit.


This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible.

I think you're going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory indexing? Comparisons? If you allow bitwise binary operations (including shifts) and either hashing or unbounded memory then it's all over, even without multiplication or division:

def sort(intlist):
    backtrans = {}
    bits = 0
    for x in intlist:
        y = 1<<x
        if y in backtrans:
            backtrans[y][1] += 1
        else:
            backtrans[y] = [x,1]
        bits |= y
    while bits:
        y = bits &~ (bits - 1)
        x,reps = backtrans[y]
        for i in range(reps):
            yield x
        bits &=~ y

There's also a linear time sorting algorithm (for large enough machine words) by Albers and Hagerup 1997 but I'm not sure which operations it needs or whether it could be adapted to use only arithmetic and not bit manipulation. The reference is:

Albers, Susanne; Hagerup, Torben (1997), "Improved parallel integer sorting without concurrent writing", Information and Computation 136 (1): 25–51.


Research problems in communication complexity

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity.

It's hard to say what areas a new communication complexity researcher should delve into, since easy problems have likely been solved already, and harder problems are hard ;)  One suggestion is to take known communication lower bounds (such as for Disjointness or Equality) and apply these to get new lower bounds in other areas of computer science.  New applications of communication complexity pop up all the time, and if you can find a niche no one's considered before, you might be able to leverage the existing bounds you're learning now rather than having to develop new lower bounds.  This will help you get some papers out while you're learning all about communication complexity ;)

Another suggestion is to work hard to ask new questions people haven't yet considered, or to think about new settings that are fresh and less well-studied. Multiparty communication might be a good area to look at---it is generally less understood than two-party communication, and (IMO at least) there's lots of fresh motivation for studying it (from e.g. multicore processors to wireless sensor networks)

For a concrete open problem, there's a nice one from multiparty communication in the number-on-the-forehead (NOF) model.  In the NOF communication model, there are $k$ players who wish to compute some function $f(x_1,\ldots, x_k)$ on $k$ inputs.   However, each player $PLR_i$ sees every input except $x_i$.  (You can imagine $PLR_i$ having $x_i$ written on his forehead.) Because lots of input is shared between players, it should be easier to compute functions of their input.  Conversely, proving lower bounds on the communication complexity in the NOF model is harder.

Here's a $\textbf{big open problem}$ in this area:  come up with some explicit function f(x_1,\ldots, x_k) for k=polylog(n) such that $\omega(polylog(n))$ communication is required in the NOF model.

Through a chain of results from the early nineties [Hastad-Goldman91, Beigel-Tarui94], it's known that such a result would imply that $f \not\in ACC_0$.  For this connection to circuit complexity, you're actually free to assume that each player sends a single message to some "referee" who compiles the messages to produce an output.  Lower bounds even in this restricted setting are far from what we'd like.  The current state-of-the-art lower bound techniques for the NOF model don't give lower bounds better than $\Omega(n/2^k)$ or thereabouts.  These become trivial once $k > \log(n)$.


Shortest distance/path between two households

This problem is well considered and learned in recent decades as every GPS device faces this problem.

In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, which usually (or more correctly, used to) approximate the distance between every two nodes by keeping only a $k\times n$ distances tables for a well-selected $k$ vertices.

The lastest result I'm aware of, keep a data structure of size $O(kn^{1+1/k})$, answering queries in $O(1)$ time and giving a stretch (i.e. the return value $\delta$ is promised to suffice $d\leq \delta \leq d\cdot s$). of $2k-1$.

Alternatively, if you're looking for a stretch smaller than 2, I suggest looking at this paper.


Is there any reference on the hardness of approximation for 2-partition problem?

From the Wikipedia page on the Partition problem: "...there are fully polynomial-time approximation schemes for the subset-sum problem, and hence for the partition problem as well". The references given there are
Kellerer, Pferschy, Pisinger and Martello, Toth.


Preparatory Rant

I've gotta tell you, I don't see how talking about "proofs" of the CT or ECT adds any light to this discussion.  Such "proofs" tend to be exactly as good as the assumptions they rest on---in other words, as what they take words like "computation" or "efficient computation" to mean.  So then why not proceed right away to a discussion of the assumptions, and dispense with the word "proof"?

That much was clear already with the original CT, but it's even clearer with ECT---since not only is the ECT "philosophically unprovable," but today it's widely believed to be false!  To me, quantum computing is the huge, glaring counterexample that ought to be the starting point for any modern discussion about the ECT, not something shunted off to the side.  Yet the paper by Dershowitz and Falkovich doesn't even touch on QC until the last paragraph:

The above result does not cover large-scale parallel computation, such as quantum computation, as it posits that there is a fixed bound on the degree of parallelism, with the number of critical terms fixed by the algorithm.  The question of relatively [sic] complexity of parallel models will be pursued in the near future.

I found the above highly misleading: QC is not a "parallel model" in any conventional sense.  In quantum mechanics, there's no direct communication between the "parallel processes"---only interference of amplitudes---but it's also easy to generate an exponential number of "parallel processes."  (Indeed, one could think of every physical system in the universe as doing so as we speak!)  In any case, whatever you think about the interpretation of quantum mechanics (or even its truth or falsehood), it's clear that it requires a separate discussion!

Now, on to your (interesting) questions!

No, I don't know of any convincing counterexample to the ECT other than quantum computing.  In other words, if quantum mechanics had been false (in a way that still kept the universe more "digital" than "analog" at the Planck scale---see below), then the ECT as I understand it still wouldn't be "provable" (since it would still depend on empirical facts about what's efficiently computable in the physical world), but it would be a good working hypothesis.

Randomization probably doesn't challenge the ECT as it's conventionally understood, because of the strong evidence today that P=BPP.  (Though note that, if you're interested in settings other than language decision problems---for example, relational problems, decision trees, or communication complexity---then randomization provably can make a huge difference.  And those settings are perfectly reasonable ones to talk about; they're just not the ones people typically have in mind when they discuss the ECT.)

The other class of "counterexamples" to the ECT that's often brought up involves analog or "hyper" computing.  My own view is that, on our best current understanding of physics, analog computing and hypercomputing cannot scale, and the reason why they can't, ironically, is quantum mechanics!  In particular, while we don't yet have a quantum theory of gravity, what's known today suggests that there are fundamental obstacles to running more than about 1043 computation steps per second, or resolving distances smaller than about 10-33 cm.

Finally, if you want to assume out of discussion anything that might be a plausible or interesting challenge to the ECT, and only allow serial, discrete, deterministic computation, then I agree with Dershowitz and Falkovich that the ECT holds! :-)  But even there, it's hard to imagine a "formal proof" increasing my confidence in that statement -- the real issue, again, is just what we take words like "serial", "discrete", and "deterministic" to mean.

As for your last question:

Quantum computing would be a likely counterexample, if in fact it can be instantiated, but are there possibilities "weaker" than quantum that would be counterexamples as well?

Today, there are lots of interesting examples of physical systems that seem able to implement some of quantum computing, but not all of it (yielding complexity classes that might be intermediate between BPP and BQP).  Furthermore, many of these systems might be easier to realize than a full universal QC.  See for example this paper by Bremner, Jozsa, and Shepherd, or this one by Arkhipov and myself.


Determine the minimum number of coin-weighings

I had a brief look at this paper, and it appears that the answer to your question is yes (that is - no need for randomization). Also, the Introduction section surveys previous algorithms, information theoretic lower bounds and so on.


Is longest common subsequence with bounded occurrences NP-complete?

This paper by Blin et al. (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.


Adding integers represented by their factorization is as hard as factoring? Reference request

Assume that we can solve the problem (lets call it FactSum) in complexity class $C$ and $C$ is closed under $\log$-iteration (aka $\log$-bounded recursion)(e.g. if we can compute $x*y$ where $*$ is a binary function, we can computed $x_1*\ldots*x_{\log{n}}$) and contains $\mathsf{P}$ (this last condition can be made weaker). We show that factoring is in also in $C$.

Note that each number can be written as a sum of $\log n$ powers of $2$. Each of them are easy to factor.

Now given a number, write it as the sum of powers of it, then write each summand in the factoring representation, and then use the algorithm to sum them in the factoring representation. The result will be the factoring of the input number.

This shows that factoring is reducible to $\log$-iteration of your problem FactSum. Therefore factoring is in $\mathsf{P}^{\text{FactSum}}$ (and I think $\mathsf{P}$ can be replaced with  $\mathsf{NC^1}$ here).


Space efficient "industrial" unbalanced expanders

Eickmeyer and Grohe (2010) prove that your candidate construction can be made explicit: take $d$ somewhat linearly independent linear hash functions $h_1,\dots,h_d$ and connect left vertices $v$ with right vertices $h_1(v),\dots,h_d(v)$. Eickmeyer and Grohe show that this construction gives $(k,\epsilon)$-expanders with left degree $d=k(t-1)/(2\epsilon)$, whenever $t$ is an integer, the left vertex set has size $n=q^t$, the right vertex set has size $m=dq$, and $q>d$ is a prime power. The hash functions $h_1,\dots,h_d$ are chosen in such a way that any $t$ of them are linearly independent.


Does MCMC belong to the statistical query model?

Let me first clarify what the paper states: "Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented using only access to such an [meaning SQ] oracle". So the question is not really whether MCMC "falls into the SQ framework" (the framework does not place any restrictions on computation) but whether the access to data samples that is necessary to run the algorithm can be replaced with access to an SQ oracle without invalidating the guarantees provided by the algorithm. One can also show that an algorithm for which we have no guarantees is an SQ algorithm but that requires an implementation using an "unbiased" oracle (referred to as 1-STAT in the paper). Lower bounds that can be proved against such an oracle are weaker.

Now regarding MCMC with SQs: the main way to apply MCMC to these kinds of problems that we had in mind in described in an example at the bottom of page 4. Please also take a look at the proof of Thm. 9 here in a follow up paper on this type of techniques:
http://arxiv.org/pdf/1311.4821v5.pdf


Expected values of Kolmogorov complexity in a random sample

Kolmogorov complexity is only determined up to some additive constant, so it is not possible to give an exact answer. The bound that I describe here is even weaker.

Of course the expected number can be computed easily once we know how many of the $2^n$ strings have complexity less than $n_0$, so let me answer this. It is usually the first statement about Kolmogorov complexity that this number is at most $2^{n_0}-1$ - since there are only these many strings of smaller length. On the other hand, if your program says "of length $n$, take the $x$th number", then you get $2^{n_0-K(n)-C}$ strings of complexity less than $n_0$, where $K(n)$ is the prefix-free version of Kolmogorov complexity of $n$ (so at most $\log n+\log^* n + O(1)$). In more detail, the string first contains the description of the Turing machine that taken input $px$, where p is the description of a prefix-free program that outputs $n$, outputs the $x$th number of length $n$, which is $O(1)$ bits, and then this is followed by $px$.

Probably it is possible to improve these bounds, but I doubt that you could get an exact answer.


How well can an arbitrary (unknown) quantum state be imperfectly cloned?

This problem has been studied in great detail, not just for the case of imperfectly cloning 1 qubit to get 2 copies, but more general problems of how to get m copies of a state given n copies, etc. I don't work in the area, but I'll try to give you some answers. Others may be able to provide a better answer.
For the problem you describe, 1 qubit to 2 qubit cloning, the optimal cloner is due to

Bužek, Vladimir, and Mark Hillery. "Quantum copying: Beyond the no-cloning theorem." Physical Review A 54, no. 3 (1996): 1844.

They show how to take an input state $|\psi\rangle$ and output two qubits such that the reduced density matrix of either output qubit (let's call it $\rho$) satisfies $\langle\psi|\rho|\psi\rangle=5/6$.
This was later shown to be optimal by several authors:

Bruß, Dagmar, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello, and John A. Smolin. "Optimal universal and state-dependent quantum cloning." Physical Review A 57, no. 4 (1998): 2368.
Gisin, Nicolas, and Serge Massar. "Optimal quantum cloning machines." Physical review letters 79, no. 11 (1997): 2153.
Gisin, Nicolas. "Quantum cloning without signaling." Physics Letters A, Volume 242, Issues 1–2, 1998, Pages 1-3

A survey on the topic that covers this and much more:

Scarani, Valerio, Sofyan Iblisdir, Nicolas Gisin, and Antonio Acin. "Quantum cloning." Reviews of Modern Physics 77, no. 4 (2005): 1225.


Does there exist a CAS for formal language theory?

I am vaguely aware that it's possible to do some computations with formal languages in GAP, but I don't know the details, sorry.  There is a package "Automata", but I'm not sure if there's anything for grammars.


Practical approaches to solving whether programs will halt

Yes, an example of a system that performs this task is T2. It does not solve the halting problem but instead it only attempts to solve certain special cases. A overview is at https://en.wikipedia.org/wiki/Microsoft_Terminator . The newest version of this system is at https://mmjb.github.io/T2/ .


Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances

Here's the first approach that occurs to me.  Build a complete graph on 11,000 vertices, and label all edges with the great-circle distance.  Apply some travelling salesman algorithm to choose the best route you can find.  Then, for every edge on that route, query the map service for the road distance and replace the label on that edge with the road distance.  Then, apply the travelling salesman algorithm again on the modified graph.  Repeat this basic process until it converges.

I think the great-circle distance should be a lower-bound on the road distance, so I suspect this should be correct (in the sense that it doesn't miss out on a better solution).

One possible complication is that this might cause triangle-inequality violations, so if you are relying upon a heuristic that assumes the triangle inequality, this approach might screw things up.  I don't know; you could try it out and see.

If you wanted to reduce the number of queries for the road distance even further, here's one more idea you could try.  I suspect that the smaller the great-circle distance, the closer it is to the road distance; or, in other words, I suspect the gap between the distances might be largest for points that are far away.  That's something you'd need to validate yourself.  If it is correct, then a variant of the algorithm I suggested above is: only query the map service to obtain the road distance for edges where the great-circle distance is above some threshold.  (You could even gradually reduce this threshold in each iteration of the above algorithm.)


Research on call-site based type inference?

Almost all systems with type inference use call-site information to do this.  Examples include Standard ML, OCaml, F#, and Haskell.  Many other languages use call-site information to infer type parameter instantiation, such as Java, C#, Scala, and Typed Racket.  This often goes by the name "Local Type Inference".

I would just describe what you're looking for as "Type Inference", and you should probably start by looking up what's commonly known as the "Hindley-Milner" system.  The Wikipedia page gives a reasonable introduction, and pointers to the original papers.

The place to start for Local Type Inference is Pierce and Turner's original paper, best read in the TOPLAS 2000 version (ACM, PDF).


1000 individuals is typically a fairly large population, so lacking further information, you're probably fine there.

You don't say how quickly your algorithm is converging or exactly you calculate the weights for weighted selection, but if you're doing the typical roulette-wheel or fitness-proportionate selection, it's known that that method produces a large amount of selection pressure, particularly early in the run. What happens is that most early solutions are terrible, so the first mediocre thing it finds gets a much higher proportion of the total fitness than it really deserves and quickly swamps the population. The easiest way to avoid that is to use something with a more controllable selection pressure, like binary tournament selection or rank-biased selection.

For mutation, the general rule of thumb has always been to mutate each allele independently with probability 1/n. Like any heuristic, that's only a starting point, and you should let experiment guide you in making any adjustments, but if I'm understanding you correctly, you have 192 alleles, so a 4% mutation rate gives an expectation of about 8 mutations per individual, which I would guess is too high.

Or do you mean you make a single mutation to 4% of the generated offspring? If that's the case, it's probably too low. I'd start with a method that mutates every single individual by a randomly selected amount, with the expected amount being one flip. Some individuals will get two or three flips, others will not be altered at all.

The third idea, having multiple populations and sharing between them goes by the name of "island model" GAs, and has been known to work pretty well for some problems. However, I think in your case there are some issues with the way the underlying algorithm is working that need to be addressed before moving to a parallel model that will only make it more difficult to tease out the dynamics of what's going on.

Without more details about exactly how you're encoding your solutions, how your crossover and mutation operators work, etc., we're kind of limited to general statements such as those I just made. Feel free to post any clarifications though and I'll take another run at helping understand what might be going on.


Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

Pat Morin demonstrates a structure with $O(\sqrt{n})$ extra words of space and $O(\log^2 n)$ insert, delete, and predecessor search in his notes for his advanced data structures class.


Fractional but not integer multi-commodity minimum cost flow

You can use the example for an undirected edge with unit capacities, but replace each undirected edge from A to B with a set of directed edges that look like this.

Each edge has a unit capacity. And if you have $x$ units of flow from A to B and $y$ units of flow from B to A, you can route it as long as $x+y \leq 1$.

This is the gadget referred to in Andreas Björklund's comment.


VC-Dimension and sample complexity dependent on size of subsets

No, you cannot. See Thm 2.1 of http://link.springer.com/article/10.1007%2FBF02187833 (it says that a random family gives an example, with appropriately chosen parameters).


Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$

It's not clear if this is directly useful, but lower bounds are known for depth-3 circuits computing an $n$-variate version of your function over $\mathrm{GF}(p)$ for $p \neq 2$. See Theorem 3.7 in the survey of Shpilka and Yehudayoff for details and references.

I don't believe lower bounds of the form $\omega(\log d)$ are known for general circuits computing an explicit univariate polynomial of degree $d$, so proving an $\omega(\log p)$ lower bound for your problem will likely be difficult.