| 8:30 |
Random resolution refutations
(abstract, slides)
Pavel Pudlák (Czech Academy of Sciences), Neil Thapen (Czech Academy of Sciences)
We study the random resolution refutation system defined in~[Buss et al. 2014].This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if P\neq NP, then random resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time.
We prove several upper and lower bounds on the width and size of random resolution refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random resolution and quasipolynomial size resolution, which solves the problem stated in~[Buss et al. 2014]. We also prove exponential size lower bounds on random resolution refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size refutations in constant depth Frege.
|
| 9:00 |
Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
(abstract, slides)
Massimo Lauria (Sapienza - Universita di Roma), Jakob Nordstrom (KTH Royal Institute of Technology)
We consider the natural encoding of the $k$-colouring problem for a given graph as a set of polynomial equations. We prove that there are bounded-degree graphs that do not have legal $k$-colourings but for which the polynomial calculus proof system defined in [Clegg et al. '96, Alekhnovich et al. '02] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gröbner bases solving $k$-colouring problems using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al. '08,~'09,~'11,~'15] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. '09] and [Li et al. '16]. % We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Mik\v{s}a and Nordström~'15] with a reduction from FPHP to $k$-colouring derivable by polynomial calculus in constant degree.
|
| 9:30 |
Representations of monotone Boolean functions by linear programs
(abstract, slides)
Mateus De Oliveira Oliveira (University of Bergen), Pavel Pudlák (Czech Academy of Sciences)
We introduce the notion of monotone linear-programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this model, we prove the following results.
1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.
2. MLP circuits are exponentially stronger than monotone span programs.
3. MLP circuits can be used to provide monotone feasibiliy interpolation theorems for Lovasz-Schrijver proof systems, and for mixed Lovasz-Schrijver proof systems.
4. The Lovasz-Schrijver proof system cannot be polynomially simulated by the cutting planes proof system. This is the first result showing a separation between these two proof systems.
|
| 10:00 | Coffee break |
| 10:30 |
Tutorial (part 1)
Operator scaling: theory, applications and connections
(abstract)
Avi Wigderson (Institute for Advanced Study)
|
| 12:30 | Lunch |
| 14:30 |
A note on amortized branching program complexity
(abstract)
Aaron Potechin (Institute for Advanced Study)
In this paper, we show that while almost all functions require exponential size branching programs to compute, for all functions f there is a branching program computing a doubly exponential number of copies of f which has linear size per copy of f. This result disproves a conjecture about non-uniform catalytic computation, rules out a certain type of bottleneck argument for proving non-monotone space lower bounds, and can be thought of as a constructive analogue of Razborov's result that submodular complexity measures have maximum value O(n).
|
| 15:00 |
Derandomizing isolation in space-bounded settings
(abstract, slides)
Dieter van Melkebeek (University of Wisconsin-Madison), Gautam Prakriya (University of Wisconsin-Madison)
We study the possibility of deterministic or randomness-efficient
isolation in space-bounded models of computation: Can one
efficiently reduce instances to equivalent instances that have at most
one solution? We present results for branching programs (related to
the complexity class NL) and for shallow semi-unbounded circuits
(related to the complexity class LogCFL).
A common approach employs small weight assignments that make the
solution of minimum weight unique (if a solution exists). The
Isolation Lemma and other known procedures use $\Omega(n)$ random bits
to generate weights of individual bitlength $O(\log n)$. We develop a
derandomized version in both settings that uses $O((\log
n)^{3/2})$ random bits and produces weights of bitlength $O((\log
n)^{3/2})$ in logarithmic space. The construction allows us to show
that every language in NL can be accepted by a nondeterministic
machine that runs in polynomial time and $O((\log n)^{3/2})$ space
simultaneously, and has at most one accepting computation path on
every input. Similarly, we show that every language in LogCFL can be
accepted by a nondeterministic machine that runs in polynomial time
and $O((\log n)^{3/2})$ space simultaneously when given access to a
stack that does not count towards the space bound, and has at most
one accepting computation path on every input.
We also show that the existence of somewhat more restricted isolations
for branching programs implies that all of NL has branching programs of
polynomial size, as well as a similar result for LogCFL.
|
| 15:30 |
The computational complexity of integer programming with alternations
(abstract)
Danny Nguyen (UCLA), Igor Pak (UCLA)
We prove that integer programming with three quantifier alternations is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra and Kannan, which together say that integer programming with at most two quantifier alternations can be done in polynomial time for a fixed number of variables. As a byproduct of the proof, we show that for two polytopes P,Q in R^4, counting the projection of integer points in Q\P is #P-complete.
This contrasts the 2003 result by Barvinok and Woods, which allows counting in polynomial time the projection of integer points in P, Q and P\Q.
|
| 16:00 | Coffee break |
| 16:30 |
On the average-case complexity of MCSP and its variants
(abstract, slides)
Shuichi Hirahara (University of Tokyo), Rahul Santhanam (University of Oxford)
We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MKTP (Minimum Kolmogorov Time-Bounded Complexity Problem):
- We observe that under standard cryptographic assumptions, MCSP has a {\it pseudorandom self-reduction}. This is a new notion we define by relaxing the notion of a random self-reduction to allow queries to be pseudorandom rather than uniformly random. As a consequence we derive a weak form of an average-case to worst case reduction for (a promise version of) MCSP. Our result also distinguishes MCSP from natural $\mathsf{NP}$-complete problems, which are not known to have average-case to worst-case reductions. Indeed, it is known that strong forms of average-case to worst-case reductions for $\mathsf{NP}$-complete problems collapse the Polynomial Hierarchy.
- We prove the first non-trivial formula size lower bounds for MCSP by showing that MCSP requires nearly quadratic-size De Morgan formulas.
- We show average-case superpolynomial size lower bounds for MKTP against $\AC^0[p]$ for any prime $p$.
- We show the hardness of MKTP on average under assumptions that have been used in much recent work, such as Feige's assumptions, Alekhnovich's assumption and the Planted Clique conjecture. In addition, MCSP is hard under Alekhnovich's assumption. Using a version of Feige's assumption against co-nondeterministic algorithms that has been conjectured recently, we provide evidence for the first time that MKTP is not in $\mathsf{coNP}$. Our results suggest that it might worthwhile to focus on the {\it average-case hardness} of MKTP and MCSP when approaching the question of whether these problems are $\mathsf{NP}$-hard.
|
| 17:00 |
Easiness amplification and uniform circuit lower bounds
(abstract, slides)
Cody Murray (MIT), Ryan Williams (MIT)
We present new consequences of the assumption that time-bounded algorithms can be ``compressed'' with non-uniform circuits. Our main contribution is an ``easiness amplification'' lemma for circuits. One instantiation of the lemma says: if $n^{1+\varepsilon}$-time, $\tilde{O}(n)$-space computations have $n^{1+o(1)}$ size (non-uniform) circuits for some $\varepsilon > 0$, then every problem solvable in \emph{polynomial} time and $\tilde{O}(n)$ space has $n^{1+o(1)}$ size (non-uniform) circuits as well. This amplification has several consequences:
* An easy problem without small LOGSPACE-uniform circuits. For all $\varepsilon > 0$, we give a natural decision problem {\sc General Circuit $n^{\varepsilon}$-Composition} that is solvable in $n^{1+\varepsilon}$ time, but we prove that \emph{arbitrary} poly-time and log-space preprocessing cannot produce $n^{1+o(1)}$-size circuits for the problem. This shows that there are problems solvable in $n^{1+\varepsilon}$ time which are not in LOGSPACE-uniform $n^{1+o(1)}$ size, the first result of its kind. We show that our lower bound is non-relativizing, by exhibiting an oracle relative to which the result is false.
* Problems without low-depth LOGSPACE-uniform circuits. For all $\varepsilon > 0$, $1 < d < 2$, and $d' < d$ we give another natural circuit composition problem computable in $\tilde{O}(n^{1+\varepsilon})$ time, or in $O((\log n)^d)$ space (though not necessarily simultaneously) that we prove does not have $SPACE[(\log n)^{d'}]$-uniform circuits of $\tilde{O}(n)$ size and $O((\log n)^{d'})$ depth. For NP-hard problems, we show SAT does not have circuits of $\tilde{O}(n)$ size and $\log^{2-o(1)} n$ depth that can be constructed in $\log^{2-o(1)} n$ space.
* A strong circuit complexity amplification. For every $\varepsilon > 0$, we give a natural problem {\sc Circuit $n^{\varepsilon}$-Composition} and show that if it has $\tilde{O}(n)$-size circuits (uniform or not), then every problem solvable in $2^{O(n)}$ time and $2^{O(\sqrt{n}\log n)}$ space (simultaneously) has $2^{O(\sqrt{n} \log n)}$-size circuits (uniform or not). We also show the same consequence holds assuming SAT has $\tilde{O}(n)$-size circuits.
As a corollary, if $n^{1.1}$ time computations (or $O(n)$ nondeterministic time computations) have $\tilde{O}(n)$-size circuits, then all problems in exponential time and subexponential space (such as quantified Boolean formulas) have significantly subexponential-size circuits. This is a new connection between the relative circuit complexities of easy and hard problems.
|
| 17:30 |
PPSZ for general k-SAT — making Hertli’s analysis simpler and 3-SAT faster
(abstract, slides)
Dominik Scheder (Shanghai Jiaotong University), John Steinberger (Tsinghua University)
The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane. Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify Hertli’s analysis for input formulas with multiple satisfying assignments. Second, we show a “translation result”: if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. Combining this with a result by Hertli from 2014, in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.
|
| 18:00 | Break |
| 20:30 | Business meeting |
| 8:30 |
Noise stability is computable and approximately low-dimensional
(abstract, slides)
Anindya De (Northwestern University), Elchanan Mossel (MIT), Joe Neeman (UT Austin)
Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting.
In many applications, the goal is to find an optimizer of noise stability among all possible partitions of $\R^n$ for $n \geq 1$ to $k$ parts with given Gaussian measures $\mu_1,\ldots,\mu_k$. We call a partition $\epsilon$-optimal, if its noise stability is optimal up to an additive $\epsilon$.
In this paper, we give an explicit, computable function $n(\epsilon)$
such that an $\epsilon$-optimal partition exists in $\R^{n(\epsilon)}$.
This result has implications for the computability of certain problems
in non-interactive communication, which are addressed in a subsequent work.
|
| 9:00 |
From weak to strong LP gaps for all CSPs
(abstract, slides)
Mrinalkanti Ghosh (TTI Chicago), Madhur Tulsiani (TTI Chicago)
We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP)
relaxations.
We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than
the approximation obtained using relaxations given by $\Omega(\frac{\log n}{\log \log n})$
levels of the Sherali-Adams hierarchy on instances of size $n$.
It was proved by Chan et al. [FOCS 2013] (and recently strengthened by Kothari et al. [STOC 2017])
that for CSPs, any polynomial size LP extended formulation is no stronger
than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy.
Combining this with our result also implies that any polynomial size LP extended
formulation is no stronger than simply the \emph{basic} LP, which can be thought of as the base
level of the Sherali-Adams hierarchy. This essentially gives a dichotomy result for approximation of
CSPs by polynomial size LP extended formulations.
Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on
(strong) approximation resistance for LPs. They provided a necessary and sufficient condition under
which $\Omega(\log \log n)$ levels of the Sherali-Adams hierarchy cannot achieve an approximation
better than a random assignment. We simplify their proof and strengthen the bound to
$\Omega(\frac{\log n}{\log \log n})$ levels.
|
| 9:30 |
Query-to-communication lifting for P^NP
(abstract, slides)
Mika Göös (Harvard University), Pritish Kamath (MIT), Toniann Pitassi (University of Toronto), Thomas Watson (University of Memphis)
We prove that the $\P^\NP$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\P^\NP$-type communication complexity of a lifted version of $f$. As an application, we show that a certain ``product'' lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture $\P^\NP$ communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).
|
| 10:00 | Coffee break |
| 10:30 |
Tutorial (part 2)
Operator scaling: theory, applications and connections
(abstract)
Avi Wigderson (Institute for Advanced Study)
|
| 12:30 | Lunch |
| 14:30 |
Improved bounds for quantified derandomization of constant-depth circuits and polynomials
(abstract, slides)
Roei Tell (Weizmann Institute of Science)
This work studies the question of \emph{quantified derandomization}, which was introduced by Goldreich and Wigderson (STOC 2014). The generic quantified derandomization problem is the following: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, given a circuit $C\in\mathcal{C}$ with $n$ input bits, decide whether $C$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs. In the current work we consider three settings for this question. In each setting, we bring closer the parameter setting for which we can unconditionally construct relatively fast quantified derandomization algorithms, and the ``threshold'' values (for the parameters) for which any quantified derandomization algorithm implies a similar algorithm for standard derandomization.
For {\bf constant-depth circuits}, we construct an algorithm for quantified derandomization that works for a parameter $B(n)$ that is only \emph{slightly smaller} than a ``threshold'' parameter, and is significantly faster than the best currently-known algorithms for standard derandomization. On the way to this result we establish a new derandomization of the switching lemma, which significantly improves on previous results when the width of the formula is small. For {\bf constant-depth circuits with parity gates}, we lower a ``threshold'' of Goldreich and Wigderson from depth five to depth four, and construct algorithms for quantified derandomization of a remaining type of layered depth-$3$ circuit that they left as an open problem. We also consider the question of constructing hitting-set generators for multivariate {\bf polynomials over large fields that vanish rarely}, and prove two lower bounds on the seed length of such generators.
Several of our proofs rely on an interesting technique, which we call the \emph{randomized tests} technique. Intuitively, a standard technique to deterministically find a ``good'' object is to construct a simple deterministic test that decides the set of good objects, and then ``fool'' that test using a pseudorandom generator. We show that a similar approach works also if the simple deterministic test is replaced with a \emph{distribution over simple tests}, and demonstrate the benefits in using a distribution instead of a single test.
|
| 15:00 |
Bounded independence plus noise fools products
(abstract, slides)
Elad Haramaty (Harvard University), Chin Ho Lee (Northeastern University), Emanuele Viola (Northeastern University)
Let D be a b-wise independent distribution over {0,1}^m. Let E be the ""noise"" distribution over {0,1}^m where the bits are independent and each bit is 1 with probability η/2. We study which tests f: {0,1}^m → [-1,1] are Ɛ-fooled by D+E, i.e., |E[f(D+E)] - E[f(U)]| ≤ Ɛ where U is the uniform distribution. We show that D+E Ɛ-fools product tests f: ({0,1}^n)^k → [-1,1] given by the product of k bounded functions on disjoint n-bit inputs with error Ɛ = k (1-η)^{Ω(b^2/m)}, where m = nk and b ≥ n. This bound is tight when b = Ω(m) and η ≥ (log k)/m. For b ≥ m^{2/3} log m and any constant η the distribution D+E also 0.1-fools log-space algorithms.
We develop two applications of this type of results. First, we prove communication lower bounds for decoding noisy codewords of length m split among k parties. For Reed-Solomon codes of dimension m/k where k = O(1), communication Ω(ηm) - O(log m) is
required to decode one message symbol from a codeword with ηm errors, and communication O(ηm log m) suffices. Second, we obtain pseudorandom generators. We can Ɛ-fool product tests f: ({0,1}^n)^k → [-1,1] under any permutation of the bits with seed lengths 2n + ~O(k^2 log (1/Ɛ)) and O(n) + ~O(\sqrt{nk \log 1/Ɛ}). Previous generators had seed lengths ≥ nk/2 or ≥ n \sqrt{nk}.
|
| 15:30 |
Tight bounds on The Fourier spectrum of AC0
(abstract, slides)
Avishay Tal (Institute for Advanced Study)
We show that $AC^0$ circuits on $n$ variables with depth $d$ and size $m$ have at most $2^{-\Omega(k/\log^{d-1} m)}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result improves the seminal result of Linial, Mansour and Nisan (JACM, 1993) and is tight up to the constants hidden in the $\Omega$ notation.
As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any $r(m,d,\varepsilon)$-wise independent distribution $\varepsilon$-fools $AC^0$ circuits of size $m$ and depth $d$, for
$$r(m,d,\varepsilon) = O(\log (m/\varepsilon))^{2d^2+7d+3}.$$
Our improved bounds on the Fourier tails of $AC^0$ circuits allows us to improve this estimate to
$$r(m,d,\varepsilon) = O(\log(m/\varepsilon))^{3d+3}.$$
In contrast, an example by Mansour (appearing in Luby and Velickovic's paper - Algorithmica, 1996) shows that there is a $\log^{d-1}(m) \cdot \log(1/\varepsilon)$-wise independent distribution that does not $\varepsilon$-fool $AC^0$ circuits of size $m$ and depth $d$. Hence, our result is tight up to the factor $3$ in the exponent.
|
| 16:00 | Coffee break |
| 16:30 |
Complexity-theoretic foundations of quantum supremacy experiments
(abstract, slides)
Scott Aaronson (UT Austin), Lijie Chen (Tsinghua University)
In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible.
First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by by the Quantum AI group at Google. We show that there's a natural average-case hardness assumption, which has nothing to do with sampling, yet implies that no polynomial-time classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work---for example, on BosonSampling and IQP---the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled.
Second, in an attempt to refute our hardness assumption, we give a new algorithm, inspired by Savitch's Theorem, for simulating a general quantum circuit with n qubits and m gates in polynomial space and m^O(n) time. We then discuss why this and other known algorithms fail to refute our assumption.
Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem---of the form ""if approximate quantum sampling is classically easy, then the polynomial hierarchy collapses""---must be non-relativizing. This sharply contrasts with the situation for exact sampling.
Fourth, refuting a conjecture by Aaronson and Ambainis, we show that the Fourier Sampling problem achieves a constant versus linear separation between quantum and randomized query complexities.
Fifth, in search of a ""happy medium"" between black-box and non-black-box arguments, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if one-way functions exist, then quantum supremacy is possible relative to such oracles. We show, conversely, that some computational assumption is needed: if SampBPP=SampBQP and NP is in BPP, then quantum supremacy is impossible relative to oracles with small circuits.
|
| 17:00 |
Stochasticity in algorithmic statistics for polynomial time
(abstract, slides)
Alexey Milovanov (National Research University Higher School of Economics), Nikolay Vereshchagin (National Research University Higher School of Economics)
A fundamental notion in Algorithmic Statistics (without resource bounds) is that of a stochastic object, for which there is a simple plausible explanation. Informally, a probability distribution is a plausible explanation for $x$ if it looks likely that $x$ was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical hypothesis for Algorithmic Statistics with polynomial time bounds, which are called
acceptability, plausibility and optimality. Roughly speaking, a probability distribution $\mu$ is called an acceptable explanation for $x$, if $x$ possesses all properties decidable by short programs in a short time and shared by almost all objects (with respect to $\mu$). Plausibility is a similar notion, however this time we require that $x$ possess properties $T$ decidable even by long programs in a short time and shared by almost all objects. To compensate the increase in program length, we strengthen the notion of `almost all'---the longer the program recognizing the property is, the more objects must share the property. Finally, a probability distribution $\mu$ is called an optimal explanation for $x$ if $\mu(x)$ is large (close to $2^{-\K^{\poly}(x)}$).
Almost all our results hold under some plausible complexity theoretic assumptions.
Our main result states that for acceptability and plausibility there are infinitely many non-stochastic objects, which do not have simple plausible (acceptable) explanations. We explain why we need assumptions---our main result implies that
P $\ne$ PSPACE. In the proof of that result, we use the notion of an elusive set,
which is interesting in its own right. Using elusive sets, we show
that the distinguishing complexity of a string $x$ can be super-logarithmically less than the conditional complexity of $x$ with condition $r$ for almost all $r$ (for polynomial time bounded programs). Such a gap was known before, however only in the case when both complexities are conditional, or both complexities are unconditional.
It follows from the definition that plausibility implies acceptability and optimality. We show that there are objects that have simple acceptable but implausible and non-optimal explanations. We prove that for strings whose
distinguishing complexity is close to Kolmogorov complexity (with polynomial time bounds) plausibility is equivalent to optimality for all simple distributions, which
fact can be considered as a justification of the Maximal Likelihood Estimator.
|
| 17:30 |
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
(abstract, slides)
Igor Carboni Oliveira (Charles University Prague), Rahul Santhanam (University of Oxford)
We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let $\mathfrak{C}$ be any typical class of Boolean circuits, and $\mathfrak{C}[s(n)]$ denote $n$-variable $\mathfrak{C}$-circuits of size $\leq s(n)$. We show:\\
\noindent \textbf{Learning Speedups.} If $\mathfrak{C}[\mathsf{poly}(n)]$ admits a randomized weak learning algorithm under the uniform distribution with membership queries that runs in time $2^n/n^{\omega(1)}$, then for every $k\geq 1$ and $\varepsilon>0$ the class $\mathfrak{C}[n^k]$ can be learned to high accuracy in time $O(2^{n^\varepsilon})$. There is $\varepsilon > 0$ such that $\mathfrak{C}[2^{n^{\varepsilon}}]$ can be learned in time $2^n/n^{\omega(1)}$ if and only if $\mathfrak{C}[\mathsf{poly}(n)]$ can be learned in time $2^{(\log n)^{O(1)}}$.\\
\noindent \textbf{Equivalences between Learning Models.} We use learning speedups to obtain equivalences between various randomized learning and compression models, including sub-exponential time learning with membership queries, sub-exponential time learning with membership and equivalence queries, probabilistic function compression and probabilistic average-case function compression.\\
\noindent \textbf{A Dichotomy between Learnability and Pseudorandomness.} In the non-uniform setting, there is non-trivial learning for $\mathfrak{C}[\mathsf{poly}(n)]$ if and only if there are no exponentially secure pseudorandom functions computable in $\mathfrak{C}[\mathsf{poly}(n)]$.\\
\noindent \textbf{Lower Bounds from Nontrivial Learning.} If for each $k \geq 1$, (depth-$d$)-$\mathfrak{C}[n^k]$ admits a randomized weak learning algorithm with membership queries under the uniform distribution that runs in time $2^n/n^{\omega(1)}$, then for each $k\geq 1$, $\mathsf{BPE} \nsubseteq$ (depth-$d$)-$\mathfrak{C}[n^k]$. If for some $\varepsilon > 0$ there are $\mathsf{P}$-natural proofs useful against $\mathfrak{C}[2^{n^{\varepsilon}}]$, then $\mathsf{ZPEXP} \nsubseteq \mathfrak{C}[\mathsf{poly}(n)]$.\\
\noindent \textbf{Karp-Lipton Theorems for Probabilistic Classes.} If there is a $k > 0$ such that $\mathsf{BPE} \subseteq \mathtt{i.o.}\mathsf{Circuit}[n^k]$, then $\mathsf{BPEXP} \subseteq \mathtt{i.o.}\mathsf{EXP}/O(\mathsf{log}\,n)$. If $\mathsf{ZPEXP} \subseteq \mathtt{i.o.}\mathsf{Circuit}[2^{n/3}]$, then $\mathsf{ZPEXP} \subseteq \mathtt{i.o.}\mathsf{ESUBEXP}$.\\
\noindent \textbf{Hardness Results for $\mathsf{MCSP}$.} All functions in non-uniform $\mathsf{NC}^1$ reduce to the Minimum Circuit Size Problem via truth-table reductions computable by $\mathsf{TC}^0$ circuits. In particular, if $\mathsf{MCSP} \in \mathsf{TC}^0$ then $\mathsf{NC}^1 = \mathsf{TC}^0$.
|
| 18:00 | Break |
| 18:15 | Rump session |
| 8:30 |
A quadratic lower bound for homogeneous algebraic branching programs
(abstract, slides)
Mrinal Kumar (Rutgers University)
An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of all paths from $s$ to $t$, where the weight of a path is the product of the weights of the edges in the path. An ABP is said to be homogeneous if the polynomial computed at every vertex is homogeneous. In this paper, we show that any homogeneous algebraic branching which computes the polynomial $x_1^n + x_2^n + \ldots + x_n^n$ has at least $\Omega(n^2)$ vertices (and hence edges).
To the best of our knowledge, this seems to be the first non-trivial super-linear lower bound on the number of vertices for a general \emph{homogeneous} ABP and slightly improves the known lower bound of $\Omega(n\log n)$ on the number of edges of in a general (possibly \emph{non-homogeneous}) ABP, which follows from the classical results of Strassen~\cite{Strassen73} and Baur \& Strassen~\cite{BS83}.
Our proof is quite simple, and also gives an alternate and unified proof of an $\Omega(n\log n)$ lower bound on the size of a \emph{homogeneous} arithmetic circuit (follows from~\cite{Strassen73, BS83}), and an $n/2$ lower bound ($n$ over $\mathbb{R}$) on the determinantal complexity of an explicit polynomial~\cite{mr04, CCL10, Yabe15}. These are currently the best lower bounds known for these problems for any explicit polynomial, and were originally proved nearly two decades apart using seemingly different proof techniques.
|
| 9:00 |
On algebraic branching programs of small width
(abstract, slides)
Karl Bringmann (Max-Planck-Institut für Informatik), Christian Ikenmeyer (Max-Planck-Institut für Informatik), Jeroen Zuiddam (CWI)
In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds.
Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar.
As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.
|
| 9:30 |
Reconstruction of full rank algebraic branching programs
(abstract, slides)
Neeraj Kayal (Microsoft Research India), Vineet Nair (Indian Institute of Science), Chandan Saha (Indian Instituite of Science), Sebastien Tavenas (University of Savoie Mont Blanc)
An algebraic branching program (ABP) A can be modelled as a product expression X_1.X_2...X_d, where X_1 and X_d are 1 x w and w x 1 matrices respectively, and every other X_k is a w x w$ matrix; the entries of these matrices are linear forms in m variables over a field F (which we assume to be either Q or a field of characteristic poly(m)). The polynomial computed by A is the entry of the 1 x 1 matrix obtained from the product \prod_{k=1}^{d} X_k. We say A is a full rank ABP if the w^2.(d-2) + 2w linear forms occurring in the matrices X_1,X_2,...,X_d are F-linearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an m-variate polynomial f of degree at most m, the algorithm outputs a full rank ABP computing f if such an ABP exists, or outputs `no full rank ABP exists' (with high probability). The running time of the algorithm is polynomial in m and \beta, where \beta is the bit length of the coefficients of f. The algorithm works even if X_k is a w_{k-1} x w_k matrix (with w_0 = w_d = 1), and \vecw = (w_1, ..., w_{d-1}) is unknown.
The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMM_{\vecw,d}, the (1,1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to \vecw \in N^{d-1}. At its core, the algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM_{\vecw,d} and the `layer spaces' of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMM_{\vecw,d} and show that IMM_{\vecw,d} is characterized by its group of symmetries.
|
| 10:00 | Coffee break |
| 10:30 |
Tutorial (part 3)
Operator scaling: theory, applications and connections
(abstract)
Avi Wigderson (Institute for Advanced Study)
|
| 12:30 | Lunch |
| 14:30 |
Trading information complexity for error
(abstract, slides)
Yuval Dagan (Technion), Yuval Filmus (Technion), Hamed Hatami (McGill University), Yaqiao Li (McGill University)
We consider the standard two-party communication model.
The central problem studied in this article is how much one can save in information complexity by allowing an error.
Our major result is that the epsilon-error randomized communication complexity of set disjointness is n[C_DISJ - Theta(h(epsilon))] + o(n), where C_DISJ ≈ 0.4827 is the constant of set disjointness found by Braverman et al.
|
| 15:00 |
Augmented index and quantum streaming algorithms for DYCK(2)
(abstract, slides)
Ashwin Nayak (University of Waterloo), Dave Touchette (University of Waterloo and Perimeter Institute)
We show how two recently developed quantum information theoretic tools can be
applied to obtain lower bounds on quantum information complexity.
We also develop new tools with potential for broader applicability,
and use them to establish a lower bound on the quantum information
complexity for the Augmented Index function on an easy distribution.
This approach allows us to handle superpositions rather than
distributions over inputs, the main technical challenge faced previously.
By providing a quantum generalization of the argument of Jain and
Nayak~[IEEE TIT'14], we leverage this to obtain a lower bound on the
space complexity of multi-pass, unidirectional
quantum streaming algorithms for the DYCK(2) language.
|
| 15:30 |
Separating quantum communication and approximate rank
(abstract, slides)
Anurag Anshu (National University of Singapore), Shalev Ben-David (MIT), Ankit Garg (MSR New England), Rahul Jain (National University of Singapore and MajuLab), Robin Kothari (MIT), Troy Lee (Nanyang Technological University, Centre for Quantum Technologies, and MajuLab)
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma_2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank.
In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F.
|
| 16:00 |
Optimal quantum sample complexity of learning algorithms
(abstract, slides)
Srinivasan Arunachalam (CWI), Ronald de Wolf (CWI and University of Amsterdam)
In learning theory, the {VC dimension} of a concept class \C is the most common way to measure its ``richness.''
A fundamental result says that the number of examples needed to learn an unknown target concept c\in\C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class \C. Specifically, in the PAC model
\Theta\Big(\frac{d}{\eps} + \frac{\log(1/\delta)}{\eps}\Big)
examples are necessary and sufficient for a learner to output, with probability 1-\delta, a hypothesis h that is \eps-close to the target concept c (measured under D). In the related {agnostic} model, where the samples need not come from a c\in\C, we know that
\Theta\Big(\frac{d}{\eps^2} + \frac{\log(1/\delta)}{\eps^2}\Big)
examples are necessary and sufficient to output an hypothesis h \in \C whose error is at most \eps worse than the error of the best concept in \C.
Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is
\Omega\Big(\frac{d^{1-\eta}}{\eps} + d + \frac{\log(1/\delta)}{\eps}\Big)\mbox{ for arbitrarily small constant }\eta>0.
Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models.
We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a \log(d/\eps) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the ``Pretty Good Measurement'' on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class \C.
|
| 16:30 | Excursion |
| 20:00 | Banquet |
| 8:30 |
Settling the query complexity of non-adaptive junta testing
(abstract, slides)
Xi Chen (Columbia University), Rocco A. Servedio (Columbia University), Li-Yang Tan (TTI Chicago), Erik Waingarten (Columbia University), Jinyu Xie (Columbia University)
We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f:{0,1}^n -> {0,1} is a k-junta or \eps-far from every k-junta must make \widetilde{\Omega}(k^{3/2}/\eps) many queries for a wide range of parameters k and \eps. Our result dramatically improves previous lower bounds from [BGSMdW13, STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Bla08], which makes \widetilde{O}(k^{3/2})/\eps queries. Combined with the adaptive tester of [Bla09] which makes O(k log k + k/\eps) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.
|
| 9:00 |
An adaptivity hierarchy theorem for property testing
(abstract, slides)
Clément Canonne (Columbia University), Tom Gur (Weizmann Institute of Science)
The notion of adaptivity can play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers received to prior queries, and their non-adaptive counterparts, in which all queries are independent of answers obtained from previous queries.
In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of "rounds of adaptivity" it uses. More accurately, we say that a tester is k-(round) adaptive if it makes queries in k rounds, where the queries in the (i+1)'st round may depend on the answers obtained in the previous i rounds. Then, we ask the following question:
"Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity?"
We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every n and 0 <= k <= n^{0.99} there exists a property P_{n,k} of functions for which (1) there exists a k-adaptive tester for P_{n,k} with query complexity ~O(k), yet (2) any (k-1)-adaptive tester for P_{n,k} must make Omega(n) queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.
|
| 9:30 |
Distribution testing lower bounds via reductions from communication complexity
(abstract, slides)
Eric Blais (University of Waterloo), Clément Canonne (Columbia University), Tom Gur (Weizmann Institute of Science)
We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove several new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds.
Our main result is concerned with testing identity to a specific distribution p, given as a parameter. In a recent and influential work, Valiant and Valiant [VV14] showed that the sample complexity of the aforementioned problem is closely related to the 2/3-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs.
More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre's K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p).
This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.
|
| 10:00 |
Exponentially small soundness for the direct product Z-test
(abstract, slides)
Irit Dinur (Weizmann Institute of Science), Inbal Livni Navon (Weizmann Institute of Science)
Given a function f:[N]^k\rightarrow[M]^k, the Z-test is a three query test for checking if a function f is a direct product, namely if there are functions g_1,\dots g_k:[N]\to[M] such that f(x)=(g_1(x_1),\dots g_k(x_k)) for every input x\in [N]^k.
This test was introduced by Impagliazzo et. al. (SICOMP 2012), who showed that if the test passes with probability \epsilon > \exp(-\sqrt k) then f is poly(\epsilon) close to a direct product function in some precise sense. It remained an open question whether the soundness of this test can be pushed all the way down to \exp(-k) (which would be optimal). This is our main result: we show that whenever f passes the Z test with probability \epsilon > \exp(-k), there must be a global reason for this: namely, f must be close to a product function on some poly(\epsilon) fraction of its domain.
Towards proving our result we analyze the related (two-query) V-test, and prove a ``restricted global structure'' theorem for it. Such theorems were also proven in previous works on direct product testing in the small soundness regime. The most recent work, by Dinur and Steurer (CCC 2014), analyzed the V test in the exponentially small soundness regime. We strengthen the conclusion of that theorem by moving from an ``in expectation'' statement to a stronger ``concentration of measure'' type of statement, which we prove using hyper-contractivity. This stronger statement allows us to proceed to analyze the Z test.
We analyze two variants of direct product tests. One for functions on tuples, as above, and another for functions on sets, f:\binom{[N]}{k}\to[M]^k. The work of Impagliazzo et. al was actually focused only on functions of the later type, i.e. on sets. We prove exponentially small soundness for the Z-test for both variants. Although the two appear very similar, the analysis for tuples is more tricky and requires some additional ideas.
|
| 10:30 | Coffee break |
| 11:00 |
On the polynomial parity argument complexity of the combinatorial Nullstellensatz
(abstract, slides)
Aleksandrs Belovs (University of Latvia), Gabor Ivanyos (Hungarian Academy of Sciences), Youming Qiao (University of Technology Sydney), Miklos Santha (CNRS, Université Paris Diderot, and National University of Singapore), Siyi Yang (National University of Singapore)
The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems.
Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field F2. The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.
|
| 11:30 |
An exponential lower bound for homogeneous depth-5 circuits over finite fields
(abstract, slides)
Mrinal Kumar (Rutgers University), Ramprasad Saptharishi (TIFR Bombay)
In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$ circuits over all small finite fields. More formally, we show that there is an explicit family $\{P_d : d \in \N\}$ of polynomials in $\VNP$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, such that over all finite fields $\F_q$, any homogeneous depth-$5$ circuit which computes $P_d$ must have size at least $\exp(\Omega_q(\sqrt{d}))$.
To the best of our knowledge, this is the first super-polynomial lower bound for homogeneous depth-5 circuits for any field $\F_q \neq \F_2$.
Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-$4$ circuits~\cite{gkks13, FLMS13, KLSS, KS14} and for non-homogeneous depth-$3$ circuits over finite fields~\cite{grigoriev98, gr00}.
Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from $\F_q^n \rightarrow \F_q$ as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf~\cite{KS14}.
|
| 12:00 |
Complete derandomization of identity testing and reconstruction of read-once formulas
(abstract, slides 1, slides 2)
Daniel Minahan (University of Michigan), Ilya Volkovich (University of Michigan)
In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models.
A read-once formula is formula (a circuit whose underlying graph is a tree) in which the operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for read-once formulas, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas. Our results are obtained by improving and extending the analysis of the algorithm of \cite{ShpilkaVolkovich15a}.
|
| 12:30 |
Greedy strikes again: A deterministic PTAS for commutative rank of matrix spaces
(abstract, slides)
Markus Blaeser (Saarland University), Gorav Jindal (Max-Planck-Institute for Informatics), Anurag Pandey (Max-Planck-Institute for Informatics)
We consider the problem of commutative rank computation of a given matrix space,
$\mathcal{B}\subseteq\mathbb{F}^{n\times n}$. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is $n$, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic $\frac{1}{2}$-approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.
We present a deterministic $\textrm{PTAS}$ for computing the commutative rank
of a given matrix space. More specifically, given a matrix space
$\mathcal{B}\subseteq\F^{n\times n}$ and a rational number $\epsilon > 0$, we give an algorithm, that runs in time $O(n^{4+\frac{3}{\epsilon}})$ and computes
a matrix $A\in\mathcal{B}$ such that the rank of $A$ is at least $(1-\epsilon)$
times the commutative rank of $\mathcal{B}$. The algorithm is the natural
greedy algorithm. It always takes the first set of $k$ matrices that will increase the rank of the matrix constructed so far until it does not find any improvement,
where the size of the set $k$ depends on $\epsilon$.
|
| 13:00 | End of the conference |
