Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2019:
All reports in year 2019:
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.

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-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-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-137 | 24th September 2019
Shachar Lovett, Kewen Wu, Jiapeng Zhang

#### Decision list compression by mild random restrictions

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-136 | 23rd September 2019

#### 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-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-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-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-132 | 26th September 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

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-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-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-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-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-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-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-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-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-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-122 | 13th September 2019
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters

#### LDPC Codes Achieve List-Decoding Capacity

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-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-120 | 11th September 2019
Or Meir

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

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-119 | 9th September 2019 Dean Doron, Amnon Ta-Shma, Roei Tell #### On Hitting-Set Generators for Polynomials that Vanish Rarely 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-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-117 | 4th September 2019 Silas Richelson, Sourya Roy #### Locally Testable Non-Malleable Codes 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-116 | 9th September 2019 Venkatesan Guruswami, Sai Sandeep ####$d$-to-$1$Hardness of Coloring$4$-colorable Graphs with$O(1)$colors 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-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-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-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-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-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-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-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-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-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 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-106 | 12th August 2019 Noah Fleming, Pravesh Kothari, Toniann Pitassi #### Semialgebraic Proofs and Efficient Algorithm Design Revisions: 1 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-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-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-103 | 7th August 2019 Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi #### Query-to-Communication Lifting Using Low-Discrepancy Gadgets 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-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-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-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-099 | 29th July 2019 Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman #### Nearly Optimal Pseudorandomness From Hardness 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-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-097 | 4th July 2019 Jacobo Toran, Florian Wörz #### Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space Comments: 1 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-096 | 23rd July 2019 Aditya Potukuchi #### 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-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-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-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-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-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-090 | 27th June 2019 Ronen Shaltiel, Swastik Kopparty, Jad Silbak #### Quasilinear time list-decodable codes for space bounded channels Revisions: 1 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-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-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-087 | 10th June 2019 Rohit Agrawal #### Coin Theorems and the Fourier Expansion 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-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-085 | 7th June 2019
Xuangui Huang, Emanuele Viola

Revisions: 1

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-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-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-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-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-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-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-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-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-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-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-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-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-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-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-070 | 14th May 2019 Alessandro Chiesa, Peter Manohar, Igor Shinkar #### On Local Testability in the Non-Signaling Setting 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-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-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-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-066 | 3rd May 2019 Thomas Watson #### A Lower Bound for Sampling Disjoint Sets Revisions: 1 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-065 | 1st May 2019 Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon #### Derandomization from Algebraic Hardness: Treading the Borders Revisions: 2 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-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-063 | 28th April 2019 Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay #### Efficient Black-Box Identity Testing for Free Group Algebra 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-062 | 18th April 2019 Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler #### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials 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-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-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-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-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-057 | 6th April 2019 Olaf Beyersdorff, Joshua Blinkhorn #### 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-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-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-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-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-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-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-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-049 | 2nd April 2019 Itay Berman, Iftach Haitner, Eliad Tsfadia #### A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments Revisions: 1 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-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-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-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-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-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-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-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-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-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-039 | 12th March 2019 Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee #### Planarity, Exclusivity, and Unambiguity Comments: 1 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-038 | 7th March 2019 Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Nalini 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-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-036 | 5th March 2019
Pavel Hrubes

#### On the complexity of computing a random Boolean function over the reals

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-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-034 | 5th March 2019
Pavel Hrubes

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-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-032 | 4th March 2019 Srikanth Srinivasan #### Strongly Exponential Separation Between Monotone VP and Monotone VNP 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-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-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-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-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-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-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-025 | 28th February 2019
Shuichi Hirahara, Osamu Watanabe

#### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

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-024 | 20th February 2019
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

#### The Surprising Power of Constant Depth Algebraic Proofs

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-023 | 25th February 2019

#### Smooth and Strong PCPs

Revisions: 1

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-022 | 23rd February 2019
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

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-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-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-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-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-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-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-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-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-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-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-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-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-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-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-007 | 17th January 2019 Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh #### 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-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-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-004 | 11th January 2019 Amey Bhangale, Subhash Khot #### UG-hardness to NP-hardness by Losing Half 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-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-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-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 >>>

ISSN 1433-8092 | Imprint