Public-key encryption without the assumption that $P \neq NP$ I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure under CPA (which has equal power as eavesdropper in the public-key area) without the assumption that $P \neq NP$.

If $P=NP$ the task to compute a decision of "whether a secret key $S_k$ is the complement of the given public key $P_k$?" takes a poly time (where complement may be refer to inverse in the Euler group in RSA or discrete-log in El-Gamal or any other term but my question is general) is equal (in regard to the time complexity) to the task of "finding the actual complement $S_k$ from a given $P_k$ and additional public settings (as the group description etc.)" which will also take poly time.

Does my last state seems logical/correct?
How can I further formalize it?

In a CPA game, a key pair $(sk,pk)$ is generated, and $pk$ is given to the adversary.
The adversary outputs a pair of messages $(m_0,m_1)$ in the message space, such that $|m_0|=|m_1|$. A random bit $b \in \{0,1\}$ is then generated, and $m_b$ is encrypted and returned as the cipher $c = E_{pk}(m_b ; r)$, where $r$ is the randomness used for encryption. The task of the adversary is to guess $b$ correctly.

Lemma. There do not exist $r_0$ and $r_1$ such that $c = E_{pk}(m_0 ; r_0)$ and $c = E_{pk}(m_1 ; r_1)$.

Proof. If such $r_0$ and $r_1$ exist, $c$ can be decrypted to both $m_0$ and $m_1$, which contradicts the uniqueness of decryption.

Note. In some texts, uniqueness of decryption is not required. It is only required that decryption is unique with overwhelming probability. In such cases, the above lemma must be changed accordingly.

Now, assume that $\mathsf{P = NP}$. The adversary can then find in polynomial time whether there exists an $r$ (i.e., an $\mathsf{NP}$-witness) such that $c = E_{pk}(m_0 ; r)$. If so, the adversary outputs $b=0$. Otherwise, he outputs $b=1$.

Therefore, if $\mathsf{P = NP}$, there exists a polynomial-time adversary which always succeeds in the CPA game, and no encryption scheme will be CPA-secure.


Is there an efficient algorithm to determine the parity of the longest path in a graph? Finding the longest path in a graph is intractable problem. The decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in a graph?

The algorithm should output YES if the length of the longest path is even otherwise the output is NO. Also, What is the complexity if we restrict the input to cubic graphs?

EDIT 1: I moved some of my comments here as requested by a friend.

My problem is LPEP={graph G: the longest path in G has even length }. The answer of Gadi A proves intractability and I accepted it. I was waiting for Karp reduction.

Cross posted on Math StackExchange

Based on Gadi's answer on Math.SE (which proves NP-hardness using a Cook reduction), here is a proof of NP-hardness using a Karp reduction (as requested).
General case
The reduction is from Hamiltonian Cycle through Hamiltonian Path.
Part 1: Hamiltonian Cycle $\le_m^P$ Hamiltonian Path
We begin with a graph $G$ with $n$ vertices and want to know if it contains a Hamiltonian cycle.  We use a standard reduction to Hamiltonian Path (see Theorem 8.19 of Algorithm Design, which gives the directed graph version). Specifically,

pick a vertex $v \in G$,
add a vertex $v_0$,
for each edge $(v, u)$, add an edge $(v_0, u)$,
add vertices $u_1$ and $u_2$, and
add edges $(v, u_1)$ and $(v_0, u_2)$.

Call this graph $G_1$. If $G$ has a Hamiltonian cycle, then $G_1$ has a Hamiltonian path (that with end points $u_1$ and $u_2$). If $G_1$ has a Hamiltonian path, then it's end points must be $u_1$ $u_2$ since they have degree one, so other vertices in the Hamiltonian path give a Hamiltonian cycle when equating $v$ and $v_0$.
Part 2: Hamiltonian Path $\le_m^P$ Parity of Longest Path Even
This reduction continues the one started above, so we have the graph $G_1$ with $n_1 = n + 3$ vertices.
If $n_1$ is odd, then a Hamiltonian path in $G_1$ (if one exists) would have to be of even length. In this case, we use the same reduction as Gadi, which adds a disjoint path of length $n_1 - 2$ to $G_1$ to form a graph $G_2$.
If $n_1$ is even, then a Hamiltonian path in $G_1$ (if one exists) would have to be of odd length. The case of odd $n_1$ is better, so we reduce to it by adding a vertex $w$ and edge $(w, u_1)$, forming a graph $G_2$. Now, a Hamiltonian path in $G_1$ (if one exists) would have to be of even length (and have end points $w$ and $u_2$ since they both have degree one), so we complete the reduction as above by adding a disjoint path of length $n_1 - 1$ to form a graph $G_2$.
If $G_1$ contains a Hamiltonian path, then the length of the longest path in $G_2$ is even (of length $n_1 - 1$ when $n_1$ is odd and of length $n_1$ when $n_1$ is even). If $G_2$ contains a longest path of even length, then $G_1$ must contain a Hamiltonian path since we know there is a path of odd length that is one shorter than the length required in a Hamiltonian path.
Restricted to cubic graphs
I do not see how the reduction for the general case can be made to work for cubic graphs since all cubic graphs have an even number of vertices. However, your requirement that the algorithm should say Yes iff the parity of the longest path is even is contrary what I have always heard regarding parity, which is the algorithm says Yes iff the parity is odd.
Restricted to cubic (and planar) graphs when Yes iff longest path of odd parity
The reduction for the general case can be made to work for cubic planar graphs when the algorithm says Yes iff the parity of the longest path is odd.
This time, we reduce from Hamiltonian Path directly. Thus, we begin with a cubic planar graph $G$ with $n$ vertices and want to know if it contains a Hamiltonian path.
Since $n$ is even, we want to add a disjoint graph with a longest path of size $n-2$. This is possible for $n \ge 10$ as pictured...

...since that is the shortest (even) length of the longest path possible via this path gadget.
For $n < 10$, we do a brute force search for the existence of a Hamiltonian path in $G$ and add the smallest path gadget if we don't find one.


Minimum distance of a code Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over $\mathbb{F}_{2^l}$) quasi-cyclic  of rate q/q+1. Parity check matrix for such codes have a structure
$H=[I|C_1|C_2|...|C_m]$ where each $C_¡$ is a from class of circulant matrices. It may be useful that one can treat these codes as modules.
Or even if there are any approximate algoruihms for this ?

The problem for an arbitrary binary code is NP-hard.

Reference: Alexander Vardy, “The Intractability of Computing
the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757--1766.


Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm Given $p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$ such that coefficients of $p,q$ are bounded by $B$, does $p\equiv q$ hold?

Schwartz-Zippel lemma applies here since it holds for general fields and $\Bbb Z\subset\Bbb Q$ and there is an efficient randomized algorithm for this problem.

We expect this problem to have efficient derandomization.

What is the consequence if this problem does not have an efficient derandomization?

Since PIT is in $\mathsf{coRP}$, if there is no efficient derandomization then $\mathsf{P} \neq \mathsf{RP}$ (and, in particular, $\mathsf{P} \neq \mathsf{NP}$, but that's not so surprising, since we expect that to be true anyways). This also implies, of course, that $\mathsf{P} \neq \mathsf{BPP}$, so anything which implies $\mathsf{P} = \mathsf{BPP}$ becomes false. For example, sufficiently strong pseudorandom number generators do not exist, and $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$ would have subexponential size circuits!


Complexity results about locally bipartite graphs A graph is locally bipartite if the open neighborhood of
every vertex induces a bipartite graph.
(According to searches the same name might be used for
something else related to surfaces).

  Which NP-hard for general graphs problems become polynomial
  for locally bipartite graphs and which remain NP-hard?

Especially interested in clique and coloring.

  Are there inclusions between locally bipartite and other
  graph classes?

Added According to a paper they are also called "almost bipartite" and their complements
are generalized line graphs which are claw free.

Locally bipartite graphs obviously contain the locally independent (= triangle-free) graphs. According to graphclasses.org, most of the standard graph problems are already NP-complete for triangle-free graphs, and therefore also NP-complete for locally bipartite graphs. The two exceptions are clique (which is obviously polynomial for locally bipartite graphs because the maximum clique is a triangle) and clique cover, which is polynomial for triangle-free graphs but might be harder for locally bipartite graphs.


Parallel algorithms for reachability in directed planar graphs Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors.

What is the best known parallel algorithm for st-connectivity in directed planar graphs ?

Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial).

This question is related to one of my previous questions. My previous question is about general directed graphs which are not necessarily planar.

See

Kao, Ming-Yang; Klein, Philip N. (1993), Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. System Sci. 47 (1993), no. 3, 459–500.

Their Theorem 10 gives a deterministic CRCW algorithm for $st$-reachability in planar digraphs with $O(n)$ processors and $O(\log^3 n)$ time. Searching Google scholar for other papers that cited theirs, I didn't see anyone else with improvements to this.


Reference for a class of graphs that preserve subgraph distances when ordered Let us say that a graph $G$ has the property $M$ if its vertices can be ordered $v_1, v_2, \ldots v_n$ in such a way that the graph $H_i$ induced by the vertices $\{v_1, \ldots, v_i\}$ has $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ for all $j,k \leq i$. In other words adding the next vertex in our ordering does not affect the distance metric of the current graph.

An example of such a graph is the regular $n \times n$ grid.

Does this property or class of graphs have a name? Have they been studied?

I don't have an answer for your whole class of graphs, but three subclasses of graphs that have this property are the distance-hereditary graphs, chordal graphs, and median graphs.

Distance-hereditary graphs are defined by the property that every connected induced subgraph has the same distances. So you can pick an arbitrary starting vertex $v_1$ and then choose each successive vertex to be any not-already-chosen vertex that is adjacent to a previously-chosen vertex.

The chordal graphs are the graphs that have an ordering with the property that each successive vertex, when added, has a clique for its neighbors. This ordering is obviously distance-preserving.

Similarly, median graphs (including your grid example) have the property that, for any breadth-first ordering, each vertex has a hypercube neighborhood at the time it is added. (See pages 76–77 of Eppstein et al, "Media Theory", Springer, 2008). Again, this property means that the addition cannot change the distances among the previous vertices.

There's a class of graphs that I don't know a name for, generalizing both chordal and distance-hereditary graphs, that can be recognized in polynomial time and that have your property. They are the connected graphs that can be built up from a single vertex by adding vertices one by one, where the neighbors of each new vertex are a subset of one of the closed neighborhoods of the previous graph. They are almost (but not quite) the same as the dismantlable graphs, the difference being that the new vertex does not have to be adjacent to the vertex whose neighborhood is being copied. An elimination ordering of a chordal graph is a construction of this type where each new vertex chooses a clique subset of a neighborhood. Similarly distance-hereditary graphs have a construction of this type where the neighbors of each new vertex are an entire closed neighborhood, an open neighborhood, or a single vertex. Each new vertex can't change the distances of the previous vertices, so this construction sequence has the property you're looking for.

If you define a vertex v to be "removable" if it could be the last one in this sequence (it has an open neighborhood that is a subset of someone else's closed neighborhood) then removing other removable vertices doesn't change the removability of v: if v's neighborhood is a subset of u's, and we remove u as having a neighborhood that is a subset of w's, then v is still removable because its neighborhood is still a subset of w's. Therefore, the sequences of removal steps that we can follow to take a graph back down to nothing form an antimatroid, and one such sequence can be found in polynomial time by a greedy algorithm that repeatedly removes a removable vertex whenever it can find one. Reversing the output of this algorithm gives the construction sequence for the given graph. The graph of the cube gives an example of a graph that has your property (a median graph) but is not constructible in this way. I think the median graphs that can be constructed in this way are exactly the squaregraphs (which include the regular grids). The graphs that have a construction sequence of this type also include all graphs that have a universal vertex, such as the wheel graphs, so (unlike chordal graphs and distance-hereditary graphs) they are not perfect and not closed under induced subgraphs.


Separating time classes A student of mine recently ask the following question:

Assume $$DTIME(f(n)) \subsetneq DTIME(g(n)).$$ Must there exist an $h(n)$ such that $$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$$

This could probably be shown true by constructing an $h(n)$ if $f,g$ are time-constructible. But in general, I feel that this should be false similar to $DSPACE(o(\log(\log(n)))) = DSPACE(1)$.

If $DTIME(f(n))$ is defined as the class of all languages decidable in $O(f(n))$ time by a two tape Turing machine, then I suspect that the answer is no.  In other words, I think that there does not always exist a strictly intermediate time complexity class.

Note: This answer might not be exactly what you are looking for because I'm considering non-computable functions and I don't include every detail of the argument.  But, I felt that it is a good start.  Please feel free to ask any questions.  Maybe I can fill in these details further at some point or maybe this will lead to a better answer from an interested reader.

Consider functions of the form $f : \mathbb{N} \rightarrow \mathbb{N}$.  We refer to these functions as natural number functions.

  Claim 1: I claim that we can construct a very slow growing non-decreasing natural number (non-computable) function
  $\varepsilon(n)$ such that:

  (1) $\varepsilon(n)$ is non-decreasing

  (2) $\varepsilon(n) = \omega(1)$

  (3) For all unbounded computable $f: \mathbb{N} \rightarrow \mathbb{N}$, the set
  $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ is infinite.

We construct $\varepsilon(n)$ as a slow growing non-decreasing step function. Let us enumerate all unbounded computable functions $\{ f_i \}_{i \in \mathbb{N}}$. We want to construct $\varepsilon(n)$ in such a way that for every $i$ and every $j \leq i$, $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$. In other words, we wait to map $\varepsilon(n)$ to $i$ until the first $i$ functions in the enumeration have mapped to a value greater than or equal to $i$ at least once.  Then, $\varepsilon(n)$ continues to map to $i$ until the first $i+1$ functions in the enumeration have mapped to a value greater than or equal to $i+1$ at least once and at this point it starts mapping to $i+1$. If we continue this iterative process for constructing $\varepsilon(n)$, then for any given unbounded computable function, although $\varepsilon(n)$ might not always be smaller, it will infinitely often be at least as small.

Note: I just provided some intuition behind claim 1, I did not provide a detailed proof.  Please feel free to join in on discussion below.

Because $\varepsilon(n)$ is such a slow growing function, we have the following:

  Claim 2: For all computable natural number functions $f(n)$ and $h(n)$, if $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ and $h(n) = O(f(n))$, then $h(n) = \Theta(f(n))$.

For claim 2, if there existed a computable function $h(n)$ between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ such that $h(n) \neq \Theta(f(n))$, then we would be able to compute an unbounded natural number function that grows more slowely than $\varepsilon(n)$ which isn't possible.

Let me explain some relevant details.  Suppose for sake of contradiction that such a function $h(n)$ existed.  Then, $\lfloor \frac{f(n)}{h(n)} \rfloor$ is unbounded.

Note: The preceding function is computable because $f(n)$ and $h(n)$ are computable.

Since $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$, we have $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$.  It follows that there is some constant $\alpha$ such that for all $n$ sufficiently large, $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$.  Since this function is unbounded and computable we may apply Claim 1 to get that $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$ infinitely often which contradicts the previous statement.

  Claim 3: For a time constructible function $f(n)$, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$, yet there does not exist $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$.

In order to just show that, $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ we need to use a stronger time hierarchy theorem and this is where we use the assumption that the number of tapes is fixed (we said two tapes above).  See "The tight deterministic time hierarchy" by Martin Furer.

Since there are no computable natural number functions between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ other than those that are $\Theta(f(n))$, we have that for every function $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $h(n) \neq \Theta(f(n))$, $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$.


Given a subset of the hypercube and a copy translated by s, find s Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible in randomized RAM model with say $d$-bit wide words. Here we think of bit strings as elements of $\mathbb{F}_2^d$ and addition is modulo 2, namely the xor operation. (Note that even though we receive both A and B, we are not told which element is a translated version of which.)

I have 3 4 questions regarding this problem. I have encountered this question in a competitive programming (practice) contest years back. Now revisiting this question, it really looks like it originated from some tcs related question.

  Has anyone seen this or a related problem in their research? Does this relate to any PCP or property testing related constructions? (Or Simon's problem in any way)

Naive solution

Fix an element $a_0\in A$ and for each element $x\in B$, guess that $s=x-a_0$ and verify this guess in linear time by computing $A+s$ and comparing it against $B$ (we can then compare $A+s$ and $B$ in linear time by, say, hashing as we are assuming $d$-bit wide words).
This gives us an $O(n^2)$ time algorithm.

A better solution:

Here is a solution that does much better for most inputs (which allowed me to pass the test cases during the contest). Pick a random subset of $S\in[d]$. Partition $A=\{x^1,x^2,\ldots,x^n\}$ into $2^{|S|}$ equivalence classes according to $x_S$. Here subscript means restricting $x$ to those coordinates in $S$. Denote for $v\in\{0,1\}^S$, the class of $v$ as $C_v = \{x\in A\mid x_S = v\}$. For $v\in\{0,1\}^S$, let $m_v = |C_v|$. Now let us partition $A$ into equivalence classes according to $m_{x_S}$ this time. Denote for an integer $i\in[n]$ the class of $i$ as

$$ D_i = \{x\in A\mid m_{x_S} = i\}.$$

Now take the smallest nonempty class $i^* = \arg\min_i |D_i|$. If we pick $a_0$ from this class, we just need to make $|D_{i^*}|$ guesses as to what element to pair $a_0$ with inside $B$. Therefore the runtime becomes $n|D_{i^*}|$.

An idea: What if we pick a random full rank matrix $M\in\mathbb{F}_2^{d\times d}$ and transform $A$ by $M$ first, does this ensure that $\mathbb{E}_{M,S} |D_{i^*}|$ is small for any $A$? Note that for $x^1, x^2\in A$ we have $(Mx^1)_S = (Mx^2)_S$ iff $(M(x^1+s))_S = (M(x^2+s))_S$

The above solution will not provide any improvements when $A$ is a subcube. Though, in this case we can easily solve it by other observations. In general I am unable to think of hard instances to this problem and suspect there should be a provably efficient solution for all inputs.

A Fourier theoretic approach:

Lets not try to learn $s$ all at once; that way we make no measurable progress up until we actually solve the problem. How about we try to learn s bit by bit. I will use A,B to denote the subsets of $\{0,1\}^d$ as well as the corresponding indicator functions. We have

$$\hat{A}(u) = \hat{B}(u)(-1)^{\langle u, s\rangle}$$

If we pick a random $u\in\{0,1\}^d$, by the above equation in linear time we will learn 1 bit of information about $s$, unless $\hat{A}(u) = 0$.

Note that this already solves the problem when $d\gg \log n$ due to the uncertainty principle in Fourier analysis: it will imply that at most $2^d/n$ Fourier coefficients are zero. Therefore the hardest case is when $d\approx \log n$.

What can we do in this case?

Question 2: What is the randomized RAM complexity of this problem?

Question 3: What is the quantum complexity?

Here is an $O(nd)$ time randomized solution.

We will use the shifting (aka compression) technique from combinatorics, in a seemingly new algorithmic way, which I have never seen done before (see this post for the definition of the compression technique).

Let us define a partial order on $\{0,1\}^d$ called the set inclusion partial order, denoted $\preceq$, as so: Two strings $x,y$ satisfy $x\preceq y$ if $x_i = 1 \implies y_i = 1$ for all $i\in[d]$.

A subset $S\subseteq\{0,1\}^d$ is called downward closed, or downset for short, if $y\in S \land x\preceq y\implies x\in S$.

Intuitively, we will morph $A$ and $B$ into downsets a dimension at a time after which it will be clear which elements $x$ of $A$ are the "pairs" of which elements $x+s\in B$; this evidently will reveal $s$.

For reasons which will be clear let $A'=\{(x,x)\mid x\in A\}$ and $B' = \{(x,x)\mid x\in B\}$; we will modify only the left items in these pairs $(x,x)$ and the right items are fixed and only there so we can keep track of the original labels. When I say left $i$th coordinate of $(w,x)\in A'$ it will refer to the $i$th coordinate of the string on the left pair element, that is $w$.

The algorithm will proceed in $d$ rounds numbered $i=1,\ldots,d$. In round $i$, we do the following. Let $I= [d]\setminus \{i\}$ and partition $A'$ and $B'$ into equivalence classes according to coordinates $I$ of the left pair element. It will be clear soon each nonempty class has either 1 or 2 elements depending on the last unfixed left coordinate $i$ (there is always a bijection between the left and right parts of the pairs as we'll see during this inductive argument).

Here is an example: Let $i=1$. Consider the class
$C_u = \{(w,x)\in A' \mid w_I = u\}$. In each iteration, there will be a bijection between the left parts and right parts, so it remains to specify the first bit of $w$. Either both $(0u,\cdot), (1u,\cdot)$ are in $C_u$ or just one of them or none (we discard empty classes). This way among nonempty classes, the size is either 1 or 2.

The classes of size 2 are already good, don't touch them; no matter what $s$ is in the $i$th coordinate, they will work okay. The classes of size 1 either have $w_i=0$ or $w_i=1$. If the number of $w_i=0$ classes of $A'$ is different than the number of $w_i=1$ classes of $A'$, then we already know what $s_i$ must be (using the fact that $B$ is a translated version of $A$), so if the number of $w_i=0$ classes of $A'$ is equal to number of $w_i=1$ classes of $B'$, then flip the left $i$th coordinate of each element in $B'$, otherwise do nothing.

Now in both $A'$ and $B'$ set the left $i$th coordinate of the $w_i=1$ classes to 0. This is called a down-shift operation, as we gradually make the sets monotone.
This is the end of $i$th iteration.

Claim 1: At the end of the $d$th iteration, the left part of $A'$, i.e., $\{w\mid (w,x)\in  A'\}$ forms a downset. Likewise for $B'$.

Claim 2: These two downsets are equal to each other, i.e., $\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$.

Now that we have $\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$, we have a natural bijection $b$ between $A'$ and $B'$. One can see this bijection maps $(w,x) \in A'$ to $(w, x+s) \in B'$, so it directly reveals $s$.

How to implement each iteration in $O(n)$ time: We have a set of items of size $n$ that we need to partition with respect to a $d-1$ bit key (corresponding to $x_I$ for $I$ defined above) in each iteration. This we can do $O(n)$ randomized time by hashing, or $O(nd/\log n)$ deterministic time by bucketing (bucketing can be done in $O(n)$ time but $2^d$ space which could be excessive, instead we "radix it" by $\log n$).


Distinguishing between $N$ quantum states Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?

This problem can be turned into a two state distinguishability problem by considering the problem of distinguishing $\rho_A$ from $\rho_{B} = \frac{1}{N-1}\sum_{i\neq A}\rho_i$.

I know for two quantum states the problem has a nice solution in terms of the trace distance between the states when you minimize the maximum probability of error rather than the minimizing the average probability of error, and I was hoping that there might be something similar for this case. It is of course possible to write the probability in terms of an optimization over POVMs, but I am hoping for something where the optimization has already been performed.

I know there is a huge literature on the distinguishability of quantum states, and I've been reading through a lot of papers over the last few days trying to find the answer to this question, but I'm having trouble finding the answer to this particular variation of the problem. I'm hoping someone who knows that literature better can save me some time.

Strictly speaking, I don't need the exact probability, a good upper bound would do. However, the difference between any one state and the maximally mixed state is quite small, so the bound would have to be useful in that limit.

As you mention, it is possible to determine the optimal average success probability numerically, which can be done efficiently via semidefinite programming (see e.g. this paper by Eldar, Megretski and Verghese or these lecture notes by John Watrous), but no closed form expression is known.

However, there are several known upper and lower bounds on the probability of error (i.e. 1 minus the average success probability). In terms of pairwise fidelities, the probability of error in your setting is known to be lower bounded by $\frac{1}{N^2} \sum_{i>j} F(\rho_i,\rho_j)$, and upper bounded by $\frac{2}{N} \sum_{i>j} F(\rho_i,\rho_j)^{1/2}$.

There is also another lower bound known in terms of trace distance: $\frac{1}{2}(1 - \frac{1}{N(N-1)} \sum_{i>j} tr|\rho_i-\rho_j|)$, which reduces to the exact Helstrom bound in the case $N=2$. See this paper for a comparison of all of these, and some other bounds too. Note that all of these bounds hold in the average-case setting where there is a prior probability distribution on the states.


The worst-case scenario(s) for MAX3E SAT MAX3E SAT is defined as SAT with all clauses consisting of 3 literals and their possible negations.  We define clause counting, for this question, as the ability to count the total number of satisfied clauses for all remaining possible truth assignments.  Let's say that we are allowed to pick a single variable and assign it a value, and then perform clause counting to get a total for all remaining possible truth assignments.  Further, we can do this for all variables and their negations.

Let's consider this clause counting ability for MAX3E SAT with an equation that is garaunteed to be satisfiable by at least one possible truth assignment.  Now, the clause counting from above can be used to help predict part of a satisfying truth assignment.  The variable we pick with the highest clause count should (probably) be part of a satisfying truth assignment.  I'd like to construct the smallest example (in terms of clauses) where this notion of clause counting fails.  Can someone please help?

In fact, we are able to perform "clause counting".  The total number of satisfied clauses for all remaining truth assignments is proportional to the expected number of satisfied clauses for a random truth assignment, which is the sum of the probabilities $P(C_i | \{x, y, ...\})$, where $C_i$ is the $i$-th clause, and $\{x,y,...\}$ are the literals that have been assigned to be true.  In particular, if there are three distinct literals per clause, and we are promised a satisfying truth assignment (so a variable and its negation never occur in the same clause), and a single literal $x$ has been assigned to be true, then the probability that a particular clause is satisfied by a random assignment of the remaining variables is $3/4$ if the clause contains $\neg{x}$, or $7/8$ if the clause contains neither $x$ nor $\neg{x}$, or $1$ if the clause contains ${x}$.  That is,
$$P(C_i | \{x\}) = \frac{7}{8} + \frac{1}{8}n_i(x),$$
where $n_i(x) \in\{-1, 0,1\}$.  So the literal picked out by "clause counting" will be the one that maximizes $\sum_{i}n_i(x)=N(x)$, where the sum is over all clauses, and $N(x)$ is the (net) number of occurrences of the literal $x$ in the entire formula.

To use this to construct a counterexample, we need a literal that is false (say) in all satisfying assignments, but that maximizes the above count.  We can force a literal to be false with four occurrences of its negation, as follows:
$$
\begin{eqnarray}
\neg{a} &\equiv& \neg{a} \wedge (b \vee \neg{b}) \wedge (c \vee \neg{c}) \\
&\equiv& (\neg{a} \vee b \vee c) \wedge (\neg{a} \vee b \vee \neg{c}) \wedge (\neg{a} \vee \neg{b} \vee c) \wedge (\neg{a} \vee \neg{b} \vee \neg{c}) \\
&\equiv& \Phi(\neg{a};b,c),
\end{eqnarray}
$$
for any additional literals $b$ and $c$; this subformula has $N(a)=-4$ and $N(b)=N(c)=0$.  We then need to include enough occurrences of $a$ in the rest of the formula to make $N(a)$ the largest count.  This can be done using
$$
\Omega(a;d,f) \equiv (a \vee d \vee f) \wedge (a \vee d \vee \neg{f}) \wedge (a \vee \neg{d} \vee f),
$$
which is equivalent to $a \vee (d \wedge f)$, and has $N(a)=3$ and $N(d)=N(f)=1$.  So a counterexample with four variables and ten (unique) clauses is
$$
\Phi(\neg{a}; x_1, x_2) \wedge \Omega(a; x_1, x_3) \wedge \Omega(a; x_2, x_3),
$$
which has $N(a)=2$ and $N(x_1)=N(x_2)=N(x_3)=1$, and a unique satisfying assignment: $\{\neg{a}, x_1, x_2, x_3\}$.


Checking formulas with two quantifiers ($\forall \exists$) - 2QBF SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier.

For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine whether $\varphi(x)$ is satisfiable.  To check the validity of $\forall x . \varphi(x)$, we can use a SAT solver to determine whether $\neg \varphi(x)$ is satisfiable.  (Here $x=(x_1,\dots,x_n)$ is a $n$-vector of boolean variables, and $\varphi$ is a boolean formula.)

QBF solvers are designed to check the validity of a boolean formula with an arbitrary number of quantifiers.

What if we have a formula with two quantifiers?  Are they any efficient algorithms for checking validity: ones  that are better than just using generic algorithms for QBF?  To be more specific I have a formula of the form $\forall x . \exists y . \psi(x,y)$ (or $\exists x . \forall y . \psi(x,y)$), and want to check its validity.  Are there any good algorithms for this?  Edit 4/8: I learned that this class of formulas is sometimes known as 2QBF, so I am looking for good algorithms for 2QBF.

Specializing further: In my particular case, I have a formula of the form $\forall x . \exists y . f(x)=g(y)$ whose validity I want to check, where $f,g$ are functions that produce a $k$-bit output.  Are there any algorithms for checking the validity of this particular sort of formula, more efficiently than generic algorithms for QBF?

P.S. I am not asking about the worst-case hardness, in complexity theory.  I am  asking about practically useful algorithms (much as modern SAT solvers are practically useful on many problems even though SAT is NP-complete).

If I may, quite blatantly, advertise myself, we wrote an article about this last year
Abstraction-Based Algorithm for 2QBF. I've got an implementation for qdimacs, which I can provide if you wish but from my experience, one can benefit greatly from specializing the algorithm for a particular problem. There is also an older paper A Comparative Study of 2QBF Algorithms, which also presents fairly easily implemetable algorithms.


Coreset and VC dimension I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them  give an $\epsilon$-approximation sketch of the input data. However, for the later case we know a characterization i.e. if a range space has finite VC dimension, then it can be approximated by a small (constant) size sample. On the other hand, for the case of $\epsilon$-coreset (similar to the concept of VC dimension)  is there any characterization known over the problems which can or cannot be sketched by a small size sample?

Thanks,

Samples provides you only with statistical guarantees. For a fixed $\epsilon$ whatever you compute would hold for everything "except" $(1-\epsilon)$ fraction (I am being very informal here). Thus, taking an $\epsilon$-net sample of a set of points in the plane, computing its smallest enclosing disk, results in a disk $D$ that contains $(1-\epsilon)$ fraction of the whole point set (or $(1-\epsilon)$ of the measure).

Coresets on the other hand, provide geometric guarantees. For example, for a point set $P$ in the plane, an $\epsilon$-coreset for smallest enclosing disk is a subset $S$, such that any disk $D$ that contains $S$, if you slightly expand it (formally, scale it up by a factor of $(1+\epsilon)$, the it must contain all the points of $P$.

The beauty of samples is that you can generate them without a priori knowing what you are going to use them for. Coresets on the other hand are application dependent - you need different algorithms to compute them depending on the function you are trying to capture.

As for characterization - we have many positive results (see the survey here: http://sarielhp.org/p/04/survey/). We also have counter examples which are somewhat mysterious - http://sarielhp.org/p/02/2slab/ (no coreset no cry [after working for months on trying to compute a coreset for this problem, I definitely wanted to cry]). The rule of thumb is that you are not going to have a coreset if:

(A) The underlying function change dramatically if you can remove a single point, and there are many such points (say, closest pair, or k-center clustering, etc). Solving such problems in linear time requires different techniques.

(B) Or putting (A) differently - the underlying function is not very stable if you move points around.

It is unlikely to have a better characterization without assuming something significantly stronger on the underlying function that one is trying to compute.


Degree restriction for polynomials in $\mathsf{VP}$ why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?

It's not really needed, so much as it is a matter of convention and utility. Of course, depending on your aims and your specific problem, it is completely reasonable to consider arithmetic circuits of polynomial size regardless of degree. This class is often denoted $\mathsf{VP}_{nb}$ (for "Non-degree-Bounded"), or sometimes "algebraic $\mathsf{P/poly}$ or $\mathsf{algP/poly}$.

I was curious about this same question for a long time, so a while ago I spent some time digging. I found both a posteriori motivations, based on what we now know, and more historical, a priori motivations. I'm sure this list is incomplete, but here's what I found.

A priori motivations:

Skyum and Valiant [A Complexity Theory Based on Boolean Algebra. J.
ACM 32(2):484-502, 1985] seems to make it clear that the real
motivation is that in the Boolean setting p-bounded degree is what we
have, since every function can be expressed as a multilinear (and hence degree $\leq n$) polynomial. See (2), (3), and (4) below.
Valiant’s original paper (Valiant. Completeness classes in
algebra. STOC 1979) is focused on formula size, and his original
definition of p-definable is given in terms of multilinear polynomials
whose coefficients have poly size formulae, and then taking the
closure under p-projections. The motivation for p-projections is
clear. This yields p-bounded degree as a consequence.
One motivation for considering formula size:  ”We note that in the
Boolean case, although no analogue of Hyafil’s result is known, the
logarithm of formula size is intimately related to the space required
to compute the function.” [Valiant, p. 11] (We now know that, in the
Boolean case, polynomial formula size is equivalent to nonuniform $\mathsf{NC}^1$
(log-depth, poly-size circuits), but at the time I do not know if this
class was yet considered.)
Another motivation for formula size from the Boolean case (which he
discusses in Section 9): Boolean p-definable families exactly capture
$\mathsf{NP/poly}$ – that is, the only difference between "Boolean p-definable"
and "$\mathsf{NP}$" is nonuniformity. (The use of multilinearity in his
definition of p-definable may also have been motivated by this, since
all Boolean functions can be written multilinearly.)
Strassen’s result on eliminating divisions multiplies the
complexity by a factor of $deg^2$, so maintaining polynomial
complexity while eliminating divisions uses p-bounded degree.
For quasipolynomial instead of polynomial bounds, we have
qp-computable iff qp formula size, but only for families of
qp-bounded degree. This follows from two results that were known at the time: Hyafil (1979) showed that depth is at most $O((\log d + \log s)\log d)$, where $d$ is the degree and $s$ is the circuit size, and Brent (1974) showed that depth is $\Theta(\log(\text{formula size}))$
Without the restriction on degree, permanent would not be
$\mathsf{VNP}$-complete under p-projections, as any p-projection of permanent has
p-bounded degree.

A posteriori motivations:

Valiant-Skyum-Berkowitz-Rackoff [SIAM J. Comput. 12(4):641-644,
1983] extends Hyafil’s result to yield circuits of the same depth as
Hyafil, but whose size is polynomial in the original size and the
degree.
The more recent depth-reduction results (the chasms at depth 3 and 4) also involve the degree of the polynomial. As with VSBR, they become significantly less powerful for polynomials of large degree (and trivial for polynomials of really large degree).
von zur Gathen’s “Feasible Arithmetic Computations: Valiant’s
Hypothesis” [J. Symb. Comput. (1987) 4, 137-172] provides several
useful reasons for bounding the degree. In particular, by bounding the
degree in the definition of $\mathsf{VNP}$, $\mathsf{VNP}$ is closed under many natural
operations that it would not otherwise be closed under. See esp. the
two paragraphs at the top of p. 156 mentioning results of Kaltofen
(1986) and Plaisted (1984).
von zur Gathen, ibid., p. 7: "Restricting the degree is quite reasonable over infinite fields, e.g.
over $\mathbb{Q}$, where the binary representation of the value of a polynomial
like $x^{2^n}$ has exponential length even for small inputs. In a
different setting–over varying finite fields–natural problems like
the trace, testing for quadratic residuosity, or factoring
polynomials, lead to polynomials of large degree, which can
nevertheless be computed efficiently (yon zur Gathen & Seroussi,
1986)."


Applications of representation theory of the symmetric group Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:

  Do you know of any applications of the representation theory of the symmetric group in TCS?

The symmetric group $S_n$ is the group of all permutations of $\{1, \ldots, n\}$ with group operation composition. A representation of $S_n$ is a homomorphism from $S_n$ to the general linear group of invertible $n \times n$ complex matrices. A representation acts on $\mathbb{C}^n$ by matrix multiplication. An irreducible representation of $S_n$ is an action that leaves no proper subspace of $\mathbb{C}^n$ invariant. Irreducible representations of finite groups allow one to define a Fourier transform over non-abelian groups. This Fourier transform shares some of the nice properties of the discrete Fourier transform over cyclic/abelian groups. For example convolution becomes pointwise multiplication in the Fourier basis.

The representation theory of the symmetric group is beautifully combinatorial. Each irreducible representation of $S_n$ corresponds to an integer partition of $n$. Has this structure and/or the Fourier transform over the symmetric group found any application in TCS?

Here are a few other examples.

Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions.
Kassabov (2005) proved that one can build a bounded degree expander on the symmetric group. Symmetric Groups and Expander Graphs.
Kuperberg, Lovett and Peled (2012) proved that there exist small sets of permutations which act uniformly on k-tuples. Probabilistic existence of rigid combinatorial structures.


Max cut problem between two connected subgraphs Let $G$ be a connected graph.

Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known about this, e.g. complexity, approximation, randomized algorithms, etc.?

The situation without connectedness is MAX-CUT. The situation when only $A$ is required to be connected has been studied here: https://arxiv.org/abs/1507.00648

I'm also interested in the case when $A$ and $B$ are required to be of roughly equal size.

Here is a straightforward reduction from the max-cut problem:

Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a very very big weight edge. In an optimal solution to the above problem $u$ is in one partition and $v$ in the other (this also ensures that each part is a connected component), hence an algorithm that solves this problem in the new graph, could solve the max-cut problem in the original graph and vice versa.

P.S: I supposed we can have edge weights as otherwise a similar argument works however instead of adding vertices we add two long paths (each of length $n^2$), for $i\le n$ we connect the $i$'th vertex of the path $P_j$ (for $j\in \{0,1\}$) to the $i$'th vertex of the graph and we connect all vertices of $P_1$ to the all vertices of $P_2$. Then again in an optimal solution path $P_1$ is on one side and path $P_2$ on the other side.


c factor in PageRank In page 3 of PageRank paper is mentioned:

  let c be a factor used for normalization
  (so that the total rank of all web pages is constant).

What is the use of c and how can its value be computed?

The point of such a factor in general is that you want to be able to calibrate the scores you get, by forcing them to be within a specific range like $[0,1]$. In particular, this factor would be computed (in principle) by getting the rank of all pages and then dividing by their sum.


Known property? Maximum radius of connected induced subgraph I was wondering if the following graph property has a name and has been researched:
Consider any connected induced subgraph $H \subseteq G$.
Then $r(G)$ denotes the maximum radius of any such $H$.

I think it is an interesting property since graphs with bounded $r(G)$ are closed under taking induced subgraphs whereas graphs of bounded radius are not.

Edit: The reason why I am only interested in induced subgraphs is that it otherwise would degenerate to the length of the longest (not necessarily) induced path.

The property $\Pi_r$, defined as containing exactly the graphs $G$ such that every induced subgraph $H$ of $G$ has diameter at most $r$, is the same as the class of graphs that do not contain a $P_{r+2}$ as induced subgraph, where the $P_{r+2}$ is the path on $r+2$ vertices.

The equivalence can be seen as follows. The two degree-one vertices in the $P_{r+2}$ have a distance of $r+1$. Hence, if $G$ contains a subgraph isomorphic to the $P_{r+2}$, then $G$ does not fulfill $\Pi_r$. Conversely, if $G$ does not fulfill $\Pi_r$, then $G$ has an induced subgraph $H$ containing two vertices $u$ and $v$ such that the distance between $u$ and $v$ in $H$ is at least $r+1$. Take the vertex set $P$ of a shortest path between $u$ and $v$ in $H$. Since $P$ is a shortest path, $G[P]$ is an induced path, that is, it is isomorphic to some $P_\ell$. Since $u$ and $v$ have distance at least $r+1$ in $G[P]$, we have $\ell\ge r+2$. Hence $G$ contains $P_{r+2}$ as an induced subgraph.


Are there incompressible strings $S$ such that $K(SS) \lt K(S)$? This question was inspired by Sune Jakobsen's question and Tsuyoshi's answer. In Kolmogorov-complexity, a string is incompressible if $K(S) \ge |S|$.

Is there incompressible string $S$ such that $K(SS) \lt K(S)$? Is there an infinite set of such strings? What is the theoretical consequence if such infinite set of strings does exist?

A rough argument that there should be infinitely many such strings is as follows.

Consider a machine $M$ that first left-pads its input with zeroes out to some known length $2f(|T|)$ (we will specify $f$ below), then repeatedly performs some length-preserving and random-looking operation on it, halting only when it has produced (essentially by accident) a string consisting of two copies of the same string.  It is not required to halt for every input.  When it does, the output it produces from input $T$ will have complexity satisfying $K(SS) \approx K(T) + K_M$ for some $K_M$, as long as $f(|T|)$ is large enough, and $S$ will have length $f(|T|)$.  The string $S$, moreover, will have complexity $K(S) \approx K(SS) + K_C$ for some $K_C$.  The key final step is to choose the right $f(|T|)$.  It must be large enough to ensure that $SS$ is best described as "the output of $M$ applied to $T$", but small enough to ensure that the description of $S$ as "half the output of $M$ applied to $T$" is not less than $|S| = f(|T|)$.  Taking $f(|T|)=|T|+K_M+K_C-1$ should work.  We conclude that arbitrarily long incompressible inputs $T$, if they halt, will typically produce outputs $SS$ such that $K(SS) < K(S)$ and such that $S$ is incompressible.  The machine $M$ could do any number of things; for instance, the machine $M$ that squares its input and then discards every other bit of the result would probably work.


What is the best text of computation theory/theory of computation? In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression.  I borrowed that book and don't have one in my collection, so I need one.  So to the question, are there are any other books which could be seen as better and possibly more complete?

I didn't see a community wiki section here, so I couldn't note it as such.

I strongly recommend the book Computational Complexity: A Modern Approach by Arora and Barak. When I took computational complexity at my Master level, the main textbook is Computational Complexity by Papadimitriou. But, maybe due to my background in Software Engineering, I found the writing in Papadimitriou challenging at times. Whenever I had problem understanding Papadimitriou's book, I simply went back to Sipser, or read the draft of Arora and Barak.

In retrospect, I really like Papadimitriou's book, and I often find myself looking up from this book. His book has plenty of exercises that are quite effective at connecting readers to research-level questions and open problems.

In any case, you should have a look at both Papadimitriou and Arora-Barak. People also suggest Oded Goldreich's textbook, but I really prefer the organization of Arora-Barak.


Maintain mex with efficient union Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations:

Given $S[A],$ calculate minimal excludant $\mbox{mex} A = \min \ \mathbb{Z_{\geq 0}} \setminus  A.$
Given two data structures for sets $A$ and $B$, construct a data structure, maintaining the union of the two $S[A \cup B]$.

Disjoint set union comes into mind, but I can't think of a way to make it support mex-es.
Intuitively, the problem I see is that we can have a situation in which both $A$ and $B$ contain many small intervals, and then their union is hard to obtain.

Ideally, both of these should be polylog (on the size of the represented sets).

How about if the sets are from a bounded universe?

Here are two solutions which (as suggested in the question and comments) assume that all the given sets are disjoint and performs destructive set unions (when we find the union of sets A and B, we remove A and B themselves from the family of sets).

Amortized constant time

We maintain objects for the sets and objects for the elements. The sets know what elements they have, as a concatenable list, so that we can list those elements quickly, but we don't keep pointers from the objects to the sets that contain them (because it would be too slow to update them).

There is at most one special set Z, the one containing zero. Every object knows whether it is part of Z or not (a binary flag). The set Z maintains the value of its mex. For every other set, the mex is zero. So you can compute the mex of a set in constant time, given either the set itself or one of its elements.

To form the union of two sets, if neither one is Z, just concatenate their lists. If one of the two sets is Z, run through its elements setting the flag that says the element is now in Z. Then, while the mex is an element of Z, increment it.

Each element accounts for one increment operation to the mex of Z, so the amortized time per element, merge, or mex request is constant.

Worst-case logarithmic time

For a worst-case rather than amortized (but slower) solution, that also allows for creation of new singleton sets and does not assume that the union of all the sets is a contiguous interval, we use the following data structures:

union-find rather than flags to determine the set that contains any element (even if we just do union-by-rank without path compression, this is worst-case logarithmic per find operation)
a binary search tree of the elements in the union of all the sets
for each element, the smallest non-element between it and its predecessor in the binary search tree (or zero if it has no predecessor)
for each binary search tree node, the smallest non-element listed in its subtree (updated in constant time per tree rotation)
the smallest element of each set
a priority queue of the smallest elements of sets that are not Z.

Then at all times mex(Z) is the minimum of the priority queue value and the smallest non-element. And as before, for sets that are not Z, the mex is zero. Adding a new singleton set, merging two sets, or finding a mex all take logarithmic time with more-or-less obvious updates.


Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages. Immerman (Descriptive Complexity, 1999) presents the EF games for existential monadic second order (Ajtai-Fagin games) on page 127.  As $\exists$MSO on words is equivalent to regular languages, the game can be written as follows.

A language $L \subseteq \{a, b\}^*$ is regular if and only if Delilah has no winning strategy in the following game:
1. Samson chooses $c, m \in \mathbb{N}$,
2. Delilah chooses $w \in L$,
3. Samson chooses $c$ subsets $C_1^w, \ldots, C_c^w$ of the set of positions in $w$ (i.e. $\{0, \ldots, |w|-1\}$),
4. Delilah chosses $v \not\in L$ and $c$ subsets $C_1^v, \ldots, C_c^v$ of the set of positions in $v$,
5. Samson and Delilah play the $m$-turn EF game on $(\mathfrak{S}(w), C_1^w, \ldots, C_c^w)$ and $(\mathfrak{S}(v), C_1^v, \ldots, C_c^v)$,
where $\mathfrak{S}(w)$ is the structure associated with the word $w$, i.e. :
$$\mathfrak{S}(w) = \langle \{0, \ldots, |w|-1\}, SUCC, Q_a, Q_b \rangle$$
with $Q_l = \{p \;|\; w_p = l\}$, and $SUCC$ is the binary successor predicate.

I have two questions:
- How does one show that $\{a^nb^n \;|\; n \in \mathbb{N}\}$ is not regular, using an EF argument like this,
- Is it easier/harder to play those games (to show non-regularity) when one has an ordering rather than the successor relation? (Those are equivalent in existential MSO).

We will give a winning strategy for Delilah. Let Samson choose his $c$ and $m$. Then Delilah chooses $w = a^n b^n$ for a large $n$ to be determined later. Let Samson choose his subsets $C^w_1,\ldots,C^w_c$ which we view as a coloring of the positions of $w$ with $2^c$ colors. Let $w'$ denote this colored word. The goal of Delilah at this point is to find a segment $w'[i,\ldots,j]$ of $w'$ with the following properties for an $r$ and a $t$ to be chosen later:

$0 \leq i \leq j \leq n$ (thus the segment belongs to the first part of $w'$),
the $r$-neighborhoods (neighborhoods of radius $r$) of $i$ and $j$ in $w'$ are isomorphic,
for every $k \in [i,\ldots,j]$, the $r$-neighborhood of $k$ in $w'$ appears as $r$-neighborhood of at least $t$ other positions of $w'$.

If she manages to do that, then she will choose her colored word to be
$$
v' = w'[0,\ldots,i-1] w'[i,\ldots,j]^2 w'[j+1,\ldots,2n-1].
$$
If $v$ is the ${a,b}$-word underlying $v'$, it will follow that $v$ does not belong to $L$ (because we pumped a non-empty segment of $a$'s), and Delilah has a winning strategy in the $m$-turn EF game on $w'$ and $v'$ (this follows from Hanf's Theorem if $r$ and $t$ are sufficiently large with respect to $c$ and $m$; see Theorem 1.4.1 in Ebinghaus and Flum book "Finite Model Theory").

Thus, it remains to show that if $n$ is sufficiently large with respect to $c$, $m$, $r$ and $t$ we can find a segment $w'[i,\ldots,j]$ as above. But this follows from a standard pigeonhole argument using the fact that the number of ismorphism types of $r$-neighborhoods is finite.

This worked for successor structures. With a linear order it will be a bit harder but I didn't think much about it.

Note that, not surprisingly, this argument looks a bit like "pumping" argument in automata. However, it is not as silly as just translating the formula to an automaton. I think it counts as a model-theoretic argument.


Linear programming solution in one pass with ordered variables I have a family of linear programming problems:  maximise $c' x$ subject to $A x\le b$, $x\ge0$. The elements of $A$, $b$, and $c$ are nonnegative integers, $c$ strictly positive. ($x$ should also be integral but I will worry about that later.)

It often happens in my application that the coefficients $A$ and $c$ are such that a simplified one-pass algorithm gives the optimal solution for every choice of $b$: the one-pass algorithm determines the elements $x_1,\dots,x_n$ in sequence, choosing each $x_j$ to be the largest possible value consistent with the already-determined values $x_1,\dots,x_{j-1}$. In simplex language, the sequence of entering variables is just $x_1$ to $x_n$, and it terminates after $n$ steps. This saves a lot of time compared to full-on simplex.

This algorithm works when the columns of $A$ and the elements of $c$ have been sorted from "cheap" to "expensive". A "cheap" variable is a column of $A$ with generally small values, for which the corresponding element of $c$ is large:  for that element of $x$ you get a lot of output with not very much demand on the constraint $b$. So the algorithm just says "do the easy stuff first."

My question is: what property of $A$ and $c$ would assure us that this simplified algorithm works for all $b$? My initial conjecture was that the nonzero elements of $A$ should be increasing in each row, but that is not correct.

Here are some examples, all with $c=(1,1,1)$:
$A_1=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 0\end{pmatrix}$,
$A_2=\begin{pmatrix} 0 & 0 & 1 \\ 3 & 0 & 2 \\ 0 & 3 & 2 \end{pmatrix}$,
$A_3=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$,
$A_4=\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$.
For all of these, the sequential algorithm gives the optimal solution for all values of $b$ (by numerical experimentation). $A_3$ is the only one for which all permutations of columns also work. $A_1$ and $A_3$ are especially baffling, since $(1,1,3)$ looks more expensive than $(1,3,0)$ and $(1,1,1)$ more expensive than $(1,0,0)$.

I would be tremendously grateful for any pointers to the literature, for any problems like this, or any suggestions at all. There must have been other cases where some variables can be determined to be "cheaper" than others and can safely be done first. With all the work that has been done on linear programming over the years, it seems that something similar must have come up, but I haven't been able to find it.

Probably the most famous instance in which a greedy algorithm is known to solve an LP is for the special case of the transportation problem.  Hoffman ("On simple linear programs", in Convexity, vol. 7 of Proceedings of Symposia in Pure Mathematics, pages 317-327, 1963) proved that if the cost matrix for a (maximization) transportation problem satisfies the Monge property ($c_{ij} + c_{kl} \geq c_{il} + c_{kj}$ when $1 \leq i < k \leq n$, $1 \leq j < l \leq n$) then an optimal solution can be found in a greedy manner like the one you describe.

Hoffman also has a survey paper ("On greedy algorithms that succeed") from 1985 in which he discusses known cases in which a greedy algorithm gives an optimal solution to an LP.  Besides his own work cited above (about which he says, "most of the linear programming problems known [by 1963] to be susceptible to a greedy algorithm were special cases of the Monge idea"), he mentions Edmonds' linear programming interpretation of a generalization of matroids and a discussion of the case when $A$ is nonnegative, among other things.

I imagine there are more recent results, but hopefully this at least partially answers your question and gives you some ideas of where else to look.


maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph Has this problem been studied before?

Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the minimum spanning tree of the subgraph induced by S. Has this problem been studied before? Is it NP-hard? Thanks a lot.

It's NP-complete by a reduction from vertex cover.

Let $G$ be a graph in which an optimal vertex cover is hard to find.
Make a new graph $H$ with twice as many vertices, by attaching a new degree-one vertex to each vertex of $G$. Turn $H$ into a metric space by making the distance between adjacent vertices equal to $1$ and the distance between non-adjacent vertices equal to $2$. For this metric space, the weight of a minimum spanning tree of an induced subgraph equals the number of vertices plus the number of connected components of the subgraph minus one.

We can assume that the subgraph with the heaviest MST includes all of the degree-one vertices, because adding one of these vertices to a subset can never decrease the number of components. So the vertices that were removed to form the subgraph are a subset of $G$. We can assume also that these removed vertices form a vertex cover of $G$. For, if some other induced subgraph is formed by removing vertices that do not form a vertex cover, and $uv$ is an edge that is not covered, then removing $v$ leads to an induced subgraph that is at least as good: it has one less vertex but one more connected component, created by the degree-one vertex of $H$ that was attached to $v$.

So the optimal subgraph of $H$ is formed by removing a vertex cover from $G$. Such a subgraph will have exactly $n$ components (one for each degree-one vertex added to $H$, either by itself or connected to a vertex of $G$), and a number of vertices equal to $2n-k$ where $n=|V(G)|$ and $k$ is the size of the cover. Thus, the weight of its MST will be $3n-k+1$. To maximize this, we must minimize $k$.


Parallel solution of recurrence equation One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the form:

$x_{1}=b_{1}$
$x_{i}=f_{i}(x_{i-1})=f(b_{i},g(a_{i},x_{i-1}))$

can be solved if the following restrictions are satisfied:
1) $f$ is associative, $f(x,f(y,z))=f(f(x,y),z)$
2) $g$ distributes over $f$, $g(x,f(y,z))=f(g(x,y),g(x,z))$
3) $g$ is semiassociative, that is, there exists some function $h$ such that $g(x,g(y,z))=g(h(x,y),z)$.

Question: Are there any other general algorithms that can solve some class of recurrence equations in parallel?

For linear recurrences, you may find interesting this recent work:

Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, and Nicolae Tapus. 2009. Optimizing the parallel computation of linear recurrences using compact matrix representations. J. Parallel Distrib. Comput. 69, 4 (April 2009), 373-381. DOI=10.1016/j.jpdc.2009.01.004 http://dx.doi.org/10.1016/j.jpdc.2009.01.004

A discussion of the parallel complexity of solving recurrences is available in

Oscar H. Ibarra and Nicholas Q. Tr\&#226;n. 1994. On the Parallel Complexity of Solving Recurrence Equations. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC '94), Ding-Zhu Du and Xiang-Sun Zhang (Eds.). Springer-Verlag, London, UK, 469-477.

Hope this helps.


Call-by-push-value's denotational semantics of "thunk diverge" I was reading about Call-by-Push-Value in the introducing paper from 1999, but I have some confusion, partially because of my unfamiliarity with domain theory. I might have figured it out, but I'd hope to get it confirmed. (If this is not the appropriate venue, advise is welcome on which one is).

I was confused by the statement:

  $[[ \mbox{thunk diverge} ]]\ \rho$ is the least element of the predomain $[[U\ \underline B]]\ \rho$

I was confused because AFAICS, predomains are not guaranteed to have a bottom element in general.

The behavior of $[[U\ \underline B]]$ was defined earlier by saying:

  if $[[\underline B]]$ is the domain $(X, \le, \bot)$, then $[[U\ \underline B]]$ is its underlying predomain $(X, \le)$

Finally, predomains and domains are defined as:

  A domain $(X, \le, \bot)$ is a predomain with a least element $\bot$.*

Originally, I misunderstood the text as implying that to construct $[[U\ \underline B]]$, you remove the bottom element from $[[\underline B]]$. Now, instead, I realize that probably, the semantics of U is just forgetting that $\bot$ is a distinguished element (like a forgetful functor from the category of domains to category of predomains, if my intuition is right). That's because, in a domain, we assume that $\bot$ belongs to X, not to its lifting: that is, $\bot \in X$, instead of $\bot \in X_\bot$.

Question: Is my new reading (above paragraph) correct?

Furthermore, the paper seems to imply that $[[U (F A)]]$ is a predomain created by lifting $[[A]]$ (by adding an additional bottom element below all elements of $[[A]]$). Does that make sense? If so, $T = U \circ F$ would seem to be a partiality monad, matching the fact that this definitions are needed to support the "divergence side effect".

*The definition of predomain is longer, but apparently it does indeed not imply the existence of least elements, so it should be irrelevant to the question. For reference:

  A predomain $(X, \le)$ is a countably based, algebraic directed-complete poset, with joins of all nonempty bounded subsets, in which the down-set $\{y \in X : y \le x\}$ of each $x \in X$ has a least element.

Yes, your reading is correct.

$U$ forgets that something is a domain, but does not change the underlying carrier set or the poset structure. The least element is still there.

It is also the case that $U \circ F$ can be equipped with the structure of a monad, as you say.

And yes, predomains need not have a least element.


How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension? AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1].  (Note that AIC refers to Akaike Information Criterion)

However, AIC relies solely on the number of parameters in the model to assess/penalize model complexity.  And yet models can have infinite representational capacity even with just 2 parameters, as measured by VC-dimension [2], e.g. {sign(sin(ωx + θ) : ω}.  So this infinite VC model can act as a lookup table and perfectly overfit the data, while only having 2 parameters in the penalty term, so it would have low AIC, but no guarantee of low error out-of-sample.

I'm assuming that the issue is that the AIC convergence theorems don't apply to all models, and in particular perhaps these infinite VC-dimension models violate one of the assumptions.  But at least based on the papers I've looked at so far it's not clear to me what assumption that might be (if any)?

By the way, according to this review article [1] the convergence theorems apply quite broadly e.g.:

  When the true model is not in the candidate model set the AIC is
  efficient, in that it will asymptotically choose whichever model
  minimizes the mean squared error of prediction/estimation...
  The AIC's minimax rate of convergence in risk (and the BIC's lack of
  it) is a highly general result in regression and density estimation,
  and holds under more general circumstances than required for
  consistency properties discussed above. For example, the AIC is
  minimax-rate optimal regardless of whether the true model is finitely
  or infinitely dimensional; it is optimal whether the true model is
  among the candidates or not; and it extends to highly non-linear
  models, such as functions defined in Sobolev spaces

[1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3366160/

[2] http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf

I tried to find a simple and accessible analysis of AIC. A definitive work seems to be Barron, Birgé, Massart, "Risk bounds for model selection via penalization"
https://link.springer.com/article/10.1007/s004400050210
though I can't vouch for accessibility.

Instead, let's analyze your sinusoids example. Suppose I have a parametric class of densities over $[0,1]$, parametrized by a single parameter $\alpha$, which is the frequency of the sinusoid. I take the positive part of the sinusoid and normalize the function to integrate to $1$ -- now it's a density. I can choose the $\alpha$ via any of the model selection techniques, including maximum likelihood and AIC. For any fixed $\alpha$, I think all of these will converge (maybe even almost surely) to the true $\alpha$. So why doesn't this contradict the fact that this family of functions (when thresholded at $0$) has infinite VC-dimension?

It's all about the order of quantifiers. Finite VC-dimension means that you can specify a sample size $m_0(\epsilon,\delta)$ that will suffice to achieve $\epsilon$-accuracy at $\delta$-confidence -- in advance of seeing any data. In our model selection example above, you will not be able to specify such an $m_0(\epsilon,\delta)$.

There are certainly infinite-VC classes that are learnable in this sense, which is weaker than PAC. For any target concept and distribution on the integers, you will eventually see enough examples to know the true concept to any desired accuracy -- you will just not be able to specify this sample size independently of the distribution and the target concept. (See Ex. 0.2(c) here
https://www.cs.bgu.ac.il/~asml162/wiki.files/hwk0.pdf
).


What forms of randomness are 'allowed' in FPRASs? I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able to generate uniformly random numbers in the unit interval is strictly stronger than being able to generate random bits. Is this true? Or can you approximate the uniform distribution over $[0, 1]$ sufficiently well with dyadic rationals? (Note that I'm explicitly talking about approximation schemes, so maybe you're able to hide an error term in your probability
distribution in the $\epsilon$ of the approximation.)

If it is true that one form of randomness is stronger than the other, what forms of randomness are generally assumed to be available to an (F)PRAS?

It's the standard model for any randomized algorithm, e.g., generate a random bit.

You can't generate a uniformly random number in the unit interval in the standard model.  You can't even represent a real number in a finite amount of space.  If you want to compute with real numbers, you need a different model of computation designed for reasoning about computation with real numbers.


Multiple independent random number streams Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel.

In other words, one thread will have a full-period independent and uniformly distributed stream of pseudo-random numbers. Each thread will consume these numbers in four different functions (a,b,c,d).

My concern is about the distribution across threads for each function. Thread.1 func_a.1, thread.2 func_a.2... and so on. Do I still need to make sure this distribution is indeed uniform across func_a1, func_a2, etc? Failing to do so can make my simulation have flaws?

In summary,if I start using the pseudo-random numbers in a "random" fashion, rejection sampling. Can I still be sure of the normal distribution among the different parts?

Do not use a single stream of random numbers generated in one thread (or process) and consumed in other threads (or processes). In general, you must instead use several random number streams for your calculations, one for each thread/process. It is extremely important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective at the desired variance reduction, which is, of course, the point of large Monte Carlo calculations.

You may want to take advantage of the Scalable Parallel Random Number Generators Library (SPRNG), which is a parallel library (but you may also use it sequentially as well) providing these and other additional properties; it is particularly well suited for parallel Monte Carlo simulations.


Is this a regular relation? I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that could be done on a finite-state transducer.

I give the machine a description of a string to look for, and when it finds a string that fits its description, it maps it to another string that's a function of the input string.

Examples of things this machine can do:

"if the string contains a /b/, map that /b/ to /p/"
"if the string contains a /t/, map that /t/ to /ts/"
"if the string contains a sequence /dw/, map that /dw/ to /p/"
"if the string contains a /z/, delete the /z/"
"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"
"if the string contains a /t/ or it contains a /k/, add a /d/ to the end"
"if the string contains a sequence /ti/ and it contains a sequence /in/ (which may or may not be overlapping), add a /d/ to the end"
"if the string does not contain a /k/, add a /d/ to the end"
"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"

In other words, it applies to an input string if that string has some (not necessarily contiguous) substring - and then applies some simple function, like mapping the relevant substring to something else, or adding something to the end of the string. And it can have words like and, or, and not in the descriptions of the strings it applies to.

Is there anything in here (if it's possible to tell from a prose description) that a finite-state transducer wouldn't be able to do? I have an intuition that there isn't, but I'm not able to prove that.

Regular relations

All of them are regular relations, assuming the rules are applied only once and assuming we don't have to deal with overlapping matches.

You have to be a bit careful when specifying these kinds of rules to determine what you want to happen if there are multiple places where the rule might apply.  I'm going to assume that the rule avoids ambiguity (e.g., always pick the leftmost match), and that the rule is applied only once, so that the rule can be implemented by scanning from left-to-right over the string in a single pass.

With that clarification, all of these are regular relations, i.e., can be implemented as a (possibly non-deterministic) finite-state transducer.  There are two rules whose intended meaning wasn't entirely clear to me, so let me discuss each in more detail:

"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/": I can see two possible meanings, both regular:

"if the string contains a /d/ with a /g/ anywhere later than it, map the leftmost /d/ to /t/": a regular relation. or,
"if the string contains a /d/ with a /g/ anywhere later than it, map all /d/'s that precede the last /g/ to /t/": also a regular relation.

"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/": This requires more care.  I can see two possible meanings:

Perhaps you mean to scan for the first /w/, then for the first /y/ after it, and if found swap the /w/ and /y/ and then continue scanning the rest of the string after that.  If so, that's a regular relation.
However, if you meant to pair up the /w/'s and /y/'s in a nested fashion (leftmost /w/ with rightmost /y/, and so on) and swap them all (e.g., /wwwwyyyy/ becomes /yyyywwww/), then that's not a regular relation.  Or, to put it another way, if you meant that the rule should be applied repeatedly until no further changes occur, it's not a regular relation.

I'll assume you meant the former.

Deterministic finite-state transducers

That said, the notion of regular relation might not be the notion you are looking for.  A mapping forms a regular relation if and only if it can be applied by a, possibly non-deterministic, finite-state transducer.  Unfortunately, non-deterministic finite-state transducers are not as convenient as deterministic finite-state transducers.  There are two problems:

Ambiguous output: Given a single input word and a non-deterministic finite-state transducer, there might be multiple possible outputs.  I suspect you want your rules to correspond to deterministic functions, so each input string corresponds to a single output string.  (Otherwise, there's ambiguity about what the input string should map to.)  If so, non-deterministic transducers are too powerful.  You might want to restrict attention to deterministic finite-state transducers or unambiguous finite-state transducers, which ensure that each input corresponds to just one possible output.
Efficient simulation: Given a single input string and a deterministic finite-transducer, you can very efficiently compute the corresponding output string by just simulating the transducer.  However, the same is not true for non-deterministic finite-state transducers (not even unambiguous finite-state transducers).  Therefore, you might want to restrict attention to deterministic finite-state transducers.

With that motivation, we can ask a follow-up question: which of these rules can be modelled by deterministic finite-state transducers?  The answer is that all but two of those rule can be implemented as a deterministic finite-state transducer.

The two that cannot are:

"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"
"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"

Those two cannot be implemented with a deterministic finite-state transducer, because they require unbounded memory.  After you see a /d/, you can't output anything: you have to keep scanning until you see a /g/ and meanwhile save everything you've seen.  There's no limit to how much you might need to remember, because there's no limit to how long you might have to wait until you see a /g/.  A similar reason applies for the second example above.

The remainder can be implemented as a deterministic finite-state transducer, because they only require a fixed constant amount of memory.

Those two rules can be implemented as a non-deterministic finite-state transducer.  For instance, when the transducer sees a /d/ it can non-deterministically guess whether or not there is any subsequent /g/, and follow both paths.  Those two rules can even be implemented with an unambiguous non-deterministic finite-state transducer.

If you want an overview of theoretical tools to prove that a language is/isn't regular, take a look at https://cs.stackexchange.com/q/1331/755 and https://cs.stackexchange.com/q/1031/755.  Those relate to regular languages, but similar theoretical tools can be adapted to apply to regular relations as well.  See also https://en.wikipedia.org/wiki/Finite-state_transducer.

Literature

There appears to be some literature on exactly your idea: modelling phonological rules as regular relations.  See, for example, the following paper:

Ronald M. Kaplan, Martin Kay.  Regular Models of Phonological Rule Systems.  Computational Linguistics 20(3), pp.331-378, 1994.

From a technical perspective, they model phonological rules as same-length regular relations, i.e., a regular relation $R \subseteq \Sigma^* \times \Gamma^*$ with the added property that for every $(s,t) \in R$ the length of $s$ is the same as the length of $t$.  Equivalently, they consider the class of non-deterministic finite-state transducers that have no $\epsilon$-transitions.  It looks like they work out the mathematics and its application to linguistics in considerable detail.


Was counting complexity first introduced by Valiant in 1979? Was #P first introduced in [1]?

  [1] Valiant, Leslie G. "The complexity of computing the permanent."
  Theoretical computer science 8.2 (1979): 189-201.

Yes, the complexity class $\mathsf{\#P}$ is first introduced in Valiant's seminal paper "The complexity of computing the permanent." TCS, (1979).  This is very clear. As for the terminology, strictly speaking, Valiant does not use the term "counting complexity" in this paper. Instead, he speaks of "counting problems" in several places. In any case, it is probably hard to tell who coined these terms first, but this is probably also not very important.

What remains important is the fact that the complexity class $\mathsf{PP}$ (which, intuitively, is the decision-theoretic variant of $\mathsf{\#P}$) had already been introduced in 1974, by Gill's seminal paper "Computational complexity of probabilistic Turing machines". In this sense, Valiant was very much influenced by Gill's work. In fact, Valiant cites Gill's paper and loosely tells that #P is essentially equivalent to $\mathsf{PP}$ (which is not meant in the strict, formal sense).


Language in $PSPACE$ and not necessarily in $P$ if $P=PP$? If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is true for all languages in $PSPACE$, or not.

  What is a candidate language $L\in PSPACE$ such that we do not know that $P=PP$ implies that $L\in P$?

Trivially there will be space-bounded classes $P\ne Space(n)\subsetneq Space(n^2)\subsetneq PSPACE$, and $NSpace(n)\subsetneq NSpace(n^2)\subsetneq PSPACE$, which do not collapse due to the space hierarchy theorem.
More interestingly, the Complexity Zoo lists two other classes that is in PSPACE but not in CH, namely

$QSZK$ (Quantum Statistical Zero Knowledge)
$RG[\#1]$ (single-round referreed games).

Perhaps $QSZK$ satisfies your condition. The best published upper bound (that I can find) is that $QSZK\subseteq PSPACE$ by Watrous[1]. Perhaps it does not satisfy your condition; because it has a complete problem that asks to determine the trace distance between the quantum states produced by two quantum circuits given as input, and this is typically doable in $P^{\#P}$, which you have assumed is equal to $P^{\#P}=P$. I don't know, and invite people to think about whether $QSZK\subseteq CH$ or not. Since you asked specifically for a hierarchy, you can think about the hierarchy $QSZK^{{QSZK}^{\cdots}}$. It is unknown whether this class is self-low, i.e. whether $QSZK=QSZK^{QSZK}$ and the hierarchy collapses.
Update
Known results:
$$QMA=QIP[1]\subseteq A_0PP\subseteq PP$$
$$QMA[2]=QMA[k]$$
$$QSZK\subseteq QIP[2]\subseteq QIP[3]=QIP=PSPACE.$$
Perhaps $RG[\#1]$ satisfies your condition. No upper bound is known except that $RG[\#1]\subseteq RG[\#2]=PSPACE\subseteq RG=EXP$.
[1] J. Watrous. Limits on the power of quantum statistical zero-knowledge, to appear in Proceedings of IEEE FOCS'2002


How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming? Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.

If you think of $1 - X_{uv}$ as the "distance" between $u$ and $v$, then you can impose the triangle inequality: $1 - X_{uw} \le 1 - X_{uv} + 1 - X_{vw}$, which can be rewritten $X_{uv} + X_{vw} - X_{uw} \le 1$. This forces (in integral 0-1 solutions) the vertices to group into cliques. You can then check that the degree of every vertex is $k-1$ to ensure they form $k$-cliques.


Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions? If this is known, can someone point me to a proof?

Edit:

A QP is essentially a LP with a quadratic objective. That is, it looks like:

minimize $\frac{1}{2} x^T Q x + c^T x$

s.t. $Ax \leq b$

It's known that in general, solving a QP is NP-Hard. Is it NP-Complete to know if there are at least two different solutions to the QP?

[Since I could not edit my comment, I repost it here as an answer]

To determine if a quadratic program (QP) has multiple solutions (so you have to answer "Yes" if the QP has more than one solutions, and "No" if it has one or no solution) can be shown to be NP-complete by modifying the proof on NP-completeness of QP here http://link.springer.com/article/10.1007%2FBF00120662.

The proof uses a reduction from k-clique to a QP. Now, add a free variable to the QP, so that it has one solution iff it have multiple ones. Thus, the answer to the problem if QP has multiple solutions or not gives the answer to the question if a graph has a clique of size k or not.


Master Equations and Operator Sum Form I'm more of a quantum optics guy than a quantum info guy, and deal mainly in master equations. I'm interested in operator-sum form, and I'd like to derive the errors in this form for a small quantum system that I'm simulating.

The catch: The quantum system is driven by an external (classical) field modelled with a sinusoidal function, and the damping rates are low, so I can't make a rotating wave approximation to eliminate this time dependence. Given that I must solve the master equation numerically by integration, and the result of each integration at time $t$ is not sufficient information to figure out these errors, and I need to do some work to recover the superoperator matrix that has operated on a vectorised density matrix. i.e. I feed the master equation a vectorised density matrix with a single entry of 1 and the rest zero, and build the matrix like that for a particular time $\tau$. Am I on the right track here (sanity check)? More explicitly, if $\mathrm{vec}(\rho_{ij,t=\tau})$ is the vectorised (so it's a column vector) form of a density matrix with a single entry of 1 in position $i,j$, at $t=0$ that has been evolved to time $\tau$, then a matrix to take the vector form of the density matrix from $t=0$ to $t=\tau$ is given as $\mathbf{M}=\sum_{i,j}\mathrm{vec}(\rho_{ij,t=0})\mathrm{vec}(\rho_{ij,t=\tau})^\dagger$.

The question: Given this superoperator $\mathbf{M}$ that does $\mathbf{M}\,\mathrm{vec}(\rho_0)=\mathrm{vec}(\rho_\tau)$, how can I get Krauss operators for the operator-sum equivalent of $\mathbf{M}$ that are in a useful form? i.e. the system in question is a qubit or a qutrit and another qubit or qutrit. I'd like to be able to do the operator sum in the form of tensor products of spin matrices on each channel if possible.

Side question: Is $\mathbf{M}$ a Choi matrix?

Final note: I awarded the acceptance to Pinja, as I used the paper Pinja suggested. I have provided an answer myself below that fills in the details.

I worked on a very similar problem on my Masters thesis, in which I studied the non-Markovian dynamics of a driven qubit in a dissipative environment. My interest was in checking that the master equation I obtained was completely positive, but this is just one side of your problem. The question turned out to be very non-trivial if no RWA is made, but I was able to get some results using Ref. [J Mod. Opt. 54, 1695 (2007)] and exploiting the fact that the qubit is weakly coupled to the environment. I'll beat my drum and also give the Ref. to an article where I present some of these results, [P. Haikka and S. Maniscalco, Phys. Rev. A 81, 052103 (2010)], you may find it useful.


Is there a relationship between computational complexity theory and complex systems theory? Computational complexity theory classifies problems according to their inherent difficulty.

Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the properties of the system's individual parts.  Examples include chaotic systems, complex adaptive systems, or nonlinear systems.

Is there any formal bridge between these fields?

For what it's worth, the notion of performing cryptography with cellular automata is not new, and earlier this year
Applebaum, Ishai, and Kushilevitz identified "complexity" with computational intractability.

This paper by Kanter, Kopelowitz, and  Kinzel, Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem shows that there is a strong connection between nonlinear dynamics and NP-complete problems with the promise of novel secure public-channel protocols.

Phys. Rev. Lett. 101, 084102 (2008)


Use of Lagrangian dual information to prove optimalitiy of a solution : Any example? Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that once you get a solution, you use LDI to prove that it is optimal?? Any example?

Lagrangian duality generalizes standard linear programming duality to the minimization of arbitrary functions (although it's often most effective for convex programs). The rough idea (and Convex Optimization by Boyd and Vandenberghe does a fantastic job of explaining this) is this:

take a a constrained optimization problem,
replace it by an unconstrained optimization problem in which the constraints are folded into the objective linearly by multiplying them by variables (the Lagrange multipliers)
minimize this unconstrained optimization over the original variables
what you end up with is a convex function of the Lagrange variables, the so-called Lagrange dual
and minimizing this (easy, because it's convex regardless of the original function) provides a bound on the original optimization.

If the original problem was convex to begin with, and assuming some technnical conditions, this bound is tight and you have strong duality. Since NP-complete problems are nonconvex in general, you can't use Lagrange duals to prove optimality. However, you can use it to get guaranteed approximations. One of the more well known uses of Lagrange duality is in the approximation algorithm for facility location and the $k$-median problem by Jain and Vazirani.


Ising spin vs Pauli spin matrices Are Ising spins scalar or operators? I am not a condensed matter physicist hence having some confusion. I have learnt about Ising models from adiabatic quantum algorithm papers. For example this presentation or this paper encodes their quantum adiabatic algorithm for an Ising model. In an Ising model the spins are $\pm 1$. In his original adiabatic quantum computation paper, Farhi didn't mention about Ising models. Moreover he explicitly used Pauli's spin matrices and not the  $\pm 1$ spins.

Can we use $\pm$ spins and Pauli's matrices interchangeability at least in the context of adiabatic quantum algorithms?

Neither, they are domain elements.  Any two domain elements would do: $\{+1, -1\}$, $\{0,1\}$, $\{\text{cat}, \text{dog}\}$.

Physicists have wonderful imaginations and thus name certain parameters based on their physical intuition for the behavior of nature.  In this case, they interpret the states of the particles interacting in the Ising model as either spinning up or down.  Furthermore, opposite spins produce opposite effects, such as their resulting magnetic fields being the negative of each other.  Thus, the state of the particles (i.e. the spins) are succinctly represented in the model as either $+1$ or $-1$.

Another good naming example from physics is in string theory.  The equations that describe the motion of these exceedingly small "objects" reminded the physicists of the equations that describe the motion of strings.  Thus the name.

The Potts model is a generalization of the Ising model.  One of the generalizations is that each particle can take one of $q$ values (i.e. the domain size is now $q$).  By continuing the intuitive naming from the Ising model, these $q$ states are also called spins.


Is there a characteristic function of a tree? Consider a set of trees $T=\{T_{\alpha}\}$, and for any $T_{\alpha}\in T$, $T_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' topological feature? That is to say, $T_{\alpha}\simeq T_{\beta}$ only and if only $f(T_{\alpha})=f(T_{\beta})$, and if $T_{\alpha}$ is more similar to $T_{\gamma}$ than $T_{\beta}$ is, then $|f(T_{\alpha})-f(T_{\gamma})|<|f(T_{\beta})-f(T_{\gamma})|$.

It seems that $f$ is a topological invariant of $T$ and this is a very natural thought. I'm not much familiar with graph theory and I'm wondering if someone has considered this problem before. There are two aspects about this problem, one is such $f$ exists, and another is how to calculate $f$， or what the algorithm is.

First, Yixin Cao's comment that similarity is problem-specific is entirely correct. It doesn't make sense to talk about trees being similar or not, without having an idea of what you are trying to compute.

That caveat aside, it is indeed very common to equip trees with metrics. One of the most common is to equip them with an ultrametric, where we define a distance function on trees:

$$d(t_1, t_2) = 2^{-n}$$

where $n$ is the first level at which the branching structure of $t_1$ and $t_2$  differ. This is a generalization of the Cantor metric for sequences, where two strings have a distance of $2^-n$ where $n$ is the first position at which they differ.

The intuition behind this is a temporal one -- we think of a sequence as representing a series of events, and we want to say that two series are more similar the longer we have to wait to distinguish them. When we move from sequences to trees, it's a bit like moving from a linear model of time to a branching model of time. Trees with this kind of ultrametric are, IIRC, used a lot in phylogenetics, where they are called dendrograms, and used to work out possible lineages for species.

Another important metric on sequences is the Levenshtein distance, or edit distance. This measures the number of edits you have to make to change one string into another one. Generalizing this to trees gives you what is unsurprisingly called a "tree edit distance". Here's a survey by Phillip Bille on tree edit distances:

A survey on tree edit distance and related problems, Philip Bille. Theoretical Computer Science, 2004.

These tree edit distances are used for problems like detecting plagiarism in student source code, or diff algorithms for HTML and XML.


Philosophers friendly TCS theorem I understand that it is a naive and very general question. I would like to know when does a theorem of theoretical computer science become interesting to professional philosophers? I understand that the question whether P != NP is pretty interesting to philosophers. Now let's take the conjecture about the existence of one way functions. Is there any philosophical implications of the existence of one way functions?

You might be interested in Scott Aaronson's recent paper Why Philosophers Should Care About Computational Complexity, to appear in Computability: Gödel, Turing, Church, and Beyond, edited by B. J. Copeland, C. Posy, and O. Shagrir, MIT Press, 2012. ECCC TR11-108, arXiv:1108.1791.


How well can an arbitrary (unknown) quantum state be imperfectly cloned? How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned?

Given an unknown state ${\rvert \psi \rangle}$, say one can clone ${\rvert \phi \rangle}$ , such that
$${\langle \phi }{\rvert \psi \rangle}= \delta$$

If $\rvert \phi \rangle$  and  $\rvert \psi \rangle$ are identical and same, $\delta = 1$, however we know, due the no cloning theorem, that $\delta<1$.

My question is what is the 'highest' value of $\delta$ one can achieve using polynomial time 'resources', i.e. how well can an UNKNOWN quantum state be imperfectly cloned?

(Let's agree we $\rvert \psi \rangle$, both $\alpha, \beta$ are non-zero, i.e. not basis states)

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

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

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

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

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

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