Route existence between n pairs of nodes

As Chandra Chekuri pointed out in a comment, you could just compute the transitive closure via fast matrix multiplication, solving the problem in O($n^\omega$) time (use your favorite method, O($n^{2.376}$) via Coppersmith and Winograd, or more practically using Strassen's O($n^{2.81}$)), and this would be good for dense graphs.

Now, I claim that if you can beat this running time for your problem for dense graphs, you would obtain an algorithm for triangle detection which is more efficient than computing the product of two Boolean matrices. The existence of such an algorithm is a major open problem.

I'll reduce the triangle problem to the n-pairs-DAG-reachability problem.
Suppose we are given a graph G on n nodes and we want to determine whether G contains a triangle.

Now, from G create a DAG G' as follows. Create four copies of the vertex set, $V_1$, $V_2$, $V_3$, $V_4$. For copies $u_i\in V_i$, $v_{i+1}\in V_{i+1}$ for $i=1,2,3$, add an edge $(u_i,v_{i+1})$ iff $(u,v)$ was in G.  Now if we ask whether there is a path between any of the pairs $(u_1, u_4)$ for all $u\in $G, then this would exactly be asking whether there is a triangle in $G$. The current graph has $4n$ nodes and we are asking about $n$ pairs. However, we can add $2n$ isolated dummy nodes and have $3n$ queries instead (by adding a query for $2n$ distinct pairs $(y,d)$ where $y\in V_2\cup V_3$ and $d$ a dummy), thus obtaining a $6n$-node instance of exactly your problem.


From a mathematical perspective: Try

  1) Handbook of coding theory - Huffman and Pless

  2) Fundamentals of Error-Correcting Codes - Huffman and Pless

  3) Introduction to coding theory - Ron Roth

  4) Algebraic Geometric Codes: Basic Notions - Vladut, Nogin and Tsfasman

  5) Introduction to Coding Theory - Van Lint

  6) Algebraic Geometry in Coding Theory and Cryptography - Harald Niederreiter and Chaoping Xing.

From an engineering perspective: Try

  1) Error Control Coding - Shu Lin and Daniel Costello

  2) Modern Coding Theory - Richardson and Urbanke

  3) Error Correction Coding - Todd K Moon

  4) Channel Codes: Classical and Modern - William Ryan and Shu Lin.

From Computer Science perspective: Try

  1) Madhu Sudan MIT Notes

  2) Algorithmic Results in List Decoding -  Guruswami

  3) Computational complexity - Boaz Barak (Chapter 19)

  4) Refer this cstheory question - Using error-correcting codes in theory

  5) Locally Decodable Codes - Yekhanin

  6) Chapter on applications of coding theory in complexity theory in Different Aspects of Coding Theory - Calderbank.


Can any Steiner Tree Problem be converted to Node-Weighted Steiner Tree Problem?

Sounds right. Denote by $G$ the original graph, and by $G'$ the graph after introducing the new vertices.

The first direction is trivial - every Steiner tree in $G$ corresponds to a Steiner tree in $G'$, with the same weight (by splitting each edge with its new vertex).

The second direction is less trivial. Still, consider a minimal Steiner tree $T$ in $G'$. We can assume w.l.o.g that $T$ does not contain any leaf that corresponds to a new edge-vertex. Indeed, this vertex is not in $S$, so if it is a leaf, it can be removed from the tree, keeping it a Steiner tree with minimal weight (unless you allow negative weights, which I assume you don't).

Now that we have a Steiner tree without edge-vertex leafs, we can convert it to a Steiner tree in $G$: root the tree by some vertex that is not an edge-vertex, then by the construction, all the edge-vertices have a single child in this tree. So you can replace each pair of edges $(u,X),(X,v)$ by $(u,v)$ in the original graph, obtaining a Steiner tree with the same weight.

I don't see any bugs here, but maybe I missed something.


Yes, it is NP-complete, by reduction from 3SAT.  In particular, we will go through an intermediate problem, which I will define as follows:

Definition.  The 1-to-3 of $k$ problem is as follows: given $n$ sets $S_1,\dots,S_n$, decide whether there exists $y_1,\dots,y_m \in \{0,1\}$ such that $1 \le \sum_{j\in S_i} y_j \le 3$ holds for all $i$.

Theorem 1. The 1-to-3 of $k$ problem is at least as hard as 3SAT.

Proof: Suppose we have a formula $\varphi$ with $n$ clauses over $m$ variables, $x_1,\dots,x_m$.  Introduce $m'=2m$ variables, $y_1,\dots,y_m$.  The intent is that these will correspond to the $2m$ literals $x_1,\dots,x_m,\neg x_1,\dots,\neg x_m$ (e.g., $y_i=1$ if and only if $x_i=\text{True}$; $y_{m+i}=1$ if and only if $x_i=\text{False}$); we will introduce a few sets to enforce this intent.  There are $n'=n+m+\lceil m/3\rceil$ sets, as follows:

First, there are $n$ sets, one for each clause of $\varphi$.  If $\varphi$ has the clause $(y_a\lor y_b\lor y_c)$ (where $y_a,y_b,y_c$ are three literals), then we'll add a set $S=\{a,b,c\}$ to enforce that at least one of $y_a,y_b,y_c$ must be true.
The next $m$ sets enforce that $x_i \lor \neg x_i$ is true for all $i$.  In particular, for each $i$, we add a set to enforce that at least one of $x_i, \neg x_i$ must be true, e.g., the set $S=\{i,i+m\}$ (if $y_i$ corresponds to $x_i$ and $y_{i+m}$ corresponds to $\neg x_i$).
Finally, the last $\lceil m/3 \rceil$ sets enforce that $x_i$ and $\neg x_i$ are not allowed to both be true.  We'll do this by enforcing that one, two, or three of $x_1,\neg x_1,x_2,\neg x_2,x_3,\neg x_3$ are true (e.g., the set $S=\{1,2,3,m+1,m+2,m+3\}$), and that at least one, two, or three of $x_4,\neg x_4,x_5,\neg x_5,x_6,\neg x_6$ are true (e.g., the set $S=\{4,5,6,m+4,m+5,m+6\})$, and so on.   Notice that, thanks to the previous category of sets, surely at least three of these 6 literals will be true, so asking that "one, two, or three should be true" amounts to asking that exactly three of them must be true -- which has the desired effect.

Finally, it is easy to see that this 1-to-3 of $k$ problem has a solution if and only if $\varphi$ has a satisfying assignment.  That completes the proof.

Theorem 2. Your problem is at least as hard as the 1-to-3 of $k$ problem.

Proof. Suppose we have a 1-to-3 of $k$ problem with $s$ sets over variables $y_1,\dots,y_r$.    Define $f(0)=0$, $f(1)=1$, $f(2)=1$, $f(3)=1$, and $f(k)=0$ for all $k>3$.  Define the matrix $M$ based upon the sets $S_1,\dots,S_s$.  In particular, if $S_i=\{a,b,c,\dots\}$, the $i$th column of $M$ has a 1 in the $a$th, $b$th, $c$th, $\ldots$ rows and is zero elsewhere ($M_{j,i}=1$ if and only if $j \in S_i$).  Finally, set $\alpha=s$.

Now $|f(v)|\ge \alpha$ holds if and only if $f(v_1)=f(v_2)=\dots=f(v_s)=1$.  Thus, this choice of $f$ and setting of $\alpha$ ensures that the only way to satisfy the equation $|f(v)|\ge \alpha$ is if each $v_i$ is 1, 2, or 3.  If we focus on $v_i$, corresponding to the set $S_i=\{a,b,c,\dots\}$, then $f(v_i)=1$ if and only if $1 \le y_a+y_b+y_c+\dots \le 3$.  Therefore, this instance of your problem has a solution if and only if the original 1-to-3 of $k$ instance does.


Permanents - Approximation and connection to integer factorization

Thanks for clarifying your earlier question.

In this case, we would indeed say the Permanent is in $P$. First, since addition and multiplication on $O(n^k)$ size numbers can be done in $n^k \log^{O(1)} n$ time, the $O(n^2)$ arithmetic operations would take less than $O(n^{k+3})$ time to execute. If $k$ is independent of $n$ and the numbers themselves, this is polynomial time.

Secondly, if you are computing the Permanent over the integers, then in the "hard case" you may not only assume that the integers are non-negative, but also you may assume that all integers are just $0$ and $1$! This is commonly known as Valiant's theorem. For information on how to prove this, see:

http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix

This means that restricting to a non-negative matrix with bounded entries is not really a restriction of the Permanent problem. A polynomial time algorithm for this version of the problem would result in a polynomial time algorithm for the Permanent over any integer matrix.


(False?) proof for computability of a function?

Think of it this way, Mike: This proof is "branching" into multiple possible cases, one of which has to be true (using the law of excluded middle that for every proposition $p$, either $p$ is true or $\neg p$ is true). But at the end of each of these branches, you always manage to prove that the function $f$ is computable. Therefore, no matter which of the cases actually holds in real life, $f$ must be computable. (However, the precise reason why $f$ is computable will be different, depending on the branch.)


Successful application of branch-and-bound methods for NP-hard problems

For TSP, checkout this book...
http://www.tsp.gatech.edu/book/index.html

My understanding is that there is no one tool to kill them all. Arguably any recursive solution deploying backtracking and some scoring function is using branch and bound. As such, a large fraction of solvers to NP hard problems use some form of branch and bound.


The 1998 chapter about the second LBA Problem, from Schöning and Pruim Gems of TCS mentions the first LBA problem.
The chapter does not say much more than the wikipedia article though, apart from mentioning the related Savitch's theorem, whose optimality is a notorious open question.

Perhaps by looking at papers quoting the Kuroda or Savitch paper you could get a picture of recent results in the field?


NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

This problem is NP-hard. In fact, even deciding whether there exists a choice of x such that all the dot products are positive is NP-complete. I show this below by reduction from set cover.

Reduction

Suppose we are given a set cover instance consisting of number $k$ and sets $S_1, S_2, \ldots, S_m \subseteq \{1,2,\ldots,n\}$. The corresponding question is whether there exists a subset $C$ of $\{1,2,\ldots,n\}$ with $|C| = k$ such that each $S_i$ contains at least one element of $C$ (or equivalently such that $S_i \cap C$ is non-empty for each $i$).

We use this input to construct an instance of your problem, that is, a set of vectors over $\{-1, 1\}$ of the same length. The length of these vectors is going to be $n+k+1$, and there will be $m+k+2$ of them. In particular, we will have vectors $a$, $b_1, b_2, \ldots, b_{k+1}$, and $c_1, c_2, \ldots, c_m$ as defined below.

Denote by $1(n)$ a vector of length $n$ whose values are all $1$s. Denote by $e_i(n)$ a vector of length $n$ whose $i$th value is $1$ and whose other values are $-1$. Denote by $s_j$ a vector of length $n$ whose $i$th value is $1$ if $i \in S_j$ and $-1$ otherwise.

Then

$a = [~1(k+1)~;~-1(n)~]$
$b_j = [~e_j(k+1)~;~1(n)~]$ for $1 \le j \le k+1$ and
$c_j = [~-e_1(k+1)~;~s_j~]$ for $1 \le j \le n$

Correctness

Let $x = [~x'~;~x''~]$ be any vector of $0$s and $1$s expressed as two subvectors $x'$ and $x''$ of lengths $k+1$ and $n$.

Suppose that the dot product of $x$ with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$ is positive. Then consider the two vectors $a$ and $b_j$ (for some $j$). These two vectors are almost exactly negatives of each other. In particular, they both have $1$ as the $j$th component but are otherwise negatives of each other (this is easy to verify). Then if $x$ is a vector of $0$s and $1$s with a $0$ in the $j$th component, the dot product of $x$ with $a$ is the negative of the dot product of $x$ with $b_j$. In this case, these two dot products cannot both be positive. Therefore, $x$ must have a $1$ in the $j$th component.

The above logic can be applied for every $j$ with ($1 \le j \le k+1$). From this, we can conclude that if $x$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$, then $x' = 1(k+1)$.

Furthermore, we know that $x \cdot a > 0$, and $$x \cdot a = [~x'~;~x''~] \cdot [~1(k+1)~;~-1(n)~]= [~1(k+1)~;~x''~] \cdot [~1(k+1)~;~-1(n)~] = 1(k+1) \cdot 1(k+1) + x'' \cdot -1(n) = k+1 - |x''|_1$$ where $|x''|_1$ is the number of $1$s in $x''$, so $k+1-|x''|_1 > 0$ and $|x''|_1 < k+1$.

Similarly, $x \cdot b_1 > 0$, and $$x \cdot b_1 = [~x'~;~x''~] \cdot [~e_1(k+1)~;~1(n)~]= [~1(k+1)~;~x''~] \cdot [~e_1(k+1)~;~1(n)~] = 1(k+1) \cdot e_1(k+1) + x'' \cdot 1(n) = -(k-1) + |x''|_1,$$ so $-(k-1)+|x''|_1 > 0$ and $|x''|_1 > k-1$.

Together the above implies that $|x''|_1 = k$. To summarize, we have shown that if $x$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$, then $x' = 1(k+1)$ and $|x''|_1 = k$. In fact, it is easy to verify that the reverse is also true. In other words, $x = [~x'~;~x''~]$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$ if and only if $x' = 1(k+1)$ and $|x''|_1 = k$.

From now on, consider only vectors $x$ of the above form. Notice that there is a one to one correspondence between possible vectors $x''$ and subsets of $\{1, \ldots, n\}$ of size $k$: in particular, $x''$ can be put into correspondence with set $X \subseteq \{1, \ldots, n\}$ with $|X| = k$ such that $(x'')_i = 1$ iff $i \in X$.

Under this correspondence, we can consider the necessary and sufficient conditions for $x$ to have positive dot product with vectors $c_1$, $\ldots$, and, $c_n$.

For any $j$, we can expand $x \cdot c_j$ as $$x \cdot c_j = [~1(k+1)~;~x''~] \cdot [~-e_1(k+1)~;~s_j~] = 1(k+1) \cdot -e_1(k+1) + x'' \cdot s_j = (k-1) + x'' \cdot s_j.$$
Notice that the value of $x'' \cdot s_j$ is exactly a sum of $k$ components of $s_j$: in particular, $x'' \cdot s_j = \sum_{i \in X}(s_j)_i$. If these $k$ components are all $-1$s, then this sum is $-k$, and so $x \cdot c_j = (k-1) + x'' \cdot s_j = (k-1) + -k = -1 < 0$. If these $k$ components include at least one $1$, then this sum is at least $-1\times(k-1) + 1\times 1 = -(k-2)$ in which case $x \cdot c_j = (k-1) + x'' \cdot s_j \ge (k-1) + -(k-2) = 1 > 0$. Thus, we see that $x \cdot c_j \ge 0$ for a specific $j$ if and only if $X$ includes at least one $i$ such that $(s_j)_i = 1$.

Remember that $(s_j)_i = 1$ if and only if $i \in S_j$. Thus, $x \cdot c_j \ge 0$ for a specific $j$ if and only if $X$ includes at least one $i$ such that $i \in S_j$, or equivalently if and only if $X \cap S_j$ is non-empty.

Then $x \cdot c_j \ge 0$ for every $j$ if and only if for every $j$, $X \cap S_j$ is not empty. Notice that the latter condition is exactly equivalent to the condition that $X$ is a solution to the input set cover instance.

In summary, we see that $x$ is a vector of $0$s and $1$s with positive dot product with all the vectors produced by the reduction if and only if $x = [~1(k+1)~;~x''~]$ with $|x''|_1 = k$ and $x''$ corresponds to a set $X \subseteq \{1, \ldots, n\}$ with $|X| = k$ such that $X$ is a solution to the input instance of set cover. In other words, a solution to the set cover instance exists if and only if a solution to the instance produced by the reduction exists.


PhD positions in TCS and Discrete Math are sometimes announced on TheoryNet and DMANET. These are mailing lists to circulate announcements and questions regarding conferences, workshops, seminars, books and jobs in these areas.


Connectivity of graphs by edge and vertex removal

This is an edited version of a previous "answer" which incorrectly claimed a polynomial-time algorithm for the problem. What I write below is a connection to an existing problem which suggests that the problem is difficult.

Let $s,t$ be two nodes in $G$ and we want to check if they are $(a,b)$-connected. That is removing any $a$ nodes and any $b$ edges should not disconnect $s$ and $t$. Another way to look at it as follows: what is the minimum number of nodes that we need to remove to reduce the edge-connectivity between $s$ and $t$ to $b$? These type of problems have been studied under the name multi-route cuts and they are dual to multi-route flows. Various approximation results have been shown though many basic problems are not yet resolved. A result of interest is the following. Suppose each edge has a cost $c(e)$ and we wish to remove the minimum-cost set of edges to reduce the edge-connectivity between $s$ and $t$ to $b$; then this problem is NP-Hard when $b$ is part of the input. This result is in the paper by Barman and Chawla: http://arxiv.org/abs/0908.0350

Two papers that will appear in upcoming SODA 2012 are on multi-route cuts which have further results on the topic. The one by Chuzhoy etal has hardness results for some variants.


Does the $\mathsf{TC^0}$ hierarchy collapse?

We know of no good lower bounds (meaning, say, a superpolynomial lower bound for a language in $\mathsf{NEXP}$) for depth 2 threshold circuits (unbounded weights). Depth 3 circuits built from majority gates, i.e. $\mathsf{TC}^0_3$ contains this class, and thus we know no good lower bounds for this class either.


Is it a bad idea to critique someone's paper in my first publication?

I think the same standards apply, regardless of whether it's your 1st or 100th publication. If you think you've found a mistake in a published paper, a common courtesy is to first contact the paper's authors for a clarification, as Noam suggested in the comments. If the authors confirm that it's indeed a mistake, you can indicate that in the paper (cite it as "private communication"); this should make the review process smoother.

When pointing out people's mistakes in print, gentle understatement is a good practice. "There appears to be a mistake in the proof" should be gentle enough. Having a counterexample certainly helps.


Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?

This paper by Keith Ball seems to be what you are looking for:

  Ball, Keith. "Isometric embedding in $\ell_p$-spaces."
  European Journal of Combinatorics 11.4 (1990): 305-311.

Link to the paper here:
https://www.sciencedirect.com/science/article/pii/S019566981380131X


Yes, there is!  I will give three examples:

Given a set S and a "multiplication table" over S x S, consider the problem of determining if the input describes an abelian group or whether it is far from one.  Friedl, Ivanyos, and Santha in STOC '05 showed that there is a property tester with query complexity polylog(|S|) when the distance measure is with respect to the edit distance of multiplication tables which allows addition and deletion of rows and columns from the multiplication table.  The same problem was also considered in the Hamming distance model by Ergun, Kannan, Kumar, Rubinfeld and Viswanathan (JCSS '00) where they showed query complexity of O~(|S|^{3/2}).
There is a large amount of work done on testing graph properties where the graphs are represented using adjacency lists and there is a bound on the degree of each vertex.  In this case, the distance model is not exactly Hamming distance but rather how many edges can be added or deleted while preserving the degree bound.
In the closely related study of testing properties of distributions, various notions of distance between distributions have been studied.  In this model, the input is a probability distribution over some set and the algorithm gets access to it by sampling from the set according to the unknown distribution.  The algorithm is then required to determine if the distribution satisfies some property or is "far" from it.  Various notions of distance have been studied here, such as L_1, L_2, earthmover.  Probability distributions over infinite domains have also been studied here (Adamaszek-Czumaj-Sohler, SODA '10).


Presburger Arithmetic Decision Procedures

John Harrison's handbook on automated theorem proving contains a fairly detailed description of Cooper's algorithm, including the steps necessary for an implementation in ML.

Harrison, J. (2009). Handbook of practical logic and automated reasoning. Cambridge University Press.


Provable statements about genetic algorithms

Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999. (Also available from Avi Wigderson's home page)


Balls and Bins analysis in the $m \gg n$ regime: gaps

Answer: $\Theta\left(\sqrt{\frac{m}{n\log n}}\right)$.

Applying a multidimensional version of the Central Limit Theorem, we get that the vector $(X_1,\dots, X_n)$ has asymptotically multivariate Gaussian distribution with
$$\mathrm{Var}[X_i] = m\left(\frac{1}{n} - \frac{1}{n^2}\right),$$
and
$$\mathrm{Cov}(X_i, X_j) = -m/n^2.$$
We will assume below that $X$ is a Gaussian vector (and not only approximately a Gaussian vector). Let us add a Gaussian random variable $Z$ with variance $m/n^2$ to all $X_i$ ($Z$ is independent from all $X_i$). That is, let
$$
\begin{pmatrix}
Y_1\\Y_2\\ \vdots\\Y_n
\end{pmatrix}
=
\begin{pmatrix}
X_1+Z\\X_2+Z\\ \vdots\\X_n +Z
\end{pmatrix}.
$$
We get a Gaussian vector $(Y_1, \dots, Y_n)$. Now each $Y_i$ has variance $m/n$:
$$\mathrm{Var}[Y_i] = \mathrm{Var}[X_i] + \underbrace{2\mathrm{Cov}(X_i,Z)}_{=\, 0}+\mathrm{Var}[Z] = m/n,$$
and all $Y_i$ are independent:
$$\mathrm{Cov}(Y_i, Y_j) = \mathrm{Cov}(X_i, X_j) + \underbrace{\mathrm{Cov}(X_i,Z) + \mathrm{Cov}(X_j,Z)}_{=\, 0} +\mathrm{Cov}(Z, Z) = 0.$$

Note that $Y_i - Y_j = X_i - X_j$. Thus our original problem is equivalent to the problem of finding $Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}$. Let us first for simplicity analyze the case when all $Y_i$ have variance $1$.

  Problem. We are given $n$ independent Gaussian r.v. $\gamma_1,\dots, \gamma_n$ with mean $\mu$ and variance $1$. Estimate the expectation of $\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}$.

Answer: $\Theta\left(\frac{1}{\sqrt{\log n}}\right)$.

Informal Proof.
Here is an informal solution to this problem (it's not hard to make it formal).
Since the answer does not depend on the mean, we assume that $\mu = 0$. Let $\bar\Phi(t) = \Pr[\gamma > t]$, where $\gamma\sim{\cal N}(0,1)$. We have (for moderately large $t$),
$$\bar\Phi(t)\approx \frac{1}{\sqrt{2\pi}t} e^{-\frac{1}{2}t^2}.$$

Note that

$\Phi(\gamma_i)$ are uniformly and independently distributed on $[0,1]$,
$\Phi(\gamma_{\mathrm{max}})$ is the smallest among $\Phi(\gamma_i)$,
$\Phi(\gamma_{\mathrm{sec-max})}$ is the second smallest among $\Phi(\gamma_i)$.

Thus $\Phi(\gamma_{\mathrm{max}})$ is close to $1/n$ and $\Phi(\gamma_{\mathrm{max}})$ is close to $2/n$ (there is no concentration but if we don't care about constants these estimates are good enough; in fact, they are even pretty good if we care about constants — but that needs a justification). Using the formula for $\bar\Phi(t)$, we get that
$$
2\approx \bar\Phi(\gamma_{\mathrm{sec-max}})\left/\bar\Phi(\gamma_{\mathrm{max}})\right. \approx e^{\frac{1}{2}\left(\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2\right)}.
$$

Thus $\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2$ is $\Theta(1)$ w.h.p. Note that $\gamma_{\mathrm{max}}\approx \gamma_{\mathrm{sec-max}} = \Theta(\sqrt{\log n})$. We have,
$$\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}\approx \frac{\Theta(1)}{\gamma_{\mathrm{max}} + \gamma_{\mathrm{sec-max}}} \approx \frac{\Theta(1)}{\sqrt{\log n}}.$$

QED

We get that
\begin{align}
\mathbb{E}[{X_{\mathrm{max}} - X_{\mathrm{sec-max}}}] &= \mathbb{E}[{Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}}] \\
&= \sqrt{\mathrm{Var}[Y_i]} \times\mathbb{E}[{\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}}] = \Theta\left(\sqrt{\frac{m}{n\log n}}\right).
\end{align}

  The same argument goes through when we have arbitrary scores. It shows that
  $$\mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{sec-max}}] = c\, \left. \mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{min}}]\right/\log n.$$


Google quantum supremacy experiment data

Yes, it seems to be available on this link.


No. Fix a $k$, and let $x_1, x_2, ..., x_k$ be the variables in your Horn formula. Then for all $i$ the clause $(x_i)$ is a Horn clause – there is at most one positive literal. Using such clauses, you can construct $2^k - 1$ different Horn formulas: $(x_1)$; $(x_2)$; $(x_1) \wedge (x_2)$; $(x_3)$; etc. Each of these is trivially satisfiable – just set $x_i = 1$ for all $i$. The length of each formula is $O(k \log k)$, assuming any reasonable encoding.

(You can add extra requirements like "all clauses must contain at least one negative literal", "all variables must occur in at least one clause", etc., but this doesn't really change anything; just tweak the above construction slightly.)


Has anyone mixed linear algebra with formal language theory in this way?

The approach you're describing is the generating function approach. By solving systems of polynomial equations, one can calculate the number of words of given length (generated by any non-terminal), and through it the corresponding asymptotics.

For regular languages one can directly use linear algebra to estimate the number of words of given length. The result is described in the Wikipedia article as well as here; see also this question.


When n is given and the objective is to minimize d, it is the well-known n-center problem.


What's the difference between term rewriting and pattern matching?

One way of looking at these two concepts is to say that pattern matching is a feature of programming languages for combining discrimination on constructors and destructing terms (while at the same time selecting and locally naming term fragments) safely, compactly and efficiently. Research on pattern matching typically focusses on implementation efficiency, e.g. on how to minimise the number of comparisons the matching mechanism has to do.

In contrast, term rewriting is a general model of computation that investigates a wide range of (potentially non-deterministic) methods of replacing subterms of syntactic expressions (more precisely an element of a term-algebra over some set of variables) with other terms. Research on term rewriting systems is usually about abstract properties of rewriting systems such as confluence, determinism and termination, and more specifically about how such properties are or are not preserved by algebraic operations on rewrite systems, i.e. to what extent these properties are compositional.

Clearly there are conceptual overlaps between both, and the distinction is to a degree traditional, rather than technical. A technical difference is that term rewriting happens under arbitrary contexts (i.e. a rule $(l, r)$ induces rewrites $C[l\sigma] \rightarrow C[r\sigma]$ for arbitrary contexts $C[.]$ and substitutions $\sigma$), while pattern matching in modern languages like Haskell, OCaml or Scala provides only for rewriting 'at the top' of a term. This restriction is also, I think, imposed in Jay's pattern calculus.
Let me explain what I mean by this restriction. With pattern matching in the OCaml, Haskell, Scala sense, you cannot say something like

match M with
   | C[ x :: _ ]  -> printf "%i ...\n" x
   | C[ [] ] -> printf "[]"

What is C[.] here? It's supposed to be a
variable that ranges over one-holed contexts.  But languages like
OCaml, Haskell or Scala don't give programmers variables that
range over arbitrary (one-holed) contexts, only variables that range
over values.  In other words, in such languages you cannot pattern
match at an arbitrary position in a term. You always have to specify
the path from the root of the pattern to the parts that you are
interested in.  I guess the key reason for imposing this restriction
is that otherwise pattern matching would be non-deterministic, because
a term might match a pattern in more than one way. For example the
term (true, [9,7,4], "hello", 7) matches the
pattern C[7] in two ways, assuming C[.]
ranged over such contexts.


minimal finite automata given in-words and out-words

If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete

Gold1978 - Complexity of Automaton Identification from Given Data.

The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of states is an approximation of the number of states of a minimum consistent DFA.

Pitt-Warmuth-1993 - The minimum consistent DFA problem cannot be approximated within any polynomial.

There are many known heuristics and algorithms for tackling this problems. A well studied algorithm is due to Angluin.

Angluin-1987 - Learning regular sets from queries and counterexamples


Approximate bound/algorithm for "product of sums maximization" problem

Intuitively, you are looking for partitioning the given numbers into k sets that are all have the same sum. Indeed, otherwise, you can benefit by taking two of these sets, and make them as balanced as possible.

As such, you can take an approximation algorithm for subset sum, and turn it into an approximation algorithm to partition. Then extend it to handle $k$-sides partitions, and you would get the required approximation. See for example here: http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/08_approx_III.pdf

Then you need to modify it to care about your target function....

I assume that going through the details, you would get an $(1+\epsilon)$-approximation algorithm and its running time would be $(n/\epsilon)^{O(k)}$. But better running time might be possible if you are more careful.


FPT algorithm for Partial k-tree Isomorphism

As M. Kanté pointed out, it's open whether or not graph isomorphism is FPT when parameterized by tree-width. Furthermore, I don't believe there is any complexity-theoretic barrier to creating an FPT algorithm in this case.

For a survey of what's known about the fixed-parameter tractability of graph isomorphism, see the introduction of my paper with Anuj Dawar and Eryk Kopczyński here. In the paper we show graph isomorphism is FPT in the tree-depth of a graph, which is a necessary (but not sufficient) condition for graph isomorphism to be FPT in tree-width.


Higher order Quines - when do super Quines exist?

There's a good chance this question is independent of ZFC for most programming languages.  In particular, I'd expect it to be true of any language where the shortest Quine is longer than the Kolmogorov complexity decidability bound, the integer $n$ such that no string can be proven to have Kolmogorov complexity $> n$.  I don't know to prove this, since even if you could express a Quine by a shorter program it wouldn't be a Quine, but I would expect a similar result to apply.

However, if the above argument were true, the argument itself might also be unprovable in ZFC, since it would require showing that no Quines exist below the complexity bound.


Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

I don't know of any function with communication much higher than the $\gamma_2$ bound. However, my intuition of why it is not tight is because the $\gamma_2$-norm is also a lower bound for QCMA communication. See this paper by Klauck for the definition of QCMA communication.

To prove the lower bound on QCMA communication using the $\gamma_2$-norm you can use the same reduction to an XOR game as in the  proof of Theorem 14 of this paper. This will also hold for certain types of entanglement.


Is there an oracle separating Parity-P from PSPACE?

From the comment above: you can use the same oracle $A$ used in:

Richard Beigel, Harry Buhrman, and Lance Fortnow. 1998. NP might not be as easy as detecting unique solutions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98).

for which $P^A= \oplus P^A  \neq NP^A = EXP^A$  ($EXP^A=NP^A\subseteq PSPACE^A$ also holds)


Polynomial time solvable instances of Max-Sat

This does not answer directly your Max-SAT problem but the references may guide you to the complete answer.

Szeider showed that Satisfiability is ﬁxed-parameter tractable when parameterized by the treewidth of the incidence graph. Samer and Szeider gave an eﬃcient dynamic programming algorithm.

References

S. Szeider. On ﬁxed-parameter tractable parameterizations of SAT. In Proc. 6th
International Conference on Theory and Applications of Satisﬁability (SAT’03),
Selected and Revised Papers, vol. 2919 of LNCS, pages 188–202. Springer-Verlag,
2004.

M. Samer and S. Szeider. Algorithms for propositional model counting. In Proc.
14th Internationial Conference on Logic for Programming, Artiﬁcial Intelligence
and Reasoning (LPAR’07), vol. 4790 of LNCS, pages 484–498. Springer-Verlag,
2007.

Samer and Szeider, Fixed-parameter tractability. In A. Biere, M. Heule,
H. van Maaren, and T. Walsh, editors, Handbook of Satisﬁability, part 1,
chapter 13. IOS Press


Scott Aaronson addresses this particular question on his blog Shtetl-Optimized when considering the timeline of Computer Science. The relevant posts in chronological order:

Timeline of Computer Science

Top 150 computer science events to be decided once and for all

CS timeline voting: the results are in!

Most of the events in his list would make good exhibits, although it might be difficult to figure out how to present some of them physically.


This is not an answer. It is a simple but long observation. I hope it will be useful.

The decision version of your problem is: Does $\cal X$ contain a subset of $A$?

This problem is related to the problem of evaluating monotone boolean functions of $n$ variables. A subset of $\{1,\ldots,n\}$ is equivalent to an $n$-bitstring, so the family $\cal X$ is equivalent to a boolean function $f$ of $n$ variables. Given a function $f$, one can define the least monotone function that is not bigger than $f$, namely $g(y)=(\exists x\subseteq y,\,f(x))$. The original problem is then reduced to evaluating $g(A)$. Conversely, the problem of evaluating a monotone boolean function can be reduced to the original problem, either naively by taking $f=g$ or by choosing an $f$ that makes $\cal X$ smaller.

In practice BDDs tend to work well. So one possible approach is to build the BDD for $f$, derive from it the BDD for $g$, and then evaluate $g$. The average size of the BDD for $g$ must be $\Omega\left(\binom{n}{n/2}\right)$, because there are many monotone boolean functions. Hence, in theory this is a bad solution.

But (1) a better analysis might be possible and (2) there might be tweaks to this approach that make it better. For example, I didn't use in any way the correlation between the size of $\cal X$ and the size of $g$'s BDD. (There must be a correlation, but I don't know if it is simple or usable here.)

For completeness, a simple algorithm for computing the BDD for $g$ from the BDD for $f$ is the following.
$$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$$
Here $\lor$ is the standard or-operation on BDDs.


Neural Networks: Incorporate feature-specific knowledge

This 2013 paper integrates deep learning models with structured hierarchical Bayesian models, for the net to learn novel concepts from very few training examples. It shows encouraging results.

Another approach is to import a general-purpose top-performing neural net, and replace the top fully connected layers with initialised ones (including an output layer that corresponds to the number of classes in your specific task). OverFeat is an example, for image classification - it was trained on ImageNet.


Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

In your initial use of it, there was no need for "As far as we know" - We do know that

promiseBPP ⊆ promiseS2P  ⊆  promise - (Σ2 ∩ Π2)

holds.

If  ZPP = NP  then

NP ∪ coNP  =  ZPP ∪ coZPP  =  ZPP ∪ ZPP  =  ZPP  ⊆  BPP  ⊆  S2P  ⊆  Σ2 ∩ Π2

, so as far as we know

NP ∪ coNP  ⊆  BPP  ⊆  Σ2 ∩ Π2

could hold.

If  NP = coNP  then    BPP \ (NP ∪ coNP)  =  BPP \ S2P  ⊆  BPP \ BPP  =  { }  ,

in which case there are no problems "outside class  NP ∪ coNP  but inside BPP".

In particular, no problems are "currently known to be outside class  NP ∪ coNP  but inside BPP".

I'm also not aware of any languages L known to be in BPP for which

it's also known that if L is in  NP ∪ coNP  then    BPP  ⊆  NP ∪ coNP  .

"Is exactly 1 of these 2 polynomials identically zero?"  is "a problem currently known to be"

inside BPP but not known to be in  NP ∪ coNP .    More generally, non-monotone

combinations of [problems in RP that aren't known to be in coNP] yield such problems.

There is an oracle relative to which BPP is not a subset of PNP,

so presumably  BPP ⊆ PNP  is not known to hold.

If that containment is indeed not known to hold, then there pretty much can't be any known

result to the effect that "All problems in BPP are reducible to amalgamations of NP problems.".


Edit: Please see the comments for why this does not address the question, however, I think I should not delete it in order to preserve the discussion...

--

Not an expert, but my impression is that reversible computation does not by itself result in a change in entropy: the amount of information in the system has not changed, only the format in which it is stored. In other words such processes obey the second law with only a weak inequality, not a strict one. To get a strict increase in entropy, one has to erase or destroy information, i.e. irreversible computation. I don't see why the rest of the details in your question -- two dimensions, cellular automata, chaos, recurrence -- would affect this.

Happy to be corrected by any experts, however.


I find the answer to my own question in [2]:

Let $G = \langle N, \Sigma, P \rangle$ be a context-free grammar. We can make $G$ into a many-sorted algebra by taking $N$ as the set of sorts and

$$
G_{w, n} = \{\, p \in P \,\mid\, p = (n, w') \land \operatorname{nt}(w') = w \,\}
$$
as an $N^* \times N$-sorted family ($\operatorname{nt}(\alpha)$ returns the ordered sequence of non-terminal symbols in $\alpha \in (N \cup \Sigma)^*$).

The initial $G$-algebra contains the parse trees for all the derivations in the grammar.

Conversely, if $\Sigma$ is an $S$-sorted operator domain, the initial algebra obtained under the previous construction with the grammar

$$
\hat{\Sigma} = \langle S, \Sigma \cup \{(,)\}, P \rangle\quad P=\{\, (s, \sigma(s_1\cdots s_n)) \,\mid\, \sigma \in\Sigma_{s_1\cdots s_n,s} \,\}
$$

is isomorphic to the initial $\Sigma$-algebra.

[2] Goguen, Joseph A., et al. "Initial algebra semantics and continuous algebras." Journal of the ACM (JACM) 24.1 (1977): 68-95.


A line graph has O(V) edges and diameter V-1. A star graph also has O(V) edges and diameter 2. So it seems that the constraint that a graph has O(V) edges places almost no restriction at all on what the diameter can be.

Of course, 2 is the minimum, since only a complete graph has diameter 1.


Lower bounds for monotone arithmetic circuits come easier because they forbid cancellations. On the other hand, we can prove exponential lower bounds for circuits computing boolean functions even if any monotone real-valued functions $g:R\times R\to R$ are allowed as gates (see e.g. Sect. 9.6 in the book).

Even though monotone arithmetic circuits are weaker than monotone boolean circuits (in the latter we have cancellations $a\land a=a$ and $a\lor (a\land b)=a$), these circuits are interesting because of their relation to dynamic programming (DP) algorithms. Most of such algorithms can be simulated by circuits over semirings $(+,\min)$ or $(+,\max)$. Gates then correspond to subproblems used by the algorithm. What Jerrum and Snir (in the paper by V Vinay) actually prove is that any DP algorithm for the Min Weight Perfect Matching (as well as for the TSP problem) must produce exponentially many subproblems. But the Perfect Mathching problem is not of "DP flawor" (it does not satisfy Bellman's Principle of Optimality). Linear programming (not DP) is much more suited for this problem.

So what about optimization problems that can be solved by reasonably small DP algorithms - can we prove lower bounds also for them? Very interesting in this respect is an old result of Kerr (Theorem 6.1 in his phd). It implies that the classical Floyd-Warshall DP algorithm for the All-Pairs Shortest Paths problem (APSP) is optimal: $\Omega(n^3)$ subproblems are necessary. Even more interesting is that Kerr's argument is very simple (much simpler than that Jerrum and Snir used): it just uses the distributivity axiom
$a+\min(b,c)=\min(a,b)+\min(a,c)$, and the possibility to "kill" min-gates by setting one of its arguments to $0$.This way he proves that $n^3$ plus-gates are necessary to multiply two $n\times n$ matrices over the semiring $(+,\min)$. In Sect. 5.9 of the book by Aho, Hopcroft and Ullman it is shown that this problem is equivalent to APSP problem.

A next question could be: what about the Single-Source Shortest Paths (SSSP) problem? Bellman-Ford DP algorithm for this (seemingly "simpler") problem also uses $O(n^3)$ gates. Is this optimal? So far, no separation between these two versions of the shortest path problem are known; see an interesting paper of Virginia and Ryan Williams along these lines. So, an $\Omega(n^3)$ lower bound in $(+,\min)$-circuits for SSSP would be a great result. Next question could be: what about lower bounds for Knapsack?  In this draft lower bounds for Knapsack are proved in weaker model of $(+,\max)$ circuits where the usage of $+$-gates is restricted; in Appendix Kerr's proof is reproduced.


${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

${\bf E} \not = {\bf NP}$ does not imply ${\bf E} \subset {\bf NP}$ nor ${\bf NP} \subset {\bf E}$. Similarly, ${\bf E} \not = {\bf PSPACE}$ does not imply ${\bf E} \subset {\bf PSPACE}$ nor ${\bf PSPACE} \subset {\bf E}$. You would need to show one of these containment's to be able to get a proper separation result out of those inequalities.


Completeness under injective Karp reductions

Here is an answer to a special case, when we restrict ourselves to the case when the Karp reduction can also be made length-increasing, along with making it injective.  (Length-increasing means that $|f(x)|>|x|$, where $f$ is the function that represents the reduction.)

Claim: If every Karp reduction in $NP$ can be transformed into one that is injective and  length-increasing, then $P\neq NP$ holds.

Proof.
Let us assume that every  Karp reduction in $NP$ can be transformed into one that is injective and length-increasing. Then there are two possibilities:

All these reductions are not just computable in polynomial time, but the inverse of each function, which exists after making the function injective, is also computable in polynomial time. It is known that if two languages are both reducible to each other  by reductions that are polytime computable, polytime invertible and length-increasing, then they are polytime isomorphic (see Theorem 7.4 in the book "Theory of Computational Complexity" by Ding-Zhu Du and Ker-I Ko). This would mean that all $NP$ complete languages are $p$-isomorphic, that is, the Isomorphism Conjecture holds, which is known to imply $P\neq NP$.
There is at least one among these functions, for which the inverse is not computable in polynomial time. This function would provide an example of a worst-case one-way function. It is known, however, that the existence of worst-case one-way functions also implies $P\neq NP$. (See Theorem 2.5 in the book "The Complexity Theory Companion" by Hemaspaandra and Ogihara.)

Therefore, the assumption that every  Karp reduction can be made injective and lenght-increasing implies $P\neq NP$, so it is likely very hard to prove. On the other hand, it might be easier to disprove because that does not seem to have such a dramatic consequence. It is also unclear, what happens if we drop the length-increasing assumption.


Your objective is to minimize the convex function $-\sum_{i=1}^n(x_i−a_i)y_i$ subject to a system of linear constraints on the continuous variables $x_i$ and $y_i$.

Such convex minimization problems are polynomially solvable by so-called interior point methods; see for instance the book by Stephen Boyd and Lieven Vandenberghe: "Convex Optimization"; free pdf copy at: http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf


Of course, plenty of introductory resources are available and it is impossible to be objective here. So what follows is merely my biased choice.

I would definitely start with reading something on algorithms and on discrete mathematics (possibly in parallel). Here, I would recommend the following books:

Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein
The Design and Analysis of Computer Algorithms, by Aho, Hopcroft and Ullman
Invitation to Discrete Mathematics, by Matoušek and Nešetřil

The first book mentioned is one of the most widely known resources on algorithms, suitable as an introductory resource. The second book is little bit older and more theoretical, however imho still valuable. The third book is (in my opinion) an excellent and readable introduction to various parts of discrete mathematics.

Later, I would recommend to focus on formal languages and automata theory. Here, my choice is the following book:

Introduction to Automata Theory, Languages, and Computation, by Hopcroft Ullman and Motwani

You might also like to consult the Sipser's book mentioned in one of the comments.

Of course, if you have some background, there may not be a need for you to thoroughly study these textbooks. However, it is imho necessary to have a stable grounding in the above mentioned subjects before proceeding any further. Thus, it may be sensible for you to consult the above mentioned resources and focus on the material that you find new and/or interesting.

After mastering these preliminaries, there are plenty of choices where to continue. In my opinion, you should definitely study some complexity theory. Here, I would recommend the following book:

Computational Complexity, by Papadimitriou

You also might be interested in some slightly more advanced (or, let us say, intermediate) mathematical methods used in the analysis of algorithms. Here, the following resource is considered to be classic:

Concrete Mathematics, by Graham, Knuth and Patashnik

Some basics of optimization (especially linear programming) are a must for computer scientists. Here, I would recommend the following gentle introduction:

Understanding and Using Linear Programming, by Matoušek and Gärtner

A well written (and not very demanding) introduction to randomized algorithms is the following:

Design and Analysis of Randomized Algorithms, by Hromkovič

Finally, some nice books on advanced algorithms and/or computation theory include:

The Design and Analysis of Algorithms, by Kozen
Theory of Computation, by Kozen
Algorithmics for Hard Problems, by Hromkovič
Complexity and Approximation, by Ausiello et al.
Randomized Algorithms, by Motwani and Raghavan

However, I would suggest reading these only after thoroughly mastering those mentioned above.

This is not a complete list, however. Many other excellent resources are available. The selection I have made is based on my personal bias. Moreover, I have included only resources focused on the "algorithmic part" of theoretical computer science. That is, the selection I have made is not only incomplete, but also very narrow.

And I have to mention that learning some more advanced math would be very helpful for you. My general advice is: the more mathematics you know, the better. It is more and more obvious that there is not any mathematics absolutely irrelevant to computer science.


Relaxing $\ell_0$ constraints in an optimization

I am not sure if I understand the problem correctly, but as is written, the problem seems to admit several simplifications, and in particular the problem in the ℓ22 case is equivalent to the minimum-weight vertex cover if I am not mistaken.

Without loss of generality we can assume that |S|=2 in every constraint, because a constraint with |S|>2 is equivalent to the set of constraints where S runs over all pair of elements in the original set S.  Therefore, the ℓ0 constraints can be visualized as a graph G with d vertices.  Using the graph G, the constraints can be restated as follows: the set of the vertices corresponding to the coordinates i with qi=0 must be a vertex cover of G.
Assume that the distance is defined by ℓ22 or some norm.  In this case, any point q can be transformed to a point q′ that satisfies for every i, q′i∈{0,pi}, simply by setting $$ q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases} $$ and this transformation never increases the distance from the point p.  In particular, if the distance is the sum of coordinate-wise distance (as in the case of the ℓ22 distance), the problem is exactly the same as the minimum-weight vertex cover.

As for an LP relaxation of the vertex cover problem, a quick search leads to e.g. the lecture notes (Lecture 9) by Uriel Feige.


a leading one is Codebreaker with a list of reviews/publicity here [unfortunately several are behind paywalls]. here is one web review by chris harvey & with quotes by the writer warner.

this documentary originated by channel 4 seems balanced and avoids hagiography, looking at all the aspects of his complex life. has award winning writer, actors and acclaimed producer.


In short: yes.

More particularly: Chomsky was one of the first to formalize a hierarchy relating languages, grammars, and automata. This insight is still very relevant and is taught in all intro courses on automata theory. However, the specific hierarchy Chomsky came up with and the names for the elements of the hierarchy aren't really significant anymore. We've since invented numerous formalisms which fall between levels of Chomsky's hierarchy, above it, or below it. And the names Chomsky used aren't particularly interesting, i.e. they aren't based on an interesting measure of complexity or anything, they're just numbers. Should mildly context sensitive languages be Type-1.5 or Type-1.7 or Type-1.3? Who cares. "Mildly context sensitive" is a much more informative name.

The Complexity Zoo is a bit different because it's full of all sorts of conditional equivalences and the like. A more modern hierarchy for automata theory wouldn't be linear (e.g., compare CFG vs PEG) but it would still have a well-known topology. To get a perspective on modern automata theory you should look at work on parser combinator libraries and some of the stuff on unification and type theory (though those both branch out far afield).


If an abstract machine can simulate itself, does that make it Turing complete?

No, it's not. I know two major classes of techniques for avoiding inconsistency/Turing completeness.

The first line of attack is to set up the system so that syntax can be arithmetized, but Godel's fixed point theorem doesn't go through. Dan Willard has worked extensively on this and given consistent self-verifying logical systems. The trick is to eliminate the multiplication and addition function symbols, and replace them with divisibility and subtraction. This gives you enough horsepower to represent syntax arithmetically, but the fixed point theorem doesn't go through since multiplication is not provably total.

See Dan Willard. Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles. Journal of Symbolic Logic 66 (2001) pp. 536-596.
The second line of attack allows more use of fixed points, but to set things up so that syntax doesn't arithmetize. The prettiest systems for this are (IMO) based on variants of linear logic. For example, in Kazushige Terui's Light Affine Set Theory, even the full unrestricted set comprehension principle is sound, but since the ambient logic of the set theory is linear (and hence contraction is not allowed), Russell's paradox is not derivable.

The intuitive reason that arithmetization fails is that the light linear function space $A \multimap B$ is set up so that all its inhabitants are polynomial time. As a result, the light linear version of the Peano axioms can't prove exponentiation total (since exponentiation of unary numbers takes exponential time), and so there is no longer an isomorphism between the natural numbers and bit strings.

Kazushige Terui. Light affine set theory: A naive set theory of polynomial time. Studia Logica, Vol. 77, No. 1, pp. 9-40, 2004.

I think this paper is more accessible after reading the following paper of Yves Lafont:

Y. Lafont, Soft Linear Logic and Polynomial Time, Theoretical Computer Science 318 (special issue on Implicit Computational Complexity) p. 163-180, Elsevier (2004)

Terui's set theory is very expressive, but it's hard to compare with traditional set theories, since proof-theoretic ordinals are not a good tool for comparing very weak systems. For example, Terui's set theory obviously cannot prove exponentiation total, and hence its proof-theoretic strength cannot even reach up to $\omega$. Complexity classes are probably better -- it is complete for polytime (it can prove every polytime function total, but no more).

I tend to think of these kinds of systems as proofs-of-concept for the idea that complexity theory can serve as a foundation for certain kinds of ultrafinitism.


It's not quite the same, but you may be interested in the 0-1 law for first order properties of graphs. A first order property is something you can describe by a logical formula with existential and universal quantifiers, in which the variables refer to vertices of a graph and there are two two-argument predicates: equality, and another predicate $\sim$ that tests whether two vertices are adjacent. For example, whether there is a universal vertex adjacent to all other vertices can be tested by the first-order formula $\exists v\forall w\,v\ne w\rightarrow v\sim w$.

Then, for every first-order property, the fraction of all $n$-vertex graphs that satisfy the property, as $n\to\infty$, approaches either 0 or 1. More strongly, there exists an infinite graph, the Rado graph, such that this fraction approaches 0 or 1 exactly when the Rado graph does not or does have the same property, respectively. But when the fraction approaches 1, it still might not be the case that the property holds for all graphs, so this differs somewhat from what you're asking.


A paper by Mark Bun and Justin Thaler has been posted on ECCC very recently (mid-March 2017) that precisely answers this question: "A Nearly Optimal Lower Bound on the Approximate Degree of AC0"

They claim that for any $\delta > 0$, there exists a function $f$ in $\mathrm{AC}^0$ such that $\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$, nearly closing the gap with the trivial $O(n)$ upper bound. They achieve this with a general method to boost the approximate degree of a function with sublinear approximate degree, keeping the number of variables quasi-linear. From the abstract :

  Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a
  function $F$ on $O(n \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} · d^{2/3} )$. In
  particular, if $d = n^{1−Ω(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a
  polynomial-size Boolean circuit of constant depth, then so is $F$.

That is the most recent update on the lower bound end of this problem, and it is quite a significant step forward. The Introduction and Application sections of the paper are also good sources of references for prior works and related problems.

Disclaimer: I haven't read the paper carefully yet.


One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).

There are also related works in the context of Fixed Parameter Tractability such as
Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013).
These hardness results are proven under various assumptions such as ETH or existence of very strong PCPs.


Probability for an element to appear in at least one set

For very crude bounds, you could use Chebyshev's inequality.

Let $x$ denote one (fixed) value from the set of $M$ possibilities.  The probability that $x$ appears at least once in the union of the sets is something like

$$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$

Now if we let the random variable $X$ denote the number of elements that appear at least once in the union of the sets, we can use linearity of expectation to get that $\mathbb{E}[X] = Mp$.  You should be able to compute $\text{Var}[X]$ using similar methods.  Then, you should be able to use Chebyshev's inequality to bound the probability that $X$ is far away from its expected value.

This will give a pretty weak bound, so it's unlikely that this is the best approach.  Hopefully others will suggest better methods.


Polygon within polygon generalization problem

I don't know how your polygons look, but perhaps a simplified version of the Ramer–Douglas–Peucker algorithm is enough:

for each convex part, calculate the area $A_j$ of of the triangles $P_i P_{i+1} P_{i+2}$ formed by three consecutive points;
for each concave part, calculate the area $B_k$ of of the two triangles $P_i P'_i P_{i+1}$ and $P_{i+1} P'_{i+2} P_{i+2}$ formed by the extension of the two points $P_i, P_{i+2}$ and the middle point $P_{i+1}$
calculate the $min\{A_j,B_k\}$ and delete the corresponding point (and shift points if the operation is done on the concave part);
loop until $n-m$ points have been deleted.

The border of the polygon ($A_j$ green triangles, $B_k$ red triangles). On the right, the border after the elimination of two points.

For more complex algorithms you can search for "polygon generalization techniques" though your first condition (points in A are contained in B) implies some additional scaling operations.


Decidability/algorithm for checking universality of a quantum gate set

For the case of Hamiltonians, rather than gates the answer is trivially yes: you simply enumerate the independent elements of the Lie algebra. Since the Lie algebra is a vector space with the addition of the Lie bracket operator. Since the space is finite, it has a finite basis, and which can easily be checked as to whether it is closed or open under the Lie bracket operation. Simply checking the Lie bracket of all pairs of orthogonal operators can be done in time polynomial in the dimensionality of the space, and a suitable operator basis can be found by the Gram-Schmidt method.

For gates, you don't really have the same option to resort to infinitesimals straight off, and need to construct gates with irrational eigenvalues so that you can arbitrarily well approximate the required infinitesimal generators. I guess that there is a relatively simple way to do this, but it is not immediately obvious to me.

In any case, taking the log of the gates to obtain a set of operators which generate them when exponentiated and checking whether these generated the full Lie algebra would provide a simple necessary but not sufficient criteria for universality.


Can reversible computations alone be used to create a computer?

You need workspace (registers set to 0) to read the user's input. Once you've read it, and completed the program, the user needs to erase the input and the output in order to restore the workspace. However, if you assume that the user wants to keep a copy of the input and the output, this is possible to do reversibly.

Similarly for the program, to erase the program from the computer there needs to be another copy stored somewhere.

If you don't allow any reversible operations between the user and the computer, and you insist that everything be done reversibly, then you can't load input into the computer, and you have a useless machine.


What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?

This problem is NP-hard, as can be shown by a straightforward reduction from SAT.

It sounds like you are interested in the case of $m$ quadratic equations on $n$ variables (over $\mathbb{R}$).  In practice, the hardness of this problem depends on the relationship between $m$ and $n$:

If $m = \Theta(n)$, this problem is believed to be very hard (say, exponential in $n$).
If $m \ge n^2/2$ (roughly), this problem is easy and can be solved through linearization: replace each quadratic monomial $x_i x_j$ with a new variable $t_{i,j}$, then use Gaussian elimination.
If $m = \Theta(n^2)$, this problem can be solved in polynomial time through relinearization.  Roughly speaking, you linearize as above; then, for each $i,j,k,l$, you add constraints $t_{i,j} t_{k,l} = t_{i,k} t_{j,l} = t_{i,l} t_{j,k}$, which are themselves quadratic equations.  This gives you a new system of quadratic equations in the variables $x_i$, $t_{i,j}$.  Now you can apply linearization (or recursively apply relinearization) to this system of quadratic equations.  For details, see my explanation elsewhere and the reference into the literature there: https://crypto.stackexchange.com/a/3736/351
If $m = \omega(n)$ and $m = o(n^2)$, I don't know what the complexity is.

There are also Grobner basis algorithms, the XL and XSL algorithms, and probably others as well.  I don't know if there are any provable, useful running time bounds for any of them for any useful parameter ranges.

Incidentally, you probably don't want to work over the real numbers (where even testing equality is hard), but over the rationals or the integers or some finite field.


Why is the state of a FSM traditionally denoted $q$?

In his 1936 paper "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM", Alan Turing wrote :

  "We may compare a man in the process of computing a real number to
  machine which is only capable of a finite number of conditions q1, q2,
  .... qR which will be called " m-configurations"

So he stressed the fact that the machine has a finite, discrete (not continuous) number of states or quantities. For me, it is a reference to the term Quanta used in physics to denote phenomena variating not continuously but by "leaps" or "quanta". In his 1950 article "Computing Machinery and Intelligence" Alan Turing is more explicit about "leaps" speaking of "sudden jumps":

  "The digital computers considered in the last section may be
  classified amongst the "discrete-state machines." These are the
  machines which move by sudden jumps or clicks from one quite definite
  state to another."

So I think that Alan Turing used q instead of s to denote a machine state to stress the fact that the state machine can be only in a set of discrete and finite values like the quanta in physics. And since then, the same notation is generally used.


"Interesting" categories whose internal logic is a dependent-linear type theory

Take any small symmetric monoidal category $V$.
Then the category of $V$-valued presheaves will (a) have closed monoidal structure (via Day convolution), and (b) have enough stuff (inherited from $\mathrm{Set}$) to interpret dependent types.  This gives you enough structure to interpret something like our LNL calculus pretty easily, because there is a nice adjunction between $\mathrm{Set}$ and this category given by the constant functor ($F(X) = V \mapsto X$) and the global elements functor ($G(A) = \Pi X : Obj(V). A_X$).
Matthijs Vakar wrote a nice paper, A Categorical Semantics for Linear Logical Frameworks, which describes the categorical models of this style of calculus in detail.


What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Virginia Vassilevska Williams lectured at a bootcamp (link to outline) at the Simons Institute, and presents what may be your memory in the introductory video. The whole workshop is worthwhile; the outline and links to videos of all talks can be found here.

She explains (starting at 42:30 in the video) that if there is a $O\left(n^{2-\varepsilon}\right)$ algorithm for some $\varepsilon>0$ for the Orthogonal Vectors problem, then the Strong Exponential Time Hypothesis (SETH) is false. This would not immediately imply $P=NP$, but it would show an $O\left(2^{n-\epsilon}\right)$ algorithm for every $k$-SAT, which would be better than what we have right now; right now we have algorithms which solve $k$-SAT in $2^{n-O\left(\frac{1}{k}\right)}$, so these algorithms tend to $2^{n}$ for large $k$.

The proof is originally by Ryan Williams, and is quite elegant; I do recommend the lecture.


Algorithm to compute distance between powers

First I thought it would be best to use the continued fraction of $\log(a)/\log(b)$ and test at its convergents, because at that convergents there are points $(x,y)$ of in some sense optimal approximation. After that it becomes clear, that one needs to use at least the generalized continued fractions to make sure to have monotonic decreasing distances.
After that and the complicated algorithm with this the following brute-force algo was even faster in Pari/GP

\\ print X,Y,d conditional X>lowboundX, Y > lowboundY, d<upperboundD
{pri1(lbX,lbY,ubd,a,b,X,Y,d)=if(X<lbX || Y<lbY || abs(d)>ubd,return(0));
                  print(a,"^",X,"-",b,"^",Y,"=",d)); }

{mylist(maxa=19,maxb=99,lbX=3,lbY=2,ubd=100)=print(" ");
for(a=2,maxa,for(b=a+1,maxb,
     if(gcd(a,b)>1,next()); \\ ignore trivial multiples
     X=1;Y=1;Xa=a;Yb=b;
     d=Xa-Yb;  pri1(lbX,lbY,ubd,a,b,X,Y,d);
     for(k=1,20,
        while(d<0,Xa*=a;d=Xa-Yb;X++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        while(d>0,Nb*=b;d=Xa-Yb;Y++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        if(X>30 || Y>20, break());  \\ stop at max X=30 or Y=20
       );
   )); }

after that call mylist(100,1000,3,3,100) to find all small difference with $|d| \lt 100$ where both exponents are at least $3$ for all bases $a=2..100$ and $b=(a+1) .. 1000$ . Check only up to $\max (X)=30$ and $\max(y)=20$.

This was much faster than the continued-fraction approach (which also had more unkind issues (for instance with completeness of the solutions) which are difficult to handle) although it is a somehow naive algo ...

A protocol (manually ordered) :

gettime();mylist(200,10 000,3,3,100);gettime() /1000.0 \\ ~ a*b/6000 sec
  (400 sec)

 2^8- 3^5= 13

 6^7-23^4= 95
 2^7- 3^4= 47

 2^7- 5^3=  3
 2^5- 3^3=  5
 3^4- 4^3= 17

---------------
 2^6- 3^4=-17

 3^5- 4^4=-13
 2^5- 3^4=-49

 2^8- 7^3=-87
(4^4- 7^3=-87)

 3^7-13^3=-10
 2^6- 5^3=-61
(4^3- 5^3=-61)
 2^5- 5^3=-93

 2^4- 3^3=-11
 3^4- 5^3=-44
 6^4-11^3=-35
15^4-37^3=-28

 3^3- 4^3=-37
 3^3- 5^3=-98
 5^3- 6^3=-91


What is the best exact algorithm to compute the core of a graph?

Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see Hell and Nesetril.  There are settings where core computation can be done efficiently, see Efficient Core Computation in Data Exchange by Georg Gottlob and Alan Nash for a database setting; here some reasonable restrictions on the kinds of constraints in the database schema allow cores to be computed efficiently.

Edit: Other than the Gottlob/Nash work mentioned above, I am not aware of any other attempts to provide efficient algorithms for core computation.  Pointers to any algorithms better than brute force (exact or otherwise) would be welcome.


As far as I am aware, a comparison of approximation algorithms has not been done so far with respect to smoothed analysis. There are only a few papers on smoothed analysis of approximation ratios in the first place.

Maybe only loosely related: bijective analysis has been used to directly compare the competitive ratio of online algorithms (Angelopoulos, Schweitzer, "Paging and List Update under Bijective Analysis", J. ACM, 2013).

See also here for more about smoothed analysis of approximation algorithms: "Smoothed analysis of approximation algorithms".


Parallel algorithms for directed st-connectivity

Directed s-t reachability can easily be done using O($n^3$) processors and O$(\log n$) time on a CRCW-PRAM, or in O($n^\omega$) processors and  O($\log^2 n$) time on a EREW-PRAM
 where $\omega<2.376$ is the matrix multiplication exponent and $n$ is the number of vertices. The following paper claims O($n^\omega$) and  O($\log n$) time on a CREW-PRAM: "Optimal Parallel Algorithms
for Transitive Closure and Point Location
in Planar Structures" by Tamassia and Vitter. Other papers claim the same thing and cite the Karp and Ramachandran survey (Parallel algorithms for shared-memory machines, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science). The survey itself does mention that transitive closure is in AC1 and hence can be solved in O(log n) time on a CRCW-PRAM, but the part about CREW-PRAM is missing.

All Strassen-like algorithms for matrix multiplication (including the one by Coppersmith-Winograd) are essentially parallel algorithms that run in O$(\log n)$ time; transitive closure incurs an extra log (but if you allow unbounded fan-in the trivial O($n^3$) matrix mult can be done in constant depth and so reachability is in O$(\log n)$ time on a CRCW-PRAM). It's an open problem to improve the number of processors from the current best ~$n^{2.376}$; it is also a major open problem if reachability is in NC1, as it would imply L=NL among other things.


Is true randomness and the physical Church-Turing thesis incompatible?

The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random output (for a given input)? There is at most one (random) output occurring with probability $>\frac{1}{2}$, so taking that output if it exists (and undefined otherwise) as definite value could be a reasonable definition. (One might argue that $\frac{1}{2}$ is too small for physical implementation and one should take $\frac{2}{3}$ instead, but I guess that is not really important for this answer.) The Church-Turing thesis now asserts that even this extended notion of computability for (partial) functions $\mathbb{N} \to \mathbb{N}$ still leads to the same set of computable functions.

If we are willing to leave the strict setting of (partial) functions $\mathbb{N} \to \mathbb{N}$, then we risk those toasting toast discussions. (Based on the older mustard watches or montres à moutarde parody by Jean-Yves Girard.) I prefered Martin Berger's and Neel Krishnaswami's position in that discussion over Scott Aaronson's position, but most everybody else seems to agree with Scott. I guess even Andrej Bauer would be unable to change that outcome. Scott's position is not meant as a parody:

  To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question. What is it that lets all those high-level languages exist in the first place, that ensures they can always be compiled down to machine code? Could it be ... err ... THE CHURCH-TURING THESIS, the very same one you've been ragging on?

I previously wrote "So if a theoretical machine had access to a random source which its opponent could not predict (and could conceal its internal state from its opponent), then this theoretical machine would be more powerful than a Turing machine." But that argument takes place in a game theoretic setting (and idealization of some real world scenario) different from the context of the Church-Turing thesis. The simulation argument (explained by Martin Berger in the above discussion) could reduce that setting back to TMs by simulating all interactions between the random source enhanced Turing machines, but that misses my original point, about the random source being a separate idealization which can fail in its own ways. But if already clear concepts like higher-level formalisms gets dismissed, then there is little point in elaborating such fine interpretative points.

It might be possible to keep the "$\mathbb{N} \to \mathbb{N}$" part, and replace the "(partial) functions" part with something else (I am thinking here of an analogy Fermions <-> "(partial) functions", Bosons <-> "something else"), but the Church-Turing thesis would probably still hold in such modified settings.


I can interpret this question in two different ways:

1) When it comes to algorithmic properties of packing problems on graphs of bounded treewidth, Courcelle's Theorem shows that for every fixed $k$ we can optimally solve problems expressible in Monadic Second Order Logic in linear time on graphs of treewidth at most $k$ (see for example http://dx.doi.org/10.1093/comjnl/bxm037 for a survey on the algorithmic properties of bounded-treewidth graphs). As many packing problems can be formulated in MSOL, this proves tractability of many such problems on graphs of bounded treewidth, including Independent Set, Triangle Packing, Cycle Packing, packing vertex/edge disjoint copies of any fixed graph, packing vertex-disjoint minor models of some fixed graph H, and so on. But as this tractability extends to all MSOL-definable problems, it is not specific to packing.

2) When it comes to graph-structural relationships between packings and treewidth, the following might be of interest. Thanks to the work of Robertson and Seymour it is known that there is a function $f \colon \mathbb{N} \to \mathbb{N}$ such that every graph of treewidth at least $f(r)$ contains an $r \times r$ grid as a minor (the original bound for $f$ given by Seymour and Robertson was later improved in collaboration with Thomas; see http://www.sciencedirect.com/science/article/pii/S0095895684710732 for the current-best bound). Hence if you have a structure $S$ such that many copies of $S$ can be packed into an $r \times r$ grid minor, then you know that any graph of large treewidth contains a large packing of copies of $S$. For example, as an $r \times r$ grid (for even $r$) contains $(r/2)^2$ vertex-disjoint cycles, it follows that a graph of treewidth $f(r)$ contains at least $(r/2)^2$ disjoint cycles.


List of strongly NP-hard problems with numerical data

Here is a strongly $NP$-complete problem (with numerical data as you requested):

Schur Triples problem:

Input: list of 3N distinct positive integers

Question: Is there a partition of the list into N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?

The condition that all numbers must be distinct makes the problem very interesting and McDiarmid calls it a surprisingly troublesome .


Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

The conjecture does not hold:
Let $L$ be the set of prefixes of $(c^*ac^*b)^*$.
Then $L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$.
Take the word $\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$.
For all $k\in\mathbb N$, we can show that $PF_k(\eta)\not\subseteq L'$, as witnessed by $$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\omega.$$
Indeed we have $u_k\in PF_k(\eta)$ but $u_k\notin L'$.


Extensions of Ramsey's theorem: monochromatic but diverse

First I have to say: this problem is really interesting!! And here I briefly describe why my previous approaches failed, as suggested in this meta post about incorrect answers.

My first attempt was trying to construct a coloring related to the sumset of the k-subset which makes all n-subset non-monochromatic. Lemma 1 is still available; but Lemma 2 was wrong, by observing that if k and d are related prime, then an n-subset $\{1,3,1,3, \ldots\}$ in module d suggested by @Jukka is a counter-example.
The second try was a proof to the theorem; by counting the ratio of diverse and monochromatic $n$-subsets, we hope that the number of monochromatic ones will surpasses those of non-diverse ones. But the is an error in my calculations, observed by @domotorp: the ratio of being non-diverse will not approaches zero; it converges to about $n/d$, which is clearly larger than $R(n,n;k)^{-n}$.
The third one goes back to the first method, and it shows that for a uber-weak parameter set ($n > k+d-1$ and $d \mid k$), the theorem is false. We used a famous lemma in additive combinatorics: the EGZ-theorem.

The fourth try is due to the answer by @domotorp; it is both clever and inspiring, and I'll try to modify his proof to deal with all the parameters. But still his method is elegant, and I totally appreciate this simple approach.

A diverse n-set contains at least one k-subset with at least $k-1$ "switches between mod classes"; precisely, let $X = x_1,\ldots,x_n$ be a diverse n-set, and let $S^* = x_1,\ldots,x_k$, a switch is defined if $x_i$ and $x_{i+1}$ are in different mod-d classes. We have k-1 switches for $S^*$.

Let a k-subset $S$ be red if $S$ has at most k-2 switches; otherwise it is blue. By the previous paragraph we already had a blue one, now we prove that for $n > k+d+1$, there is an red $S$ in any n-set $X$. Since $n > d$, there are two numbers $x_i,x_j$ in the same mod-d class and $j-i \leq d-1$; and since $n > k+d+1$, there are at least k-2 elements $x_k$ in $X$ with $k<i$ or $k>j$. And we can construct a k-subset $S$ with $x_i$ next to $x_j$, which only switches at most k-2 times. Thus $S$ is a red k-subset.


Viola's Reduction of 3XOR to listing triangles

[Copying here the answer from here]

  In this paper, Corollary 1, we show that if you solve 3XOR in close to linear time then you can list $t$ triangles in a graph with $m$ edges in time $m\cdot t^{1/3},$ ignoring lower-order terms.


Magic constant to solve NP-complete problem in polynomial time

Probably not. What you are asking is whether NP $\subset$ P/poly. If this were true, then the polynomial hierarchy would collapse (this is the Karp–Lipton theorem), something that is widely believed not to happen.


The Wikipedia page on "Post-quantum cryptography" provides a list of proposals for PKE resistant to quantum attacks. Quantum algorithms can solve DL in finite abelian groups (as well as a few nonabelian and infinite abelian ones), so they get very close to the spirit of the question you are asking. The learning with errors problem mentioned by one of the commenters is on that list.

I do not know of a general answer to the question of "What is the power of DL in arbitrary (that is, nonabelian) groups?".


Simplification of Presburger formulas in practice

Not knowing anything about the input problem, I suspect that if the blow up is coming from quantifier elimination of Presburger formulas. Cooper's algorithm can introduce a lot of redundancies and duplication during case splitting.
My suggestion comes from a trivial observation: Any tool that can find "very simple" Presburger formula also has to be able to find "very simple" pure boolean formulas. (Just encode each propositional variable $x_i$ with some trivial Presburger atom $s_i < 2$.)

BDDs are a fairly natural candidate for trying to get simple formulas (or at least unique wrt a variable order).
The closest work I am aware of to extending BDDs over Presburger is the Linear Decision Diagram (LDD) work of Chaki et al: slides and the project's homepage. Links to the papers are on the project's site.  This work combines linear real/rational arithmetic with BDDs.  The goal of this work was to have a compact representation in order to do Fourier-Motzkin quantifier elimination. Already LDDs do not try to be canonical, just "canonical enough".  The main idea is to add local conditions to eliminate certain kinds of redundancy during construction. These local conditions are things like: put the constraints on $x$ next to each other in the variable order, if $x < 5$, then $x<7$ always holds on the high branch, etc.  They do mention support for UTVPI constraints over integers in the paper and slides (like what you have above). The tool's API does not seem to support divisibility constraints coming from quantifier elimination or other more elaborate kinds of integer specific reasoning (gcd computations, conversion of $x < 2$ to $x \leq 1$, etc.)

If the formulas have a lot of propositional redundancy introduced by quantifier elimination, this might be a reasonable thing to look into.  (I doubt this includes all of the reasoning you used to get down to the smaller formulas so it might not work out of the box.) I've used tricks like BDDs + unate implications (eg. $x < 2 \implies x < 3$) to reduce Presburger formulas that were blown up by a different algorithm to "very simple" equivalent ones. But I did this for debugging purposes only. It has never made sense to stick what I did into a real implementation so I do not have a tool I can point you to. Good luck.


Isomorphism between algebraic data-types

Spoiler: the types are isomorphic.

First let me clarify what might be meant by "isomorphic". Say that two datatypes $S$ and $T$ are isomorphic if there are maps $f : S \to T$ and $g : T \to S$ such that $f(g(v)) = v$ for every value $v : T$ and $g(f(u)) = u$ for every value $u : U$.

Let us fix a type $A$. We can then write your equations without the parameter $A$ as
$$T_1 = 1 + A + T_1 \times T_1$$
and
$$T_2 = 1 + A \times T_2 + T_2 \times T_2.$$
(We really want to consider the types polymorphic in $A$, and we shall do so, but for the moment I'd like to get rid of $A$ as a parameter, so let us consider it temporarily fixed.) If we define "polynomial" type constructors $P_1(X) = 1 + A + X \times X$ and $P_2(X) = 1 + A \times X + X \times X$ then the above definitions become fixed-point equations
$$T_1 = P_1(T_1)$$
and
$$T_2 = P_2(T_2).$$
We can consider either the inductive solution (the initial algebra for the polynomial functor) or the coinductive solution (the final coalgebra). The former is what you get in ML-style language and the latter in Haskell. Let's do inductive, as that is algebra, while coinductive gets us into topology (which is cooler but a bit trickier).

Now, we would like to know whether the initial algebras for $P_1$ and $P_2$ are isomorphic parametrically in $A$, by which we mean that we want isomorphisms that are parametrically polymorphic in $A$. Beware, non-isomorphic functors may produce isomorphic initial algebras: lists of $A$'s are the initial algebra for both $X \mapsto 1 + A \times X$ and $X \mapsto 1 + A \times X + A \times A \times X$! So for instance it is not sufficient to find $Y$ such that $P_1(Y) \not\cong P_2(Y)$. But since we want isomorphisms that work for all $A$'s it is sufficient to find a single instance of $A$'s for which $T_1 \not\cong T_2$ (although that might be a bit hard to find...)

I am going to take it for granted that there are no isomorphisms between $A^n$ and $A^m$ for $n \neq m$ that are parametric in $A$. (Consider $A = \mathtt{bool}$.)

We can think of $T_1$ as an "infinite" nesting $P_1(P_1(P_1(\cdots)))$, so it makes sense to look at a finite approximation. Let us compute $P_1^n(X)$ for some $n$. The result is a polynomial in $A$ and $X$, which we express as $Q_n(A) + X \times R_n(A,X)$. For $n = 1$ we get (using Mathematica and expanding as a power series in $X$):
$$(A+1)+O\left(X^2\right),$$
for $n = 2$ we get
$$\left(A^2+3 A+2\right)+O\left(X^2\right)$$
for $n = 6$ we get
$$\left(A^{32}+48 A^{31}+1112 A^{30}+16568 A^{29}+178484 A^{28}+1481816
   A^{27}+9867676 A^{26}+54160004 A^{25}+249844422 A^{24}+982869432
   A^{23}+3333905572 A^{22}+9834052604 A^{21}+25390949338 A^{20}+57672050948
   A^{19}+115666688826 A^{18}+205373975070 A^{17}+323359748527
   A^{16}+451792820168 A^{15}+560048078060 A^{14}+615271918604
   A^{13}+597813614038 A^{12}+512098495020 A^{11}+385051162322
   A^{10}+252634062394 A^9+143508813439 A^8+69855202828 A^7+28739884958
   A^6+9808926186 A^5+2705141303 A^4+579784870 A^3+90704955 A^2+9224803
   A+458330\right)+O\left(X^2\right)$$
So it seems that we get a whole lot of every power of $A$. A similar thing happens with $T_2$, for instance $P_2$ unfolded 6 times is
$$
\left(256 A^{16}+6656 A^{15}+80768 A^{14}+607488 A^{13}+3171408 A^{12}+12191008
   A^{11}+35710688 A^{10}+81347056 A^9+145690452 A^8+205905596 A^7+228957512
   A^6+198261418 A^5+131104690 A^4+64020678 A^3+21778198 A^2+4612401
   A+458330\right)+\left(3072 A^{17}+80128 A^{16}+975744 A^{15}+7366080
   A^{14}+38598592 A^{13}+148916448 A^{12}+437720280 A^{11}+1000231448
   A^{10}+1796273100 A^9+2544344160 A^8+2833851236 A^7+2456339273 A^6+1624706942
   A^5+792912172 A^4+269323336 A^3+56895232 A^2+5632640 A\right)
   X+O\left(X^2\right)$$
In the "infinity" these coefficients on $A$'s will be infinite. We will get something that looks like
$$T_1 = P_1^\infty(X) = \infty + \infty A + \infty A^2 + \infty A^3 + \cdots
= \infty \times (1 +A + A^2 + A^3 + \cdots) = \infty \times \mathtt{List}(A)$$
and the same for $T_2$. So we form a hypothesis:

Theorem: Both $T_1$ and $T_2$ are isomorphic (parametrically in $A$) to the type $\mathtt{nat} \times \mathtt{List}(A)$.

Proof. The best proof would be actual implementations of the isomorphisms in question, but I do not have the time to do that. Perhaps a nice soul can volunteer to write these. Let me sketch an outline of the proof. Think of the elements of $T_1$ as trees which store some $A$'s in their leaves. To each value $v : T_1$ we assign a list $\ell_v = [a_1, \ldots, a_{n_v}]$ of the $A$'s stored in $v$, in left-to-right traversal order. There are infinitely many $v$'s which share the same $\ell_v$ because we can have arbitrarily many empty leaves. Order all $v$'s with the same $\ell_v$ in a canonical order of some sort, so that to each $v$ with a given $\ell_v$ we assign a number $n_v$ in this order. The mapping $v \mapsto (n_v, \ell_v)$ is the isomorphism from $T_1$ to $\mathtt{nat} \times \mathtt{List}(A)$. A similar construction works for $T_2$. QED.


The complexity of a multi-objective shortest path problem

It is NP-hard by reduction from Partition.

Let $x_1,\dots,x_n$ be the partition instance.

Create a graph on levels $0,1,\dots,n$ with level $0$ containing the start vertex $s$, and level $i$ containing two vertices, $a_i$ and $b_i$.

Every path from $s$ to a vertex in the last level corresponds to a partition of $x_1,\dots,x_n$ into two blocks, $A$ and $B$, as follows:
If the path goes through $a_i$, then $x_i$ is placed in $A$, otherwise the path must go through $b_i$, and $x_i$ is placed in $B$.
Conversely, every partition is realized by some path in this way.

For every edge to $a_i$ from the level below, let the cost be $(x_i,0)$, and for every edge to $b_i$ from the level below, set the cost to $(0,x_i)$.
Finally, set $L_i = \sum_{i=1}^n x_i/2$.
Now the partition instance has a balanced partition if and only if there is a solution to the path problem with cost $\le \sum_{i=1}^n x_i/2$.

(Edit: I originally gave a reduction from the shortest weight-constrained path problem, and then to answer a comment; a reduction from partition to the shortest weight-constrained path problem. However, the last reduction is enough by itself.)


There has been a series of breakthroughs on Dichotomy Theorems by Professor Jin-Yi Cai https://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/
Another dichotomy theorem https://rjlipton.wordpress.com/2014/06/23/counting-edge-colorings-is-hard/

https://rjlipton.wordpress.com/2011/02/14/classifying-papers-on-classifying-problems/

https://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/


My solution is incorrect. See other answer...


Turing Machine restrictions that render halting decidable

A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example:

Juris Hartmanis: Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968)

Edit: [this variation is more artificial] the halting problem is decidable for a Non-erasing Turing machine that has at most two left instructions on alphabet $\{0,1\}$; see Maurice Margenstern: Nonerasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality. Theor. Comput. Sci. 129(2): 419-424 (1994)


Is the Cheeger constant $\mathsf{NP}$-hard?

I too encountered this issue when I was writing a paper that required a citation to hardness of edge expansion (or Cheeger constant) defined as $\min_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$. The classic paper of Leighton and Rao on separators ( http://dl.acm.org/citation.cfm?id=331526 ) mentions that this is a hard problem and refers to the paper of Garey, Johnson and Stockmeyer (http://www.sciencedirect.com/science/article/pii/0304397576900591). I could not figure out for a while what they were referring to since there is no mention of edge expansion in the referred to paper. I communicated with Avi Wigderson about this. It finally transpired that one can use the hardness of Max-Cut as shown in the Garey et al paper to relatively easily show that edge-expansion is hard. I forget the details now but it should not be hard to recreate. The paper of Blum etal on hardness of checking whether a graph is a superconcentrator does not directly imply hardness of edge expansion. They are technically not the same problem.


Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength

Let me rephrase the question:

  Which one is preferred?

  Proving a protocol secure in the standard model, based on non-standard assumptions
  Proving a protocol secure in non-standard models (like CRS), based on standard assumptions.

The short answer is: It depends!

Details follow.

Assume that you can prove a protocol secure in the CRS model using standard assumptions. In addition, assume that you can implement the CRS model in the standard model without significant overhead, and using only standard assumptions. Then, the second approach is preferable. (Here, "significant" depends on the application.)

On the other hand, assume that you cannot implement the CRS model in the standard model easily ,i.e. either the overhead is too high, or the protocol setting is that you cannot implement the CRS without resorting to non-standard assumptions (For instance: You don't have access to some trusted 3rd party, etc.) In such cases, it seems that the first approach is preferable.

Side note: I must add that both approaches are highly valuable in theory, regardless of the real-world application.


The theory of definitions in first order logic

I don't have the books handy at the moment, but I think Shoenfield's "Mathematical Logic" and Hinman's "Fundamentals of Mathemtical Logic" would contain much if not all of what you're looking for.

Probably not what you want but perhaps worth mentioning anyway is A. P. Morse's book "A Theory of Sets". This is a development of (a rather idiosyncratic version of) what is usually called Morse-Kelley set theory, but Morse also pays a great deal of attention to the formulation of definitions. His goal is to make the formal language close to normal mathematical English, while avoiding ambiguities. There's a long chapter, early in the book, spelling out what is allowed in definitions.

Another logician who paid close attention to definitions was S. Lesniewski. He developed a system of foundations of mathematics in which definitions played a crucial role. In contrast to most systems, definitions are not conservative in Lesniewski; some definitions play the role of comprehension axioms. Because of their importance in his framework, Lesniewski gave very careful rules for what constitutes a legitimate (in his sense) definition. Some of his work is very hard to find (and it's mostly in Polish, though a little of it is in German), but there's a book, "The Logical Systems of Lesniewski" by Luschei, that describes it well. (There should be an acute accent on the first s in "Lesniewski" but the best my keyboard and browser can do here is Le´sniewski.)


3-OCC-MAX 2SAT: given a CNF formula $\varphi$ in which each clause contains at most 2 literals and each variable appears in at most three clauses (counting together both positive and negative literals); does there exist an assignment that satisfies at least $k$ clauses?

In P. Berman, M. Karpinski, On some tighter inapproximability results (1998). Lecture
Notes In Computer Science, vol. 1644 (1999), pp. 200-209 :

... for any $\epsilon > 0$ it is NP hard to decide whether an
instance of 3-OCC-MAX 2SAT
with $2016 n$ clauses has a truth assignment that satisfies
at least $(2012 - \epsilon)n$ clauses.

As noted in the domotorp's comment, if a variable appers only positive or negative we can fix its value (satisfying and deleting all the clauses in which it appears); so we can assume that the 3 occurrences are not-all-equal ending up in a "3-NAE-OCC-MAX 2SAT" instance :-)


Resources for mathematicians hoping to learn more computer science

You're essentially asking for resources that will let you turn your existing knowledge of logic, recursion theory, and category theory into knowledge about theoretical computer science.I would suggest looking at realizability theory, especially via its connections to topos theory and categorical proof theory.

Here are a handful of suggestions; my advice is to pick one and go into depth. With the exception of Taylor's book (which explains this), my suggestions assume you have been exposed to enough lambda calculus and category theory to have seen categorical interpretations of the simply-typed lambda calculus.

Paul Taylor's book Practical Foundations of Mathematics

IMO, this is probably the single best technical introduction to the relationship between logic, category theory and computation. It assumes almost no pre-requisites, but it gets into quite deep waters very quickly, and is sure to tax (and greatly improve) your mathematical maturity.
Wesley Phoa's notes An Introduction to Fibrations, Topos Theory, the Effective Topos, and Modest Sets

These are some lecture notes that Wesley Phoa wrote up. If you are categorically fluent, then these notes offer a really fast path into understanding some of the most  important constructions in realizability and topos theory (namely, the construction of the effective topos).
Bart Jacobs' book Categorical Logic and Type Theory

This is one of the definitive references on the categorical semantics of type theory. It is also very large.

At the same time you are reading one of these books, I would advise downloading and learn how to use the Agda programming language. This language implements the sophisticated type theories described above, and IMO it is incredibly helpful to see how the often quite subtle semantic constructions cash out in type theory.

Andrej Bauer can probably give you even better advice. Perhaps he can be persuaded to post. :)


Is it worthwhile to try to prove a conjecture by mapping it to a Turing machine?

First, you don't need to turn them into Turing machines, it is essentially the same as running a proof search algorithm. The logical complexity of the formula (which in the cases you have in mind are $\Pi^0_1$) has no effect on this, searching for proofs in any effective theory (like ZFC, for proof to make sense you have to fix a theory) can be done in a straight forward manner, the set of provable statements for any effective theory is $\Sigma^0_1$ and therefore computable enumerable.  But there are no reasons to do that, you don't gain anything a priori just by adding one extra unnecessary layer of coding, it has no benefit (AFAIK).

Also don't confuse proof search with a direct reduction from the truth of a $\Pi^0_1$ statement to the halting problem (which exists as not halting is $\Pi^0_1$-complete).

Second, consider the much simpler case of propositional tautologies in place of first-order statements like GC. (propositional tautologies is a coNP set also known as $\Pi^B_1$). The state of art proof search algorithms (i.e. SAT solvers) are exponentially inefficient in finding proofs of very simple finitary mathematical statements like the pigeon-hole principle tautologies. You can run a first-order proof search program to look for a ZFC proof of GC but I haven't seen any interesting mathematical statement being discovered/proven by unguided brute-force search of proofs. So there is no example of this being useful. (For human-guided use of computer in proving mathematical theorems we have the four colors theorem.)

Third, if you use a proof search algorithm you will only know if there is a proof, if there isn't any you will not know and the algorithm will continue forever without halting. In other words, you can't write a program like the one you have stated in the question (which is why I commented that this is more suitable for CS Q&A site since this is very basic mistake in computability theory).

See also my answers to similar questions on math and CS.


Well, your edited version of the question revealed a reference to the following paper:

Rafael Pass. 2003. Simulation in quasi-polynomial time, and its application to protocol composition. In Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques (EUROCRYPT'03), Eli Biham (Ed.). Springer-Verlag, Berlin, Heidelberg, 160-176. (See also this version.)

The paper discusses and justifies the need for such simulators.
The abstract reads:

  We propose a relaxation of zero-knowledge, by allowing the
  simulator to run in quasi-polynomial time. We show that protocols satisfying this notion can be constructed in settings where the standard definition is too restrictive. Specifically, we construct constant-round straight-line concurrent quasi-polynomial time simulatable arguments and show
  that such arguments can be used in advanced composition operations without any set-up assumptions. Our protocols rely on slightly strong,
  but standard type assumptions (namely the existence of one-to-one one-way functions secure against subexponential circuits).

For a more thorough discussion, I suggest taking a look at Rafael Pass's M.Sc. thesis.