Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2019:
All reports in year 2019:
TR19-001 | 5th January 2019
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

#### On OBDD-based algorithms and proof systems that dynamically change order of variables

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

TR19-002 | 31st December 2018
Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

#### Complexity of Linear Operators

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

TR19-003 | 2nd January 2019
Alexander A. Sherstov, Pei Wu

#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

TR19-004 | 11th January 2019
Amey Bhangale, Subhash Khot

#### UG-hardness to NP-hardness by Losing Half

Revisions: 1

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

TR19-005 | 16th January 2019
Omar Alrabiah, Venkatesan Guruswami

#### An Exponential Lower Bound on the Sub-Packetization of MSR Codes

An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some field $\mathbb{F}$) of dimension $k\ell$, such that any $k$ (vector) symbols of the codeword suffice to determine the remaining $r=n-k$ (vector) symbols. The length $\ell$ of each codeword symbol is called the sub-packetization of the code. Such a ... more >>>

TR19-006 | 17th January 2019
Anna Gal, Ridwan Syed

#### Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity ... more >>>

TR19-007 | 17th January 2019

#### Lower Bounds for Linear Decision Lists

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.
We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ... more >>>

TR19-008 | 20th January 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>> TR19-009 | 16th January 2019 Jiawei Gao, Russell Impagliazzo #### The Fine-Grained Complexity of Strengthenings of First-Order Logic Revisions: 1 The class of model checking for first-order formulas on sparse graphs has a complete problem with respect to fine-grained reductions, Orthogonal Vectors (OV) [GIKW17]. This paper studies extensions of this class or more lenient parameterizations. We consider classes obtained by allowing function symbols; first-order on ordered structures; adding various notions ... more >>> TR19-010 | 21st January 2019 Dorit Aharonov, Alex Bredariol Grilo #### Stoquastic PCP vs. Randomness The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>> TR19-011 | 27th January 2019 Benny Applebaum, Eliran Kachlon #### Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders Revisions: 2 We initiate the study of the following hypergraph sampling problem: Sample a$d$-uniform hypergraph over$n$vertices and$m$hyperedges from some pseudorandom distribution$\mathcal{G}$conditioned on not having some small predefined$t$-size hypergraph$H$as a subgraph. The algorithm should run in$\mathrm{poly}(n)$-time even when the size of the ... more >>> TR19-012 | 27th January 2019 Oded Goldreich #### Multi-pseudodeterministic algorithms In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011). Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>> TR19-013 | 31st January 2019 Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami #### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo$M$, for various choices of the modulus$M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>> TR19-014 | 22nd January 2019 Himanshu Tyagi, Shun Watanabe #### A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem We present an information theoretic proof of the nonsignalling multiprover parallel repetition theorem, a recent extension of its two-prover variant that underlies many hardness of approximation results. The original proofs used de Finetti type decomposition for strategies. We present a new proof that is based on a technique we introduced ... more >>> TR19-015 | 7th February 2019 William Kretschmer #### QMA Lower Bounds for Approximate Counting We prove a query complexity lower bound for$QMA$protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle$A$such that$SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>> TR19-016 | 5th February 2019 Alexander A. Sherstov #### The hardest halfspace We study the approximation of halfspaces$h:\{0,1\}^n\to\{0,1\}$in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all ... more >>> TR19-017 | 6th February 2019 Chin Ho Lee #### Fourier bounds and pseudorandom generators for product tests We study the Fourier spectrum of functions$f\colon \{0,1\}^{mk} \to \{-1,0,1\}$which can be written as a product of$k$Boolean functions$f_i$on disjoint$m$-bit inputs. We prove that for every positive integer$d$, $\sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d .$ Our upper bound ... more >>> TR19-018 | 18th February 2019 Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal #### AC0[p] Lower Bounds against MCSP via the Coin Problem Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an$n$-variate boolean function has circuit complexity less than a given parameter$s$. We prove that MCSP is hard for constant-depth circuits with mod$p$gates, for any prime$p\geq 2$(the circuit class$AC^0[p])$. Namely, ... more >>> TR19-019 | 19th February 2019 Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi #### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits We show that any$n$-variate polynomial computable by a syntactically multilinear circuit of size$\mathop{poly}(n)$can be computed by a depth-$4$syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most$\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree$d = \omega(n/\log n)$, this improves upon the upper bound of$\exp\left({O(\sqrt{d}\log n)}\right)$obtained by Tavenas (MFCS ... more >>> TR19-020 | 4th February 2019 Ludmila Glinskih, Dmitry Itsykson #### On Tseitin formulas, read-once branching programs and treewidth Revisions: 1 We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an$n\times n$grid graph has size at least$2^{\Omega(n)}$. Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph$G(V,E)$any nondeterministic read-once branching program that computes ... more >>> TR19-021 | 19th February 2019 Rahul Ilango ####$AC^0[p]$Lower Bounds and NP-Hardness for Variants of MCSP The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>> TR19-022 | 23rd February 2019 Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis #### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators Revisions: 1 The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function$f$can be computed by a Boolean circuit of size at most$\theta$, for a given parameter$\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>> TR19-023 | 25th February 2019 Orr Paradise #### Smooth and Strong PCPs Revisions: 3 Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs: - ... more >>> TR19-024 | 20th February 2019 Russell Impagliazzo, Sasank Mouli, Toniann Pitassi #### The Surprising Power of Constant Depth Algebraic Proofs Revisions: 2 A major open problem in proof complexity is to prove super-polynomial lower bounds for AC^0[p]-Frege proofs. This system is the analog of AC^0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), ... more >>> TR19-025 | 28th February 2019 Shuichi Hirahara, Osamu Watanabe #### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets Revisions: 1 We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>> TR19-026 | 28th February 2019 Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff #### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits Revisions: 1 There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets$S_1,\ldots,S_k \subset [n]$is balancing if for every subset$X \subset \{1,2,\ldots,n\}$of size$n/2$, there is an$i \in [k]$so that$|S_i \cap X| = ... more >>>

TR19-027 | 1st March 2019
Mark Bun, Nikhil Mande, Justin Thaler

#### Sign-Rank Can Increase Under Intersection

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.

For a communication problem ... more >>>

TR19-028 | 1st March 2019
Shachar Lovett, Noam Solomon, Jiapeng Zhang

#### From DNF compression to sunflower theorems via regularity

Revisions: 1

The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds ... more >>>

TR19-029 | 20th February 2019
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

#### Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

TR19-030 | 19th February 2019
Claude Crépeau, Nan Yang

#### Non-Locality in Interactive Proofs

In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call “contamination” by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new ... more >>>

TR19-031 | 4th March 2019
Lijie Chen

#### Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Revisions: 1

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ... more >>>

TR19-032 | 4th March 2019
Srikanth Srinivasan

#### Strongly Exponential Separation Between Monotone VP and Monotone VNP

Revisions: 1

We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $\exp(\Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $\exp(\tilde{\Omega}(\sqrt{n})).$

more >>>

TR19-033 | 20th February 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

#### Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

TR19-034 | 5th March 2019
Pavel Hrubes

Revisions: 1

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>> TR19-035 | 5th March 2019 Alexey Milovanov #### PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials This text is a development of a preprint of Ankit Gupta. We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$circuits with bounded top fanin. This approach is similar to Kayal-Saraf approach for depth-$3$circuits. Kayal and Saraf based their ... more >>> TR19-036 | 5th March 2019 Pavel Hrubes #### On the complexity of computing a random Boolean function over the reals Revisions: 1 We say that a first-order formula$A(x_1,\dots,x_n)$over$\mathbb{R}$defines a Boolean function$f:\{0,1\}^n\rightarrow\{0,1\}$, if for every$x_1,\dots,x_n\in\{0,1\}$,$A(x_1,\dots,x_n)$is true iff$f(x_1,\dots,x_n)=1$. We show that: (i) every$f$can be defined by a formula of size$O(n)$, (ii) if$A$is required to have at most$k\geq 1$... more >>> TR19-037 | 5th March 2019 Chi-Ning Chou, Mrinal Kumar, Noam Solomon #### Closure of VP under taking factors: a short and simple proof Revisions: 1 In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree$d$polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>> TR19-038 | 7th March 2019 Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Vasudevan #### Statistical Difference Beyond the Polarizing Regime Revisions: 1 The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits$(C_0,C_1)$and an integer$k$and outputting a new pair of circuits$(D_0,D_1)$such that if$\mathrm{SD}(C_0,C_1)\geq\alpha$then$\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$and if$\mathrm{SD}(C_0,C_1) \leq ... more >>>

TR19-039 | 12th March 2019
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

#### Planarity, Exclusivity, and Unambiguity

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

#### The Complexity of Finding {$S$}-factors in Regular Graphs

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

TR19-041 | 7th March 2019
Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

#### Quantum hardness of learning shallow classical circuits

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>

TR19-042 | 18th March 2019
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

#### Determinant equivalence test over finite fields and over $\mathbf{Q}$

The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is ... more >>>

TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

TR19-044 | 28th March 2019
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space $U$ is $\delta$-far in ... more >>>

TR19-045 | 19th February 2019
Jiawei Gao

#### On the Fine-grained Complexity of Least Weight Subsequence in Graphs

Revisions: 1

Least Weight Subsequence (LWS) is a type of highly sequential optimization problems with form $F(j) = \min_{i < j} [F(i) + c_{i,j}]$. They can be solved in quadratic time using dynamic programming, but it is not known whether these problems can be solved faster than $n^{2-o(1)}$ time. Surprisingly, each such ... more >>>

TR19-046 | 1st April 2019
Akash Kumar, C. Seshadhri, Andrew Stolman

#### andom walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs

Revisions: 1

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).
We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.
The problem of property testing $\mathcal{P}$ was introduced in ... more >>>

TR19-047 | 2nd April 2019
Mrinal Kumar, Ben Lee Volk

#### Lower Bounds for Matrix Factorization

We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of ... more >>>

TR19-048 | 2nd April 2019
Per Austrin, Amey Bhangale, Aditya Potukuchi

#### Simplified inpproximability of hypergraph coloring via t-agreeing families

We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs ... more >>>

TR19-049 | 2nd April 2019

#### A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments

Revisions: 2

Parallel repetition is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols. However, it does not do so in the general case.

Haitner [FOCS '09, SiCOMP '13] presented a simple method for transforming any interactive argument $\pi$ into a slightly modified ... more >>>

TR19-050 | 20th March 2019
Titus Dose, Christian Glaßer

#### NP-Completeness, Proof Systems, and Disjoint NP-Pairs

The article investigates the relation between three well-known hypotheses.
1) Hunion: the union of disjoint complete sets for NP is complete for NP
2) Hopps: there exist optimal propositional proof systems
3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:
a) The hypotheses are pairwise independent ... more >>>

TR19-051 | 9th April 2019
Emanuele Viola

#### Pseudorandom bits and lower bounds for randomized Turing machines

We exhibit a pseudorandom generator with nearly quadratic stretch for randomized Turing machines, which have a one-way random tape and a two-way work tape. This is the first generator for this model. Its stretch is essentially the best possible given current lower bounds. We use the generator to prove a ... more >>>

TR19-052 | 9th April 2019
Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen

#### Polynomial calculus space and resolution width

We show that if a $k$-CNF requires width $w$ to refute in resolution, then it requires space $\sqrt w$ to refute in polynomial calculus, where the space of a polynomial calculus refutation is the number of monomials that must be kept in memory when working through the proof. This is ... more >>>

TR19-053 | 5th April 2019
Andrei Krokhin, Jakub Opršal

#### The complexity of 3-colouring $H$-colourable graphs

We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to decide whether a given graph has a homomorphism to $H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph $H$. In ... more >>>

TR19-054 | 9th April 2019
Joshua Brakensiek, Venkatesan Guruswami

#### Bridging between 0/1 and Linear Programming via Random Walks

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial ... more >>>

TR19-055 | 9th April 2019
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

#### Lower Bounds for Oblivious Near-Neighbor Search

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

TR19-056 | 11th April 2019
Tom Gur, Oded Lachish

#### A Lower Bound for Relaxed Locally Decodable Codes

Revisions: 1

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>

TR19-057 | 6th April 2019

#### Proof Complexity of Symmetry Learning in QBF

For quantified Boolean formulas (QBF), a resolution system with a symmetry rule was recently introduced by Kauers and Seidl (Inf. Process. Lett. 2018). In this system, many formulas hard for QBF resolution admit short proofs.

Kauers and Seidl apply the symmetry rule on symmetries of the original formula. Here we ... more >>>

TR19-058 | 16th April 2019
Pavel Pudlak, Vojtech Rodl

#### Extractors for small zero-fixing sources

A random variable $X$ is an $(n,k)$-zero-fixing source if for some subset $V\subseteq[n]$, $X$ is the uniform distribution on the strings $\{0,1\}^n$ that are zero on every coordinate outside of $V$. An $\epsilon$-extractor for $(n,k)$-zero-fixing sources is a mapping $F:\{0,1\}^n\to\{0,1\}^m$, for some $m$, such that $F(X)$ is $\epsilon$-close in statistical ... more >>>

TR19-059 | 18th April 2019
Rohit Agrawal

#### Samplers and extractors for unbounded functions

Revisions: 1

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions $f:\{0,1\}^m \to \mathbb{R}$ such that $f(U_m)$ has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact ... more >>>

TR19-060 | 18th April 2019
Scott Aaronson, Guy Rothblum

#### Gentle Measurement of Quantum States and Differential Privacy

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... more >>>

TR19-061 | 16th April 2019
Scott Aaronson, Daniel Grier, Luke Schaeffer

#### A Quantum Query Complexity Trichotomy for Regular Languages

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\Theta}(\sqrt n)$, or $\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>>

TR19-062 | 18th April 2019
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

#### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Revisions: 2

This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set $S\subseteq [N]$.

Given only a membership oracle for $S$, it is well known that approximate counting takes $\Theta(\sqrt{N/|S|})$ quantum queries. But what if a quantum algorithm ... more >>>

TR19-063 | 28th April 2019
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Hrubeš and Wigderson [HW14] initiated the study of
noncommutative arithmetic circuits with division computing a
noncommutative rational function in the free skew field, and
raised the question of rational identity testing. It is now known
that the problem can be solved in deterministic polynomial time in
more >>>

TR19-064 | 23rd April 2019
Igor Carboni Oliveira

#### Randomness and Intractability in Kolmogorov Complexity

We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability.

This complexity measure gives rise to a ... more >>>

TR19-065 | 1st May 2019
Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

#### Derandomization from Algebraic Hardness: Treading the Borders

Revisions: 3

A hitting-set generator (HSG) is a polynomial map $Gen:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $Q$ of small enough circuit size and degree, if $Q$ is non-zero, then $Q\circ Gen$ is non-zero. In this paper, we give a new construction of such a HSG assuming that we have ... more >>>

TR19-066 | 3rd May 2019
Thomas Watson

#### A Lower Bound for Sampling Disjoint Sets

Revisions: 2

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. ... more >>>

TR19-067 | 6th May 2019
Hamed Hatami, Kaave Hosseini, Shachar Lovett

#### Sign rank vs Discrepancy

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.
In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank ... more >>>

TR19-068 | 27th April 2019
Shuo Pang

#### LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION

We prove resolution lower bounds for $k$-Clique on the Erdos-Renyi random graph $G(n,n^{-{2\xi}\over{k-1}})$ (where $\xi>1$ is constant). First we show for $k=n^{c_0}$, $c_0\in(0,1/3)$, an $\exp({\Omega(n^{(1-\epsilon)c_0})})$ average lower bound on resolution where $\epsilon$ is arbitrary constant.

We then propose the model of $a$-irregular resolution. Extended from regular resolution, this model ... more >>>

TR19-069 | 6th May 2019
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

#### Bounded-depth Frege complexity of Tseitin formulas for all graphs

Revisions: 1

We prove that there is a constant $K$ such that \emph{Tseitin} formulas for an undirected graph $G$ requires proofs of
size $2^{\mathrm{tw}(G)^{\Omega(1/d)}}$ in depth-$d$ Frege systems for $d<\frac{K \log n}{\log \log n}$, where $\tw(G)$ is the treewidth of $G$. This extends H{\aa}stad recent lower bound for the grid graph ... more >>>

TR19-070 | 14th May 2019
Alessandro Chiesa, Peter Manohar, Igor Shinkar

#### On Local Testability in the Non-Signaling Setting

Revisions: 1

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

TR19-071 | 14th May 2019
Sumegha Garg, Ran Raz, Avishay Tal

#### Time-Space Lower Bounds for Two-Pass Learning

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{2})$ or an exponential number ... more >>>

TR19-072 | 17th May 2019
Lijie Chen, Ofer Grossman

#### Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators

Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) ... more >>>

TR19-073 | 17th May 2019
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

#### Parity helps to compute Majority

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC$^0[\oplus]$ circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$. By using a divide-and-conquer approach, it is easy to show that Majority can ... more >>>

TR19-074 | 22nd May 2019
Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum

#### Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that ... more >>>

TR19-075 | 25th May 2019
Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

#### Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>

TR19-076 | 24th May 2019
Leroy Chew, Judith Clymo

#### The Equivalences of Refutational QRAT

The solving of Quantified Boolean Formulas (QBF) has been advanced considerably in the last two decades. In response to this, several proof systems have been put forward to universally verify QBF solvers.
QRAT by Heule et al. is one such example of this and builds on technology from DRAT, ... more >>>

TR19-077 | 30th May 2019
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek

#### Consistency of circuit lower bounds with bounded theories

Proving that there are problems in $P^{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>>

TR19-078 | 1st June 2019
Itai Benjamini, Oded Goldreich

#### Pseudo-Mixing Time of Random Walks

We introduce the notion of pseudo-mixing time of a graph define as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer, where, in addition to the tested vertex, the observer is also provided with oracle access to the ... more >>>

TR19-079 | 28th May 2019
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

#### Average Bias and Polynomial Sources

Revisions: 2

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

TR19-080 | 1st June 2019
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

#### On List Recovery of High-Rate Tensor Codes

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

TR19-081 | 31st May 2019
Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

#### Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Revisions: 1

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>

TR19-082 | 2nd June 2019
Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

#### Approximate degree, secret sharing, and concentration phenomena

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

TR19-083 | 4th June 2019
Lior Gishboliner, Asaf Shapira

#### Testing Graphs against an Unknown Distribution

Revisions: 1

The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property $\mathcal{P}$ is said ... more >>>

TR19-084 | 26th May 2019
Michal Garlik

#### Resolution Lower Bounds for Refutation Statements

For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolution refutations of a propositional statement that the formula has a resolution refutation. We describe three applications. (1) An open question in [Atserias-Müller,2019] asks whether a certain natural propositional encoding of the above statement is ... more >>>

TR19-085 | 7th June 2019
Xuangui Huang, Emanuele Viola

Revisions: 2

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps ... more >>> TR19-086 | 7th June 2019 Alex Bredariol Grilo, William Slofstra, Henry Yuen #### Perfect zero knowledge for quantum multiprover interactive proofs In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP$^*$, the set of languages decidable by multiprover interactive ... more >>> TR19-087 | 10th June 2019 Rohit Agrawal #### Coin Theorems and the Fourier Expansion Revisions: 1 In this note we compare two measures of the complexity of a class$\mathcal F$of Boolean functions studied in (unconditional) pseudorandomness:$\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in$\mathcal ... more >>>

TR19-088 | 16th June 2019
Oded Goldreich

#### On the Complexity of Estimating the Effective Support Size

Loosely speaking, the effective support size of a distribution is the size of the support of a distribution that is close to it (in totally variation distance).
We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distributions as well ... more >>>

TR19-089 | 21st June 2019
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

#### Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, ... more >>>

TR19-090 | 27th June 2019
Ronen Shaltiel, Swastik Kopparty, Jad Silbak

#### Quasilinear time list-decodable codes for space bounded channels

Revisions: 2

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>

TR19-091 | 7th July 2019
Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, Vinodchandran Variyam, Osamu Watanabe

#### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>

TR19-092 | 9th July 2019
Venkatesan Guruswami, Jakub Opršal, Sai Sandeep

#### Revisiting Alphabet Reduction in Dinur's PCP

Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... more >>>

TR19-093 | 15th July 2019
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

#### Improved 3LIN Hardness via Linear Label Cover

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

TR19-094 | 16th July 2019
Venkatesan Guruswami, Sai Sandeep

#### Rainbow coloring hardness via low sensitivity polymorphisms

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>

TR19-095 | 18th July 2019
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

#### Unambiguous Catalytic Computation

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,
Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing
machine, this model has an extra space which is filled with arbitrary content in addition
to the clean space. In such a model we study ... more >>>

TR19-096 | 23rd July 2019

#### On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem

Andreev's Problem asks the following: Given an integer $d$ and a subset of $S \subseteq \mathbb{F}_q \times \mathbb{F}_q$, is there a polynomial $y = p(x)$ of degree at most $d$ such that for every $a \in \mathbb{F}_q$, $(a,p(a)) \in S$? We show an $\text{AC}^0[\oplus]$ lower bound for this problem.

... more >>>

TR19-097 | 4th July 2019
Jacobo Toran, Florian Wörz

#### Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>>

TR19-098 | 20th July 2019
Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

#### Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit

We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information about their samples due to various information constraints. Recently, a subset of the authors showed that having access to a common random seed (i.e., ... more >>>

TR19-099 | 29th July 2019
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

TR19-100 | 31st July 2019
Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

#### Nonnegative rank measures and monotone algebraic branching programs

Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove ... more >>>

TR19-101 | 24th July 2019
Amit Chakrabarti, Prantar Ghosh

#### Streaming Verification of Graph Computations via Graph Structure

We give new algorithms in the annotated data streaming setting---also known as verifiable data stream computation---for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to ... more >>>

TR19-102 | 10th August 2019
Oded Goldreich

#### Testing Isomorphism in the Bounded-Degree Graph Model

Revisions: 1

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.
We essentially determine the query complexity of these testing problems in the special case of ... more >>>

TR19-103 | 7th August 2019

#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 1

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

TR19-104 | 6th August 2019
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

#### Reconstruction of Depth-$4$ Multilinear Circuits

We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. For any fixed $k$, given black-box access to a polynomial $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ computable by a multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time ... more >>>

TR19-105 | 16th August 2019
Ragesh Jaiswal

#### A note on the relation between XOR and Selective XOR Lemmas

Given an unpredictable Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$, the standard Yao's XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in [k]}f(x_i)$ given $x_1, ..., x_k \in \{0, 1\}^n$, whereas the Selective XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in S}f(x_i)$ ... more >>>

TR19-106 | 12th August 2019
Noah Fleming, Pravesh Kothari, Toniann Pitassi

#### Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 3

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

TR19-107 | 29th July 2019
Zachary Remscrim

#### The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups

Revisions: 1

The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in ... more >>>

TR19-108 | 23rd August 2019
Chaoping Xing, chen yuan

#### Beating the probabilistic lower bound on perfect hashing

Revisions: 2

For an interger $q\ge 2$, a perfect $q$-hash code $C$ is a block code over $\ZZ_q:=\ZZ/ q\ZZ$ of length $n$ in which every subset $\{\bc_1,\bc_2,\dots,\bc_q\}$ of $q$ elements is separated, i.e., there exists $i\in[n]$ such that $\{\proj_i(\bc_1),\proj_i(\bc_2),\dots,\proj_i(\bc_q)\}=\ZZ_q$, where $\proj_i(\bc_j)$ denotes the $i$th position of $\bc_j$. Finding the maximum size $M(n,q)$ ... more >>>

TR19-109 | 21st August 2019
Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

#### Decoding Downset codes over a finite grid

In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general grid $S_1\times\cdots \times S_m.$ We show that their algorithm can be adapted to solve the unique decoding problem for the general ... more >>>

TR19-110 | 23rd August 2019
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

#### Improved bounds for the sunflower lemma

A sunflower with $r$ petals is a collection of $r$ sets so that the
intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ... more >>>

TR19-111 | 16th August 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

#### Noisy Beeps

We study the effect of noise on the $n$-party beeping model. In this model, in every round, each party may decide to either beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... more >>>

TR19-112 | 1st September 2019
Yotam Dikstein, Irit Dinur

#### Agreement testing theorems on layered set systems

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test.

Previous work has shown that high dimensional expansion ... more >>>

TR19-113 | 5th September 2019
Tomer Grossman, Ilan Komargodski, Moni Naor

#### Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, ... more >>>

TR19-114 | 2nd September 2019
Visu Makam, Avi Wigderson

#### Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: ${\rm SING}_{n,m}$, consisting of all $m$-tuples of $n\times n$ complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in ${\rm SING}_{n,m}$ will imply super-polynomial circuit lower bounds, ... more >>>

TR19-115 | 4th September 2019
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

#### Parameterized Intractability of Even Set and Shortest Vector Problem

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

TR19-116 | 9th September 2019
Venkatesan Guruswami, Sai Sandeep

#### $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

Revisions: 1

The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ ... more >>>

TR19-117 | 4th September 2019
Silas Richelson, Sourya Roy

#### Locally Testable Non-Malleable Codes

Revisions: 1

In this work we adapt the notion of non-malleability for codes or Dziembowski, Pietrzak and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is non-malleable if any tampered codeword which passes the local test with good probability is close to a valid codeword which either ... more >>>

TR19-118 | 5th September 2019
Lijie Chen, Ce Jin, Ryan Williams

#### Hardness Magnification for all Sparse NP Languages

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of ... more >>>

TR19-119 | 9th September 2019
Dean Doron, Amnon Ta-Shma, Roei Tell

#### On Hitting-Set Generators for Polynomials that Vanish Rarely

Revisions: 1

We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was ... more >>>

TR19-120 | 11th September 2019
Or Meir

#### Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revisions: 1

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f ... more >>> TR19-121 | 17th September 2019 Alexander A. Sherstov, Justin Thaler #### Vanishing-Error Approximate Degree and QMA Complexity The$\epsilon$-approximate degree of a function$f\colon X \to \{0, 1\}$is the least degree of a multivariate real polynomial$p$such that$|p(x)-f(x)| \leq \epsilon$for all$x \in X$. We determine the$\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>> TR19-122 | 13th September 2019 Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters #### LDPC Codes Achieve List-Decoding Capacity Revisions: 2 We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. ... more >>> TR19-123 | 12th September 2019 Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell #### On the Hardness of Robust Classification It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. ... more >>> TR19-124 | 28th August 2019 Roy Gotlib, Tali Kaufman #### Testing Odd Direct Sums Using High Dimensional Expanders In this work, using methods from high dimensional expansion, we show that the property of$k$-direct-sum is testable for odd values of$k$. Previous work of Kaufman and Lubotzky could inherently deal only with the case that$k$is even, using a reduction to linearity testing. Interestingly, our work ... more >>> TR19-125 | 27th August 2019 Elazar Goldenberg, Karthik C. S. #### Hardness Amplification of Optimization Problems In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products. We say that an optimization problem$\Pi$is direct product feasible if it is possible to efficiently aggregate any$k$instances of$\Pi$and form one large instance ... more >>> TR19-126 | 19th September 2019 Irit Dinur, Roy Meshulam #### Near Coverings and Cosystolic Expansion -- an example of topological property testing We study the stability of covers of simplicial complexes. Given a map f:Y?X that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of X? Complexes X for which this holds are called cover-stable. We show that this is equivalent ... more >>> TR19-127 | 19th September 2019 Noga Ron-Zewi, Ron Rothblum #### Local Proofs Approaching the Witness Length Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits ... more >>> TR19-128 | 24th September 2019 Anna Gal, Robert Robere #### Lower Bounds for (Non-monotone) Comparator Circuits Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and ... more >>> TR19-129 | 27th September 2019 Zeev Dvir, Allen Liu #### Fourier and Circulant Matrices are Not Rigid The concept of matrix rigidity was first introduced by Valiant in [Val77]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed that rigidity can be used to prove ... more >>> TR19-130 | 26th September 2019 Naomi Kirshner, Alex Samorodnitsky #### A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres Let$p \ge 2$. We improve the bound$\frac{\|f\|_p}{\|f\|_2} \le (p-1)^{s/2}$for a polynomial$f$of degree$s$on the boolean cube$\{0,1\}^n$, which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of$p$and$s$, which is smaller than$(p-1)^{s/2}$for ... more >>> TR19-131 | 11th September 2019 Lieuwe Vinkhuijzen, André Deutz #### A Simple Proof of Vyalyi's Theorem and some Generalizations In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if$\text{QMA}=\text{PP}$then$\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using ... more >>> TR19-132 | 26th September 2019 Klim Efremenko, Gillat Kol, Raghuvansh Saxena #### Radio Network Coding Requires Logarithmic Overhead Revisions: 1 We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>> TR19-133 | 2nd October 2019 Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi #### More on$AC^0[\oplus]$and Variants of the Majority Function Revisions: 1 In this paper we prove two results about$AC^0[\oplus]$circuits. We show that for$d(N) = o(\sqrt{\log N/\log \log N})$and$N \leq s(N) \leq 2^{dN^{1/d^2}}$there is an explicit family of functions$\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$such that$f_N$has uniform$AC^0$formulas of depth$d$and size at ... more >>> TR19-134 | 4th October 2019 Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten #### Finding monotone patterns in sublinear time We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed$k \in \mathbb{N}$and$\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$monotone subsequence of$f \colon [n] \to \mathbb{R}$, assuming that$f$is$\varepsilon$-far ... more >>> TR19-135 | 2nd October 2019 Michel Goemans, Shafi Goldwasser, Dhiraj Holden #### Doubly-Efficient Pseudo-Deterministic Proofs In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>> TR19-136 | 23rd September 2019 Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar #### Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function$f : \{-1, 1\}^n \to \{-1, 1\}$and$\bullet : \{-1, 1\}^2 \to \{-1, 1\}$the two-party bounded-error quantum communication complexity of$(f \circ \bullet)$is$O(Q(f) \log n)$, where$Q(f)$is the bounded-error quantum query complexity of$f$. ... more >>> TR19-137 | 24th September 2019 Shachar Lovett, Kewen Wu, Jiapeng Zhang #### Decision list compression by mild random restrictions Revisions: 1 A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>> TR19-138 | 6th October 2019 Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh #### On the Probabilistic Degrees of Symmetric Boolean functions The probabilistic degree of a Boolean function$f:\{0,1\}^n\rightarrow \{0,1\}$is defined to be the smallest$d$such that there is a random polynomial$\mathbf{P}$of degree at most$d$that agrees with$f$at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>> TR19-139 | 8th October 2019 Irit Dinur, Konstantin Golubev #### Direct sum testing - the general case A function f:[n_1] x ... x [n_d]-->F is a direct sum if it is of the form f(a_1,...,a_d) = f_1(a_1) + ... + f_d (a_d) (mod 2) for some d functions f_i:[n_i]-->F_i for all i=1,...,d. We present a 4-query test which distinguishes between direct sums and functions that are ... more >>> TR19-140 | 7th October 2019 Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson #### Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. Revisions: 1 We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions). more >>> TR19-141 | 22nd October 2019 Mark Braverman, Subhash Khot, Dor Minzer #### On Rich$2$-to-$1$Games We propose a variant of the$2$-to-$1$Games Conjecture that we call the Rich$2$-to-$1$Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the$2$-to-$1$Games Conjecture, we hope to understand ... more >>> TR19-142 | 23rd October 2019 Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret #### Semi-Algebraic Proofs, IPS Lower Bounds and the$\tau$-Conjecture: Can a Natural Number be Negative? We introduce the binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>> TR19-143 | 25th October 2019 Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian #### Equivalence of Systematic Linear Data Structures and Matrix Rigidity Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an$NP$oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between ... more >>> TR19-144 | 29th October 2019 Young Ko, Omri Weinstein #### An Adaptive Step Toward the Multiphase Conjecture Revisions: 1 In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving$polynomial$lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make$n^\epsilon$cell-probes in either the update or query phase, ... more >>> TR19-145 | 31st October 2019 Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman #### XOR Lemmas for Resilient Functions Against Polynomials A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over$F_2$. We introduce a new technique to prove such correlation bounds with$F_2$polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>> TR19-146 | 31st October 2019 Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau #### Dynamic Kernels for Hitting Sets and Set Packing Computing kernels for the hitting set problem (the problem of finding a size-$k$set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with$m$hyperedges, each of size at most~$d$, the best algorithms can compute kernels of size$O(k^d)$in ... more >>> TR19-147 | 31st October 2019 Gil Cohen, Shahar Samocha #### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors Revisions: 2 , Comments: 1 We devise a deterministic interactive coding scheme with rate$1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$against$\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction$\varepsilon>0$of adversarial errors could obtain rate no larger ... more >>> TR19-148 | 1st November 2019 Amey Bhangale, Subhash Khot #### Simultaneous Max-Cut is harder to approximate than Max-Cut Revisions: 1 A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a$.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an ... more >>> TR19-149 | 4th November 2019 Dean Doron, Pooya Hatami, William Hoza #### Log-Seed Pseudorandom Generators via Iterated Restrictions There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length$\mathrm{polylog} n$or even$\tilde{O}(\log n)$for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>> TR19-150 | 24th October 2019 Stanislav Žák #### A Logical Characteristic of Read-Once Branching Programs We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties:\\ i) The "knowledge" arising at a stage of computation in question is derivable from the "knowledge" arising ... more >>> TR19-151 | 5th November 2019 Per Austrin, Jonah Brown-Cohen, Johan Håstad #### Optimal Inapproximability with Universal Factor Graphs The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many ... more >>> TR19-152 | 6th November 2019 Uma Girish, Ran Raz, Avishay Tal #### Quantum versus Randomized Communication Complexity, with Efficient Players We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean ... more >>> TR19-153 | 6th November 2019 Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi #### Optimally Resilient Codes for List-Decoding from Insertions and Deletions Revisions: 1 We give a complete answer to the following basic question: What is the maximal fraction of deletions or insertions tolerable by$q$-ary list-decodable codes with non-vanishing information rate?'' This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results ... more >>> TR19-154 | 6th November 2019 Venkatesan Guruswami, Andrii Riazanov, Min Ye #### Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity Revisions: 2 Let$W$be a binary-input memoryless symmetric (BMS) channel with Shannon capacity$I(W)$and fix any$\alpha > 0$. We construct, for any sufficiently small$\delta > 0$, binary linear codes of block length$O(1/\delta^{2+\alpha})$and rate$I(W)-\delta$that enable reliable communication on$W$with quasi-linear time encoding and decoding. ... more >>> TR19-155 | 6th November 2019 Rahul Santhanam #### Pseudorandomness and the Minimum Circuit Size Problem We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[$s$]), which asks whether a Boolean function on$n$bits specified by its truth table has circuits of size$s(n)$. 1. (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for ... more >>> TR19-156 | 7th November 2019 Nader Bshouty #### Almost Optimal Testers for Concise Representations We give improved and almost optimal testers for several classes of Boolean functions on$n$inputs that have concise representation in the uniform and distribution-free model. Classes, such as$k$-Junta,$k$-Linear Function,$s$-Term DNF,$s$-Term Monotone DNF,$r$-DNF, Decision List,$r$-Decision List, size-$s$Decision Tree, size-$s$Boolean Formula, size-$s$Branching ... more >>> TR19-157 | 25th September 2019 Leroy Chew, Judith Clymo #### How QBF Expansion Makes Strategy Extraction Hard In this paper we show that the QBF proof checking format QRAT (Quantified Resolution Asymmetric Tautologies) by Heule, Biere and Seidl cannot have polynomial-time strategy extraction unless P=PSPACE. In our proof, the crucial property that makes strategy extraction PSPACE-hard for this proof format is universal expansion, even expansion on a ... more >>> TR19-158 | 11th November 2019 Stasys Jukna, Hannes Seiwert #### Sorting Can Exponentially Speed Up Pure Dynamic Programming Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are pure'' in that they only perform basic operations, as$\min$,$\max$,$+$, but no conditional branchings via if-then-else in their recursion equations. It is known that any ... more >>> TR19-159 | 11th November 2019 Noah Stephens-Davidowitz, Vinod Vaikuntanathan #### SETH-hardness of Coding Problems We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, ... more >>> TR19-160 | 10th November 2019 Md Lutfar Rahman, Thomas Watson #### Tractable Unordered 3-CNF Games The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in ... more >>> TR19-161 | 13th November 2019 Suprovat Ghoshal, Rishi Saket #### Hardness of Learning DNFs using Halfspaces The problem of learning$t$-term DNF formulas (for$t = O(1)$) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A$t$-term DNF can be efficiently learnt using a$t$-term DNF only if$t = 1$i.e., when it is an AND, while even ... more >>> TR19-162 | 15th November 2019 Ran Raz, Wei Zhan #### The Random-Query Model and the Memory-Bounded Coupon Collector We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables$x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index$i \in \{1,\ldots,n\}$, together with the input variable$x_i$(rather than querying an ... more >>> TR19-163 | 16th November 2019 Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten #### Approximating the Distance to Monotonicity of Boolean Functions We design a nonadaptive algorithm that, given a Boolean function$f\colon \{0,1\}^n \to \{0,1\}$which is$\alpha$-far from monotone, makes poly$(n, 1/\alpha)$queries and returns an estimate that, with high probability, is an$\widetilde{O}(\sqrt{n})$-approximation to the distance of$f$to monotonicity. Furthermore, we show that for any constant$\kappa > ... more >>>

TR19-164 | 6th November 2019
Siddharth Bhandari, Sayantan Chakraborty

#### Improved bounds for perfect sampling of $k$-colorings in graphs

Revisions: 1

We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k > 3\Delta$, and returns a random proper $k$-coloring of $G$. The
distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; ... more >>>

TR19-165 | 18th November 2019
Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

#### Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... more >>>

TR19-166 | 20th November 2019
Guy Blanc, Jane Lange, Li-Yang Tan

#### Top-down induction of decision trees: rigorous guarantees and inherent limitations

Consider the following heuristic for building a decision tree for a function $f : \{0,1\}^n \to \{\pm 1\}$. Place the most influential variable $x_i$ of $f$ at the root, and recurse on the subfunctions $f_{x_i=0}$ and $f_{x_i=1}$ on the left and right subtrees respectively; terminate once the tree is an ... more >>>

TR19-167 | 21st November 2019
Anant Dhayal, Russell Impagliazzo

#### UTIME Easy-witness Lemma & Some Consequences

Revisions: 1

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... more >>>

TR19-168 | 20th November 2019
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

#### Beyond Natural Proofs: Hardness Magnification and Locality

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

TR19-169 | 21st November 2019
Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

#### On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Revisions: 1

The Exponential-Time Hypothesis ($ETH$) is a strengthening of the $\mathcal{P} \neq \mathcal{NP}$ conjecture, stating that $3\text{-}SAT$ on $n$ variables cannot be solved in time $2^{\epsilon\cdot n}$, for some $\epsilon>0$. In recent years, analogous hypotheses that are exponentially-strong'' forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq\mathcal{BPP}$ or $co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>>

TR19-170 | 27th November 2019
Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

#### A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>>

TR19-171 | 27th November 2019
Oded Goldreich

#### Improved bounds on the AN-complexity of multilinear functions

Revisions: 2

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.
This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ... more >>>

TR19-172 | 28th November 2019
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

#### Schur Polynomials do not have small formulas if the Determinant doesn't!

Schur Polynomials are families of symmetric polynomials that have been
classically studied in Combinatorics and Algebra alike. They play a central
role in the study of Symmetric functions, in Representation theory [Sta99], in
Schubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84,
Sta99]. In recent years, they have ... more >>>

TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

#### Extractor Lower Bounds, Revisited

Revisions: 1

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>

TR19-174 | 2nd December 2019
Susanna de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov

#### Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense ... more >>>

TR19-175 | 4th December 2019
Emanuele Viola

#### Matching Smolensky's correlation bound with majority

We show that there are degree-$d$ polynomials over $\mathbb{F}_{2}$ with
correlation $\Omega(d/\sqrt{n})$ with the majority function on $n$
bits. This matches the $O(d/\sqrt{n})$ bound by Smolensky.

more >>>

TR19-176 | 4th December 2019
Gal Arnon, Guy Rothblum

#### On Prover-Efficient Public-Coin Emulation of Interactive Proofs

Revisions: 1

A central question in the study of interactive proofs is the relationship between private-coin proofs, where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where the verifier's random coins are sent to the prover.

In this work, we study transformations ... more >>>

TR19-177 | 6th December 2019
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff

#### Pseudo-deterministic Streaming

A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, $\ell_2$ approximation, finding a nonzero entry in a vector (for turnstile algorithms) ... more >>>

TR19-178 | 5th December 2019
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

#### Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

We show that the size of any regular resolution refutation of Tseitin formula $T(G,c)$ based on a graph $G$ is at least $2^{\Omega(tw(G)/\log n)}$, where $n$ is the number of vertices in $G$ and $tw(G)$ is the treewidth of $G$. For constant degree graphs there is known upper bound $2^{O(tw(G))}$ ... more >>>

TR19-179 | 7th December 2019
Avishay Tal

#### Towards Optimal Separations between Quantum and Randomized Query Complexities

Revisions: 1

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. ... more >>>

TR19-180 | 6th December 2019
Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi

#### Covering Codes for Insertions and Deletions

Revisions: 1

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>>

TR19-181 | 9th December 2019
Michal Koucky, Vojtech Rodl, Navid Talebanfard

#### A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Revisions: 1

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. ... more >>>

TR19-182 | 9th December 2019
Zachary Remscrim

#### The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem

Revisions: 1

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language \$L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>

TR19-183 | 21st December 2019
Marshall Ball, Oded Goldreich, Tal Malkin

#### Randomness Extraction from Somewhat Dependent Sources

Revisions: 1

We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness.
Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions.
Going from the more restricted model ... more >>>

TR19-184 | 13th December 2019
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

#### Extractors for Adversarial Sources via Extremal Hypergraphs

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples ... more >>>

TR19-185 | 6th December 2019
Greg Bodwin, Ofer Grossman

#### Strategy-Stealing is Non-Constructive

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.
This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing ... more >>>

TR19-186 | 31st December 2019
Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

#### Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Revisions: 4

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

ISSN 1433-8092 | Imprint