Is that edge orientation optimization problem NP-hard? Is the following optimization problem NP-hard?

Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{out}(u) \right)^2$, where $d_{out}$ is the number of out-neighbors.

Motivation: The problem is related to listing triangles in graphs. A motivation can be found here where the optimization problem is similar, but where the edge orientation needs to induce a DAG.
One can observe that the DAG constraint is not necessary: the actual constraint in order to have a correct algorithm (i.e. an algorithm that will list all triangles) is that the edge orientation should not induce a cycle of length 3.
I think that the constraint "no induced cycle of length 3" is too complicated and decided to formulate the above problem as a stepping stone.
Another formulation: The problem can be written as the following Integer Quadratic Programming.
\begin{align}
 \text{Minimize} &\qquad \sum_{u\in V} (y_u)^2 &\qquad  (IQP)\\
 \text{s.t.} &\qquad \forall u \in V, \forall v \in N_u, x_{u,v}  \in \{0,1\}  \\
 &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &\qquad \forall u \in V, y_u=\sum_{v \in N_u} x_{u,v}\\
\end{align}
with $N_u$ the set of neighbors of node $u$ in the input undirected graph.
Is (IQP) NP-hard?
It can be relaxed into the following Quadratic Programming:
\begin{align}
 \text{Minimize} &\qquad \sum_{u\in V} (y_u)^2 &\qquad  (QP)\\
 \text{s.t.} &\qquad \forall u \in V, \forall v \in N_u, x_{u,v}  \in [0,1]  \\
 &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &\qquad \forall u \in V, y_u=\sum_{v \in N_u} x_{u,v}\\
\end{align}
for which an optimal solution can be obtained in polynomial time using a quadratic programming solver as the objective is convex. Can an exact or approximate solution to (IQP) be obtained out of the (QP) solution? Using randomized rounding maybe?
The greedy algorithm is not optimal: The algorithm "fix some orientation then repeatedly flip the orientation of an edge that decrease the score" is not optimal. The following is a counter example found by alt-tab.

We answer OP's last question: can an approximate solution to IQP be obtained by randomized rounding?
We show that the natural randomized-rounding scheme gives a 2-approximation, and a $(1+1/\overline d)$-approximation in graphs with average degree $\overline d$. (Note that any connected graph has average degree at least $2-2/|V|$.)
For the record, here's the rounding scheme. Given a fractional solution $x$ for QP, define 0/1 solution $x'$ as follows: for each edge $(u,w)$ independently: take $x'_{uw} = 1$ and $x'_{wu}=0$ with probability $x_{uw}$; otherwise take $x'_{uw} = 0$ and $x'_{wu} = 1$.
Let $f(x)$ be the objective function of QP.
Lemma 1. For any feasible $x$,
$$E[f(x')] = f(x) + 2\sum_{(u,w)\in E} x_{uw}x_{wu} \le f(x) + |E|/2.$$
Proof. This is a standard calculation.  Note that
$$f(x) = \sum_{u\in V} \Big(
\sum_{w\in N(u)} x^2_{uw} + 2\sum_{w'\in N(u), w'\ne w} x_{uw}x_{uw'}\Big)$$
and by linearity of expectation, the independence of $x'_{uw}$ and $x'_{uw'}$, and $E[x'^2_{uw}] = x_{uw}$,
$$E[f(x')] = \sum_{u\in V} \Big(
\sum_{w\in N(u)} x_{uw} + 2\sum_{w'\in N(u), w'\ne w} x_{uw}x_{uw'}\Big).$$
Using this and $x_{uw} = 1 - x_{wu}$,
$$
E[f(x')] - f(x)
= \sum_{(u,w)\in E} x_{uw} - x^2_{uw} + x_{wu} - x^2_{wu}
= 2\sum_{(u,w)\in E} x_{uw} x_{wu}.$$
Lemma 2. For any feasible $x$, $E[f(x')] \le 2 f(x)$. That is, the rounding scheme gives a 2-approximation.
Proof.
By inspection of the expansion of $f(x)$ in the proof of Lemma 1,
$$f(x) \ge \sum_{(u,w)\in E} x^2_{uw} + x^2_{wu}.$$
Applying $p^2 + (1-p)^2 \ge 2p(1-p)$ for $p\in[0,1]$ (with $p=x_{uw}$)
to each term gives
$$f(x) \ge 2\sum_{(u,w)\in E} x_{uw}x_{wu}.$$
This and Lemma 1 imply $E[f(x')] \le f(x) + f(x) = 2 f(x)$. $~~~\Box$
The bound is tight in that for any graph with maximum degree 1,
the fractional solution $x_{uw} = x_{wu} = 1/2$ obtains value $|E|/2$,
but any integer solution has value $|E|$.
(Also note that $|E|$ is a lower bound on OPT,
using $\sum_{u\in V} d^2_{out}(v) \ge \sum_{u\in V} d_{out}(v) = |E|$.)
Lemma 3. In any graph with average degree $\overline d = 2|E|/|V|$, the rounding scheme gives at least a $(1+1/\overline d)$-approximation.
Proof.  Fix an optimal solution. Let $d'_v$ denote the out-degree of vertex $v$ in the optimal solution,
so $d'$ is a vector in $\mathbb R_+^{|V|}$.
Let $\mathbf 1$ denote the all-ones vector in $\mathbb R^{|V|}$.
By Cauchy-Schwarz,
$$\text{OPT} = d' \cdot d'
\ge (d' \cdot \mathbf 1)^2/(\mathbf 1\cdot \mathbf 1)
= \textstyle \big(\sum_v d'_v\big)^2/|V|
= |E|^2/|V| = |E|\overline d/2.$$
By this and Lemma 1
$$E[f(x')] \le f(x) + |E|/2 \le f(x) + \text{OPT} / \overline d \le \text{OPT}(1+1/\overline d).$$
$~~~\Box$


Algorithms for computing the minimal vertex separator of a graph Background: Let $u,v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G−S$. If no proper subset of a $u,v$-separator $S$ is a $u,v$-separator then S is a minimal u,v-separator. A vertex set $S \subseteq V$ is a (minimal) separator if there exist vertices $u,v$ such that $S$ is a (minimal) u,v-separator.

Is there some algorithm to compute the minimal vertex separator on a generic graph?

If I'm not interested in the smallest set but just in a set of separator vertices that disconnects $u$ from $v$ how can I do it?

A simple way to find just some minimal $u$-$v$-separator is to find one that is close to $u$. A separator $S$ is called close to $u$ if $S \subseteq N_G(u)$. This is actually very easy and can be done in time $O(n + m)$. Consider the graph $G - N_G(u)$ where $u$ is isolated and $v$ lies in some different component, $C$, which simply contains all vertices which are reachable from $v$. Now, adding the vertices $N_G(u)$ back to the graph, the neighbors $N_G(C)$ of $C$ form a minimal $u$-$v$-separator.

Suppose this was not the case, then there exists $x \in N_G(C)$ such that $N_G(C) \setminus \{x\}$ still separates $u$ and $v$. As $x$ is a neighbor of $u$ and also a neighbor of some vertex in $C$, there exists a path from $u$ through $x$ to $C$, from which $v$ can be reached, a contradiction.

To find $N_G(C)$ in linear time, we can first traverse the neighborhood of $u$ and mark all of its neighbors with some color, say blue. This takes time $O(n)$. Then, we start a DFS at $v$ and mark all reachable vertices with another color, say red. However, when a blue vertex is encountered, it is not visited but simply added to another set, $S$. In the end, $S$ contains all neighbors of $C$. The running time of a DFS is $O(n + m)$, including the time that is needed for checking whether a vertex is blue, and adding it to $S$.

Also, in general any set $S \subseteq V(G)$ which separates $u$ and $v$ can be made minimal in time $O(nm)$ by the following steps:
for each $x \in S$, test whether $S \setminus \{x\}$ still separates $u$ and $v$. If it does, remove $x$ from $S$ and repeat this step. As $S$ can contain at most $n - 2$ vertices and checking whether $u$ and $v$ are still separated can be done by a simple DFS in time $O(m)$, the total time needed is $O(nm)$.


Another planar separator ref question Do any of you know a reference for the following (surprisingly tedious to prove) result?

Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \sqrt{t}+1)$.

Here is a proof using a well-known hammer.

Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges which are part of the spanning tree.

I claim that the treewidth of $G$ is $O(\sqrt{t})$ which would imply the desired separator (and some more). To prove the claim let $k$ be the treewidth of $G$. Then by a theorem of Robertson-Seymour-Thomas, since $G$ is planar, there is a grid minor of size $\Omega(k)$. However a grid minor of size $\Omega(k)$ has $\Omega(k^2)$ disjoint cycles and each of them requires one of the $t+1$ edges. Hence $k = O(\sqrt{t})$.


Infinitely large but locally finite computation problems This question is inspired by a comment Jukka Suomela made on another question.

  What are examples of infinitely large but locally finite computation problems (and algorithms)?

In other words, what are examples of computations that halt in finite time, in which each Turing Machine reads and processes only finite data, but altogether the computation solves an infinite-size problem if there are infinitely-many Turing machines networked together?

Just to give some ideas of what is possible (but somewhat non-trivial), here is one example: a distributed algorithm that finds a maximal edge packing on a bounded-degree graph.

Problem definition

Given a simple undirected graph $G = (V,E)$, an edge packing (or fractional matching) associates a weight $w(e)$ with each edge $e \in E$ such that for each node $v \in V$, the total weight of edges incident to $v$ is at most $1$. A node is saturated if the total weight of incident edges is equal to $1$. An edge packing is maximal if all edges have at least one saturated endpoint (i.e., none of the weights can be greedily extended).

Observe that a maximal matching $M \subseteq E$ defines a maximal edge packing (set $w(e) = 1$ iff $e \in M$); hence it is easy to solve in a classical centralised setting (assuming $G$ is finite).

Edge packings actually have some applications, at least if one defines an application in the usual TCS sense: the set of saturated nodes forms a $2$-approximation of a minimum vertex cover (of course this makes only sense in the case of a finite $G$).

Model of computation

We will assume that there is a global constant $\Delta$ such that the degree of any $v \in V$ is at most $\Delta$.

To keep this as close to the spirit of the original question, let us define the model of computation as follows. We assume that each node $v \in V$ is a Turing machine, and an edge $\{u,v\} \in E$ is a communication channel between $u$ and $v$. The input tape of $v$ encodes the degree $\deg(v)$ of $v$. For each $v \in V$, the edges incident to $v$ are labelled (in an arbitrary order) with integers $1,2,\dotsc,\deg(v)$; these are called local edge labels (the label of $\{u,v\} \in E$ can be different for $u$ and $v$). The machine has instructions with which it can send and receive messages through each of these edges; a machine can address its neighbours by using the local edge labels.

We require that the machines compute a valid edge packing $w$ for $G$. More precisely, each $v \in V$ has to print on its output tape an encoding of $w(e)$ for each edge $e$ incident to $v$, ordered by the local edge labels, and then halt.

We say that a distributed algorithm $A$ finds a maximal edge packing in time $T$, if the following holds for any graph $G$ of maximum degree $\Delta$, and for any local edge labelling of $G$: if we replace each node of $G$ with an identical copy of the Turing machine $A$ and start the machines, then after $T$ steps all machines have printed a valid (globally consistent) solution and halted.

Infinities

Now all of the above makes perfect sense even if the set of nodes $V$ is countably infinite.

The problem formulation and the model of computation do not have any references to $|V|$, directly or indirectly. The length of the input for each Turing machine is bounded by a constant.

What is known

The problem can be solved in finite time even if $G$ is infinite.

The problem is non-trivial in the sense that some communication is necessary. Moreover, the running time depends on $\Delta$. However, for any fixed $\Delta$, the problem can be solved in constant time regardless of the size of $G$; in particular, the problem is solvable on infinitely large graphs.

I have not checked what is the best known running time in the model defined above (which is not the usual model used in the field). Nevertheless, a running time that is polynomial in $\Delta$ should be fairly easy to achieve, and I think a running time that is sublinear in $\Delta$ is impossible.


Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$ In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), K(y) \right \}}$

where $x^*$ is the shortest program outputting $x$. I.e. $K(x) = |x^*|$. In most future papers they drop the star notation, turning the metric into

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y), K(y|x) \right \}}{\max \left \{ K(x), K(y) \right \}}$

I'm unclear on the relationship between the two quantities $K(x|y^*)$ and $K(x|y)$. It seems to me that the former is quite different from the latter, as the latter is providing both $y$ and $K(y)$ as an input to the program computing $x$. However, I can't find any justification as to how these metrics are the same (up to whatever sufficiently sloppy additive precision you like). Could someone point me to an explanation or a reference that clarifies this?

As per the comment, $K(x|y) \leq K(x|y^*) + O(1)$. Now denoting the first metric (with the *) by $d_1$ and the second by $d_2$, we have

$\displaystyle \begin{align*} d_2(x,y) &= \frac{\max \left \{ K(x|y), K(y|x) \right \} }{\max \left \{ K(x), K(y) \right \}} \\ &\leq \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \} + O(1) }{\max \left \{ K(x), K(y) \right \}} \\ &= d_1(x,y) + O(1/K) \end{align*}$

where $K = \max \left \{ K(x), K(y) \right \}$

All of the theorems in the paper give the metric inequalities and universality claims up to an additive factor of $O(1/K)$, so this fits.


Average-case complexity open problems other than one-way functions The list of unsolved problems in computer science on Wikipedia lists no problems in average-case complexity, except "Do one-way functions exist?" which is whether there is a polynomial time computable function that such that all efficient algorithms fail (with high probability) to invert it.

Are there other high-profile, specific open problems in average-case complexity?

You can look at the survey paper by Bogdanov and Trevisan, and this survey talk by Luca. The main open question is whether $\mathsf{P} \neq \mathsf{NP}$ implies that there exist hard on average problems in $\mathsf{NP}$. There are also more concrete conjectures about specific problems, two of which were mentioned in the comments:

The planted clique problem: distinguish between a uniformly random graph on $n$ vertices, and a uniformly random graph in which we have planted a $k$-clique on a random $k$-subset of the vertices. Conjectured to be hard for $k = \omega(\log n)$, $k = o(\sqrt{n})$.
Feige's random SAT hypothesis: for every $\Delta$, any polynomial time algorithm which never refutes a satisfiable 3SAT formula will fail to refute most 3SAT formulas with $\Delta n$ clauses. It is consistent with current knowledge that this hypothesis may hold even up to $\Delta = o(\sqrt{n})$.


Importance of ACM/IEEE in TCS conference Recently I was in an ACM supported conference.
During the banquet, the conference organizers told us about the future and past of the conference. They told us that during the 2010 edition of the conference there was a loss of 5000$.

They showed us the budget of the previous conference where we could see that there were 8000$ (10% of the budget if I remember correctly) given to ACM. Maybe because I am not yet fully in the field (I am starting my PhD in september 2011), I was the only one to ask what was this money given for. The answer I got was really disappointing, apparently the main contributions of the ACM was to print the proceedings and to give advice so the next year there would not be such a loss (apparently the advice given was to raise the entry fees).

I was really surprised, since in order to read the proceedings your university has to pay a subscription to ACM (correct me if I am wrong), I thought ACM (is it the same for IEEE?) had to pay to support the conference.

So my questions are:

What does ACM really bring to a conference?
Have you heard of other conferences where this is the case?

Related Blog posts:
Freedom to Thinker and Matt Blaze's post, apparently the question was already asked.

One thing ACM brings to a conference is name recognition: if I see that a conference is ACM-sponsored, even if it's one that I haven't heard of before, I can be confident that it's reasonably high quality and well organized, rather than being one of those scam conferences that accepts everything and profits off the registration fees. (I'm less sure of that with IEEE after the Schlangemann scandal.) Of course, there are also good conferences that are not sponsored by these societies. And I wouldn't want to rely on this halo effect for making decisions about tenure or anything important like that — better to solicit opinions from people who know that area better — but it can be useful when deciding where to send a paper.


Complement for joint POVMs? I'm trying to relate some notions of set theory to POVMs. I firstly explain the scenario with set theory and then in the POVM setting.

For some finite $N \in \mathbb{N}$, let $A_i$ and $B_i$ for $i=1,...,N$ be sets and assume there is some larger set $C$ such that $A_i\subset C, B_i\subset C$ for all $i$. Let's say for $J=\{1,...,N/2\}$ (just take $N$ even), I'd like to compute
$$  \left(\bigcup_{i\in J} A_i\times B_i\right)^c.$$

By De Morgan's laws we can write, $$\left(\bigcup_{i\in J} A_i\times B_i \right)^c =  \bigcap_{i\in J} (A_i\times B_i)^c  = \bigcap_{i\in J} A_i^c\times B_i \cup A_i\times B_i^c \cup A_i^c \times B_i^c$$

Now I'd like to do something similar for POVMs. Let's say I have two POVMs, $A = \{A_1,...,A_N \}$ and $B=\{B_1,...,B_N\}$.

For either POVM, I think it's clear how to define a complement for a subset. For example, if I want the complement of $\{A_2, A_3\}$, then I can do $\mathbb{1} - A_2 - A_3$. My interpretation is,  $\mathbb{1} - A_2 - A_3$ encompasses all events except $A_2$ or $A_3$. Now I want to define a (or be given a known) complement for a joint measurement.

Let's again say I have some $J = \{1, ..., N/2\}$ and I want to determine the complement of the sum joint measurements indexed over $J$. That is, I want somehow to define

$$\left(\sum_{i\in J}A_i \otimes B_i\right)^c$$

My first thought was to have

$$\left(\sum_{i\in J}A_i \otimes B_i\right)^c = \mathbb{1} - \sum_{i\in J}A_i \otimes B_i$$

But this only encompasses the analog of $\bigcup_{i \in J} A_i^c \times B_i^c$ and misses the analogs of $A_i^c \times B_i$ and $A_i\times B_i^c$.

Then I thought, in a De Morgan sense

$$\left(\sum_{i\in J}A_i \otimes B_i\right)^c = \prod_{i\in J} (A_i \otimes B_i)^c = \prod_{i\in J} (\mathbb{1} - A_i)\otimes B_i + A_i \otimes (\mathbb{1}-B_i) + (\mathbb{1} - A_i)\otimes (\mathbb{1}-B_i)$$

This I think is logical, but I've not yet convinced myself that it's true. Has anyone had a similar scenario?

Thanks for your time and sorry if the question isn't clear.

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

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


What is higher-order in higher-order abstract syntax? I understand that using higher-order abstract syntax essentially means using host (meta) language abstraction facilities to represent binders in embedded (object) language. But, Why exactly is it higher-order? Why is traditional abstract syntax called first-order abstract syntax?

I read the paper (Frank Pfenning, and Conal Elliott, Higher-Order Abstract Syntax, PLDI'88) that introduced HOAS as we use today. I could not quite understand the following paragraph ($\S$ 3.2) that describes encoding in HOAS:

  In this first generalization, simply typed lambda terms represent programs. .. . The lexical terminals and the operators that do not introduce variable bindings are, respectively, first-order and second-order constants of the $\lambda$-calculus. Another crucial change occurs for the variables. Operators in the object language that are binding constructs are now explicitly encoded as third-order constants. As the following examples will show, this requires that bound object language variables actually become variables in the typed lambda calculus.

Particularly, I am not convinced why encodings for binding-introducing constructs like let (shown in Figure 1 of the paper) are considered third-order.

You can think of $\lambda$-abstraction as an operator $\Lambda$ which takes a function from terms to terms into a term:
$$\Lambda : (\mathsf{Term} \to \mathsf{Term}) \to \mathsf{Term}.$$
The type of $\Lambda$ is higher-order because it maps functions to objects, so it is a functional of rank 2. This is where the name comes from.

For example, if $\mathsf{id}$ is the identity map then $\Lambda(\mathsf{id})$ is the term $\lambda x . x$.

Constructors, for example $\mathsf{succ}$ as a constructor for the type of natural numbers, can naturally be viewed as first-order because they take terms to terms.

Of course, for the above to make sense, we need to be able to speak about functions between terms at the meta-level. And there are various subtleties: in principle one can have weird functions between terms that do not correspond to anything that can be written down in the syntax (consider a non-computable map). So if you're not careful, you're going to end up with "exotic terms" $\Lambda(f)$ that create a lot of trouble.

The usual solution is to somehow limit $\mathsf{Term} \to \mathsf{Term}$ to only "nice" functions. One possibility is PHOAS, another is to use a meta-theory such as Logical Frameworks in which only nice functions exist.


Learning with "taciturn" oracles My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-)

Story

Mr. X, the head of the computer security department at a big company, is a bit paranoid: he requires that all employees change their passwords once a month, in order to minimise the risks of identity or information theft. Moreover, he does not trust the employees to be able to come up with secure passwords.

Therefore, every month, he generates new passwords using a piece of software he wrote, and gives them to the employees so that they can log in again. But besides being paranoid, Mr. X is also a bit lazy: the passwords he generates all follow some pattern, and the algorithm used to allow people to log in only checks that the password "looks okay" according to that rule, and that it is not in the "expired list".

Unfortunately, his pretentious behaviour made a lot of people bitter, and one of them, Mr. Y, decides to prove him that he can crack his passwords. So, one night, he collects a few of them, and starts trying to design a learning algorithm for generating valid passwords, using his personal computer to verify them.

Question

The oracle used by Mr. Y is a bit strange, in that it tells him "the truth, but not the whole truth" (hence the "taciturn" adjective). More precisely: Mr. Y will know that a password is valid when his computer accepts it, but when a password is rejected, Mr. Y will not know whether or not it could have been valid: the password may be rejected because it does not correspond to some pattern, but it may also be rejected because it used to be valid but no longer is, according to Mr. X's "change once a month"-rule.

So, will Mr. Y ever be able to come up with anything in that setting? Or can we claim/prove that Mr. X's passwords are inherently unpredictable (as defined in the PAC learning setting, but maybe this concept exists in other frameworks)?

It seems you're trying to PAC learn a language by only seeing positive examples.  This is called "learning from positive examples (only)."  But you also have the power to get some of your own made-up examples labeled: if the oracle were fully truthful, then these would be membership queries, so your model would be known as "learning from positive examples and membership queries."  In this framework, there are some results - for example, tree languages are learnable (not secure).  DFA are not due to crypto hardness results. (Also see this.)

Of course, your setting isn't quite this.  Your membership queries are more limited.  It seems that then the known intractability results would transfer to your setting from the model I described, but the learnability results would leave you with some work to do.  But Mr. X's scheme is secure or not depending on the "pattern" he uses.

Also - it seems like a strange requirement to be able to prove "Mr. X's passwords are inherently unpredictable."  Isn't it usually enough to just be able to generate a new valid password to break such a system? But this seems to be the query to Mr. Y's algorithm itself...


Finding a Hamiltonian cycle from perfect matching of a bipartite graph A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H,  constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original graph edges replaced by corresponding L-> R edges.

Is it possible to find a Hamiltonian cycle in G (assuming it exists) as one realization of the vertex-disjoint cycle cover from the bipartite graph, H, using a matching algorithm?

If $G$ has a disjoint vertex cycle cover then I agree that $H$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $H$ exactly). I think the construction you were thinking of is the one described in this answer: https://cstheory.stackexchange.com/a/8570/38111.

As for your question (assuming that $H$ is now the bipartite graph constructed in the answer I linked), I think it depends on what you are asking exactly:

if you are asking "if there is a Hamiltonian cycle in $G$, then is there a perfect matching in $H$ that 'corresponds' to this cycle" then yes, since, as David Eppstein points out in his answer, the perfect matchings of $H$ correspond 1-for-1 with cycle covers of $G$, and a Hamiltonian cycle is in particular a vertex disjoint cycle cover.
if you are asking "can we use the same kind of trick to efficiently find such a Hamiltonian cycle", then probably no, since finding a Hamiltonian cycle is NP-hard.


Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus? I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge of these interesting subjects.

I want to learn about lambda calculus because it seems like an interesting way to think about functions in general, and because a generalization called the stochastic $\pi$ calculus studied by Luca Cardelli and others seems to allow many computational interpretations of biology, something which I am really interested in. Also other reasons, like wanting to learn and understand functional programming, in order to have an alternative to C++ which I dislike.

However, I just learned that type theory, at least as stated by Lof, is supposed to be a way to formalize intuitionistic logic/constructive mathematics, which rejects the Law of the Excluded Middle and even the Axiom of Choice. My background is more in mathematics than computer science, so although I can see how having to construct something to prove that exists is an acceptable restriction for people interested primarily in computation, I am really uncomfortable with having to give up proof by contradiction and the Law of the Excluded Middle. Perhaps that makes me old-fashioned, and my grandkids will laugh at me for this concern, but proof by contradiction can be very useful and is how I learned a lot of the math which I know.

  Is there a way to learn about $\lambda-$calculus and type theory while at least being agnostic about the Law of the Excluded Middle and not outright rejecting it?

The discussion on p.9 of the Homotopy Type Theory book seems to say something to the effect that Univalent Foundations and Homotopy Type Theory can be compatible with the Law of the Excluded Middle and the Axiom of Choice, even though they contradict the univalent axiom? Needless to say I did not quite understand the argument about (-1)  types and thus am still somewhat skeptical and unconvinced.

Also, in one of his lectures at the Oregon Programming Language Summer School posted on youtube, Professor Awodey, one of the big names behind the IAS's Homotopy Type Theory/Univalent Foundations Project, seems to identify the Heyting algebra as underlying logic, rather than the Boolean algebra. I read somewhere else (I forgot where unfortunately), that Heyting algebra is what results if one rejects the Law of the Excluded Middle, and thus presumably founding logic upon Boolean algebra means accepting the Law of the Excluded Middle.

Ideally I would prefer to not have to choose between $\lambda$-calculus and Boolean algebra, since the latter underlies most of my understanding of logic, and is also the basis for probability theory, which I know very well and would not like to give up or reject as half-baked. Also I thought Boolean functions were a very hot topic of computer science research, so it seems kind of strange that some computer scientists would prefer Heyting algebra.

These questions might be relevant:      Where is the proof that Coq + Excluded Middle is consistent
Heyting algebra in simply typed lambda calculus
Can boolean algebra be expressed in simply typed lambda caclulus?

If they even answer my question, would you mind explaining to me how (as if I were five, so to speak)? I don't quite understand the discussions on them.

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

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


tournament selection in genetic algorithms I have a question about how to use a tournament selection in GA. Suppose that I have 100 individuals as an initial population and then I want to apply tournament selection for n generations, so I end up with only 20% of chromosomes for each iteration.
The algorithm that I came up with is:

choose 20% of the initial population
while (not end of iterations)
    select randomly n individuals from the left population (20%)
    if (number of chromosomes greater than two)
        select the best and mutate
        add to the population
    if (number of chromosomes greater than three)
        select best two of each pair and crossover them
        add crossover product to the population
    repeat process with new population
end while

is this schema correct?
Thanks

Here's the basic framework of a genetic algorithm.

N = population size
P = create parent population by randomly creating N individuals
while not done
    C = create empty child population
    while not enough individuals in C
        parent1 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        parent2 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        child1, child2 = crossover(parent1, parent2)
        mutate child1, child2
        evaluate child1, child2 for fitness
        insert child1, child2 into C
    end while
    P = combine P and C somehow to get N new individuals
end while

There's a little more to it than this basic skeleton, as there are things like crossover rates where you might not always do crossover, opportunities for additional operators, etc., but this is the basic idea at least.

Most often, the "while not enough individuals in C" can be thought of as "while size(C) < N"; that is, you want the same number of offspring as parents. There are plenty of other ways, but that's a good way to start at least. I'm not sure if this is what you mean by having 20% of the chromosomes in the next iteration or what, but for now, just go with it.

So then the question of how to do tournament selection can be addressed. Note that selection is only that one step of the process where we pick individuals out of the population to serve as parents of new offspring. To do so with tournament selection, you have to pick some number of possible parents, and then choose the best one as the winner. How many possible parents should be allowed to compete is the value of k I mentioned earlier.

func tournament_selection(pop, k):
    best = null
    for i=1 to k
        ind = pop[random(1, N)]
        if (best == null) or fitness(ind) > fitness(best)
            best = ind
    return best

Let k=1. Looking at the pseudocode, this yields purely random selection. You pick one individual at random and return it.

Let k=10*N. Now we have a pretty high probability of picking every member of the population at least once, so almost every time, we're going to end up returning the best individual in the population.

Neither of these options would work very well. Instead, you want something that returns good individuals more often than bad ones, but not so heavily that it keeps picking the same few individuals over and over again. Binary tournament selection (k=2) is most often used.

In this basic framework, you can't end up with an empty population. You'll always have N individuals in the population and you'll always generate N offspring. At the end of each generation, you'll take those 2N individuals and prune them down to N again. You can either throw all the parents away and just do P = C (generational replacement), you can keep a few members of P and replace the rest with members of C (elitist replacement), you can merge them together and take the best N of the 2N total (truncation replacement), or whatever other scheme you come up with.


Oblivious Turing Machine emulation lower bound Is there a proof that the emulation of a Turing machine on an oblivious Turing machine can't be done in less than $\mathcal{O}\left(m\log m\right)$ where $m$ is the number of steps the Turing machine uses? Or is this just an upper bound?

In the paper of Paul Vitányi about relativized oblivious Turing machines, Vitányi claims

  "They [Pippenger and Fischer, 1979] showed that this result cannot be improved in general, since there is a language L wich is recognized by a 1-tape real-time Turing machine $M$, and any oblivious Turing machine $M'$ recognizing $L$ must use at least an order $O(n \log n)$ steps".

This should state $O(m \log m)$ as an absolute bound. However I don't find any proof of this in

Pippenger, Nicholas; Fischer, Michael J., Relations among complexity measures, J. Assoc. Comput. Mach. 26, 361-381 (1979). ZBL0405.68041.

Any ideas?
Furthermore, what is the space complexity of this emulation? As far as I know the conversion to a universal Turing machine only doubles the tape length. Can I assume that the space complexity is $\mathcal{O}\left(l\right)$ with $l$ the space complexity of the original Turing machine?

As mentioned above, it is not known in general if there is a faster oblivious simulation.

But interesting lower bounds for this problem are known, under more constrained conditions. For instance, what if you want an oblivious simulation that preserves not only the time $t$ but also the space usage $s$? Beame and Machmouchi have recently proved an interesting time-space tradeoff lower bound for this problem: either the space must increase by a factor of $n^{1-o(1)}$, or the time must increase by a factor of $\Omega(\log n \cdot \log \log n)$.

The paper is here: http://eccc.hpi-web.de/report/2010/104/


Is there a space efficient way to represent numbers on the lambda calculus? This is something I've been thinking. While it is agreed that Lambda Calculus is equivalent to a Turing Machine in power, is it actually so? Church Numerals are not very space efficient and I'm not aware of any better way to represent numbers using the LC. This leads me to the intuitive conclusion that, while, theorically, LC is as powerful as a TM, there is a natural limit that states that a program in LC will never be able to compute natural numbers as fast as a TM, given a physical world and limited resources.

Now I've throw many ideas and it is hard to define most of what I'm saying formally, but does that intuition make any sense?

If I am not mistaken the simulations between Turing machines and $\lambda$-calculus can be accomplished with a polynomial-time slowdown. Of course, for this to make sense we need to specify an evaluation strategy and measure of cost for $\lambda$-calculus but I am sure something reasonable can be found.

You ask about numbers in particular. Of course Church encodings are inefficient but they are only one possibility. In $\lambda$-calculus we can encode finite lists and the constants true and false. With these numbers can be encoded in binary as lists of boolean values, which gives an efficient representation. The charm of Church encodings is in their elegance.


Who proved that a triangulation is 3-colourable implies its dual is bipartite Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:
(i) $G$ is 3-colourable
(ii) dual graph $G^*$ of $G$ is bipartite
and (iii) $G$ is Eulerian (i.e., every vertex has even degree).
I am interested in direct constructive proof of (i) $\iff$ (iii).
I would like to know who came up with this proof; esp. the proof of (i)$\implies$ (ii) given below
(i) $\implies$ (ii):
Suppose $G^*$ has a 3-face colouring $f$ with colours 1,2,3. Then, one can obtain a 2-colouring $f^*$ of $G^*$ by assigning colour +1 at a vertex $v$ if colours 1,2,3 appear clockwise on faces around $v$, and colour -1 at $v$ if 1,2,3 appear counterclockwise around $v$. So, $G^*$ is bipartite.
David Gale wrote to Shen giving a proof for (i) $\iff$ (iii) using homology theory (for triangulations of the sphere). In that letter, he proves that the mapping $f\to f^*$ given in the proof above is in fact a bijection (answer to this question explains why). Shen explains these in Mathematical Entertainments 20(3). I think that Gale's proof is different for the direction (i)$\implies (ii)$ (I am not sure, homology theory is Greek to me). I guess this proof should be known already because it is easier than the other direction. So, like I said, I would like to know who came up with this proof of (i)$\implies (ii)$ first.
Tsai and West's paper A new proof of 3-colorability of Eulerian triangulations refer to Lovász (Combinatorial Problems and Exercises, Problem number is 9.52 I suppose) and to Shen (reference given above).
Thank you.

This result is included in Ore's book The Four-Colour Problem (see Theorem 7.4.3).
I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof for (ii)$\implies$(i). It seems that at that time, it wasn't known that the mapping $f\longmapsto f^*$ is a bijection.
Sorry to disappoint; but that's the best I could trace back.


Examples of hard instances for Goemans and Williamson algorithm I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor.

The algorithm to create such instances would be perfect, explicit examples and references are satisfactory.

I guess this reference is about what you ask:

  N. Alon, B. Sudakov, and U. Zwick. Constructing worst case instances for semidefinite programming based approximation algorithms. SIAM Journalon Discrete Mathematics, 15:58–72, 2002.

This is an excerpt from it (p.60):

  ... we present the construction of the
  graphs that show that the local analysis of the MAX CUT algorithms of [GW95]
  and [Zwi99] are tight.


Game semantics for coinductive predicates Does anyone know of any work on game semantics for coinductive predicates?

A coinductive predicate is one where the predicate itself is called in the body of the predicate, and we are taking the meaning of the predicate to be the greatest fixed point of the underlying definition. Such a predicate will be defined over an infinite data structure, such as a stream or infinite tree or labelled transition system and so forth.

An overly simple example is the following (in Haskell):

data Cat = BlackCat | WhiteCat
data Stream a = Stream a (Stream a)

allBlacks :: Stream Cat -> Bool
allBlacks (Stream cat rest) = cat == BlackCat && allBlacks rest

I can define the stream of all black cats as:

blackCats :: Stream Cat
blackCats = Stream BlackCat blackCats

and use coinduction to prove:

allBlacks blackCats

One could think of a coinductive predicate as an infinite conjunction or disjunction, simply by imagining that it is unrolled completely. Game semantics in this setting would be straightforward: for an infinite conjunction, the Falsifier needs to select which conjunct to falsify in order to win the game; for an infinite disjunction, the Verifier needs to select which disjunct to satisfy in order to win the game.

There is, however, a natural order in 'evaluating' the coinductive predicate which is ignored when considering it as an infinite conjunction or disjunction, and I would like this ordering to be captured in the game semantics, namely that the game proceeds by playing each disjunct/conjunct in turn.

One additional problem I have is understanding which winning condition to use to capture the infinite nature of the predicate. Or to put it in lay persons terms: how do I know that there is no white cat in this supposed infinite stream of black cats––it could merely be after the point I stop looking?

additional example

Consider the following data type (again in Haskell):

data Tree a = Tree (a -> Maybe (Tree a))

Tree A corresponds to the greatest fixed point of the functor $F(X) = (X+1)^A$.

Now assume that there is some relation $R:\subseteq A\times A$. This has no intrinsic meaning, and is just used to formulate the following coinductive predicate. Thinking of $R$ as $\le$ is sufficient.

Consider the following coinductive predicate $covers\subseteq$Tree A$\times$Tree A (defined corecursively):

  $\mathit{covers}(\alpha,\beta) = $
  $\qquad \forall a\in A\mbox{ if } \alpha(a)\neq\bot \mbox{ then } \exists b\in B
  \mbox{ such that } a R b \mbox{ and } \beta(b)\neq\bot \mbox{ and } \mathit{covers}(\alpha(a),\beta(b))$.

I'm looking for a formalism for expressing such predicates in terms of game-theoretic semantics. A link to existing work would be greatly appreciated. The main thing I'm having trouble getting my head around is the winning condition (as discussed in some of the comments below). Even though the game goes forever, infinite plays do not constitute a draw.

Vicious Circles by Barwise and Moss is a cornucopia of co-algebraic/co-inductive reasoning, and includes material on co-inductive games.

Not sure if it will help you out in your specific need, but might be the source of some inspiration in this line of reasoning.

Edit (x2):

I think you can follow a modified Ehrenfeucht-Fraïssé style approach like this: Falsifier gets to select any item from the stream/disjunction/conjunction.
Verifier then has to show that any such item must be a black cat.

(You could put ordering or number of choices restrictions on Falsifier without loss of generality for a finite set of coinductive rules.)

If you think of coinduction as just induction without a base case, it is obvious that the only (co-)induction rule you have on blackCats is cat == BlackCat, so what else could an individual cat be in that stream?  Any cat that Falsifier selects will have to conform to that rule, so Verifier wins.

Obviously this would scale to more numerous and complex coinductive rules, where the "challenge" for Verifier becomes to choose the appropriate rule for whatever item Falsifier chooses.

Colin Sterling's Bisimulation, Model Checking and Other Games, should help you out. His book Modal and Temporal Properties of Processes has similar material, though in less detail.


Is feedback vertex set problem is solvable in polynomial time for some special graph Feedback vertex set (FVS) problem is NP-complete for both undirected and directed graphs, and it is NP-complete even for bipartite graphs and tournaments.

Is there any special family of graphs other than trees for which FVS is solvable in polynomial time? I kindly request you to throw some light on it.

Surely the problem is polytime for graphs of bounded treewidth via dynamic programming.


Deciding graph homomorphism Deciding Graph Homomorphism is in general NP-Complete.

Are there any results which study this problem when the underlying graphs have algebraic structure (such as deciding homomorphisms from Cayley or Cayley coset graphs to other graphs with some definite structure as well)? In addition complexity results I am also interested in helpful algebraic and/or spectral techniques.

If $\mathcal{G}$ is a class of graphs with bounded treewidth, then the homomorphism problem from graphs in $\mathcal{G}$ is polynomial-time solvable. This can be generalized to the more general property of "graphs whose core has bounded treewidth."

Grohe proves a converse: if the cores of the graphs in $\mathcal{G}$ have unbounded treewidth, then the homomorphism problem from $\mathcal{G}$ is not polynomial-time solvable (assuming $FPT\neq W[1]$). Therefore, if you restrict the left-hand side graph to Cayley graphs etc., then what matters is whether the cores have bounded treewidth.

http://dl.acm.org/authorize?951212

Note that this does not completely answer your question: in the result of Grohe, it is  assumed that the right-hand side graph is arbitrary. You seem to be interested in results where the right-hand side graph is also restricted to some specific class of graphs.


Reference request: Depth- (or Breadth-) first search with hints? Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it.

Would it be possible to pre-process the graph and compute some "hints" among all nodes in the graph, such that given any node pair $s$ and $t$, the DFS or BFS procedure knows that some edges are more likely contributing to a path (if any) between $s$ and $t$? Therefore, the DFS or BFS will only traverse the "promising" edges to find the $s$-$t$ path. Is it a known problem?

Transitive closure could be one possible "hint". I am wondering if there is any cheaper solution, preferably in O(n) time.

Edits: "promising" means very likely. It appears that it's difficult to compute definitive promising edges (i.e., the edges will definitely be in an $s$-$t$ path). However, will it be possible to compute the promising edges by allowing some reasonable error?

The Reachability Wikipedia page lists several solutions, although the only one which works for general graphs involves computing the transitive closure, which it sounds like you want to avoid.
This is additionally for exact computations of the path.


Sampling a uniformly random satisfying assignment Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists).

Clearly this problem is NP-hard. My question is whether or not this problem is also "NP-easy":

Question: Does there exist an algorithm that solves the above problem in time polynomial in $n$ and the circuit size of $\phi$ given access to a SAT oracle?

Alternatively, is there a polynomial-time algorithm assuming NP=P?

Clearly having access to a #SAT oracle suffices, so the complexity lies somewhere between NP and #P.

I feel like this should have been studied before, but I can't find an answer on Google.

I know how to solve the problem approximately (i.e. generate a satisfying assignment that is statistically close to uniform) using a variant of the Valiant-Vazirani Theorem and/or approximate counting, but getting exactly uniform seems to be a different problem.

Yes.

(backup links in case that one goes down: 1 2 3 4)

Back up reference, in case all those links go down: Bellare, Mihir, Oded Goldreich, and Erez Petrank. "Uniform generation of NP-witnesses using an NP-oracle." Information and Computation 163.2 (2000): 510-526.


What are the limits of computation in this universe? I understand that Turing completeness requires unbounded memory and unbounded time.
However there is a finite amount of atoms in this universe, thus making memory bounded. For example even though $\pi$ is irrational there is no way to store more than a certain number of digits even if all the atoms in the universe were used for this purpose.
What then are the limits of computability of an implemented Turing machine (which could use all the resources of the universe but no more) based on the limits of the universe? What is the maximum number of digits of $\pi$? Are there any papers on this subject that might be interesting to read?

Seth Lloyd has a paper on the subject. You need energy to compute, but if you put too much energy into a small region, it forms a black hole. This slows down time (making the time it takes for the computation to complete relatively longer), and any computation done in the interior of a black hole is wasted, as the results cannot be extracted from the black hole and used. Seth calculates the limits on the amount of computation possible, and shows that for some measures of computation, the most computationally intensive environment possible in the universe would be that surrounding a black hole.


The theoretical complexity of Go - The state of the art What are the latest advances in theoretical complexity of Go?

I know some early works about the complexity of Go:

"Go is polynomial-space hard" proved that Go is PSPACE-hard.
"Ladders are PSPACE-complete" proved that ladders are PSPACE-complete.
"Go endgames are PSPACE-hard" proved that Go endgames (or yose) is PSPACE-hard.
"On the complexity of Tsume-Go" proved that the the complexity of Tsume-Go is NP-complete.
"Go Complexities" proved that Atari Go is PSPACE-complete.

Since there are several rules of Go (They are different but similar), it is a little complicated to analysis it. We only know that the lower bound of the complexity of Go is PSPACE-hard and the upper bound of it is EXPSPACE.

The state of the art for the theoretical complexity of go is well summed up on Wikipedia, with relevant references.

The main remaining open problem is for rules using a superko, i.e. repeating any past position is forbidden. This is the rule used for instance in China  and western countries. It is simple to state, but could bring some difficulties to actually play in some situations, as players need (in theory) to remember all the history of the game. In reality, these situations are so rare that it does not matter. For this rule, as you mention, we only know that deciding the winner from a given position is PSPACE-hard and in EXPSPACE.

On the other hand, it is known from Robson that Go with Japanese rules is EXPTIME-complete. These are the rules using local ko, only forbidding to repeat the last  position, and declaring draw if a longer cycle occur. These rules have to include many special cases to settle the situation for particular configurations, and although they are considered more practical for human players, especially for beginners to learn about the ko rule, they are not elegant mathematically.

You can see a sketch of Robson's proof that Go with Japanese rules is EXPTIME-hard here, with fun go positions using ladders to encode boolean formulas.


What would be the next step after quantum computing? Is their anything that would make Quantum computing obsolete in the future? I know a Matrioksha Brain is the most powerful theoretical computer; but it probably won’t ever be realized. Too large and hard to build. I know about hypercomputing but again that seems also too far-fetched.

So let’s say quantum computing becomes mainstream. What would be the next upgrade?

This is mainly a philosophical question and depends on your model of reality. Under some assumptions, time trevling ability will allow aditional speedup.... You can read about the CTC model, mainly introduced by Scott Aaronson, that deals with this subject.
https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.scottaaronson.com/papers/ctchalt.pdf&ved=2ahUKEwih8a_Qz-LnAhUCGewKHUFlBZMQFjABegQIBhAL&usg=AOvVaw3TMaefh-UTmCsAHKRT6EhL


Decidability of inductive invariant existence in Presburger arithmetic Problem:

Consider a finite number of control states (including an "initial" and a "bad" state), a finite number of integer variables, and for each ordered pair of states a transition relation expressed in Presburger arithmetic.

Decide whether there exists an inductive invariant (= stable by post-states of the transition relation) containing the initial but not the bad state, definable in Presburger arithmetic.

(Note that this problem is different from the reachability problem in Presburger arithmetic, which is clearly undecidable (by reduction from two-counter machines).)

I suspect this problem is undecidable, but do not know of any proof for it. (It is obviously semidecidable.) Has somebody proved this ?

The inductive invariant separator problem for Presburger arithmetic is undecidable.

I am unaware of a proof in the literature to point you at. (It seems so straightforward a question I assume it is somewhere out there.) The proof I came up with follows roughly the same construction as the halting problem. Here is a brief overview. We first assume a decision procedure $D$ exists and then construct a machine $S$ with input $M$. $S$ uses $D$ to decide non-termination of $M$ on itself and then $S$ reverses the output. We then use the construction of $S$ to show that $D$ must give an incorrect answer on the execution of $S$ on itself.

Instead of a reduction to the halting problem, the proof is for all intents and purposes a restatement of the proof of the halting problem. It is a bit verbose as will require that the exact strongest post condition can be expressed.  (If a simpler proof is possible, I'd be very interested in hearing it.) Now on to the gory details.

The inductive invariant separator problem for Presburger arithmetic is for a given 4-tuple $\left<\bar v,Init,Next, Bad\right>$ where $\bar v$ is a finite set of variable names, $Init$ and $Bad$ are Presburger formulas whose free variables are in $\bar v$, $Next$ is Presburger formula whose free variables are in $\bar v$ or $\bar{v}'$ (a primed copy of $\bar v$) does there exist a formula $\phi$ in Presburger arithmetic with free variables in $\bar v$ such that:

$Init \implies \phi$
$\phi \land Next \implies \phi'$
$\phi \implies \lnot Bad$

where $\phi'$ primes all of the free variables in $\phi$.

Suppose this problem is decidable. There then exists a Turing machine $D'$ that decides the separator problem (for a given encoding of Presburger formulas). Let $D$ be a deterministic Turing Machine that simulates $D'$. $D$ terminates and decides the separator problem.

A variable assignment over a finite set of variables $\{v_i\}$ is a conjunction $\bigwedge v_i = c_i$ where $c_i$ is an integer constant.

I will also assume the existence of a Turing machine to Presburger arithmetic compiler $C$ with some reasonable, but strong restrictions. $C$ takes as input a Turing machine $M$ with a unique final state, $term$, and an input $w$, and constructs presburger formulas $Init$ and $Next$ over a finite set of variables $\bar v$. Informally we require the paths of the Presburger formulas to simulate the execution of $M$ on $w$. Further, we require it to be a step simulation. Formally, we require that:

$C$ assigns a unique constant to all control states in $M$ and let the constant for $term$ be $\left<term\right>$,
$C$ includes a variable $pc$ in $\bar v$ that tracks the control state of $M$ at every step in the execution,
$C$ generates $Init$ to be in the form of a variable assignment over $\bar v$,
$C$ ensures that $Next$ to have a unique successor on variable assignments over $\bar v$ (that are reachable from $Init$) if $M$ is deterministic,
for there to exist an injective function $f$ from a state of $M$ (control and tape) to a variable assignment over $bar v$ such that $Next$ has a successor, the initial state of $M$ on $w$ is mapped to exactly $Init$ and the control state of $M$ consistently assigns $pc$,
$C$ is deterministic, and
$C$ terminates.

Now construct the Turing machine $S$ that takes a Turing machine $M$ as input and does the following (in pseudocode):

S(M):
   Run C(M,M) to get v, Init and Next
   Simulate D on v, Init, Next, Bad := (pc = <term>)
   If D says a separator exists:
     terminate
   If D says no separator exists:
     loop: goto loop

We now show $D$ cannot give a consistent answer on $S$ with the input $S$.  Start executing $S(S)$. $C$ terminates with $Init$ and $Next$ that can simulate $S$ with the input $S$. We now setup a correspondence between state $i$ of the execution of $S(S)$, $s_i$, and the $i$th variable assignment $\bar v_i = f(s_i)$ of the execution of $Next$ starting from $Init$. $S$ is deterministic by construction so by the properties of $C$, $Next$ must have unique successors on variable assignments and $Init$ is a variable assignment. (For reference, $f(s_0)=\bar v_i=Init$.)

Suppose $D$ says a separator exists. Let $\phi$ be such a separator. The execution of $S(S)$ then reaches $term$ in $k$ steps. (This includes executing $C$ and $D$.) Now $\bar v_1 \ldots \bar v_k$ is a counter example to $\phi$ being a separator as it reaches $pc = \left<term\right>$. $D$ gave an inconsistent answer.

Now suppose $D$ says no such separator exists. $S(S)$ then reaches the control state $loop$ in $k$ steps. All states after $k$ are then identical $s_{k+1}=s_{k+2}=\ldots$. The corresponding variables assignment sequence after $k$ must then assign each variable to the same constant. Let $\phi = \bigvee_{i=1}^{k+1} \bar v_i$. (Note: $\phi$ is now exactly the reachable variable assignments by $Next$ starting from $Init$.) Then

$Init \implies \phi$ as $Init$ is exactly $\bar v_1$.
$\phi \land Next \implies \phi'$ as $Next$ is deterministic and for all $i$ if $\bar v_i$ holds then $\bar v_{i+1}'$ holds.
$\phi \implies \lnot Bad$ as each variable assignment $\bar v_i$ implies $pc \neq \left<term\right>$.

Thus $\phi$ is an inductive invariant separator for $\left<\bar v,Init,Next, Bad\right>$ and $D$ gave an inconsistent answer.

$D$ must always give an inconsistent answer and thus a decision procedure does not exist.

Doing this exercise really made me appreciate Jerome Leroux's work on separators for vector addition systems.


NP-Complete problems that admit an efficient algorithm under the promise of a unique solution I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is either unsatisfiable or has a unique solution. Thus showing that SAT does not admit an efficient algorithm even under the promise of there being at most one solution.

Through a parsimonious reduction (a reduction that preserves the number of solutions), it is easy to see that most NP-complete problems (I could think of) also do not admit an efficient algorithm even under the promise of there being at most one solution (unless $\mathbf{NP = RP}$). Examples would be VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.

Hence I was wondering if there was any NP-complete problem that was known to admit a poly-time algorithm under a uniqueness promise.

No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NP-complete problem.
For all known NP-complete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).
Edit: This edit is solely to allow change of votes.


How to compute GCD efficiently? I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $j$ in $\Omega(\log j)$ airthmetic operations.

Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.

Question : How to compute set $A$ in $O(k)$ many arithmetic operations?

Using a linear sieve like this:

https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html

you can factor every number in range $j=2,3,..,k-1$ in linear time.

From there, you get an array with some prime divisor (the least for example) of each number in the range. Using that you can solve your problem by filling $A$ in order, and for each new number $j$ you just use the prime divisor of it, find it's greater exponent in $a$, and $j$, and use the previously calculated results in $A$ to get your answer. I'm not totally sure this last part it runs in linear time, but it should be possible.


Counterexample to max-flow algorithms with irrational weights? It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the wrong value! However, all the examples I could find in the literature [references below, plus references therein] use just a single irrational value: the conjugate golden ratio $\phi' = (\sqrt{5}-1)/2$, and other values that are either rational, or are rational multiples of $\phi'$. My main question is:

General Question: What happens with other irrational values?

For example (but don't feel like you have to answer all of these to post - I'd find interesting an answer to any one, or to other questions that fall under the above general question):

Given any $\alpha \in \mathbb{R}$, can one construct (or even show existence of) such counterexamples?

More weakly: are there examples known that use an irrational value essentially different from $\phi'$? That is, is there some $\alpha$ which is not a rational multiple of $\phi'$ (or more strongly not in $\mathbb{Q}(\phi')$) and such that there are counterexamples to Ford-Fulkerson and/or Edmonds-Karp where all the weights lie in $\mathbb{Q}(\alpha)$?

In the other direction, does there exist an irrational $\alpha$ such that Ford-Fulkerson (resp., Edmonds-Karp) halts with the correct value on all graphs whose weights are all from $\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$? (Or more strongly, from $\mathbb{Q}(\alpha)$?)

In all cases, I want to assume something like the real RAM model, so that exact arithmetic and exact comparisons of real numbers are done in constant time.
(There are other max-flow algorithms that are known to run in strongly polynomial time, even with arbitrary real weights, which is perhaps why this type of question may not have been further explored. But having just taught these algorithms in my undergrad algorithms class, I'm still curious about this.)
References

A minimal counterexample for Ford-Fulkerson was given by Zwick TCS 1999

A counterexample for Edmonds-Karp was given by Queyranne or Queyranne Math. Oper. Res. 1980, though I don't know if that one's minimal.

These can both be found in Jeff Erickson's lecture notes, with the first in Section 23.5 and the second as Exercise 14 of Lecture 23.

The answer is that for every irrational number $r$, there exists a network

with $n=6$ vertices and $m=8$ arcs,
in which seven arcs have integer capacity,
in which one arc has capacity $r$,
and on which Ford-Fulkerson may fail to terminate.

This has been proved in the paper

  Toshihiko Takahashi:
  "The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate"
  Journal of Information Processing 24, pp 390-394, 2016.
  Link: https://www.jstage.jst.go.jp/article/ipsjjip/24/2/24_390/_article


Are arithmetic circuits weaker than boolean? Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear  polynomial
$$
 f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,
$$
 and $B(f)$ denote the minimum size of a (non-monotone) boolean $(\lor,\land,\neg)$ circuit
computing the boolean version $f_b$ of $f$ defined by:
$$
 f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,.
$$

Are polynomials $f$ known for which $B(f)$ is smaller than $A(f)$?

If we consider monotone versions of circuits -- no Minus $(-)$ and no Not $(\neg)$ gates -- then $B(f)$ can be even exponentially smaller than $A(f)$: take, for example, the shortest s-t path polynomial $f$ on $K_n$;
then $B(f)=O(n^3)$ and $A(f)=2^{\Omega(n)}$. But what happens in the "non-monotone world"? Of course, big gaps cannot be known just because we do not have large lower bounds on $A(f)$. But perhaps there are at least some small gaps known?

NOTE (15.03.2016) In my question, I do not specified how large coefficients $c_e$ are allowed. Igor Sergeev remembered me that, for example, the following (univariate) polynomial $f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$ has $A(f)=\Omega(m^{1/2})$ (Strassen and people of his group). But $B(f)=0$ for this polynomial, since $f_b(z)=z$. We can obtain fron $f$ a multivariate polynomial $f'(x_1,\ldots,x_n)$
of $n=\log m$ variables using using Kronecker substitution. Associate with every exponent $j$ a monomial $X_j=\prod_{i:a_i=1}x_i$, where $(a_1,\ldots,a_n)$ are the 0-1 coefficients of the binary representation of $j$. Then the desired polynomial
is $f'=\sum_{j=1}^m c_j X_j$, and we have that
$$
A(f')+n\geq  A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.
$$
But the boolean version of $f'$ is just an OR of variables, so $B(f')\leq n-1$, and we have an even exponential gap. Thus, if magnitude of coefficients can be triple-exponential in the number $n$ of variables then the gap $A(f)/B(f)$ can be shown to be even exponential. (Actually, not the magnitude itself -- more the algebraic dependence of the coefficients.)
This is why the real problem with $A(f)$ is the case of small coefficients (ideally, only 0-1). But in this case, as Joshua recalled, the lower bound $A(f)=\Omega(n\log n)$ of Strassen and Baur (with 0-1 coefficients) remains the best what we have today.

The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given bipartite graph has a perfect matching, which has poly-size circuits.

[Summarizing the comments below:] Despite this example being conditional, nothing more than a logarithmic gap can be expected unconditionally at the moment, since $\Omega(n \log n)$ is still the best known lower bound on general algebraic circuits. As pointed out by Stasys, this logarithmic gap is achieved by the function $\sum_{i=1}^n x_i^n$ (requires algebraic circuits of size $\Omega(n \log n)$ by Baur-Strassen), whose Boolean-ized version is just $x_1 \vee x_2 \vee \dotsb \vee x_n$.


From edge-disjoint paths to independent paths Let $\mathcal{G}_k$ denote the set of all graphs that contain two vertices $x,y$
and $k$ edge-disjoint $x-y$ paths.

Define $f(k)$ to be the maximum such that for every graph $G\in \mathcal{G}_k$
there are two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths in $G$.

Here, a set of paths is independent if none contains an internal vertex of another.

Are any lower bounds for $f(k)$ known in the literature?

In particular, I need $f(3)=3$ in an algorithm where I need to find some obstructions in a graph.
This is not hard to prove, but I'm wondering whether it is known in the literature, maybe as a special case of a more general theorem.

As a different formulation, how large can you make $f(k)$ in the following statement?

  If $G$ is an undirected graph containing two vertices $x,y$ and $k$ edge-disjoint $x-y$ paths, then $G$ contains two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths.

It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See arXiv:1203.4483 for a proof.


Complexity of computing invertible functions with reversible circuits Consider an invertible function that maps an $N$ bit string $x$ to an $N$ bit string $f(x)$. Let us use $F(x)$ to denote the inverse of the function $f(x)$, such that $F(f(x)) = x$.

Suppose that I know a circuit with ${\rm poly} \, N$ reversible Boolean logic gates that can compute this function. However, it also produces an additional output string $g(x)$ (with may be a copy of the input, for example).

Given this scenario, I have two questions that I believe to be equivalent.

Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit that only outputs $f(x)$?
Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit to output $F(x)$ (and may or may not also output some $G(x)$)?

I have some great news. If you know how to compute a function and its inverse, then you may compute the function reversibly without producing any garbage information (though the computation needs to temporarily use ancilla bits for scratchwork). Let me informally state and prove a couple of results.

$\textbf{Theorem 1:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ is a function which is easy to compute.
Then there exists a known and easy to compute reversible circuit $H:\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x}))$ on each input $\mathbf{x}$

$\mathbf{Proof:}$ It is a standard process to turn a conventional irreversible circuit into a reversible circuit at the expense where one produces a lot of garbage information along with the desired output (I will leave the process of simulating irreversible gates such as the AND gate and the OR gate by saving the inputs and using reversible gates such as Toffoli gates or Fredkin gates). Therefore, there exists a circuit $C$ along with a function $L$ such that $$C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{z})=
(0,f(\mathbf{x}),L(\mathbf{x}),\mathbf{z})$$ for each $\mathbf{x},\mathbf{z}$. Let $N$ be the circuit where $N(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{z})=
(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{x}\oplus\mathbf{z})$. Then
let $H=C^{-1}\circ N\circ C$. Then

$$H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$

$$=C^{-1}\circ N\circ C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$

$$=C^{-1}\circ N(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),\mathbf{0})$$

$$=C^{-1}(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),f(\mathbf{x}))$$

$$=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x})).$$

Q.E.D.

The technique used in Theorem 1 is known as the compute ($C$)-copy ($N$)-uncompute ($C^{-1}$) technique. This technique is essential for reversible algorithms and quantum algorithms. Since reversible circuits cannot delete any information, for a non-bijective function $f$, one must save the input $\mathbf{x}$. However, the following theorem shows that it is possible to reversibly compute a bijective function without needing to save the input $\mathbf{x}$.

$\textbf{Theorem 2:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijective function with inverse $f^{-1}$. Suppose furthermore that an irreversible circuit that computes $f$ and an irreversible circuit that computes $f^{-1}$ are known. Then there exists a reversible circuit
$K:\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}$ such that
$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{0},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit string $\mathbf{x}.$

$\mathbf{Proof:}$ By Theorem 1, there exists a reversible circuit $H$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{x},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit input $\mathbf{x}$.

Now, there exists a reversible circuit $D:\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}$ along with a function
$L:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ such that
$D(\mathbf{y},\mathbf{0})=(f^{-1}(\mathbf{y}),L(\mathbf{y}))$ for each $\mathbf{y}\in\{0,1\}^{n}$. Let $M:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}$ be the function defined by $M(\mathbf{x},\mathbf{y})=(\mathbf{x}\oplus\mathbf{y},\mathbf{y})$.

Let
$$K=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)\circ H.$$

Then $K$ is easily computable by a reversible circuit. However, for each $\mathbf{x}\in\{0,1\}^{n}$, we have
$$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)\circ H(\mathbf{x},\mathbf{0},\mathbf{0})$$

$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)(\mathbf{x},f(\mathbf{x}),\mathbf{0})$$

$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})(\mathbf{x},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$

$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})(\mathbf{x},\mathbf{x},L(f(\mathbf{x}))$$

$$=(\mathrm{Id}_{n}\times D^{-1})(\mathbf{0},\mathbf{x},L(f(\mathbf{x}))$$

$$=(\mathrm{Id}_{n}\times D^{-1})(\mathbf{0},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$

$$=(\mathbf{0},f(\mathbf{x}),\mathbf{0}).$$ Q.E.D.


The "multifunction" version of ZPP? I would like to ask if there is a name for the class of multifunctions, each of which can be computed by a probabilistic polytime Turing machine $M$ satisfying the following two conditions:

$M$ returns a correct output of the function with high probability
$M$ can either return a correct answer or "don't know", and never return an incorrect answer.

Note that although this sounds like $\mathsf{ZPP}$, it is not since $\mathsf{ZPP}$ is the class of predicates, and not multifunctions. I really appreciate any pointer to the right sources.

I think what you're looking for is Las Vegas algorithms. I do not know that the class of functions computable by polytime Las Vegas algorithms has an abbreviation beyond "Las Vegas polynomial time".

As pointed out by Tsuyoshi Ito in the comments, $ZPP$ is exactly the class of decision problems decidable in Las Vegas polynomial time.


Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known such that $\operatorname{per}(A) = \det(B)$? Any references on this with explicit examples?

Some restrictions could be the following cases:

Case $(1)$ Only linear functionals are allowed as entries of $B$.

Case $(2)$ Non-linear functionals are allowed provided each term has atmost $O(log(n))$ degree (degree is sum of degree of variables) where $n$ is the size of the matrix involved. In our case, upto degree $2$.

[EDIT]

For consistency, I switched the notations from $c(n)$ to $dc(n)$.
It was asked by v s in the comments whether my answer generalize to higher dimensions. It does and gives an upper bound over any field:
$$dc(n)\le 2^n-1.$$
See my draft on this: An Upper Bound for the Permanent versus Determinant Problem.

[/EDIT]

[A side comment: I think you could edit your previous question instead of creating a new one.]

I have the following answer for you:

$$\operatorname{per}\begin{pmatrix} a&b&c\\d&e&f\\g&h&i\end{pmatrix}=
    \det\begin{pmatrix}
    0 & a & d & g & 0 & 0 & 0 \\
    0 & 1 & 0 & 0 & i & f & 0 \\
    0 & 0 & 1 & 0 & 0 & c & i \\
    0 & 0 & 0 & 1 & c & 0 & f \\
    e & 0 & 0 & 0 & 1 & 0 & 0 \\
    h & 0 & 0 & 0 & 0 & 1 & 0 \\
    b & 0 & 0 & 0 & 0 & 0 & 1
    \end{pmatrix}$$

Note that looking for such references about explicit examples, I could'nt find any and thus the example I give you is an example I built.

This question you are asking is commonly called the "Permanent vs Determinant problem". Suppose we are given an $(n\times n)$ matrix $A$, and we want the smallest matrix $B$ such that $\operatorname{per} A=\det B$. Let us denote by $dc(n)$ the dimensions of the smallest such $B$. Here are historical results:

[Szegö 1913] $dc(n)\ge n+1$
[von zur Gathen 1986] $dc(n)\ge n\sqrt 2-6\sqrt n$
[Cai 1990] $dc(n)\ge n\sqrt 2$
[Mignon & Ressayre 2004] $dc(n)\ge n^2/2$ in characteristic $0$
[Cai, Chen & Li 2008] $dc(n)\ge n^2/2$ in characteristic $\neq 2$.

This shows that $5\le dc(3)\le 7$ (the upper bound is the matrix given above).

As I am lazy, I just give you one reference where you can find the other ones. It is the most recent paper I cited, by Cai, Chen and Li: A quadratic lower bound for the permanent and determinant problem over any characteristic $\neq 2$.

If you read French, you can also have a look to my slides on this subject: Permanent versus Déterminant.


Comparing SAT to MCSP reduction class separations and faster SAT class separations? Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $NQuasiP\neq ZPP$.
Now if $SAT$ reduces $MCSP$ by $LOGSPACE$ $m$-reductions we infer a stronger separation of $PSPACE\neq ZPP$ by https://drops.dagstuhl.de/opus/volltexte/2015/5074/.

I am wondering if $SAT$ is in $TISP(QuasiPTIME, QuasiLOGSPACE)$ will provide $PSPACE\not\subseteq P/poly$ and $PSPACE\neq ZPP$?

I think at least $SAT$ in $TISP(PTIME, LOGSPACE)$ will provide $PSPACE\not\subseteq P/poly$ and $PSPACE\neq ZPP$.

Does faster $SAT$ provide implications to $SAT$ to $MCSP$ reductions or vice versa?

If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot more unlikely than the lower bound conclusion, in my mind, so I'm not sure how interesting this implication is.

(Note SAT in QuasiP would imply EXP has functions of maximum circuit complexity, for similar reasons.)

Definitely if SAT has fast enough algorithms then MCSP has faster algorithms due to SAT's NP-completeness. Beyond that I don't see an immediate connection


Alternate notion of complexity based on gap between brute-force and the best algorithm? Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space.  This means that the problem must be easy in two senses: first, the problem can be solved in a polynomial number of steps, and second, the solution space must be very structured because the runtime is only polylogarithmic in the number of possible solutions.

However, sometimes these two notions diverge, and a problem is easy only in the first sense.  For instance, a common technique in approximation algorithms and parameterized complexity is (roughly) to prove that the solution space can actually be restricted to a much smaller size than the naive definition and then use brute-force to find the best answer in this restricted space.  If we can a priori restrict ourselves to, say, n^3 possible answers, but we still need to check each one, then in some sense such problems are still "hard" in that there's no better algorithm than brute-force.

Conversely, if we have a problem with a doubly-exponential number of possible answers, but we can solve it in only exponential time, then I'd like to say that such a problem is "easy" ("structured" may be a better word) since runtime is only log of the solution space size.

Does anyone know of any papers that consider something like hardness based on the gap between an efficient algorithm and brute-force or hardness relative to the size of the solution space?

One problem with formalizing the question is that the phrase "solution space for Problem A" is not well-defined. The definition of a solution space needs a verifier algorithm which, given an instance and a candidate solution, verifies whether or not the solution is correct. Then, the solution space of an instance wrt to a verifier is the set of candidate solutions that make the verifier output "correct".

For example, take the problem SAT0: given a Boolean formula, is it satisfied by the all-zeroes assignment? This problem is trivially in polynomial time, but its solution space can vary wildly, depending on which verifier you use. If your verifier ignores the candidate solution and just checks if all-zeroes works on the instance, then the "solution space" for any SAT0 instance on that verifier is trivial: it is all possible solutions. If your verifier checks to see if the candidate solution is a satisfying assignment, then the solution space of a SAT0 instance can actually be quite complex, arguably as complex as any SAT instance's solution space.

That said, the problem of "avoiding brute-force search" can be formalized in the following way (as seen in the paper "Improving exhaustive search implies superpolynomial lower bounds"). You are given a verifier algorithm that runs in time $t(n,k)$, on instances of size $n$ and candidate solutions of $k$ bits. The question is, *on arbitrary instances of size $n$, can we determine if there is a correct solution (wrt this verifier) with at most $k$ bits, in much less than $O(2^k t(n,k))$ time?

Note $O(2^k t(n,k))$ is the cost of trying all strings of length up to k, and running the verifier. So the above can be seen as asking whether we can improve on brute-force search for the given verifier. The area of "exact algorithms for NP-hard problems" can be seen as a long-term effort to study the difficulty of improving on brute-force search for certain very natural verifiers: e.g. the question of finding better-than-$2^n$ algorithms for SAT is the question of whether we can always improve over brute-force search for the verifier that checks if the given candidate solution is a satisfying assignment to the given SAT instance.

The paper shows some interesting consequences of improving on brute-force search for some problems. Even improving on brute-force search for "polynomial-size solution spaces" would have interesting consequences.


Why would the term "dynamically typed" be considered a misnomer? In the book "Types and Programming Languages", the author writes:

The word "static" is sometimes added explicitly - we speak of a "statically typed programming language", for example - to distinguish the sorts of compile-time analyses we are considering here from the dynamic or latent typing found in languages such as Scheme, where run-time type tags are used to distinguish different kinds of structures in the heap. Terms like "dynamically typed" are arguably misnomers and should probably be replaced by "dynamically checked", but the usage is standard.

I am not sure if I understand this. Does the author mean that, in type theory, all programs are "statically typed"?

The discussion in the section surrounding that paragraph in Pierce's book explains why this is so. In particular, consider the definition of "type system" given on the page before:

A type system is a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.

Note how aspects like "syntactic method" and "classifying phrases" mean that it applies to "source" programs, i.e., inherently is a static notion. Moreover, in actual type theory, programs that do not "type-check" are not even considered programs. The type system defines the set of well-formed programs. Something that's ill-typed has no meaning.
One could argue that this is the wrong definition. But it is shared by most researchers in the field and certainly by the ones working on type theory. It matches the notion of a "type" as established in mathematics and logic (lambda calculus, type theory). On the other hand, it would be difficult to come up with a sufficiently accurate definition of "type system" that would encompass "dynamic typing" without bordering on technically meaningless.
So from that technical point of view, a dynamic language is untyped, in the same way the untyped lambda calculus is (or equivalently, it has only one single type, such that every program is accepted as well-typed). Dynamic checks are not really on types but on the shape of values, which sometimes carry type-like "tags".


Church's Theorem and Gödel's Incompleteness Theorems I have recently been reading up on some of the ideas and history of the ground-breaking work done by various logicians and mathematicians regarding computability. While the individual concepts are fairly clear to me, I'm am trying to get a firm grasp of there inter-relations and the abstract level at which they are all linked.

We know that Church's theorem (or rather, the independent proofs of Hilbert's Entscheidungsproblem by Alonzo Church and Alan Turing) proved that in general we cannot calculate whether a given mathematical statement in a formal system is true or false. As I understand, the Church-Turing thesis provides a pretty clear description of the equivalence (isomorphism) between Church's lambda calculus and Turing machines, hence we effectively have a unified model for computability. (Note: As far as I know, Turing's proof makes use of the fact that the halting problem is undecidable. Correct me if I'm wrong.)

Now, Gödel's first incompleteness theorem states that not all statements in a consistent formal system with sufficient arithmetic power may be proven or disproven (decided) within this system. In many ways, this appears to me to be saying exactly the same thing to me as Church's theorems, considering lambda calculus and Turning machines are both effectively formal systems of sorts!

This is however my holistic interpretation, and I was hoping someone could shed some light on the details. Are these two theorems effectively equivalent? Are there any subtleties to be observed? If these theories are essentially looking at the same universal truth in different ways, why were they approached from such different angles? (There were more or less 6 years between Godel's proof and Church's). Finally, can we essential say that the concept of provability in a formal system (proof calculus) is identical to the concept of computability in recursion theory (Turing machines/lambda calculus)?

First, I suggest you read Kleene's "Metamathematics" as a good book on these topics. First two chapters of volume I of Odifreddi's "Classical Recursion Theory" can also be helpful in understanding the relation between these concepts.

We know that Church's theorem (or rather, the independent proofs of Hilbert's Entscheidungsproblem  by Alonzo Church and Alan Turing) proved that in general we cannot calculate whether a given mathematical statement in a formal system is true or false.

I think you are referring to Church's theorem that the set of theorems of first order logic is not decidable. It is important to note that the language is first order.

As I understand, the Church-Turing thesis provides a pretty clear description of the equivalence (isomorphism) between Church's lambda calculus and Turing machines, hence we effectively have a unified model for computability.

No. The equivalence if lambda-computability and Turing-computability is a theorem of Kleene. It is not a thesis. It is considered as evidence supporting Church's thesis.

Note: As far as I know, Turing's proof makes use of the fact that the halting problem is undecidable. Correct me if I'm wrong.
Now, Gödel's first incompleteness theorem states that not all statements in a consistent formal system may be proven within this system. In many ways, this appears to me to be saying exactly the same thing to me as Church's theorems, considering lambda calculus and Turning machines are both effectively formal systems of sorts!

No. Godel's theorem states that for every $\omega$-consistent, recursively enumerable theory which contains enough arithmetic, there is a sentence $\varphi$ s.t. $\varphi$ and $\lnot \varphi$ are not provable in it.
This does not state the same thing. It does not say anything about set of theorems of the theory being undecidable.

This is however my holistic interpretation, and I was hoping someone could shed some light on the details. Are these two theorems effectively equivalent? Are there any subtleties to be observed? If these theories are essentially looking at the same universal truth in different ways, why were they approached from such different angles? (There were more or less 6 years between Godel's proof and Church's).

Over the years there has been lots of abuse of Godel's theorems (and similar theorems). One should be very careful in making interpretations of them. As far as I have seen, the abuses are usually result of forgetting to mention some condition in the theorem or combining the theorems by some other beliefs. A careful look shows that theses theorems, although related, are not equivalent.

Finally, can we essential say that the concept of provability in a formal system (proof calculus) is identical to the concept of computability in recursion theory (Turing machines/lambda calculus)?

I don't understand what you mean by "identical". Certainly there are many relations between computability and provability. I may be able to make a more helpful comment if you clarify what you mean by these being identical.
update
Lets consider the set of well-formed sentences in the language of arithmetic as $L$. Let $T$ be (the axioms of) a theory satisfying the conditions of first incompleteness theorem. Let $Thm(T)$ be the set of theorems of the theory $T$ and $\lnot Thm(T)$ be the set of sentences whose negation is a theorem of $T$. Let $True$ be the set of sentences that are true in the standard model, and $False$ the set of false sentences. A sentence is in $True$ iff its negation is in $False$. Also every sentence is either true or false, i.e. $L = True \cup False$.
The Godel's incompleteness theorem states that $Thm(T) \cup \lnot Thm(T)$ is a proper subset of $L$. Therefore truth in the standard model and provability in $T$ are different.
Note that $Thm(T)$ is r.e., Church's theorem states that $Thm(T)$ is not decidable.
On the relation between provability in formal system and computability. One is the following: If the system is effective, then the set of derivable expression in it is r.e., and the system is a special case of a grammar. Grammars is another way for defining the concept of computable which is equivalent to Turing machine computability.


Models of computation strictly between classical and quantum in terms of query complexity It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity.

  Are there other models (natural or artificial) that are strictly between the quantum and classical in terms of query complexity?

The seperation can be on

specific problems: model X computes function $f$ with strictly more queries than quantum, but fewer queries than the lower bound on classic, or
different problems: model X computes function $f_1$ with strictly more queries than quantum, but computes function $f_2$ with fewer queries than classical.

In both cases, we want for every function $f$ to have $Q_2(f) \leq X(f) \leq R_2(f)$ to avoid examples that are hard to compare to quantum (like the certificate complexity of non-deterministic queries). Here $Q_2(f)$ (and $R_2(f)$) is the two-sided $1/3$-error quantum (and classical randomized) query complexity and the inequalities are within constant factors.

One easy way to come up with such a model is to first create a restricted model of quantum computation that can still do something non-classical, and then just give it classical computation for free.

An examples of this strategy is the one clean qubit model (along with a BPP machine). Some references: On the Power of One Bit of Quantum Information, Computation with Unitaries and One Pure Qubit and Estimating Jones polynomials is a complete problem for one clean qubit.

Another example would be to have a log-depth (or polylog depth) quantum circuit with access to a classical computer. This will yield something like $BPP^{BQNC}$.


Comparing two products of lists of integers? Suppose I have two lists of positive integers of bounded manitude, and I take the product of all elements of each list. What's the best way to determine which product is larger?

Of course I can simply compute each product, but I'm hoping there's a more efficient approach, as the number of digits in the products will increase linearly with the number of terms, so that the whole computation is quadratic.

If I were adding instead of multiplying, I could use a "zippering strategy" of incrementally adding entries from the first list and subtracting from the second, circumventing the need to compute the (large) overall sums. The analogous techniques for products would be to sum the logarithms of the entries, but the problem now is that computing the logs requires use of inexact arithmetic. Unless there's some way to prove the numerical error is irrelevant?

(I understand the description of the problem so that the input numbers are bounded by a constant, so I will not track dependence on the bound.)
The problem is solvable in linear time and logarithmic space using sums of logarithms. In more detail, the algorithm is as follows:

Using binary counters, count the numbers of occurrences of each possible input number in both lists.

This takes time $O(n)$, and the counters use space $O(\log n)$, as each counter is bounded by $n$ in value.
Let $p_1,\dots,p_k$ be the primes below the $O(1)$ bound. By distributing each counter for a number $a$ to the prime factors of $a$ (with appropriate multiplicity), and subtracting the counts for one list from the other list, we obtain the following in time $O(\log n)$:

Compute integers $\beta_1,\dots,\beta_k$ with $O(\log n)$ bits such that the problem is equivalent to determining the sign of $\Lambda:=\sum_{i=1}^k\beta_i\log p_i$.

If $\beta_1=\dots=\beta_k=0$, answer that the products are equal.

Otherwise $\Lambda\ne0$. By Baker’s theorem, we can lower bound
$$|\Lambda|>2^{-C\log n}$$
for a certain constant $C$. Thus, the following correctly computes the sign of $\Lambda$:

Output the sign of $\sum_{i=1}^k\beta_i\pi_i$, where $\pi_i$ is an approximation of $\log p_i$ to $m:=C\log n+k+1$ bits of accuracy.

Let $M(m)$ be the cost of multiplication of two $m$-bit integers. The current best bound is $M(m)=O(m\,\log m\,2^{O(\log^* m)})$, but here it would not make much difference even if we use the trivial $O(m^2)$ multiplication algorithm. We can compute $\log p_i$ to $m$ bits of accuracy in time $O(M(m)\log m)$ using AGM iteration (see e.g. here), and then evaluating $\sum_i\beta_i\pi_i$ takes time $O(M(m))$. Overall, step 4 takes time $O(M(m)\log m)\subseteq O(\log n\,\mathrm{poly}(\log\log n))$.
Thus, the running time of the algorithm is dominated by $O(n)$ of the first step.


Size of MAXCUT from eigenvalues Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?

Can the estimates provide sharp lower bound to MAXCUT?

Yes, there is a connection between the spectrum of the graph and the size of the maximum cut. It might be easiest to see this with the normalized graph Laplacian, $L = I - D^{-1/2}AD^{-1/2}$, where $I$ is the identity, $A$ is the adjacency matrix of the graph $G = ([n], E)$ and $D$ is the diagonal matrix defined by $D_{ii} = d_i$, the degree of vertex $i$. The largest eigenvalue of $L$ is

$$\lambda_{n-1} = \max_x\frac{x^TLx}{x^Tx} = \max_{x}\frac{\sum_{(i, j) \in E}{(x_i - x_j)^2}}{\sum_{i}{d_i x_i^2}}.$$

Because $(x_i - x_j)^2 \leq 2x_i^2 + 2x_j^2$ by Cauchy-Schwarz, $\lambda_{n-1} \leq 2$. Equality is achieved if and only if for each edge $(i, j)$, $x_i = -x_j$, which means that $\lambda_{n-1}= 2$ only if the graph has a bipartite connected component, i.e. a connected component whose maximum cut is equal to the number of edges in the component.

For a robust version of this result, see Luca Trevisan's paper. He shows that

$$
\lambda_{n-1} \geq 2\frac{\text{MaxCut}}{m},
$$

(where $m$ is the number of edges of the graph) and if $\lambda_{n-1} \geq 2(1-\epsilon)$, then there exits a set of vertices $S$ and a partition $(S_1, S_2)$ of $S$ such that

$$
|e(S_1, S_2)| \geq \frac{1}{2}(1-\sqrt{16\epsilon})\text{vol}(S),
$$
where $\text{vol}(S) = \sum_{i \in S}{d_i}$ and $e(S_1, S_2)$ is the set of edges with one endpoint in $S_1$ and the other in $S_2$.

Note that the second bound does not necessarily lower bound the max cut in a useful way: it only lower bounds the maximum cut of the set $S$ in terms of $\text{vol}(S)$. This is unavoidable: think of a graph that's the disjoint union of an edge and a large graph with small maximum cut, say a clique. The maximum cut of the graph is very close to $m/2$, which is the minimum possible value of the max cut of a graph with $m$ edges. However, $\lambda_{n-1} = 2$, the maximum possible value of $\lambda_{n-1}$. In other words, while $\lambda_{n-1}$ is a relaxation of the maximum cut (up to appropriate rescaling), the gap is arbitrarily close to 2, and a 2-approximation to max cut is trivial.

Nevertheless, in the paper Luca uses the spectral result to design a recursive approximation algorithm for max cut. This is one cool thing about the paper: it uses a relaxation that, unlike the SDP relaxation of Goemans and Wiliamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor.