Matrix multiplication with transpose Let $A,B\in\mathbb{F}^{n\times n}$ be two $n\times n$ matrices over
the underlying field $\mathbb{F}$. In addition, $A$ is guaranteed
to be a symmetric matrix, i.e, $A=A^{T}$. We assume complexity measure to be the number of field operations over $\mathbb{F}$. Now consider at the following problem:-

  Given $A,B$ and $AB$ as input, can we compute $AB^{T}$ in $o(n^{\omega})$ time?

Here $\omega$ is the exponent of matrix multiplication. Note that $AB^{T}=A^{T}B^{T}=(BA)^{T}$.
Thus computing $BA$ in $o(n^{\omega})$ time is also enough.

No.
Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. Computing $AB^T$ from $A$, $B$ and $AB$ means computing $XY^T$ from $X$ and $Y$, since $AB = 0$


Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity? Denote by  $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.
In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian cycles, which suggests that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian.
In his comment, Saeed have commented on a different extension that seems stronger, except it requires the graph to be strongly connected.
The strong connectivity was proven redundant for the Ghouila-Houri theorem about 30 years after it was first published, and I was wondering if the same holds for the extension Saeed presented.
So the question is:

Who proved (can anyone find the reference) that $\delta^+(G)+\delta^-(G) \geq n$ implies $G$ is Hamiltonian, given that $G$ is strongly connected?

Is the strong connectivity redundant here as well, i.e. Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

(Note that while the graph obviously has to be strongly connected for it to be Hamiltonian, I'm asking whether this condition is implied by the degree conditions).

The variation that I suggested was actually slightly different variation of Woodal theorem. Perhaps I saw it in the Bang-Jensen and Gutin's book. At the time that I wrote a comment I didn't check the book for correctness. So to be sure I wrote the graph should be strongly connected. BTW, that statement holds because can be interpreted as a special case of Woodal theorem. In addition does not need strongly connectivity requirement.

This is the theorem 6.4.6 from Bang-Jensen and Gutin's book:

  Let $D$ be a digraph of order $n\ge 2$. If $\delta^+(x)+\delta^-(y) \ge n$ for all pairs of vertices $x$ and $y$ such that there is no arc
  from $x$ to $y$, then $D$ is hamiltonian.

That means the answer to the second part of your question is also Yes.

There was a doubt about that whether $n$ is a tight bound or not. Here I try to answer it. We cannot reduce the requirement of at least $n$ to $k<n$, consider the following graph. $a,b,c$ are making bidirected triangle, and $e,d$ are making a bidirected $k_2$. If hamiltonian cycle starts at $e$, it cannot go to $d$ in the next move because the only way for $d$ is using $b$ but, $b$ is the only way to back to $e$. On the other hand the Hamiltonian cycle after $e$ cannot go to $c$, because then the only back way to $e,d$ is going directly to $d$ to use $b$ in next moves, but again we are in the previous position. Also from the picture it's clear that every vertex has in and out degree at least $2$. So sum of every two arbitrary in-out is at least $4=5-1 = n-1$. We can extend these sort of graphs to arbitrary $n$.

P.S1: Sure the aforementioned theorem holds for simple digraphs. i.e digraphs without loop or parallel edges.

P.S2: I don't have a good Tex tool right now. So image is not good.


Dividing a complete graph into two cliques with maximal sum of edge weights Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\frac n2\in\mathbb Z$ vertices, and the sum of all weights is maximized.

Example:

$\begin{bmatrix}
&A  &  B &   C &   D\\
A   &0    &1    &0.66 &0.5\\
    B   &1    &0    &0.01 &0.5\\
    C   &0.66 &0.01 &0    &0.33\\
    D   &0.5  &0.5  &0.33 &0
\end{bmatrix}$

The above adjacency matrix of graph $G$ is an instance of the problem with $A$, $B$, $C$ and $D$ being the vertices of the graph. In this instance, the solution to the problem is pairing $A$ with $B$ $(1)$ and $C$ with $D$ $(0.33)$, with the resulting weight sum $1.33$ being the maximum achievable value.

What would be the exact algorithm for solving this problem, or maybe there is a problem which it can be reduced to?

I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for $n = 6$ you can end up with extra edges that don't form any other maximal cliques otherwise:

If that assumption is correct, your operation is called a bisection of the graph. You want to maximize the remaining weights, and thus minimize the edge weights of the edges that are cut.

This problem is NP-complete, and you can find a reduction in "Some simplified NP-complete graph problems" by M. R. Garey, D. S. Johnson, and L. Stockmeyer in Theorem 1.3 and the preceding paragraph.


In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament. Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial time,if so please give the idea
else please mention proof of NP-completeness

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

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

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

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

Now I think the situation is as follows:

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

Some explanations and references:

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

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

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


2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ?
I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in Java.

Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly,  it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link.  https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22


Lower bound of checking graph connectivity on stream I would like to check the status of the space lower bound for solving connectivity problem on stream in $p$ passes. The $\Omega(n/p)$ was stated in the literature but it seems to be for a slightly different problem. Did I miss something? Details below.

Given a graph $G$ of $n$ vertices in a stream (edges are presented one by one in a streaming manner), we want to check whether $G$ is connected. What is the minimum space an algorithm needs to solve this problem when it is allowed to read the stream for $p$ passes?

Feigenbaum et al. showed $\Omega(n)$ space for one pass algorithms for a class of problems that includes this problem (see Section 5.1) and stated that the $\Omega(n/p)$ space lower bound for connectivity was proved by Henzinger et al.. However, the only lower bound for "connectivity" problem is actually for the "$s$-$t$ connectivity" problem: given vertices $s$ and $t$, we want to check if $s$ and $t$ are in the same connected component (Theorem 6). The proof of this cannot be used for the connectivity problem since there might be many vertices incident to no edge.

So, my question is, for the specific version of connectivity that I stated, is there any lower bound known for $p$-pass stream?

Here's a reduction from Disjointness that might work:

Given input $n$ bit vectors $x$ and $y$, Alice and Bob want to come up with edge sets $E_1$ and $E_2$ for a graph $G$ such that $G$ is connected iff there is no index such that $x_i = y_i = 1$.

The graph $G$ will have vertex set ${0,1,\ldots,n} \times {0,1}$. For $i < n$, Alice adds the edge $((i-1,0),(i,0))$ to $E_1$ iff $x_i = 0$; similarly, Bob adds the edge $((i-1,1),(i,1))$ to $E_2$ iff $y_i = 0$. Additionally, Alice adds all the edges of the form $((i,0),(i,1))$ for $i\in {0,\ldots,n}$.

I think this graph has one connected component iff $(0,0)$ is connected to $(n,0)$, which happens iff for each $i\in{1,2,\ldots,n}$, either $x_i$ or $y_i$ is 0; that is, the two inputs are disjoint.


Graph decompositions for combining "local" functions of vertex labelings Suppose we want to find
$$\sum_x \prod_{ij \in E} f(x_i,x_j)$$
or
$$\max_x \prod_{ij \in E} f(x_i,x_j)$$

Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a graph $G=\{V,E\}$ and $f$ is an arbitrary function. This quantity is easy to find for bounded tree width graphs and in general NP-hard for planar graphs. Number of proper colorings, maximum independent set and number of Eulerian subgraphs are special instances of the problem above. I'm interested in polynomial time approximation schemes for problems of this kind, especially for planar graphs. What graph decompositions would be useful?

Edit 11/1: As an example, I'm wondering about decompositions that might be analogous to cluster expansions of statistical physics (ie, Mayer expansion). When $f$ represents weak interactions, such expansions converge, which means that you could achieve given accuracy with $k$ terms of the expansion regardless of the size of the graph. Wouldn't this imply existence of PTAS for the quantity?

Update 02/11/2011

High temperature expansions rewrite partition function $Z$ as a sum of terms where higher order terms depend on higher order interactions. When "correlations decay", high order terms decay fast enough so that almost all of $Z$'s mass is contained in finite number of low-order terms.

For instance for Ising model consider the following expression of its partition function

$$Z=\sum_\mathbf{x\in \mathcal{X}} \exp J \sum_{ij \in E} x_i x_j = c \sum_{A\in C} (\tanh J)^{|A|} $$

Here $c$ a simple constant, $C$ is a set of Eulerian subgraphs of our graph, $|A|$ is number of edges in subgraph $A$.

We have rewritten partition function as a sum over subgraphs where each term in the sum is exponentially penalized by size of the subgraph. Now group terms with same exponent together and approximate $Z$ by taking first $k$ terms. When number of Eulerian subgraphs of size $p$ doesn't grow too fast, the error of our approximation decays exponentially with $k$.

Approximate counting is hard in general, but easy for "correlation decay" instances. For instance, in the case of Ising model, there's correlation decay when $f(k)$ grows slower than $(\tanh J)^k$ where $f(k)$ is the number of Eulerian subgraphs of size $k$. I believe in such case, truncating high temperature expansion gives a PTAS for $Z$

Another example is counting weighted independent sets -- it's tractable for any graph if the weight is low enough because you can make the problem exhibit correlation decay. The quantity is then approximated by counting independent sets in bounded size regions. I believe Dror Weitz' STOC'06 result implies that unweighted independent set counting is possible for any graph with maximum degree 4.

I've found two families of "local" decompositions -- Bethe cluster graphs and Kikuchi region graphs. Bethe decomposition essentially tells you to multiply counts in regions, and divide by counts in region overlaps. Kikuchi region graph method improves on this by taking into account that region overlaps can themselves overlap, using "inclusion-exclusion" type of correction.

Alternative approach is to decompose the problem into global tractable parts, like in, "Variational Inference over Combinatorial Spaces". However, local decompositions allow you to control approximation quality by selecting region size

What I want to say is too long for (but really should be) a comment.

If I am reading the question correctly, you want a FPRAS (fully polynomial randomised approximation scheme) for either of the above quantities, each of which includes various #P-complete problems as special cases.  In particular, you want a general FPRAS in the case of planar graphs, by the use of cluster expansion.

I doubt that this is possible due to the fact that NP-completeness of the existence problem (e.g. proper colouring) implies that the corresponding counting problem (e.g. number of proper colourings) is complete in #P with respect to AP-reducibility (approximation-preserving).  See Dyer, Goldberg, Greenhill and Jerrum, Algorithmica (2004) 38: 471-500.

But perhaps I've misread the question.

(Actually, would you be able to explain to the uninitiated the meaning of high-temperature expansions?)


How important is knowing how to program for TCS? Coming from a more mathematical background, I never really learned how to code.
I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in general). I can write algorithms in pseudo-code, but I don't really know any programming language.
I can imagine that someday I may have to implement some algorithms for my work, but then can I wait for this moment? Or is there something more?
How important is knowing how to code in TCS (in fields where programming is not directly involved)?
Are there reasons which could bring a CS theorist (for example) to know how to code? Is it worth spending a lot of time learning how to code? And if there are, is there a category (functional, imperative, object-oriented...) of programming language that would be more suited?

Theoretical computer science is a broad field and the importance of programming depends on what you do in TCS.  I will mention two ways in which programming can help you, without implying that these are the only ways.

First, if you design algorithms for problems of practical importance, implementing your algorithms and making the code available to others can be a big plus.  For example, the convex hull problem arises in many fields, and people use software packages such as cdd by Komei Fukuda and lrs by David Avis to solve this problem.  If they had published their algorithms only in papers, probably less people would have used their algorithms.  More users mean more feedback and probably also more opportunities to collaborate, which is invaluable.

Second, even if you do not work in algorithms, writing a one-time code helps you to test a simple conjecture when the conjecture is suitable to numerical calculation.  For example, if you wonder whether the product of three positive definite matrices always has a positive trace, it is easy to write a code to test it for some random choices of 2×2 or 3×3 positive definite matrices and find a counterexample.  Although you do not advertise that you wrote any program to test the conjecture, programming can save the time which would have been spent in vain trying to prove a false statement.

The programming language to choose depends on what you want to do with programming, and it can be a topic for a whole book in my opinion.  But if you design algorithms and want to implement your algorithms so that other people can use the implementation, then one important factor is availability.  Although you can expect that most potential users of your code have access to a C compiler, you cannot expect that the same people have access to a Haskell compiler.  For one-time programs, the choice is more based on available libraries, and includes the environments such as Matlab.

By the way, programming can also be fun.


Reference Request: Application of Block Designs to Software Testing I've started looking at incidence structures and combinatorial designs (possible motivation: to upper-bound some structures in generalized self-assembly), and the Wikipedia article makes the following interesting-yet-unexplained statement: block designs have application to software testing.  (The Wikipedia page with the claim is here).

My google-fu doesn't pick up a good reference for this application.  Can anyone give me a lead?

Suppose you have some software which includes a list of n variables s1,s2,...,sn and suppose each of these variables are able to take on a range of values.  Now suppose you want to test the program for 2-way interactions, that is, you want to test the program runs correctly for every pair of variables si and sj and every possible value that these variables can take.

To do this by a brute-force -- by processing each pair i and j one-by-one, then testing each allowable value of si and sj (while picking the others arbitrarily) -- would require testing a enormous number of cases.

But, we can test for several 2-way interactions in a single test.  For example, if we have three variables s1, s2 and s3, and we test when s1=1, s2=2 and s3=0, then we have tested three possible 2-way interactions simultaneously.

We can design a test-suite for the program based on a covering array -- the columns represent the variables and the rows represent the specific test to be performed (so fewer rows is better).  In a strength 2 covering array, within any two columns i and j, there exists every possible pair of the variables si and sj.  There are higher strength covering arrays which can test for t-way interactions (but usually interactions are a result of only a few components).

Sets of mutually orthogonal Latin squares (and various other block designs) form particularly efficient covering arrays.


What are some results on algorithms that estimate polynomials over a given set of points? There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero.  Are there any results of algorithms that do some sort of estimation of polynomials over a specific set of points? This could be, for instance, approximating for what fraction of these points the polynomial evaluates to zero, or approximating the average value of the polynomial over these points?  The set of points can be specific to the algorithm.

Not really what you asked for, but your question was a bit open, so maybe this will interest you.

For the specific problem of estimating infinite polynomials (generating functions), $A(z) = \sum_{n=0}^\infty a_n z^n$, with a combinatorial origin, there is a recently published paper, "Algorithms for combinatorial structures: Well-founded systems and Newton iterations" by Pivoteau, Salvy and Soria. I believe (though I might be slightly off) it shows that approximations can be computed in complexity that is quadratic in the required precision. The set of points is the radius of convergence, and in particular the singularity of the generating function.


Parametric equation in pi-calculus This is the first time I ask a question on cstheory, so I am very sorry for my english.
I have a (maybe very trivial) problem when trying to find a well-form representation for a root of a recursive equation in pi-calculus.

buffer(x) = out!<x>.buffer<x> + in?(y).buffer<y>

The equation above represents behaviors of a "mutable" single data buffer, it is very simple: the buffer's states are parameterized by x, that means its data cell's value is x. So the buffer can be read by the channel out! and updated by the channel in?. The buffer is somehow a fixpoint of the equation.

Firstly, it seems to me that it is easy to find out a well-formed representation for buffer (using the basic syntax of pi-calculus). The persistent output can be represented by replicating like !out. But latter, for the input, it is not easy as it seems.

Can anybody give me some suggestions ?

(I try to express some reactions from suggestions of @Martin Berger)

If we take an input with $\overline{in}\langle z \rangle$:

$\overline{in}\langle z \rangle \vert buffer(x) \rightarrow buffer(z)$ (recursive definition)

$\overline{in}\langle z \rangle \vert (\nu a)\big(\overline{a}\langle x\rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big) \Rightarrow$
$(\nu a)\big(\overline{a}\langle z\rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big)
$ (encoding version)

And now we get an output with $out(t).P$:

$out(t) . P \vert buffer(z) \rightarrow P\lbrace z/t\rbrace \vert buffer(z)$ (recursive definition)

$out(t) . P \vert (\nu a)\big(\overline{a}\langle z\rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big) \Rightarrow$
$P\lbrace z/t \rbrace \vert (\nu a)\big(\overline{a}\langle z \rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big)$ (encoding version)

The paper “On Recursion, Replication and Scope Mechanisms in Process Calculi” by Jesús Aranda, Cinzia Di Giusto, Catuscia Palamidessi, and Frank D. Valencia gives an encoding of the polyadic pi-calculus with recursive definitions in terms of the polyadic pi-calculus with replication and vice versa. The essence of the encoding (in the first direction) is to replace the recursive definition by the replication of a process, so that each invocation of the recursive definition results in a new process.


Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$? Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?

There is an oracle $\mathcal O$ such that $\textsf{ZPP}^{\mathcal O}\not\subseteq \textsf{UP}^{\mathcal O}$. The inclusion is not known, and it would therefore require non-relativizing techniques to resolve the question (and probably even non-algebrizing techniques). On the other hand, the inclusion $\textsf{ZPP}\subseteq \textsf{UP}$ is conjectured to be true, because the Derandomization Hypothesis implies $\textsf{P}=\textsf{ZPP}=\textsf{BPP}$, and since $\textsf{P}\subseteq \textsf{UP}$, we get $\textsf{ZPP}\subseteq \textsf{UP}$.
Oracle sketch. The oracle $\mathcal O$ is constructed in phases. For the $n$-th phase, we fix the strings in $\mathcal O\cap \{0,1\}^n$. For a yes-input, we take a random subset $S\subseteq \{0,1\}^{n-1}$, and set $\mathcal O\cap\{0,1\}^n:=0S$. For a no-input, we set $\mathcal O\cap\{0,1\}^n:=1S$.
The language $\mathcal L$ which now has $\mathcal L\in \textsf{ZPP}^{\mathcal O}\setminus \textsf{UP}^{\mathcal O}$ asks the question: on input $1^n$, is it true that (1) $|\mathcal L\cap 0\{0,1\}^{n-1}|>\frac{1}{4}2^{n}$, and (2) not $|\mathcal L\cap 1\{0,1\}^{n-1}|>\frac{1}{4}2^n$? Because of the way we constructed the oracle, for any $n$ we always have either both (1) and (2) are true, or neither (1) nor (2), so it suffices for an $\textsf{RP}$ algorithm to check whether (1) holds, and for a $\textsf{co-RP}$ algorithm to check whether (2) holds. Hence $\mathcal L\in \textsf{RP}^{\mathcal O}\cap \textsf{co-RP}^{\mathcal O}=\textsf{ZPP}^{\mathcal O}$.
The details of diagonalizing against all $\textsf{UP}$-Turing Machines are omitted, but are standard.


Construction of binary puzzle Does there always exists a $n \times n$ grid with $0$s and $1$s that satisfy the following conditions:

there is an equal number of 1s and 0s in each row and column
no more than two identical numbers next to or below each other are
allowed
there can be no identical rows or columns

How to construct a nxn grid that satisfy all the above conditions?

To meet condition 1, $n$ must be even, so let's assume that it is. Then we can automatically achieve both conditions 1 and 2 by making an $n/2\times n/2$ matrix whose entries are $2\times 2$ submatrices in one of the two patterns
$$ \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right),\quad \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right), $$
as these prevent any three consecutive digits (in either direction) from being equal.

Now all you need to do is to choose which of these two $2\times 2$ matrices to use in which position of the $n/2\times n/2$ matrix. You must now avoid both equal rows and columns, and complementary rows and columns, but that's still very easy, for instance by putting the 1-0-0-1 matrices down the main diagonal and the 0-1-1-0 matrices everywhere else.


The polynomial languages and ordered syntactic monoids A polynomial language is a languge which could be represented as the finite union of languages of the form:
$$
 A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X
$$
Such an expression is called a monom and it's degree is the value $k$.
Equivalently it could be defined as the smallest class containing the finite languages, languages of the form $A^*$ for $A \subseteq X$ and closed under union and concatentation.

The degree of a polynomial language is the maximum degree of the monoms in a minimal (with regard to the degree) representation of the polynomial language in the form of unions of monoms.

An ordered monoid $(M, \le)$ is a monoid $M$ together with a partial order which is compatible with multiplication. A set $D$ is called downward closed if $p \in D$ and $q \le p$ implies $q \in D$. An ordered monoid recognized a language $L$ via a morphism $\varphi : X^* \to M$ if
$$
 L = \varphi{-1}(\downarrow\varphi(L))
$$
where $\downarrow D$ denotes the smallest downward closed subset containing $D$.

For the syntactic monoid $Syn(L)$ there is a natural order given by $u \le_L v$ iff
$$
 \forall p,q \in X^* : pvq \in L \Rightarrow puq \in L.
$$
Then for $[u], [v] \in Syn(L)$ it is $[u] \le [v] :\Leftrightarrow u \le_L v$.

  Let us consider a polynomial language $L$ of degree $k$ and words $u,v$ with $\mbox{alph}(v) \subseteq \mbox{alph}(u)$. Then for all $p,q$ we have $pu^{k+1} q \in L$ implies that $pu^kv u^k q\in L$, too. Thus, the syntactic orderd monoid of $L$ satisfied an equation of type $u^{\pi}vu^{\pi} \le_L u^{\pi}$

Remark: $u^{\pi}$ denotes the unique idempotent associated with $u$, for example $\pi = n!$ where $n$ is the size of the finite monoid.

The shaded paragraph I do not understand, the relation
$$
 pu^{k+1}q \in L \Rightarrow pu^k vu^k q \in L
$$
for $\mbox{alph}(v) \subseteq \mbox{alph}(u)$ and $k$ the degree of the polynomial is clear cause a monom of degree $k$ can "fix" just $k$ letters, and so some $u$ lies in some $A_i^* \subseteq X^*$ and so also $v$. But why does this order relation for the syntactic monoid follows? Is there any simple relation between the idempotent powers and the degree I do not see?

The relation $pu^{k+1}q\in L\Rightarrow pu^k vu^kq\in L$ is true for any $p,q$, $k$ big enough and $v$ with $alph(v)\subseteq alph(u)$.

Let call $a$ the first letter of $u$ and $b$ the last letter.
Let $v$ with $alph(v)\subseteq alph(u)$, and $v'=uvu$.

Then by using the relation above with $v'$, we get that for any $p,q$ and $k$ big enough, we have $pu^{k}q\in L\Rightarrow pu^k vu^kq\in L$, which is the definition of $u^kvu^k\leq_L u^k$. In particular, for $n$ big enough, we get $u^{n!}vu^{n!}\leq_L u^{n!}$, which is the wanted equation.


Problems in NP but not in Average-P/poly The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\mathsf{\Sigma^P_3}$, no $\mathsf{NP}$-complete problem will belong to $\mathsf{P/poly}$.

I'm interested in the following question:

  Assuming that $\mathsf{PH}$ does not collapse, or assuming any other reasonable assumption in structural complexity, what hard-on-average $\mathsf{NP}$ problems are proven not to lie in $\mathsf{Average\mbox{-}P/poly}$ (if any)?

A definition of $\mathsf{Average\mbox{-}P/poly}$ can be found in Relations between Average-case and Worst-case Complexity. Thanks to Tsuyoshi for pointing out that I actually need to use $\mathsf{Average\mbox{-}P/poly}$ instead of $\mathsf{P/poly}$.

I think there are problems such as (the decision versions of) FACTORING or DLOG which are conjectured to lie in $\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$, but the conjecture is not proven based on separations between complexity classes. (Please correct me if I'm wrong.)

This is a slightly improved version of my two comments on the question combined.

Let’s restrict our attention to distributional problems in DistNP (aka (NP, P-computable)) for simplicity.  Then you are looking for a problem in DistNP ∖ Average-P/poly.  Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly.  And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under average-case reductions.

(Considering a larger class SampNP (aka (NP, P-samplable)) instead of DistNP does not change the situation much because DistNP ⊆ Average-P/poly if and only if SampNP ⊆ Average-P/poly.  This equivalence is a direct corollary of the result by Impagliazzo and Levin [IL90] that every distributional problem in SampNP is average-case reducible to some distributional problem in DistNP.)

I do not know which natural assumption implies DistNP ⊈ Average-P/poly.  The assumption that the polynomial hierarchy does not collapse is not known to imply even a weaker consequence that DistNP ⊈ Average-P, according to Section 18.4 of Arora and Barak [AB09]: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”

References

[AB09] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

[IL90] Russell Impagliazzo and Leonid A. Levin.  No better ways to generate hard NP instances than picking uniformly at random.  In the 31st Annual Symposium on Foundations of Computer Science, 812–821, Oct. 1990.  http://dx.doi.org/10.1109/FSCS.1990.89604


How to exploit knowledge of the sampling distribution for better generalization bounds? In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using PAC-Bayesian techniques to convert the distribution over $X$ into a distribution over hypotheses, which is what I think this paper is doing:
http://www0.cs.ucl.ac.uk/staff/G.Lever/pubs/ALTfinal.pdf

Any other methods for making clever use of $P$?

[Edit 25.03.2015: In light of Vitaly's answer, let me sharpen the question. Suppose that I know the sampling distribution only approximately as $Q$. Can we formulate a generalization bound in terms of $D(Q||P)$ or $||P=Q||_{TV}$?]

For specific distribution over $X$ uniform convergence bounds scale linearly with the logarithm of the size of the (smallest) $\epsilon$-cover of the concept class $C$ (the cover can use any functions over $X$). This is proved in "Learnability with respect to fixed distributions" paper of Benedek and Itai. As a result sample complexity of PAC learning scales linearly with this parameter.


Certified compiler and optimizations in Coq/Agda I am interested in verified compilers formalized in Martin-Löf type theory, i.e. Coq/Agda. At the moment I’ve written a small toy example. Therewith I can prove that my optimizations are correct. For example that additions with zero can be eliminated, i.e. expressions like "x + 0".

Are there optimizations that are difficult to perform with a regular compiler, that would serve as a good example? Is it possible to prove certain properties of a program that allow optimizations that are not possible to perform with a regular compiler? (i.e. without the inference that is possible with a theorem prover)

I would be interested in ideas or examples and also references on the topic.

A related question:
Compiler correctness proofs

edit:
As Tsuyoshi nicely put it in the comments:
I am looking for optimization techniques which are difficult to implement if a compiler is written in (say) C but easier to implement if a compiler is written in (say) Coq. As Agda compiles to C (via haskell) it is possible to do everything that is possible in Agda also in C. Probably the only benefit of theorem provers like Coq/Agda is that the compiler and the optimizations can be verified.

edit2:
As suggested by Vijay D I write what I've read so far.
I mainly focused on Xavier Leroy and the CompCert project at INRIA (there is a 80 pages paper that is a good read, I think).
A second interest was in the work of Anton Setzer on interactive programs. I though that perhaps his work could be used to prove properties about IO programs and bisimulation of IO programs.
Thanks for mentioning Sewell. I've heard his talk "Tales from the jungle" at ICFP and read perhaps 2-3 of his papers. But I haven't specifically looked at his work and that of his coauthors.
I did not yet find out where to start or look for papers on optimizing compilers; e.g., which optimizations would be interesting to look at in the setting of a verified compiler.

this paper by Yves Bertot, Benjamin Gr´egoire, and Xavier Leroy builds an optimizing compiler for a C-like language based purely on the Coq specification.  some of this technology is apparently utilized in the CompCert C compiler.

A structured approach to proving compiler
optimizations based on dataflow analysis

it considers the correctness of two optimizations, constant propagation (CP) and common subexpression elimination (CSE), section 4. these optimizations are more advanced than those that are associated with the non Coq-based compiler(s) for the same language. see eg this benchmark chart compared to gcc. (the Coq-based compiler is presumably slower to compile although this is rarely mentioned!)

  An original aspect of ConCert is that most of the compiler is written directly
  in the Coq specification language, in a purely functional style. The executable
  compiler is obtained by automatic extraction of Caml code from this specification.

however at the end of the paper they do note that there are some compiler optimizations in real compilers that cant be modelled in their framework.

improved optimization is not the only element of consideration here, another aspect is that compiler optimization logic can be subject to subtle defects esp due to its complex nature. over the years gcc has been found to have bugs in its numerous optimization logic routines. eg gcc bug?


What's the meaning of "input size" for 3-SAT? In the computational complexity theory, we say that an algorithm have complexity $O(f(n))$ if the number of computations that solve a problem with input size $n$ is bounded by $cf(n)$, for all integer $n$, where $c$ is a positive constant non-depending on $n$, and $f(n)$ is an increasing function that goes to infinity as $n$ does.

The 3-SAT problem is stated as: given a CNF expression, whose clauses has exactly 3 literals, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

A CNF expression consists of, say, $k$ clauses involving m variables $x_1,x_2, ..., x_m$.
In order to decide if 3-SAT has polynomial complexity $p(n)$, or not, I need to understand something so simple as "what is n" in the problem.

My question is:

  Which is considered, in this particular 3-SAT problem, the input
  size n?

Is it the number k of clauses? Or is it the number m of variables?
Or n is some function of k and m? ( $n=f(k,m)$ ).

What exactly the theoretical computer scientits consider as the input size for this problem?

I did the estimate that $n \leq $constant $* m^3$. Is this correct for you?

In complexity theory, $n$ is the length in bits of the input the algorithm has been given.

In particular, it is not the "number of bits required to represent the input" because that would be very hard to reason about — you'd have to prove that you'd chosen the most efficient possible coding.  If my input to 3-SAT is the formula consisting of 276 repetitions of the clause $X\vee \neg Y \vee \neg Z$, then $n$ is however many bits it took me to express that input; it is not, for example, the number of bits it would have taken me to express the equivalent formula that has just one copy of the clause.

Now, in practical terms, complexity is often expressed in terms of other measures.  For example, the running time of algorithms in graph theory is often given as a function of the number of vertices and/or edges; in satisfiability, the number of variables and/or clauses is often used.  In terms of describing algorithms, it's often more intuitive to give the bounds that way: it's a higher-level view of a graph as a set of vertices and edges, rather than the "machine-code" view of representing that as a string of bits.  In terms of complexity theory, we're often only interested in broad questions like, "Is there a polynomial-time algorithm?" or "Does it need exponential time?"  Because these questions are insensitive to polynomial factors, $n$ is sometimes used to mean other things.  For example, in 3-SAT, a formula in $N$ variables can be coded using $n=4N^3$ bits (see below).  Anything that's polynomial in $n$ is polynomial in $N$ and vice-versa so, for that kind of question, it doesn't really matter which you use.

Here's how to code a 3-CNF formula with $N$ variables in $4N^3$ bits.  Every clause has either 0, 1, 2 or 3 negations; we may permute so that the negated literals appear first in any clause. Now, fix an enumeration (say, lexicographic) of all the $N^3$ possible 3-tuples of variables. For each kind of clause (0, 1, 2 or 3 negations), make a list of $N^3$ bits such that the $i$th bit is 1 if, and only if, the $i$th 3-tuple is a clause with that number of negations. The input is those four lists.  The first thing any algorithm using this input format would do is check that its input length is $4N^3$ for some $N$.  If it isn't, the input doesn't code anything, so it doesn't code a satisfiable formula, so the algorithm rejects.

Note that even the above coding still has some redundancy, since the clause $X\vee Y \vee Z$ appears in six permutations.  If $n$ were the minimum number of bits required to code the input, we'd be forced to use a coding that avoided that redundancy. Worse, if we were reasoning about 3-SAT over random inputs selected from some distribution, the minimum number of bits required to express some input would involve something like Huffman coding the inputs according to that distribution, and it would be a total nightmare. So it's just the length of the input you were given.


Are there hypothesis classes that are hard to learn but easy to test? Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\epsilon$-far testable).

My question is:

  Fixed a distribution, is there any known hypothesis class that is hard (say NP-hard) to properly learn (to avoid the problem to be trivial, we assume the class is statistically  PAC-learnable) under this specific distribution, but easy (say within polynomial time) to test under the same distribution?

As far as I know most of the results for proving hardness of learning are reduced to the hardness of testing (i.e. decide a gap version of the risk minimization is hard).

Take the class  $\mathcal{M}$ of monotone boolean functions under the uniform distribution on $\{0,1\}^n$:

it is known that $O(\sqrt{n}/\varepsilon^2)$ queries are sufficient to test it (even with non-adaptive testers) [KhotMinzerSafra15].
learning $\mathcal{M}$ under the uniform distribution, even allowing membership queries, requires $2^{\Omega(\sqrt{n}/\varepsilon)}$ queries ([BshoutyTamon96,BlaisCOST15]).


Proof for Kolmogorov complexity is uncomputable using reductions I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, but there should be a proof by reducing from something like the Halting Problem, or Post's Correspondence Problem.

You can find two different proofs in:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)

In Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications it is presented as an exercise (with a hint on how to solve it that is credited to P. Gács by W. Gasarch in a personal communication Feb 13, 1992).

** I decided to publish an extended version of it on my blog.


Transform a CNF into an equivalent 3-CNF defined on the same variables (I posted this question on CS ten days ago, with no answer since then - so I post it here.)

Any CNF formula can be transform in polynomial time into a 3-CNF formula  by using new variables. It is not always possible if new variables are not allowed (take for instance the single clause formula : $(x_1 \lor x_2 \lor x_3 \lor x_4)$).

Let define the (SAT to 3-SAT) problem : Given $F$, a CNF formula. Is it possible to transform $F$ into an equivalent 3-CNF defined on the same variables as $F$ ? - where "equivalent" means with the same set of models.

What is the complexity of this problem ?

(From the comment above)
The problem seems coNP-hard; the simple reduction is from 3CNF-UNSAT (which is coNP-complete):
given a 3CNF formula $\varphi = C_1 \land ... \land C_m$, extend it adding a new clause with 4 new variables:

$$\varphi' = (y_1 \lor y_2 \lor y_3 \lor y_4) \land C_1 \land ... \land C_m$$

$\varphi'$ has an equivalent 3CNF formula defined on the same variables if and only if the original formula $\varphi$ is unsatisfiable.

($\Leftarrow$) the 3CNF formula $(y_1 \lor y_2 \lor y_3) \land (y_1 \lor y_2 \lor y_4) \land C_1 \land ... \land C_m$ is equivalent to $\varphi'$

($\Rightarrow$) suppose that $\varphi'$ has an equivalent 3CNF formula $\varphi''$ and that $\varphi$ is satisfiable.
Pick a satisfying assignment $X = \langle \dot{x}_1,...,\dot{x}_n \rangle$ of $\varphi$, and simplify both $\varphi'$ and $\varphi''$ replacing the variables $x_i$ with
the corresponding truth values $\dot{x}_i$. We get $\varphi'_X$ which is satisfiable if and only if $\varphi''_X$ is satisfiable
(both contain only variables $y_i$).
Clearly $\varphi'_X = (y_1 \lor y_2 \lor y_3 \lor y_4)$. Every clause of $\varphi''_X$ contains at most three variables,
so we can pick one of them, e.g. $(y_1 \lor \lnot y_2 \lor y_3)$, and use it to build a satisfying assignment for $\varphi'$:
$\langle y_1=false, y_2=true, y_3=false,y_4=true,\dot{x}_1,...,\dot{x}_n \rangle$ which is not a satisfying assignment for $\varphi''$,
leading to a contradiction.


About properties of adjacency matrix when a graph is planar 1- Is there any specific properties for adjacency matrix when a graph is planar?
2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?

Computing determinant and permanent of planar graphs are as hard as computing them in general graphs. They are complete for GapL and #P respectively. See this paper by Datta, Kulkarni, Limaye, Mahajan for more details.


Understanding least-fixed point logic To better understand a paper I'm trying to get a brief understanding of least-fixed point logic. There are a few points where I am stuck.

If $G = (V,E)$ is a graph and

$$ \Phi(P) = \{(a,b) \mid G \models E(a,b) \lor P(a,b) \lor \exists z (E(a,z) \land P(z,b)) \}$$

is an operator on the binary relation $P$. I do not understand why the least fixed point $P^*$ of $P$ is the transitive closure of $E$. The example is taken from Finite Model Theory and Its Applications (p. 60).

When extending the first-order logic with the least-fixed pointer operator I do not understand why the relation symbol $S_i$ needs to be positive in the formula. Positive means  that every occurence of $S_i$ in the formula is within an even number of negation symbols.

Does anyone have idea what is good to read for an intuitive understand of least-fixed pointer logic and its syntax and semantics?

If you are having trouble with the concept of least fixed point, I would recommend spending some time getting a background in more general order theory.

Davey and Priestley, Introduction to Lattices and Order is a good intro.

To see why the transitive closure is the least fixed point, imagine building up the closure from an empty set, applying the logical formula one step at a time.  The least fixed point arrives when you can't add any new edges using the formula.

The requirement that the formula be positive ensures that the process is monotonic, i.e. that it grows at each step.  If you had a negative subformula, you could have the case where on some steps the set of edges would decrease, and this could lead to a non-terminating oscillation up and down, rather than a convergence to the LFP.


Upper bound to number of closed itemsets Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper supersets. Closed itemsets are important in data mining because they provide a compact representation of the dataset.

I'm trying to find some non-trivial upper bound to the number of closed itemsets. It seems a natural combinatorial question and I'm surprised I can't find anything non-trivial.

Any suggestion/reference? Thank you.

The bound is $2^{\min(n, m)}$. It is an upper bound because no two "formal concepts" (i.e., closed itemsets with their respective transaction sets) can have the same subset of items or the same subset of transactions. Considering $D$ as an $n$ by $m$ matrix of $0$ or $1$ such that each cell indicates whether item $i$ is part of the $j$-th transaction of $D$, you can reach the bound by filling the matrix to '1' and setting to '0' a "diagonal" (well, not really a diagonal since the matrix is rectangular). If you wish, you can then permute the rows and/or the columns and the number of closed itemsets obviously remains the same. Any number of '1' out of the square matrix where there is the diagonal can be turned into '0' too.

Quite recently, Richard Émilion published in Discrete Applied Mathematics the average and the variance of the number of (frequent) closed itemsets in a rectangular 0/1 matrix with a Bernoulli distribution of the '1's: http://www.univ-orleans.fr/mapmo/membres/emilion/publ/sizeofgl.pdf

That is interesting because real-life datasets usually are very sparse. I am not aware of any bound of the number of (closed) itemsets w.r.t. the density. I believe the formula would not be beautiful at all!

I have already told that to a3nm at ICDT'14: you guys (I am not a theorist, just a data miner) want to read about the so-called "Formal Concept Analysis" (FCA): https://en.wikipedia.org/wiki/Formal_concept_analysis


Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed Update:
This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.
http://www.youtube.com/watch?v=VbSwwos4R2E
I want to know if there is an efficient algorithm that allows me to visit every node in a planar graph with the minimum weight, revisiting allowed.  Each node can have up to 4 linked nodes.

I uploaded the graph drawing as an example. In that example, one good route would be:

A - B - C - D - E - F - G - H - I - J - K - L - H - I - M

Summing weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 2 + 4 + 4 + 4 + 2 + 1 = 61

But another route, with less weight, would be:

A - B - C - D - E - F - G - H - I - M - I - H - L - K - J

Weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 1 + 1 + 2 + 4 + 4 + 4 = 60

Of course, I want to get the path with less weight. Revisited is allowed because otherwise I can't visit all nodes.
I'm not a Mathematician myself so easy talk would be much appreciated. I'm familiar with algorithms like A* and Dijkstra, that algorithms are useful when I have a target to search, but in this case I'm not searching a particular target.
Thanks!

According to this abstract, deciding whether a 4-regular planar graph has a Hamiltonian Path is NP-complete.

Edited to add: Call a path that is allowed to revisit nodes a walk. Let $G$ be a graph on $n$ vertices and let us impose a weight of 1 on each edge. Then, $G$ has a Hamiltonian path if and only if the minimum weight walk in G visiting each vertex has weight $n-1$. In other words, if you can compute the minimum weight of a Hamiltonian walk, you can can detect the existence of Hamiltonian paths.


Path of exact cost in edge labelled DAG? Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels.

The problem is:

  Find a path from $s$ to $t$ with cost $a$.

I suppose this is NP-hard.

Some questions:

Would putting a bound $\max w_i < C$ make the problem easier?
What are the best algorithms for this?
Is the problem NP-complete?

Update
What about this modification of Number: 63 Shortest Weight-Constrained Path

To each edge associate second label weight $r_i \in \mathbb{N}$. The weight of a path is the sum of $r_i$.

Assume (possibly small) bound $C$ of the costs $w_i$ and solve:

$cost = a$ and $weight < K$.

Would it be still polynomial in $n,m,C$ or NP-hard instances exist (one can assume positive labels if this helps)?

Yes, it's NP-complete, by a reduction from subset sum. It's easiest to see using a multigraph: make a directed path, double each edge, and make one of the two doubled edges have cost zero, then cost $a$ can be achieved if and only if it is the sum of some subset of the weights of the nonzero edges. If you don't like multigraphs, subdivide the edges.

If you assume that $\max w_i<C$ then there's a dynamic programming algorithm with time $O(mnC)$: just process the nodes in a topological ordering, and for each node calculate the set of path lengths by which it can be reached from $s$.


Determine if a LL(2) grammar is strong Given a LL(2) grammar , how can i determine if it is strong ?

From http://slkpg.com/llkparse.html

Definition:  A grammar G = ( N, T, P, S ) is said to be strong
LL(k) for some fixed natural number k if for all
nonterminals A, and for any two distinct A-productions in the grammar

$A \rightarrow \alpha$

$A \rightarrow \beta$

$FIRST_k ( \alpha \,\, FOLLOW_k (A) ) \cap  FIRST_k ( \beta \,\, FOLLOW_k (A) ) = \emptyset$

That is, each parsing decision is based only on the next k tokens of the
input for the current nonterminal that is being expanded.


On Random Self-reducible properties Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.

1) Is $k$-sum random self-reducible?

That is if $k$-sum can be computed in time $n^{O(k^b)}$ for some $0<b<1$ on $\frac{1}{2}+\epsilon$ of inputs where $n$ is the number of input integers, then can $k$-sum be computed time $n^{O(k^b)}$ for all inputs of $n$ input integers in a randomized sense?

The Patrascu-Williams paper http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf talks about deterministic algorithms and does not imply hierarchy collapse but only tells that the ETH fails (somewhat mildly) when we have a deterministic $n^{O(k^b)}$ algorithm. We have a randomized setting here and even if we have such a random self-reducible condition satisfied, we may still not upset the big picture.

2)Likewise can the $\mathsf{NP=coNP}$ problem be random self reducible?

That is, if for an $\mathsf{NP}$ complete problem we have short certificates for $\frac{1}{2}+\epsilon$ of the $\mathsf{NO}$ instances, then we have short certificates for all $\mathsf{NO}$ instances in a randomized sense?

Update The results in http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf seems to indicate the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible.

I don't know the answer to Question (1)---I suspect there is no such reduction.  But I have a couple of points to make.

A non-adaptive random self-reduction (to the uniform distribution) is a poly-time randomized algorithm $R$ which, given an arbitrary instance $x$ of length $n$ for the decision problem for $L$, produces a list $y^1, \ldots, y^{q(n)}$ of instances of some second length $\ell(n)$.  We have the properties that

(i) each $y^i$ generated by $R$ is individually uniformly distributed, for any fixed input $x$ (although there may be complicated dependence between the $y^i$s, which in some way "encodes" $x$);

(ii) there is a second poly-time algorithm $R'$ which, given $y^1, \ldots, y^q$ along with their $L$-membership values $b^1, \ldots, b^q$ ($b_i = [y_i \in L]$), outputs the desired value $[x \in L]$.

Feigenbaum and Fortnow prove that if an $NP$-complete language has such a reduction then the Polynomial Hierarchy collapses. The argument applies to other target distributions, not just the uniform distribution.

Now my first point (regarding your Question (2)) is that their result directly gives evidence for the difficulty of showing a worst-case to average-case connection for proof systems certifying unsatisfiability of Boolean formulas.  Because the most natural way you'd try to argue that random unsatisfiable formulas are hard to refute (assuming $NP \neq coNP$), is by exhibiting a random self-reduction as above.  Now in the study of proof systems, it might be natural to allow the recovery algorithm $R'$ to be nondeterministic, for example; I believe the [FF] analysis techniques would still apply, but this would take verification after defining things carefully.

My second point is that non-adaptive random self-reductions as above are not the only way to establish average-case hardness of a language $L$ (assuming its worst-case hardness).  There is also the more general notion of a self-correction reduction, which converts any mostly-correct algorithm for $L$ into a fully-correct algorithm, but which does not guarantee that its individual queries be distributed according to any particular distribution (they may depend heavily on the input $x$).  Bogdanov and Trevisan proved that non-adaptive self-correctors for $NP$-complete languages would also collapse the Polynomial Hierarchy.
But it is completely open whether adaptive self-correctors exist for $NP$-complete languages.  I believe the question of adaptive random self-reductions for SAT is also open.
Even if all of these could be ruled out (under the assumption $PH$ does not collapse, say), there might conceivably still be some other, less constructive proof of a worst-case to average-case hardness connection for $NP$.  Bogdanov-Trevisan give a good discussion of the issues here (see also their survey on average-case complexity).


funsplit and polarity of Pi-types In a recent thread on the Agda mailing list, the
question of $\eta$ laws popped up, in which Peter Hancock made thought-provoking remark.

My understanding is that $\eta$ laws come with negative
types, ie. connectives which introduction rules are invertible. To disable $\eta$ for functions, Hank suggests using a custom-made eliminator, funsplit, instead of the usual application rule. I would like to understand Hank's remark in terms of polarities.

For example, there are two presentations $\Sigma$-types. There is the
traditional Martin-Löf split eliminator, in a positive style:

$$
\begin{array}{l}
\Gamma \vdash f : (a : A)(b : B\: a) \to C (a , b) \\
\Gamma \vdash p : \Sigma a : A. B \\
\hline \\
\Gamma \vdash \mathrm{split}\: f\: p : C\: p
\end{array}
$$

And there is the negative version:

$$
\begin{array}{l}
\Gamma \vdash p : \Sigma a : A. B \\
\hline \\
\Gamma \vdash \pi_0\: p : A
\end{array}
\qquad
\begin{array}{l}
\Gamma \vdash p : \Sigma a : A. B \\
\hline \\
\Gamma \vdash \pi_1\: p : B[\pi_0\: p / a]
\end{array}
$$

This latter presentation makes it easy to obtain $\eta$ for pairs,
ie. $(\pi_0 p , \pi_1 p) == p$ for any pair $p$ (where == stands for the definitional equality). In terms of provability, this difference does not matter: intuitionistically, you can implement projections with split, or the
other way around.

Now, $\Pi$-types are usually (and uncontroversially, I believe) taken negatively:

$$
\begin{array}{l}
\Gamma \vdash f : \Pi a : A. B \\
\Gamma \vdash s : A \\
\hline \\
\Gamma \vdash f s : B[s / a]
\end{array}
$$

Which gives us $\eta$ for functions: $\lambda x. f x == f$.

However, in that mail, Hank recalls
the funsplit eliminator (Programming in ML type theory, [http://www.cse.chalmers.se/research/group/logic/book/], p.56). It is
described in the logical framework by:

$$
\begin{array}{l}
f \in \Pi(A, B) \\
C(v)\: Set [v \in \Pi(A, B)] \\
d(y) \in C(\lambda(y)) [y(x) \in B(x) [x \in A]] \\
\hline \\
\mathrm{funsplit}(f, d) \in C(f)
\end{array}
$$

Interestingly, Nordstrom et al. motivate this definition by saying that
"[this] alternative non-canonical form is based on the principle of
structural induction". There is a strong smell of positivity to this statement: functions would be 'defined' by their constructor, $\lambda$.

However, I cannot quite nail down a satisfactory presentation of that
rule in natural deduction (or, even better, sequent calculus). The
(ab)use of the logical framework to introduce $y$ seems crucial here.

So, is funsplit a positive presentation of $\Pi$-types? Do we also have something similar in the
(non dependent) sequent calculus? What would it look like?

How common/curious is that for the proof theorists in the field?

Here's a slightly different perspective on Fredrik's answer. It's generally the case that impredicative Church encodings of types will satisfy the relevant $\beta$ laws, but will not satisfy the $\eta$ laws.

So this means we can define a dependent pair as follows:

$$
\exists x:X.\;Y[x] \triangleq \forall \alpha:\ast.\; (\Pi x:X.\;Y[x] \to \alpha) \to \alpha
$$
Now, note that $\pi_1$ is easily definable:
$$
\pi_1 : \exists x:X.\;Y[x] \to X \triangleq \lambda p:(\exists x:X.\;Y[x]).\;p\;X\;(\lambda x\;y.x)
$$
However, you cannot define the second projection $\pi_2 : \Pi p:(\exists x:X.\;Y[x]).\; Y[\pi_1\;p]$ -- try it! You can only define a weak eliminator for it, which is why I wrote it with an existential.

However, the second projection is realizable, and in a parametric model you can show that it has the right behavior, too. (See my recent draft with Derek Dreyer on parametricity in the Calculus of Constructions for more on this.) So I think that the $\pi_2$ projection fundamentally demands some strong extensionality properties for it to make sense.

In terms of the sequent calculus, the weak eliminator has a rule that looks a bit like:

$$
\frac{\Gamma, x:X, y:Y[x],\; \Gamma' \vdash e' : C}
     {\Gamma, p:\exists x:X.\,Y[x],\; \Gamma' \vdash \mathsf{let}(x,y)=p\;\mathsf{in}\;e' : C}
$$
Here, the implicit well-formedness conditions imply that $p$ cannot occur free in $\Gamma'$ or $C$. If we relax that condition, we get the split rule, which has a left-rule that looks like
$$
\frac{\Gamma, x:X, y:Y[x],\; [(x,y)/p]\Gamma' \vdash e' : [(x,y)/p]C}
     {\Gamma, p:\exists x:X.\,Y[x],\; \Gamma' \vdash \mathsf{let}(x,y)=p\;\mathsf{in}\;e' : C}
$$
That substitution reminds me an awful lot of the Girard/Schroeder-Heister elimination rule for equality. I asked a question about this rule a while back, and David Baelde and Gopalan Nadathur give the state-of-the-art version in their LICS 2012 paper, Combining Deduction Modulo and Logics of Fixed-Point Definitions. I think Conor McBride has spent some time thinking about the relationship between the identity type and the Schroeder-Heister equality, so you might want to see what he thinks.


Time complexity of finding chain decomposition of partially ordered set Given a partially ordered set $P$ with $n=|P|$ and width $w$:
-What is the best known complexity (in expectation) for finding a chain decomposition of $w$ chains?
-What is the best known complexity (in expectation) for finding a chain decomposition of $O(w)$ chains?
The paper "On the Decomposition of Posets" (2012) seems to provide an algorithm in worst-case $O(wn^2)$ time for the first question but is there better for either?
Another question, possibly naive: does the chain decomposition produced by topological sort have any guarantees on the number of chains it consists of?

You may find the following recent reference useful:
M. Caceres, M. Cairo, B. Mumey, R.  Rizzi, and A. Tomescu. On the parameterized complexity of the Minimum Path Cover problem in DAGs.
arXiv preprint arXiv:2007.07575


Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL? It is a standard proof in automata courses that for $L = \Sigma^\star$ and $|\Sigma| \ge 2$ that $S(L) = \{ww : w \in L\}$ is not a context-free language.

It is also true that for any finite $L$, $S(L)$ is finite (and therefore a CFL). I'm guessing that $L$ being infinite and regular are not "sufficient" for $S(L)$ being not a CFL. Edit: what about non-CFL $L$?

Is there any characterization of what $L$ have $S(L)$ not being a CFL?

More of an extended comment with a conjecture, but here is a condition that seems to capture the problem, in the context of regular $L$ for $S(L)$ to be context-free.

Condition
In the minimal DFA $A$ for $L$, any accepting path contains at most one loop.

Exception: two loops are allowed if their labels and the label of the prefix before the first loop all commute, and the suffix after the second loop is empty. For instance $aa^*b(aa)^*$ is ok.

Recall that two words $u$ and $v$ commute if they are powers of a same word $t$. We can assume the suffix empty, because it cannot be non-empty and commute with the label of the second loop in a DFA.

Sufficient
Assume the  condition, you build a PDA for $L$ by treating each accepting pattern $xuy$ of $A$ where $u$ labels a simple loop. We want to accept words of the form $xu^nyxu^ny$. We read $x$, push a symbol for every occurence of $u$, read $yx$, then pop a symbol for every occurence of $u$, and finally read $y$.

About the exception, if we are in this case, a basic accepting path is of the form $xuyv$ where $u,v$ are the labels of the loops. We accept words of the form $xu^n y v^m xu^n y v^m$, but by assumption ($x,u,v$ commute) it is the same as $u^nxyu^n v^mxyv^m$, which can be done by a PDA: push $n$ times (for occurences of $u$), read $xy$, pop $n$ times, push $m$ times (for $v$), read $xy$, pop $m$ times.

The final PDA is the union of the PDAs for each pattern.

Necessary
(handwaving) If there is a path with two loops, even in the simplest case where you must take one then the other (for instance $a^*b^*$), you must remember how many times each one is taken, but the stack structure prevents you to repeat them in the same order. Notice that the fact that the DFA is minimal is important in the characterization, to avoid using two loops when one could suffice.

For now the necessary part is only a conjecture, and more exceptions could be needed to get the exact condition, I would be interested in counter-examples.


Effect of protocol ordering on multiparty comm. complexity Brief Background

In Multi-Party Protocols by Chandra, Lipton, and Furst [CFL83], a Ramsey-theoretic proof is used to show a lower bound (and later, a matching upper bound) for the predicate Exactly-$n$ in the NOF multiparty communication complexity model. From the paragraph at the top of the second column of Page 1, we can see that they define the model such that the communication is strictly cyclic: e.g., for parties $P_0, P_1, P_2$, $P_0$ broadcasts at time $t=0$, $P_1$ broadcasts at time $t=1$, $P_2$ broadcasts at time $t=2$, then $P_0$ broadcasts at time $t=3$, and so on.

In most other papers, this cyclic ordering restriction is not made. For (arbitrary) example, in Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity by Beame, David, Pitassi, and Woelfel [BDPW07], a counting argument over protocols separates $\bf{RP}^{cc}_k$ from $\bf{P}^{cc}_k$. By their definition, "a protocol specifies, for every possible [public] blackboard contents [i.e., broadcast history] whether or not the communication is over, the output if over and the next player to speak if not." (emphasis added)

Importantly, the proof technique in [CFL83] appears (to my eyes) to crucially depend on the parties speaking in a cyclic/modular fashion.

Question

Allow me to play Devil's Advocate:

  Doesn't the lower bound proof of [CFL83] break if we allow the parties to speak in an ordering specified by the protocol? More specifically, is it possible there could there be a protocol with a different communication pattern than cyclic for Exactly-$n$ in the NOF model that costs less than the $\log(\chi_k(n))$ lower bound given in the paper?

Or more generally -- what's going on here? Why is one (highly cited) paper (I use the following very liberally) "allowed" to restrict the possible protocols to round-robin communication patterns only?

Any protocol $\pi$ can be modified into an equivalent protocol $\hat\pi$ that has the special "round-robin" communication pattern. The modification is as follows: Whenever party $i$ generates an output in $\pi$, it holds it in a buffer until party $i-1$ has spoken. After party $i-1$ speaks, party $i$ either releases its buffer or broadcasts a "dummy" (or empty) message if there is nothing in the buffer.

The conversion of $\pi$ into $\hat\pi$ is without loss of generality, with respect to the correctness and security properties of the protocol. Whether it incurs a loss of generality with respect to communication complexity depends on whether the model allows "empty" messages. You should see whether the proof technique in this paper assumes that parties can broadcast only non-empty messages. If empty messages are allowed, then $\hat\pi$ has the same communication complexity as $\pi$.


TSP in bounded tree-width (or bounded branch width) graphs I see there are some papers/thesis which says TSP is solvable in $O(n)$ in bounded tree-width graphs and some of them implicitly refer to Cook and Seymour (not exact paper just said that they solve it), but I can't find any paper about it.

All the things I can find is branch-decomposition based algorithms with merging techniques, which are all heuristic (e.g very nice heuristic) but non of them are exact algorithm. Does anyone know the related papers for linear time solution? Or paper which says is impossible? or probably impossible? (any good news bad news, its not 3in1 question:).

TSP is the optimization version of HAMILTONIAN CYCLE, which can be expressed by an MSO-formula (Monadic Second-Order Logic) with edge-set quantifications ($MSO_2$, also known as MSO in the incidence-graph model) as follows:  Let $hamilton(F)$ express that $F$ is a set of edges of the input graph $G = (V, E)$ such that every vertex is incident to exactly two edges in $F$, and additionally $F$ is connected.   Then
$$\min_{F \subseteq E} \{ \sum_{e \in F} w(e) : G \models hamilton(F)\},$$
where $w(e)$ denodes the weight of an edge $e$.  Hence, TSP is a Linear MSO-definable Optimization problem.   Via Courcelle's Theorem, TSP can therefore be solved  in linear time on graphs of bounded treewidth (for example, using dynamic programming as mentioned by Andrew in the comment above).


What are the recent TCS books whose drafts are available online? Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.

For instance, the Approximation Algorithms entry of the above post cites a 2011 book (yet to be published) titled The design of approximation algorithms.

I think knowing recent works is really useful for whoever wants to get a taste of TCS trends. When drafts are available, one can check the books before actually buying them.

So,

  What are the recent TCS books whose drafts are available online?

Here, by "recent", I mean something that's no older than ~5 years.

Several TCS books by Now Publishers can be found in drafts:

Foundations of Cryptography– A Primer by Oded Goldreich. This is a summarized version of his famous two-volume book on cryptography. (The draft of the two-volume version can be found in Robin's answer.)
Data Streams: Algorithms and Applications by S. Muthukrishnan.
Mathematical Aspects of Mixing Times in Markov Chains by Montenegro & Tetali.
Pairwise Independence and Derandomization by Luby & Widgerson.
Average-Case Complexity by Bogdanov & Trevisan.
A Survey of Lower Bounds for Satisfiability and Related Problems by Melkebeek.
Algorithms and Data Structures for External Memory by Vitter.
Probabilistic Proof Systems: A Primer by Goldreich. Again, this is a summarized version of a part Goldreich's book Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
The Design of Competitive Online Algorithms via a Primal-Dual Approach by Buchbinder & Naor.
Spectral Algorithms by Kannan & Vempala.
On the Power of Small-Depth Computation by Viola.
Algorithmic and Analysis Techniques in Property Testing by Ron.
Arithmetic Circuits: A Survey of Recent Results and Open Questions
by Amir Shpilka and Amir Yehudayoff (2010), Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 3–4, pp 207-388. http://dx.doi.org/10.1561/0400000039

In addition, drafts of several Springer books on "Information Security and Cryptography" can be found online:

Cryptography in Constant Parallel Time by Applebaum.
A Study of Statistical Zero-Knowledge Proofs by Vadhan.
Locally Decodable Codes and Private Information Retrieval Schemes by Yekhanin.
Concurrent Zero Knowledge by Rosen.


How to calculate this string-dissimilarity function efficiently? Migrated from stackoverflow.

Hello,

I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is close to "worldhello". Obviously Levenshtein distance and Longest common subsequence don't fulfill this requirement. Using Jaccard distance on the set of n-grams gives good results but has other drawbacks (it's a pseudometric and higher n results in higher penalty for changing single character).

[original research]

As I thought about it, what I'm looking for is a function f(A,B) such that f(A,B)+1 equals the minimum number of blocks that one have to divide A into (A1 ... An), apply a permutation on the blocks and get B:

f("hello", "hello") = 0
f("helloworld", "worldhello") = 1   // hello world -> world hello
f("abba", "baba") = 2               // ab b a -> b ab a
f("computer", "copmuter") = 3       // co m p uter -> co p m uter

This can be extended for A and B that aren't necessarily permutations of each other: any additional character that can't be matched is considered as one additional block.

f("computer", "combuter") = 3       // com uter -> com uter, unmatched: p and b.

Observing that instead of counting blocks we can count the number of pairs of indices that are taken apart by a permutation, we can write f(A,B) formally as:

f(A,B) = min { C(P) | P ⊆ |A|×|B|, P is a bijective function, ∀i∈dom(P) A[P(i)]=B[P(i)] }
C(P) = |A| + |B| − |dom(P)| − |{ i | i,i+1∈dom(P) and P(i)+1=P(i+1) }| − 1

The problem is... guess what...

... that I'm not able to calculate this in polynomial time.

Can someone suggest a way to do this efficiently (possibly with minor modifications)? Or perhaps point me to already known metric that exhibits similar properties?

What you seem to be looking for is called the minimum common string partition, and it has been well studied. In particular, it's known to be NP-hard. There is also a closely related concept of edit distance with block moves, which would capture the extension you mention, where substitutions are allowed.


Quantum query complexity and certificate complexity A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum size of a certificate for input $x$ and the certificate complexity $C(f) = \max_x C_x(f)$. Thus, certificate complexity can be seen as a form of query complexity for nondeterministic machines: guess the smallest certificate for $x$ and then verify with $C_x(f)$ many queries. This is used as an intermediate complexity measure when proving relationships between deterministic query complexity ($D(f)$) and quantum query complexity ($Q_2(f)$).

Is it known, or believed that for a total functions $f$, $C(f) \leq Q_2(f)$? Are there any total functions $f$, where it is know that $C(f) \in o(Q_2(f))$ (or vice-versa)? And just for fun: does this question correspond in some formal way to the questions associated NP vs. BQP?

In the paper Negative weights make adversaries stronger, Lee, Spalek, and Hoyer give a function for which $ADV^{±}(f)= \Omega( ({C_0(f)C_1(f)})^{0.549})$, where $ADV^±$ denotes the general adversary lower bound. This lower bound has since been proved to characterize quantum query complexity.

This function is obtained by composing a function on a few bits bits with itself $d$ times. You get in the end $C_0(f)=C_1(f)=3^d$ and thus $C(f) \in o(Q_2(f))$.


Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity While searching The information System on Graph Classes and their Inclusions, I found several graph classes for which  the Hamiltonian Cycle problem is NP-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are bipartite maximum degree 3 graphs, maximum degree 3 grid graphs, and 2-connected cubic planar graphs. Also this phenomena applies to circle graphs and triangular grid graphs.

  Is there an update to the complexity of Hamiltonian path problem on those classes? Is there an explanation for this phenomena?

EDIT: I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

The Hamiltonian path problem on grid graphs with maximum degree 3 is NP-complete. The proof is in C. H. Papadimitriou and U. V. Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231–246 (Theorem 2)


What does a tangible Quantum-Gate look like? I'v read published books, articles and papers about Quantum-Computing.

I found that all the materials I've seen are, instead of describing quantum gate from basic physics to abstraction, trying hard to avoid talking about the implementation details of quantum-gates.

I firstly questioned myself: Am I searching in the wrong area where only formal mathematics are concerned?

But I found those papers and books do have explained ion-traps, optical-switches and even laser-fibre in great detail.

When it comes to quantum-gates they claimed to have used in their research, only matrices, equations, formulations and black-box components are shown.

We all know about the unitaries and matrix computation. But if you print a quantum-gate matrix operator on an A4-paper, that ain't going to do anything when photons or electrons are thrown to it.

So, does anyone know what is a quantum gate, concretely so that I can know:

Is Quantum Gate a device using magnetic field to do element arithmetics?
Is Quantum Gate a device using laser-beam?
Is Quantum Gate a device using metal wire?
When scientists happily multiply eigenstates by observables, do electrons collide in the gate when "multiplied"?

Thanks in advance.

You seem to have the idea that a quantum gate is a physical thing rather than just a conceptual thing. It doesn't  necessarily work that way. While CMOS  gates are usually actual physical devices, quantum gates may be just conceptual.

Consider an ion trap. The ions represent qubits by using one electronic state as a $|0\rangle$ and another as a $|1 \rangle$. A quantum gate is performed by applying a $4 \times 4$ unitary matrix to two of these ions. This is done by shining a sequence of laser pulses on the ions. It's not a physical device into which two ions are input, in which they interact, and out of which the ions come with their states changed.

Quantum gates are performed by shining laser pulses on the ions, but there's not necessarily one laser per quantum gate—the same lasers are used for many different quantum gates. Thus, you can't point to any specific piece of hardware and say "this is the quantum gate".

And if you use flux qubits in superconductors for your quantum computer, the quantum gates don't use lasers at all, and they look completely different (and slightly more like CMOS devices).


Research data organization This is a question in the spirit of this one where I answered that it is important to keep track of what you have done something, why you have done it and what is not working.
I personally use notebooks for that purpose, but it has several drawbacks: first I need a lot of storage surface, second when I travel I cannot access my data, and finally this is not collaborative. It has however a strong plus: the notebook can be used as the equivalent of a laboratory notebook (you just have to find somebody to sign each page...).

So, I am interested in knowing how other researchers proceed for that matter. For example, is there any specific software that solve all the issues I mentioned?

For emacs users there's the extremely useful org-mode. It is an emacs mode that, in plain ascii, help organizing your life or at least your research :) It has TODOs, deadlines, schedules, effort, tables with some computations capabilities, and lots of other features. It can export projects in LaTeX, html or other formats. Since it is text-based you can manage projects concurrently using some Distributed Concurrent Versions System, such as git or mercurial...


Interesting SUBSET-SUM problems I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ (Elberfeld at. al., 2010), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ \mathtt{SUCCINCT\mbox{-}SUBSETSUM} $ (link).

Recently, I also ran into $ \Sigma_2^p $-complete $ \mathtt{GENERALIZED\mbox{-}SUBSETSUM} $ problem (Page 16: Schaefer and Umans, 2008).

Do you know some other (non-trivial) interesting variants of SUBSETSUM problems? Specifically, $ \Sigma_l^p $- or $ \Pi_l^p $- complete problems for some $ l > 1 $.

Some definitions:

$
\mathtt{UNARY\mbox{-}SUBSETSUM} = \{ 0^n \# 0^{i_1} \# \cdots\#0^{i_k} \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}i_j = n \}.
$

$ \mathtt{SUBSETSUM} = \{ S \# a_1 \# \cdots\# a_k \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}a_j = S \}, $ where $S$ and $a_j$'s are binary numbers.

$ \mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \}, $ where $u$ and $v$ are integer vectors, $t$ is an integer, and $x$ and $y$ are binary vectors of the same length as $u$ and $v$, respectively.

The main credit should go to John Fearnley!

Here is a PSPACE-complete problem given in (John Fearnley, Marcin Jurdzinski: Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223):

\begin{equation}
 \mathtt{SUBSETSUM\mbox{-}GAME}=\{ S~ \forall(a_1 , b_1) \exists(e_1,f_1) \cdots \forall(a_n , b_n) \exists(e_n,f_n)  \},
\end{equation}
where

$S$ and each $ a_i,b_i,e_i $, and $f_i$ are natural numbers ($1 \leq i \leq n$); and,
for every $ x=(x_1,\ldots,x_n) \in \times_{i=1}^n  \{ a_i,b_i \} $, there exists a $ y=(y_1,\ldots,y_n) \in \times_{i=1}^n  \{ e_i,f_i \} $ such that $ S = \sum_{i=1}^n = x_i+y_i $.

Similarly, we can define some complete problems for each level of polynomial hierarchy (PH). But, of course, in case of being complete at some level of PH, we need to release the condition of having only two natural numbers after each quantifier.


Jointly Establishing a Shared Random String for NIZK proofs of knowledge If OWFs exist, then a Shared Random String for

NIZK proofs (of membership) can be established by:

verifier commits a random string of the same length using statistically hiding commitment

prover sends random string of the same length

verifier opens the commitments

the xor of the commited bits and the prover's string is used as the shared random string

The problem with using this for NIZK proofs of knowledge is that the

above protocol is not (at least not obviously) simulable for the prover.

  Is there a known concrete obstacle to being able to establish

  a Shared Random String for NIZK proofs of knowledge?

  (For example, showing that such a protocol can't be black-box zero knowledge?)

If no, is there a plausible computaional assumption that is known to suffice for doing so?

I'm not sure the solution you have given works.

However, it can be adapted to work -- both for NIZK proofs and proofs of knowledge -- by using a coin-tossing protocol where "secure" here means in the sense of general secure two-party computation. This can be done based on one-way functions in polynomially many rounds, or based on stronger assumptions in constant rounds.

A good reference is Lindell's paper on coin tossing.


Anyone recognize this as a special type of multi-commodity flow problem? Consider this problem:

$$
\begin{align}
\min_{y,z,l \geq 0} \quad & g(y,z,l) :=
\sum_{(i,j)\in E} \sum_p (-w_{ijp}) y_{ijp} &  \\
\textrm{s.t.} \quad & \left( \sum_{(i,j)\in E} y_{ijp} + l_{ip} \right)-
                      \left( \sum_{(j,i)\in E} y_{jip} + z_{ip} \right)=
                \begin{cases}
                 +1 \quad i=1 \\
                 -1 \quad i=n \\
                  0 \qquad i\neq 1,n
                \end{cases} & \forall i \in I, p\in P \\
               & \sum_p (z_{ip} - l_{ip}) = 0 & \forall i\in I
\end{align}
$$

Sets $I=\{1,\ldots,n\}$ and $P=\{1,\ldots,m\}$ correspond to $n$ nodes and $m$ commodities.
Set $E \subseteq I\times I$ corresponds to the arcs of a directed acyclic graph where node $1$ is the source (no predecessors) and node $n$ is the sink (no successors).
Sending $y_{ijp}$ units of commodity $p$ from node $i$ to $j$ costs $-w_{ijp}y_{ijp}$, with all $w_{ijp}$ positive.
Note that all commodities have $1$ as the source and $n$ as the sink.

If you ignore the $z_{ip}$ and $l_{ip}$ variables the problem becomes a set of $m$ independent shortest-path problems.
Specifically, let $C = \{(y,z,l)\}$ denote the class of all solutions with $z_{ip} = l_{ip}$ for all $i, p$.
Then, the best $(y,z,l) \in C$ can be found by solving $m$ independent shortest-path problems, i.e. by assigning $y_{ijp} \in \{0,1\}$.

It is this remark that makes me hope that we are dealing with a special-case of multicommodity flow that can be solved more efficiently. But I haven't found anything in the literature.

Does anyone recognize this problem or have an idea for a clever heuristic?

I think you can solve this as a single shortest path problem with respect to arc weights
$$\overline{w}_{ij}=\min\{-w_{ijp}\ :\ p\in\{1,\ldots,m\}\}.$$
For every arc $(i,j)$ fix some $p(i,j)\in\{1,\ldots,m\}$ with $-w_{ijp(i,j)}=\overline{w}_{ij}$. If you have a shortest path $\pi$ with respect to $\overline{w}$, you can put
$$y_{ijp}=\begin{cases} m & \text{if }(i,j)\in\pi\text{ and }p=p(i,j),\\ 0 & \text{otherwise.}\end{cases}$$
For the $l$- and $z$-variables you do the following.

If $(1,j)\in\pi$ is the arc leaving 1 then
$$z_{1q}=\begin{cases}m-1 & \text{for } q=p(1,j)\\ 0 & \text{for } q\neq p(1,j)\end{cases}$$
$$l_{1q}=\begin{cases}1 & \text{for } q\neq p(1,j)\\ 0 & \text{for } q= p(1,j)\end{cases}$$

If $(i,n)\in\pi$ is the arc entering $n$ then
$$z_{nq}=\begin{cases}0 & \text{for } q=p(i,n)\\ 1 & \text{for } q\neq p(i,n)\end{cases}$$
$$l_{1q}=\begin{cases}0 & \text{for } q\neq p(i,n)\\ m-1 & \text{for } q= p(i,n)\end{cases}$$

If $(j,i)$, $(i,j')$ are two consecutive arcs of $\pi$ then you put $l_{ip}=z_{ip}=0$ if $p(j,i)=p(i,j')$, and otherwise
$$z_{iq}=
\begin{cases}
m & \text{for } q=p(i,j')\\
0 & \text{for } q\neq p(i,j')
\end{cases}$$
$$l_{iq}=
\begin{cases}
m & \text{for } q=p(j,i)\\
0 & \text{for } q\neq p(j,i)
\end{cases}$$

And LP duality tells you that this is optimal.


Time complexity of derivative-based regex matchers Regex matching using the Brzozowski derivative without any caching or expression-simplifying takes exponential time and space because of the product rule.

In Brzozowski's original paper, Brzozowski shows how to generate a DFA using the derivative operation. The upper bound he finds on the size of that DFA is an iterated exponential. So going on the upper bound alone, transforming a regex to a DFA via differentiation is less efficient than "running" the regex "directly".

In a later paper "Regular-expression derivatives reexamined", the authors show how to use automatic expression-simplifying to speed up Brzozowski's algorithm; but nothing is proven about the worst-case complexity.

Also, the theory of Brzozowski differentiations works just as well on ordinary regexes as it does on Extended Regexes, which feature intersection and complement. If deciding whether an Extended Regex expresses the Empty language were possible to do efficiently, then that would imply that derivative-based matching must be worst-case inefficient.

So what is the time-complexity of Brzozowski derivative-based matchers if automatic expression-simplifying is used?

In Theorem 5.2 of his paper, Brzozowski shows that every regular expression has a finite number of dissimilar derivatives, where two regular expressions $r$ and $r'$ are similar if they are ACU-equivalent at the outermost level. That is, consider the equivalence relation generated by the following equivalences:

$$
\array{
r \vee r & \equiv &  r \\
r \vee r' & \equiv & r' \vee r \\
(r \vee r') \vee r'' & \equiv & r \vee (r' \vee r'') \\
r \vee \bot & \equiv & r \\}
$$

(Notice the absence of congruence rules in this definition -- in particular, $a\cdot(r \vee r') \not\equiv a\cdot(r' \vee r)$.) It turns out there are at most $O(2^{|r|})$ many dissimilar word Brzozowski derivatives. So the worst case of matching with Brzozowski derivatives is the same as any other method.

A nice proof of this fact takes a detour through Antimirov partial derivatives. The one-character Antimirov derivative function is defined as follows:

$$
\array{
a_c(\bot) & = & \emptyset \\
a_c(r \vee r') & = & a_c(r) \cup a_c(r') \\
a_c(\epsilon) & = & \emptyset \\
a_c(c')        & = & \emptyset \\
a_c(c)         & = & \{ \epsilon \}  \\
a_c(r_1 \cdot r_2) & = & \{ r'_1 \cdot r_2 \;|\; r'_1 \in a_c(r_1) \} \\
                   &   & \cup \; (\mbox{if}\;\mbox{nullable}(r_1)\;\mbox{then}\; a_c(r_2) \;\mbox{else}\;\emptyset) \\
a_c(r\ast) & = & \{ r' \cdot r\ast \;|\; r' \in a_c(r) \}
}
$$

Basically, instead of returning a single derivative, the Antimirov derivative returns a set of partial derivatives, whose union adds up to the Brzozowski derivative. Now, we can make the following observations:

Up to similarity, the union of the set of Antimirov partial derivatives of a regular expression and the Brzozowski derivative are one and the same.
It's also easy to prove that given a regular expression $r$, the number of Antimirov word derivatives is linear in the size of $r$.
Since a Brzozowski derivative is formed from a union of Antimirov derivatives, there can be at most $O(2^{|r|})$ possible Brzozowski derivatives of a regular expression (up to similarity).

As defined, the Antimirov derivative doesn't work with intersection.     Pascal Caron, Jean-Marc Champarnaud and Ludovic Mignot had a LATA 2011 paper, Partial Derivatives of an Extended Regular Expression, which extended this approach to cover extended regular expressions. Their idea is to define a new partial derivative operation returning a set of sets of partial derivatives (corresponding to DNF), and they show that this has a worst-case exponential size. Intuitively, this corresponds to the fact that implementing intersection on automata uses a product construction.

Anyway, the takeaway (IMO) should be that derivatives are not alternatives to the standard automata-theoretic constructions, but rather are a conceptual explanation of them.


What is the most efficient way to generate a random permutation from probabilistic pairwise swaps? The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a uniformly random permutation of $n$ elements? Here I take "probabilistic pairwise swap gate" to be the operation which implements a swap gate between to chosen elements $i$ and $j$ with some probability $p$ which can be freely chosen for each gate, and the identity otherwise.

I realise this is not usually the way one generates random permutations, where usually one might use something like a Fisher-Yates shuffle, however, this will not work for the application I have in mind as the allowed operations are different.

Clearly this can be done, the question is how efficiently. What is the least number of probabilistic swaps necessary to achieve this goal?

UPDATE:

Anthony Leverrier provides a method below which does indeed produce the correct distribution using $O(n^2)$ gates, with Tsuyoshi Ito providing another approach with the same scaling in the comments. However, the best lower bound I have so far seen is $\lceil \log_2(n!) \rceil$, which scales as $O(n\log n)$. So, the question still remains open: Is $O(n^2)$ the best that can be done (i.e. is there a better lower bound)? Or alternatively, is there a more efficient circuit family?

UPDATE:

Several of the answers and comments have proposed circuits which are comprised entirely of probabilistic swaps where the probability is fixed at $\frac{1}{2}$. Such a circuit cannot solve this problem for the following reason (lifted from the comments):

Imagine a circuit which uses $m$ such gates. Then there are $2^m$ equiprobable computational paths, and so any permutation must occur with probability $k 2^{−m}$ for some integer k. However, for a uniform distribution we require that $k 2^{−m}=\frac{1}{n!}$, which can be rewritten as $k n! = 2^m$. Clearly this can't be satisfied for an integer value of $k$ for $n\geq3$, since $3|n!$ (for $n\geq 3$, but $3\nmid 2^m$.

UPDATE (from mjqxxxx who is offering the bounty):

The bounty being offered is for (1) a proof that $\omega(n \log n)$ gates are required, or (2) a working circuit, for any $n$, that uses less than $n(n-1)/2$ gates.

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

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

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


Finding the point that maximizes a linear function Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in Q$ (a positive integer), we need to find the point that maximizes the linear function $c_j \cdot x+y$.
Ideally, I would like to preprocess all the points in at most $O(N \log N)$ time and then answer the query for each $c_j \in Q$ in $O(\log N)$ (or maybe even constant) time.
I feel there is such an algorithm where I can sort the points by $x_i$ and/or $y_i$ and do some binary searches but it is more complex than I thought. Any there tradeoffs between preprocessing vs answering time or lower bounds known for this problem?
Edit : A fellow graduate student gave the following idea - constructing a convex hull of the $N$ points, sorting the slopes of the line segments formed by consecutive points on the hull and then finding the line segments with the slope "closest" to $-c_j$ will identify the point that maximizes the linear function $c_j x + y$. I think this works but will verify the details tomorrow. My sleep will be ruined if there is a bug.

Another Answer:

Find the 2D maximal point set. Let us call it the set $M$.
Find the convex hull of $M$. Let us call it $co(M)$.

The preprocessing time for the two step is $O(n \log n)$.
Now, for the line: $c_i \cdot x + y = 0$, you need to find the point in $M$ that is farthest from the line. That point must lie on the boundary of $co(M)$. Note that distances of the points on the convex hull first increase and then decrease. You need to find that point on the boundary where this transition happens. It can be done in $O(\log n)$ time using binary search.


Are innermost reductions perpetual in untyped λ-calculus? (I have already asked this at MathOverflow, but got no answers there.)

Background

In the untyped lambda calculus, a term may contain many redexes, and different choices about which one to reduce may produce wildly different results (e.g. $(\lambda x.y)((\lambda x.xx)\lambda x.xx)$ which in one step ($\beta$-)reduces either to $y$ or to itself). Different (sequences of) choices of where to reduce are called reduction strategies. A term $t$ is said to be normalizing if there exists a reduction strategy which brings $t$ to normal form. A term $t$ is said to be strongly normalizing if every reduction strategy brings $t$ to normal form. (I'm not worried about which, but confluence guarantees there can't be more than one possibility.)

A reduction strategy is said to be normalizing (and is in some sense best possible) if whenever $t$ has a normal form, then that's where we'll end up. The leftmost-outermost strategy is normalizing.

At the other end of the spectrum, a reduction strategy is said to be perpetual (and is in some sense worst possible) if whenever there is an infinite reduction sequence from a term $t$, then the strategy finds such a sequence - in other words, we could possibly fail to normalize, then we will.

I know of the perpetual reduction strategies $F_\infty$ and $F_{bk}$ given respectively by:
\begin{array}{ll}
F_{bk}(C[(\lambda x.s)t])=C[s[t/x]]       & \text{if $t$ is strongly normalizing} \\
F_{bk}(C[(\lambda x.s)t])=C[(\lambda x.s)F_{bk}(t)] & \text{otherwise}
\end{array}
and
\begin{array}{ll}
F_\infty(C[(\lambda x.s)t])=C[s[t/x]] & \text{if $x$ occurs in $s$, or if $t$ is on normal form} \\
F_\infty(C[(\lambda x.s)t])=C[(\lambda x.s)F_\infty(t)] & \text{otherwise}
\end{array}
(In both cases, the indicated $\beta$-redex is the leftmost one in the term $C[(\lambda x.s)t]$ - and on normal forms, reduction strategies are necessarily identity.) The strategy $F_\infty$ is even maximal - if it normalities a term, then it has used a longest possible reduction sequence to do so. (See e.g. 13.4 in Barendregt's book.)

Consider now the leftmost-innermost reduction strategy. Informally, it will only reduce a $\beta$-redex which contains no other redexes. More formally, it is defined by
\begin{array}{ll}
  L(t) = t
   &\text{if $t$ on normal form}\\
  L(\lambda x.s) = \lambda x. L(s)
   &\text{for $s$ not on normal form}\\
  L(st) = L(s)t
   &\text{for $s$ not on normal form}\\
  L(st) = s L(t)
   &\text{if $s$, but not $t$ is on normal form}\\
  L((\lambda x. s)t) = s[t/x]
   &\text{if $s$, $t$ both on normal form}
\end{array}

The natural intuition for leftmost-innermost reduction is that it will do all the work - no redex can be lost, and so it ought to be perpetual. Since the corresponding strategy is perpetual for (untyped) combinatory logic (innermost reductions are perpetual for all orthogonal TRWs), this doesn't feel like completely unfettered blue-eyed optimism...

  Is leftmost-innermost reduction a perpetual strategy for the untyped $\lambda$-calculus?

If the answer turns out to be 'no', a pointer to a counterexample would be very interesting too.

I believe $tt$ with $t=(\lambda x. (\lambda y.1) (x x))$ will terminate using $L$ even if it has an infinite reduction.

The first reduction step is: $L(tt)=L(t)t=L(\lambda x.(\lambda y.1) (x x))t=(\lambda x.L((\lambda y.1) (x x)))t=(\lambda x.1)t$.

The first reduction step with $F_\infty$ is $F_\infty([(\lambda x.(\lambda y.1 (x x))) t]))=(\lambda y.1) (tt)$.