Dagstuhl workshop on Computational Complexity of Discrete Problems

I found the Dagstuhl workshop on Computational Complexity of Discrete Problems very engaging. Following are brief comments regarding twenty talks, which I attended and feel comfortable commenting on.

Recent developments in arithmetic circuits (Shubhangi Saraf)

VP and VNP are classes of polynomials that may be viewed as the Arithmetic Circuit analogues of P and NP. A relatively recent line of results shows that separating them amounts to separating the size of depth-four Arithmetic circuits for them. Specifically, while every polynomial in VP has depth-four A-circuits with bottom fan-in sqrt(n) and size $n^{O(sqrt(n))}$, VNP has polynomials for which every depth-four A-circuits with bottom fan-in sqrt(n) must have size $n^{Omega(sqrt(n))}$. Hence a separation would follow if the latter lower bound can be improved (i.e., the Omega replaced by an omega, or only by a sufficiently large constant).

Still, one should be careful about being too optimistic, since the $n^{Omega(sqrt(n))}$ holds also for VP...

Note (Apr 9, 2014): See ECCC TR14-045.

Circuits with medium fan-in (Anup Rao)

The model here is analogous to the one in my paper with Avi Boolean Circuits of Depth Three and Arithmetic Circuits with Arbitrary Gates. Specifically, the current work studies the size of circuits with general Boolean gates of a given arity for computing some Boolean functions in P, whereas our paper studies Arithmetic circuits with general (Set) Multi-linear gates for computing (set) multi-linear functions. Here the arity is fixed and one seeks lower bounds on the size, whereas in our paper the focus is on the maximum between the arity and the size.

For a fix arity $k$ (say $k=2n/3$), almost all circuits require $2^{n-k}$ many gates, and this bound is tight (e.g., consider the $2^{n-k}$ residual functions obtained by all possible fixing of the value of $n-k$ variables). The main result is that there exists a function in $P$ that requires $Omega(\log n)^2$ gates of arity $2n/3$. On the other hand, every simple function (i.e., one having a log-depth (bounded fan-in) circuit of linear size) can be computed by $o(n)$ gates of fan-in $n^{1/5}$.

Indexing irreducible polynomials over finite fields (Swastik Kopparty)

Indexing a set $S$ means having an efficiently computable bijection from $[|S|]$ to $S$. The inverse of such a function is a ranking function only if the indexing function is monotone (which is not required here). The main result is that indexing the set of irreducible polynomials of degree $n$ over $F=GF(q)$ is deterministically reducible to (1) finding such an irreducible polynomial $p$, and (2) finding a generator for $F[x]/p(x)$. The reduction reduces to the problem of indexing the "rotation classes" of $[q]^n$ of period $n$, where rotation classes are equivalence classes (of $n$-long sequences over $[q]$) such that two sequences are equivalent if they are rotations of one another.

Small circuits and big numbers; better bounds on computing the bits of arithmetic circuits (Eric Allender)

The computational problems considered are of computing bits in the binary representation of large numbers that are presented in a succinct manner. For example, given an arithmetic circuit $C:\R^n\to\R$, an integer $i$, and a binary input $x\in\{0,1\}^n$, compute the $i$th bit in the binary expansion of $C(x)$. This problem is count-P hard and resides in the counting hierarchy. The complexity of computing the $i$th bit of $\pi$ is not larger. Another problem is given natural numbers $x < y$ and $i$, to compute the $i$th bit in the binary expansion of $x / y$. This problem is in PH, and it is in P in the special case of $x=1$ (or when $x$ is a power of two). What happens if $x=3$?

On the Unique Games Conjecture and the Approximation Resistance of Predicates (Subhash Khot)

This was a double-feature of two remotely related topics. The UGC states that for every $\e,\d>0$, there exists $k=k(\e,\d)$ such that, given a 2-CSP with permutation constraints over $k$ labels, it is NP-hard to distinguish instances of valuer at least $1-\e$ from instances of value at most $\d$. The problem is equivalent to the case that $\d$ is as high as $1-\omega(sqrt(\e))$. In general, a quadratic gap seems fundamental here.

In the second talk, the focus is on $k$-ary CSP over Boolean values, where all constrains are induced by a single predicate (allowing possible negations of the chosen variables). The density of a predicate $f$, denoted $\rho(f)$, is the probability that $f$ evaluates to one under a random assignment, and $f$ is called approximation resistant if for every $\e>0$ it is hard to distinguish instances of value at least $1-\e$ from instances of value at most $\rho(f)+\e$. The result is a characterization of approximation resistant predicates, but the characterization is not effective (i.e., decidable).

Improved Inapproximability results for Hypergraph Coloring (Prahladh Harsha)

Given a simple 3-colorable graphs, we can color it with $n^{0.204}$ colors in polynomial-time, but coloring it with four colors is NPH and with polylog colors it is UGC-hard. Turning to 8-uniform hypergraphs, it is shown that given a 2-colorable hypergraph it it hard to colr it with $exp(exp(sqrt(log log n)))$ colors. The techniques involve use of the "short long code" which provides the evaluation of the input under all low degree polynomials (rather than under all polynomials/functions).

(2+epsilon)-Sat is NP-hard (Johan Hastad)

See a prior record

Small de Morgan formulas make low-frequency sound: Fourier concentration from shrinkage (Valentine Kabanets)

A function $f$ has Fourier concentration (with error $\gamma$) on degree $t$ if $\sum_{S:|S|>t} f_S^2 < \gamma$. It is known that AC0 circuits of size $s$ have F-concentration on polylogarithmic (in $s$) degree. This work shows that if $f$ has a de-Morgan formula of size $s$, then it has F-concentration for degree $s^{0.51}$, where the half corresponds to the reciprocal of the shrinkage exponent (i.e., two).

Direct product testing (Irit Dinur)

Following a general perspective, the focus was on the $k$-parallel repetition of the following confused-and-compare game played. With probability $p$, the referee sends the same random value $v\in V$ to both parties and accepts iff they answer with the same value. Otherwise, it sends them two independent random values and always accepts. The question is how are the success probability of arbitrary strategies $A,B:V^k\to\{0,1\}^k$ related to their ``closeness'' to being direct products of some functions $a,b:V\to\{0,1\}$.

For high success probability $1-\e$ and $p=1/sqrt(k)$ we get good approximate-agreement (i.e., $F$ agrees with some $f^k$ on almost all coordinates of a random $k$-tuple), and the new result referring to $p=Omega(1)$ yields exact agreement (i.e., agreement on all coordinates). For low success probability (i.e., as low as $exp(-sqrt(k))$), one gets occasional agreement.

Constant rate PCPs with sublinear query complexity (Eli Ben-Sasson)

The point is getting PCPs of length that is linear in the length of the original NP-witness (for SAT). This can be done with query complexity that is an arbitrary small power of the length. Such trade-off seems inherent if one is going to use the BFLS paradigm of embedding the input in a fixed routing network. In such a case the degree of the network lower bounds the query complexity and its depth lower bounds the overhead factor (in the length).

Set membership with two bit probes (Jaikumar Radhakrishnan)

The task is to succinctly represent an $n$-sized subset of $[m]$ such that membership queries can be answered by $t$ probes. It is known that the required length is at least $t n^{1-(1/t)} m^{1/t}$ whereas length $t n m^{4/(t+1)}$ suffices for odd $t$. But the upper bound is useless for $t=2,3,4$. Focusing on $t=2$, it is shown that length $m^{1-(1/4n)}$ suffices and length at least $m^{1-(4/n)}$.

Recent progress on interactive error correction: an overview (Mark Braverman)

The focus was on the rate of interactive error correction with coding over a constant-size alphabet. In such a case, non-interactive coding has rate $0.49999$ and rate $0.99999$ can be obtained in the list-decoding setting. In the interactive setting, the rate seems to double, but one can improve over it when the communication pattern (i.e., who talks when) is adaptive (which requires careful modeling with several non-equivalent models). A main tool in all of this is tree-codes, which are prefix codes $C:\{0,1\}^n\to\Sigma^n$ (i.e., the $i$-bit prefix of $C(x)$ only depends on the $i$-bit prefix of $x$) such that the distance between $C(x)$ and $C(y)$ is $Omega(n-|c(x,y)|$ where $c(x,y)$ is of the longest common prefix of $x$ and $y$.

An Interactive Information Odometer and Applications (Omri Weinstein)

The task is described by the following two-party functionality $(p,q)\mapsto (X,X)$, where $X$ is 1 with probability $(p-q)^2$ and zero otherwise. The aim is to perform this task while leaking a comparable amount of information. (Btw, the task of having $X$ be 1 with probability $|p-q|$ can be solved by Correlated Sampling; i.e., having each party toss a coin with bias determined by its input, exchanging the outcomes, and outputting~1 iff they differ.)

Note (Apr 9, 2014): See ECCC TR14-047.

Extended Formulations and Information Complexity (Ankur Moitra)

Given a polyhedra $P$ with many faces, one may wish to express it as a projection of a higher dimensional polyhedra that has fewer faces. At times, one may decrease the number of faces logarithmically, and this is useful when one wants to optimize a function defined over these bodies. The extended complexity of $P$, is the minimum number of faces one may obtain this way.

Arthur, Merlin, and Data Stream Computation (Amit Chakrabarti)

Interestingly, in the context of streaming private coins (probabilistic) proof systems are more powerful than the public coin counterparts. The reason is that the sketch is generated based on the random coins may be tossed before the prover-verifier interaction, and so it is crucial whether these coins are given to the prover. (In contrast, for coins tossed in the interaction itself, after the stream was processed, public-vs-private is immaterial, as it is the case whenever computational complexity is not an issue.) The result states a space-times-communication complexity of $Omega(n)$ for MA, but a three-message private-coin protocol of polylogarithmic complexity.

Turnstile Streaming Algorithms Might as Well Be Linear Sketches (David P. Woodruff)

The statement is proved in two stages. In the first stage a generic streaming algorithm is made to depend only on the accumulated frequencies (obliviously of the stream that gave rise to it). The ideas have a flavour of the compression result for finite automata, but the details are far more complex here.

Pseudorandom generators with optimal seed length for non-boolean poly-size circuits (Ronen Shaltiel)

Computational indistinguishability is defined with respect to distinguishers that output a binary value, but this work studies distinguishers $D$ that output a non-binary value and require that $D(G(s))$ be statistically close to $D(r)$, where $s\in\{0,1\}^k$ and $r\in\{0,1\}^\ell$ are uniformly distributed and $\ell=|G(s)|$. The work considers a hybrid of the BMY and NW settings: On the one hand, the pseudorandom generator (PRG) is required to run in polynomial time (as in [BM,Y]), but on the other hand it is allowed more time than the distinguisher (as in [NW]). Such PRGs are constructed based on assumptions regarding non-deterministic complexity (as in works regarding derandomization of AM). Needless to say, their seed length must exceed the length of the output of the potential distinguishers.

Testing Equivalence of Polynomials under Shifts (Amir Shpilka)

Given two Arithmetic circuits, $C_1,C_2$, the problem is to find a shift (vector) $b$ such that $C_1(x)=C_2(x+b)$, if such exists. The main result is a (deterministic) reduction of this problem to PIT (which is a specail case in which $C_2\equiv0$). This holds for any classes of circuits that satisfy some (minimal) closure properties. The related problem of finding a linear transformation (i.e., a matrix $A$ and a vector $b$ such that $C_1(x)=C_2(Ax+b)$) is NP-Hard.

Approaches to bounding the exponent of matrix multiplication (Chris Umans)

Rephrasing the problem in terms of the asymptotic rank of the (3-dim) matrix multiplication tensor, progress was obtained by a sequence of sophisticated manipulations of tensors including taking tensor powers, approximating tensors, and embedding tensors. So far all progress relied on some designs of small size (alas the search for good designs is infeasible even for such small size). The group theoretic approach offers the possibility of starting with a design of a large size, and a recent version raises the hope that Abelian groups may suffice.

Fixed Parameter Parallelism (Till Tantau)

For a class C, the parametrized class XC requires that the problem is in C for every value of the parameter, whereas FTC requires that the dependence on the parameter be isolated; for example, XP asks that for each $k$ the complexity takes the form $n^{f(k)}$, whereas FTP asks that it takes the form $f(k) n^{O(1)}$. The question is whether problems in FPT intersection XL have an FPT-type algorithm that has space complexity of the XL-type.

Back to list of Oded's choices.