Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2020:
All reports in year 2020:
TR20-175 | 24th November 2020
Emanuele Viola

#### Fourier conjectures, correlation bounds, and Majority

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results ... more >>>

TR20-174 | 18th November 2020

#### Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... more >>>

TR20-173 | 18th November 2020
Kunal Mittal, Ran Raz

#### Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>

TR20-172 | 13th November 2020
Venkatesan Guruswami, Chaoping Xing

#### Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

TR20-171 | 12th November 2020
Russell Impagliazzo, Sam McGuire

#### Comparing computational entropies below majority (or: When is the dense model theorem false?)

Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy ... more >>>

TR20-170 | 9th November 2020
Max Hopkins, Tali Kaufman, Shachar Lovett

#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>

TR20-169 | 11th November 2020
Zeyu Guo, Noga Ron-Zewi

#### Efficient List-Decoding with Constant Alphabet and List Sizes

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size ... more >>>

TR20-168 | 11th November 2020
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

#### Improved List-Decodability of Reed–Solomon Codes via Tree Packings

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>

TR20-167 | 9th November 2020
Venkatesan Guruswami, Sai Sandeep

#### Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

TR20-166 | 9th November 2020

#### Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>

TR20-165 | 6th November 2020

#### Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Revisions: 1

In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal C, \mathcal P, D)$ is a vector space associated to evaluations on $\mathcal P$ of functions in the Riemann-Roch space $L_\mathcal C(D)$. The problem of testing proximity to an ... more >>>

TR20-164 | 9th November 2020
Andrej Bogdanov, Gautam Prakriya

#### Direct Sum and Partitionability Testing over General Groups

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>

TR20-163 | 5th November 2020
Gil Cohen, Noam Peri, Amnon Ta-Shma

#### Expander Random Walks: A Fourier-Analytic Approach

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

TR20-162 | 7th November 2020
Dean Doron, Mary Wootters

Revisions: 1

An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j ... more >>> TR20-161 | 5th November 2020 Gil Cohen, Dean Doron, Shahar Samocha #### Seed Protecting Extractors We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions$C$, mappings seeds to seeds, if the seed$Y$remains close to uniform even after observing the output$\mathrm{Ext}(X,A(Y))$for every choice of$A \in ... more >>>

TR20-160 | 2nd November 2020
Oded Goldreich, Avi Wigderson

Revisions: 1

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.
It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.
We show that ... more >>>

TR20-159 | 9th October 2020
Leroy Chew, Marijn Heule

#### Relating existing powerful proof systems for QBF

We advance the theory of QBF proof systems by showing the first simulation of the universal checking format QRAT by a theory-friendly system. We show that the sequent system G fully p-simulates QRAT, including the Extended Universal Reduction (EUR) rule which was recently used to show QRAT does not ... more >>>

TR20-158 | 26th October 2020
Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

#### A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>

TR20-157 | 21st October 2020
Guy Rothblum, Ron Rothblum

#### Batch Verification and Proofs of Proximity with Polylog Overhead

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

TR20-156 | 22nd October 2020
Sankeerth Rao Karingula, Shachar Lovett

#### Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

TR20-155 | 18th October 2020
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

#### Log-rank and lifting for AND-functions

Revisions: 1

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is ... more >>>

TR20-154 | 10th October 2020
Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>> TR20-153 | 6th October 2020 Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou #### Total Functions in the Polynomial Hierarchy We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>> TR20-152 | 7th October 2020 Prasad Chaugule, Nutan Limaye, Shourya Pandey #### Variants of the Determinant polynomial and VP-completeness The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call$StackDet_n(X)$and$CountDet_n(X)$and show that they are VP and VNP complete respectively under$p$-projections. The definitions of the polynomials are inspired by a ... more >>> TR20-151 | 8th October 2020 Venkatesan Guruswami, Vinayak Kumar #### Pseudobinomiality of the Sticky Random Walk Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number$M$of marked vertices visited in a long$n$-step random walk strongly concentrates around the ... more >>> TR20-150 | 7th October 2020 Lijie Chen, Xin Lyu, Ryan Williams #### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether$\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>> TR20-149 | 29th September 2020 Oded Goldreich, Avi Wigderson #### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing Revisions: 2 A graph$G$is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from$G$to any graph that is isomorphic to$G$. We say that$G=(V,E)$is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>> TR20-148 | 28th September 2020 Lijie Chen, Roei Tell #### Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost Extending the classical hardness-to-randomness'' line-of-works, Doron et al. (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in$\mathcal{DTIME}[2^n]$that cannot be computed by randomized SVN circuits of size$2^{(1-\epsilon)\cdot n}$for a small$\epsilon$. In this work we ... more >>> TR20-147 | 24th September 2020 Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon #### Batch Verification for Statistical Zero Knowledge Proofs Revisions: 1 A statistical zero-knowledge proof (SZK) for a problem$\Pi$enables a computationally unbounded prover to convince a polynomial-time verifier that$x \in \Pi$without revealing any additional information about$x$to the verifier, in a strong information-theoretic sense. Suppose, however, that the prover wishes to convince the verifier that$k$... more >>> TR20-146 | 24th September 2020 Scott Aaronson, Yosi Atia, Leonard Susskind #### On the Hardness of Detecting Macroscopic Superpositions When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two orthogonal states (for example, the$|$Alive$\rangle$and$|$Dead$\rangle$... more >>> TR20-145 | 23rd September 2020 Andrew Drucker #### An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature "Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some$[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing ... more >>> TR20-144 | 7th September 2020 Mohammad Jahanara, Sajin Koroth, Igor Shinkar #### Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>> TR20-143 | 16th September 2020 Shuichi Hirahara #### Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence: DistPH is contained in ... more >>> TR20-142 | 15th September 2020 Vahid Reza Asadi, Igor Shinkar #### Relaxed Locally Correctable Codes with Improved Parameters Locally decodable codes (LDCs) are error-correcting codes$C : \Sigma^k \to \Sigma^n$that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>> TR20-141 | 11th September 2020 Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan #### Candidate Tree Codes via Pascal Determinant Cubes Tree codes are combinatorial structures introduced by Schulman (STOC 1993) as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining ... more >>> TR20-140 | 14th September 2020 Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price #### Optimal Testing of Discrete Distributions with High Probability We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property$\mathcal{P}$, and parameters$0< \epsilon, \delta <1$, we want to distinguish {\em with probability at least$1-\delta$} whether these distributions satisfy$\mathcal{P}$... more >>> TR20-139 | 11th September 2020 Mark Braverman, Sumegha Garg, David Woodruff #### The Coin Problem with Applications to Data Streams Consider the problem of computing the majority of a stream of$n$i.i.d. uniformly random bits. This problem, known as the {\it coin problem}, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant ... more >>> TR20-138 | 9th September 2020 William Hoza, Edward Pyne, Salil Vadhan #### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of$\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here,$n$is the length of the ... more >>> TR20-137 | 11th September 2020 Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena #### Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors ... more >>> TR20-136 | 11th September 2020 Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani #### Explicit and structured sum of squares lower bounds from high dimensional expanders We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time. Our construction is based on the high-dimensional expanders devised by Lubotzky, ... more >>> TR20-135 | 9th September 2020 Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen #### Estimation of Graph Isomorphism Distance in the Query World The graph isomorphism distance between two graphs$G_u$and$G_k$is the fraction of entries in the adjacency matrix that has to be changed to make$G_u$isomorphic to$G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>> TR20-134 | 9th September 2020 Siddhesh Chaubal, Anna Gal #### Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. Until a recent breakthrough of Huang, the conjecture had been wide open in the general case, and was proved only for a few special classes of Boolean functions. Huang's result implies that block ... more >>> TR20-133 | 8th September 2020 Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma #### Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists) A binary code$\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$is$(\frac{1}{2}-\varepsilon,L)$-list decodable if for every$w \in \{0,1\}^n$, there exists a set$\text{List}(w)$of size at most$L$, containing all messages$m \in \{0,1\}^k$such that the relative Hamming distance between$\text{Enc}(m)$and$w$is at most$\frac{1}{2}-\varepsilon$. A$q$-query local list-decoder is ... more >>> TR20-132 | 7th September 2020 Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif #### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on$n$input bits, each of which has approximate Fourier sparsity at most$O(n^3)$and randomized parity decision tree complexity$\Theta(n)$. This improves upon the ... more >>> TR20-131 | 20th August 2020 Rahul Jain, Srijita Kundu #### A Direct Product Theorem for One-Way Quantum Communication We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation$f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any$\varepsilon, \zeta > 0$and any$k\geq1$, we show that $\mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),$ where$\mathrm{Q}^1_{\varepsilon}(f)$represents the one-way entanglement-assisted quantum communication complexity of$f$with ... more >>> TR20-130 | 30th August 2020 Amey Bhangale, Subhash Khot #### Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies$\frac{1}{|G|}+\varepsilon$fraction of the constraints of a given$k$-LIN instance over an abelian group, even if there is an assignment that satisfies$(1-\varepsilon)$fraction of the constraints, for any constant ... more >>> TR20-129 | 5th September 2020 Mrinal Kumar, Ben Lee Volk #### A Lower Bound on Determinantal Complexity The determinantal complexity of a polynomial$P \in \mathbb{F}[x_1, \ldots, x_n]$over a field$\mathbb{F}$is the dimension of the smallest matrix$M$whose entries are affine functions in$\mathbb{F}[x_1, \ldots, x_n]$such that$P = Det(M)$. We prove that the determinantal complexity of the polynomial$\sum_{i = 1}^n x_i^n$... more >>> TR20-128 | 3rd September 2020 Alexander A. Sherstov, Andrey Storozhenko, Pei Wu #### An Optimal Separation of Randomized and Quantum Query Complexity Revisions: 1 We prove that for every decision tree, the absolute values of the Fourier coefficients of given order$\ell\geq1$sum to at most$c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$where$n$is the number of variables,$d$is the tree depth, and$c>0$is an absolute constant. This bound is essentially tight and settles a ... more >>> TR20-127 | 21st August 2020 Nikhil Bansal, Makrand Sinha ####$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity Revisions: 2 Aaronson and Ambainis (SICOMP '18) showed that any partial function on$N$bits that can be computed with an advantage$\delta$over a random guess by making$q$quantum queries, can also be computed classically with an advantage$\delta/2$by a randomized decision tree making${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$queries. Moreover, they conjectured ... more >>> TR20-126 | 19th August 2020 Aayush Jain, Huijia Lin, Amit Sahai #### Indistinguishability Obfuscation from Well-Founded Assumptions In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Let$\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$be arbitrary constants. Assume sub-exponential security of the following assumptions, where$\lambda$is a security parameter, and the parameters$\ell,k,n$below ... more >>> TR20-125 | 17th August 2020 Gaurav Sinha #### Efficient reconstruction of depth three circuits with top fan-in two In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree$2$. Such circuits naturally compute polynomials of the form$G\times(T_1 + T_2)$, ... more >>> TR20-124 | 3rd August 2020 Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu #### A Strong XOR Lemma for Randomized Query Complexity We give a strong direct sum theorem for computing$XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of$k$instances of$g$satisfies$\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody. As a ... more >>> TR20-123 | 17th August 2020 Nader Bshouty #### An Optimal Tester for k-Linear A Boolean function$f:\{0,1\}^n\to \{0,1\}$is$k$-linear if it returns the sum (over the binary field$F_2$) of$k$coordinates of the input. In this paper, we study property testing of the classes$k$-Linear, the class of all$k$-linear functions, and$k$-Linear$^*$, the class$\cup_{j=0}^kj$-Linear. We give a non-adaptive distribution-free ... more >>> TR20-122 | 8th August 2020 Joshua Cook #### Size Bounds on Low Depth Circuits for Promise Majority Revisions: 3 We give two results on the size of AC0 circuits computing promise majority.$\epsilon$-promise majority is majority promised that either at most an$\epsilon$fraction of the input bits are 1, or at most$\epsilon$are 0. First, we show super quadratic lower bounds on both monotone and general depth ... more >>> TR20-121 | 3rd August 2020 Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty #### Fractional Pseudorandom Generators from the$k$th Fourier Level Revisions: 2 In recent work by Chattopadhyay et al.[CHHL19,CHLT19], the authors exhibit a simple and flexible construction of pseudorandom generators for classes of Boolean functions that satisfy$L_1$Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG whose seed length depends on ... more >>> TR20-120 | 12th August 2020 Justin Holmgren, Ran Raz #### A Parallel Repetition Theorem for the GHZ Game We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel$t$times is at most$t^{-\Omega(1)}$. Previously, only a bound of$\approx \frac{1}{\alpha(t)}$, where$\alpha$is the inverse Ackermann ... more >>> TR20-119 | 1st August 2020 Nikhil Mande, Swagato Sanyal #### On parity decision trees for Fourier-sparse Boolean functions We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let$f : \mathbb{F}_2^n \to \{-1, 1\}$be a Boolean function with Fourier support ... more >>> TR20-118 | 5th August 2020 Oded Goldreich #### On Testing Asymmetry in the Bounded Degree Graph Model We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of$n$-vertex graphs with connected components ... more >>> TR20-117 | 4th August 2020 Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov #### New bounds on the half-duplex communication complexity In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>> TR20-116 | 1st August 2020 Ivan Mihajlin, Alexander Smal #### Toward better depth lower bounds: the XOR-KRW conjecture In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply$\mathbf{P} \not\subseteq \mathbf{NC}^1$if proven. We also present a weaker version of this conjecture that might be used for breaking$n^3$lower ... more >>> TR20-115 | 1st August 2020 Scott Aaronson #### The Busy Beaver Frontier The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: ... more >>> TR20-114 | 22nd July 2020 Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar #### Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond The disjointness problem - where Alice and Bob are given two subsets of$\{1, \dots, n\}$and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>> TR20-113 | 27th July 2020 Alessandro Chiesa, Tom Gur, Igor Shinkar #### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>> TR20-112 | 8th June 2020 Joshua Blinkhorn #### Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies Dependency quantified Boolean formulas (DQBF) describe an NEXPTIME-complete generalisation of QBF, which in turn generalises SAT. QRAT is a recently proposed proof system for quantified Boolean formulas (QBF), which simulates the full suite of QBF preprocessing techniques and thus forms a uniform proof checking format for solver verification. In this ... more >>> TR20-111 | 24th July 2020 Ian Mertz, Toniann Pitassi #### Lifting: As Easy As 1,2,3 Revisions: 1 Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>> TR20-110 | 22nd July 2020 Leonid Gurvits, Jonathan Leake #### Capacity Lower Bounds via Productization Revisions: 1 The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial$p(x)$which is based only on its value and gradient at$x=1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities ... more >>> TR20-109 | 19th July 2020 Oded Goldreich #### On Testing Hamiltonicity in the Bounded Degree Graph Model We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues. In addition, we present an alternative proof for the known fact that ... more >>> TR20-108 | 19th July 2020 Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar #### Query Complexity of Global Minimum Cut Revisions: 1 In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like \textsc{Degree}, \textsc{Neighbor}, and \textsc{Adjacency} queries. Given$\epsilon \in (0,1)$, ... more >>> TR20-107 | 19th July 2020 Lior Gishboliner, Asaf Shapira, Henrique Stagni #### Testing linear inequalities of subgraph statistics Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property${\cal P}$and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be ... more >>> TR20-106 | 15th July 2020 Eshan Chattopadhyay, Jesse Goodman #### Explicit Extremal Designs and Applications to Extractors Revisions: 4 An$(n,r,s)$-design, or$(n,r,s)$-partial Steiner system, is an$r$-uniform hypergraph over$n$vertices with pairwise hyperedge intersections of size$0$, we extract from$(N,K,n,k)$-adversarial sources of locality$0$, where$K\geq N^\delta$and$k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required$K\geq N^{1/2+o(1)}$. As a result, we ... more >>> TR20-105 | 14th July 2020 Zoë Bell #### Automating Regular or Ordered Resolution is NP-Hard We show that is hard to find regular or even ordered (also known as Davis-Putnam) Resolution proofs, extending the breakthrough result for general Resolution from Atserias and Müller to these restricted forms. Namely, regular and ordered Resolution are automatable if and only if P = NP. Specifically, for a CNF ... more >>> TR20-104 | 12th July 2020 Oded Goldreich #### On Counting$t$-Cliques Mod 2 Revisions: 3 For a constant integer$t$, we consider the problem of counting the number of$t$-cliques$\bmod 2$in a given graph. We show that this problem is not easier than determining whether a given graph contains a$t$-clique, and present a simple worst-case to average-case reduction for it. The ... more >>> TR20-103 | 9th July 2020 Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida #### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP Revisions: 1 For a size parameter$s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function$f \colon \{0,1\}^n \to \{0,1\}$(represented by a string of length$N := 2^n$) is at most a threshold$s(n)$. A ... more >>> TR20-102 | 9th July 2020 Stasys Jukna #### Notes on Hazard-Free Circuits Revisions: 1 The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function$f(x)$is lower-bounded by the ... more >>> TR20-101 | 7th July 2020 Uma Girish, Ran Raz, Wei Zhan #### Lower Bounds for XOR of Forrelations The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between ... more >>> TR20-100 | 6th July 2020 Amit Chakrabarti, Prantar Ghosh, Justin Thaler #### Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that ... more >>> TR20-099 | 6th July 2020 Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere #### KRW Composition Theorems via Lifting 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), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions$f ... more >>>

TR20-098 | 4th July 2020
Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

#### Impossibility of Derandomizing the Isolation Lemma for all Families

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

TR20-097 | 30th June 2020
Md Lutfar Rahman, Thomas Watson

#### 6-Uniform Maker-Breaker Game Is PSPACE-Complete

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains ... more >>>

TR20-096 | 22nd June 2020
Igor Sergeev

#### On the asymptotic complexity of sorting

We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group ... more >>>

TR20-095 | 24th June 2020
Mikito Nanashima

#### On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions

A black-box (BB) reduction is a central proof technique in theoretical computer science. However, the limitations on BB reductions have been revealed for several decades, and the series of previous work gives strong evidence that we should avoid a nonadaptive BB reduction to base cryptography on NP-hardness (e.g., Akavia et ... more >>>

TR20-094 | 24th June 2020
Ronen Shaltiel

#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>

TR20-093 | 23rd June 2020
Ronen Eldan, Dana Moshkovitz

#### Reduction From Non-Unique Games To Boolean Unique Games

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.
In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., ... more >>>

TR20-092 | 16th June 2020
Ashish Dwivedi, Nitin Saxena

#### Computing Igusa's local zeta function of univariates in deterministic polynomial-time

Igusa's local zeta function $Z_{f,p}(s)$ is the generating function that counts the number of integral roots, $N_{k}(f)$, of $f(\mathbf x) \bmod p^k$, for all $k$. It is a famous result, in analytic number theory, that $Z_{f,p}$ is a rational function in $\mathbb{Q}(p^s)$. We give an elementary proof of this fact ... more >>>

TR20-091 | 14th June 2020
Janaky Murthy, vineet nair, Chandan Saha

Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that $f(\mathbb{x}) ... more >>> TR20-090 | 10th June 2020 Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian #### Tight Quantum Time-Space Tradeoffs for Function Inversion Revisions: 1 In function inversion, we are given a function$f: [N] \mapsto [N]$, and want to prepare some advice of size$S$, such that we can efficiently invert any image in time$T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>> TR20-089 | 8th June 2020 Dror Chawin, Iftach Haitner, Noam Mazor #### Lower Bounds on the Time/Memory Tradeoff of Function Inversion Revisions: 1 We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an$s$-bit advice for a randomly chosen function$f\colon [n] \mapsto [n]$and using$q$oracle queries to$f$, tries to invert a randomly chosen output$y$of$f$(i.e., to find$x$such that$f(x)=y$). ... more >>> TR20-088 | 9th June 2020 Bill Fefferman, Zachary Remscrim #### Eliminating Intermediate Measurements in Space-Bounded Quantum Computation A foundational result in the theory of quantum computation known as the principle of safe storage'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that ... more >>> TR20-087 | 8th June 2020 Uma Girish, Ran Raz, Wei Zhan #### Quantum Logspace Algorithm for Powering Matrices with Bounded Norm Revisions: 1 We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary$n\times n$contraction matrix$A$, and a parameter$T \leq poly(n)$and outputs the entries of$A^T$, up to (arbitrary) polynomially small additive ... more >>> TR20-086 | 5th June 2020 Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi #### A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions. more >>> TR20-085 | 5th June 2020 Gal Vardi, Ohad Shamir #### Neural Networks with Small Weights and Depth-Separation Barriers In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths$2$and$3$, and achieving results for higher depths has been ... more >>> TR20-084 | 31st May 2020 Gil Cohen, Tal Yankovitz #### Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good$n$-bit locally decodable codes (LDC) with$2^{\widetilde{O}(\sqrt{\log{n}})}$queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance$\delta$of a code to a constant at ... more >>> TR20-083 | 30th May 2020 Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf #### Proximity Gaps for Reed-Solomon Codes Revisions: 1 A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are$\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are$\delta$-close to the property. In particular, no set ... more >>> TR20-082 | 23rd May 2020 Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals #### MaxSAT Resolution and Subcube Sums Revisions: 1 We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>> TR20-081 | 21st May 2020 Robert Andrews #### Algebraic Hardness versus Randomness in Low Characteristic We show that lower bounds for explicit constant-variate polynomials over fields of characteristic$p > 0$are sufficient to derandomize polynomial identity testing over fields of characteristic$p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the ... more >>> TR20-080 | 19th May 2020 Joan Bruna, Oded Regev, Min Jae Song, Yi Tang #### Continuous LWE Revisions: 1 We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues ... more >>> TR20-079 | 15th May 2020 Hermann Gruber , Markus Holzer, Simon Wolfsteiner #### On Minimizing Regular Expressions Without Kleene Star Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>> TR20-078 | 21st May 2020 Eric Allender #### The New Complexity Landscape around Circuit Minimization We survey recent developments related to the Minimum Circuit Size Problem more >>> TR20-077 | 19th May 2020 Amit Sinhababu, Thomas Thierauf #### Factorization of Polynomials Given by Arithmetic Branching Programs Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size$s$, we show that all its factors can be computed by arithmetic branching programs of size$\text{poly}(s)$. Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was ... more >>> TR20-076 | 17th May 2020 Benny Applebaum, Eliran Kachlon, Arpita Patra #### The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to$n/3$of ... more >>> TR20-075 | 6th May 2020 Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal #### Rigid Matrices From Rectangular PCPs Revisions: 2 We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*. We ... more >>> TR20-074 | 6th May 2020 Eric Allender, Archit Chauhan, Samir Datta #### Depth-First Search in Directed Graphs, Revisited We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm ... more >>> TR20-073 | 5th May 2020 Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov #### Lower Bounds on OBDD Proofs with Several Orders This paper is motivated by seeking lower bounds on OBDD($\land$, weakening, reordering) refutations, namely OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1-NBP($\land$) refutations based on read-once nondeterministic branching programs. These generalize OBDD($\land$, reordering) refutations. There are polynomial size 1-NBP($\land$) refutations of the pigeonhole principle, hence ... more >>> TR20-072 | 5th May 2020 Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi #### Locally testable codes via high-dimensional expanders Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. ... more >>> TR20-071 | 4th May 2020 Iftach Haitner, Yonatan Karidi-Heller #### A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip Revisions: 1 In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate ... more >>> TR20-070 | 4th May 2020 Ben Lund, Aditya Potukuchi #### On the list recoverability of randomly punctured codes Revisions: 1 We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this ... more >>> TR20-069 | 4th May 2020 Eshan Chattopadhyay, Jyun-Jie Liao #### Optimal Error Pseudodistributions for Read-Once Branching Programs Revisions: 1 In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length$n$and width$w$read-once branching programs with seed length$O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$and error$\varepsilon$. It remains a central question to reduce the seed length to$O(\log (nw/\varepsilon))$, which would prove that$\mathbf{BPL}=\mathbf{L}$. However, there has ... more >>> TR20-068 | 3rd May 2020 Oded Goldreich, Dana Ron #### One-Sided Error Testing of Monomials and Affine Subspaces Revisions: 1 We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results: \begin{itemize} \item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ... more >>> TR20-067 | 30th April 2020 Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin #### Computational and proof complexity of partial string avoidability The partial string avoidability problem is stated as follows: given a finite set of strings with possible holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>> TR20-066 | 28th April 2020 Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal #### Quantum Implications of Huang's Sensitivity Theorem Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function$f$, the deterministic query complexity,$D(f)$, is at most quartic in the quantum query complexity,$Q(f)$:$D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... more >>> TR20-065 | 2nd May 2020 Lijie Chen, Ce Jin, Ryan Williams #### Sharp Threshold Results for Computational Complexity We establish several sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of$n^c$for$c \geq 1$(or obtain an efficient circuit-analysis algorithm for$n^c$size), there is strong intuition that a similar result can be proved for larger functions of$n$, ... more >>> TR20-064 | 2nd May 2020 Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende #### Automating Algebraic Proof Systems is NP-Hard Revisions: 1 We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula$F$, it is NP-hard to find a refutation of$F$in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a ... more >>> TR20-063 | 29th April 2020 Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse #### On the Existence of Algebraically Natural Proofs For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties: * For every family {f_n} of polynomials in VP, where f_n is an n ... more >>> TR20-062 | 29th April 2020 Clement Canonne, Karl Wimmer #### Testing Data Binnings Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model)$\mathbf{q}$and samples from an unknown distribution$\mathbf{p}$, both ... more >>> TR20-061 | 28th April 2020 Deepanshu Kush, Benjamin Rossman #### Tree-depth and the Formula Complexity of Subgraph Isomorphism For a fixed "pattern" graph$G$, the$\textit{colored}G\textit{-subgraph isomorphism problem}$(denoted$\mathrm{SUB}(G)$) asks, given an$n$-vertex graph$H$and a coloring$V(H) \to V(G)$, whether$H$contains a properly colored copy of$G$. The complexity of this problem is tied to parameterized versions of$\mathit{P}{=}?\mathit{NP}$and$\mathit{L}$... more >>> TR20-060 | 23rd April 2020 Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li #### Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which$N$parties wish to compute some joint function$f:(\{0,1\}^n)^N\to\{0,1\}$using a public blackboard, but such that only$p$parties may collude at a time. This generalizes well studied models in ... more >>> TR20-059 | 16th April 2020 Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma #### Pr-ZSUBEXP is not contained in Pr-RP Revisions: 1 We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP. The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ... more >>> TR20-058 | 24th April 2020 Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff #### Interactive Proofs for Verifying Machine Learning We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>> TR20-057 | 20th April 2020 Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein #### Polynomial Data Structure Lower Bounds in the Group Model Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of$n^3$convex polygons in$\R^2$(each with$n^{\tilde{O}(1)}$facets/semialgebraic-complexity), against linear storage arithmetic ... more >>> TR20-056 | 17th April 2020 James Cook, Ian Mertz #### Catalytic Approaches to the Tree Evaluation Problem The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in$[k]$at each leaf of a complete binary tree and an explicit function in$[k]^2 \to ... more >>>

TR20-055 | 22nd April 2020
Ashutosh Kumar, Raghu Meka, David Zuckerman

#### Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>

TR20-054 | 22nd April 2020
Marshall Ball, Oded Goldreich, Tal Malkin

#### Communication Complexity with Defective Randomness

Revisions: 2

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ... more >>>

TR20-053 | 16th April 2020
Olaf Beyersdorff, Benjamin Böhm

#### Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution

QBF solvers implementing the QCDCL paradigm are powerful algorithms that
successfully tackle many computationally complex applications. However, our
theoretical understanding of the strength and limitations of these QCDCL
solvers is very limited.

In this paper we suggest to formally model QCDCL solvers as proof systems. We
define different policies that ... more >>>

TR20-052 | 14th April 2020
Yanyi Liu, Rafael Pass

#### On One-way Functions and Kolmogorov Complexity

Revisions: 2

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: ... more >>>

TR20-051 | 15th April 2020
Rafael Pass, Muthuramakrishnan Venkitasubramaniam

#### Is it Easier to Prove Theorems that are Guaranteed to be True?

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in $\NP$ imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that ... more >>>

TR20-050 | 18th April 2020
Shuichi Hirahara

#### Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing ... more >>>

TR20-049 | 17th April 2020
Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

#### Automating Cutting Planes is NP-Hard

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$,

(1) it is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and

(2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a ... more >>>

TR20-048 | 16th April 2020
Shachar Lovett, Raghu Meka, Jiapeng Zhang

#### Improved lifting theorems via robust sunflowers

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

TR20-047 | 16th April 2020

#### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity

Revisions: 2

We consider codes for space bounded channels. This is a model for communication under noise that was introduced 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 >>>

TR20-046 | 13th April 2020
Srikanth Srinivasan

#### A Robust Version of Heged\H{u}s's Lemma, with Applications

Heged\H{u}s's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field $\mathbb{F}$ of characteristic $p > 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of ... more >>>

TR20-045 | 15th April 2020
Ankit Garg, Neeraj Kayal, Chandan Saha

#### Learning sums of powers of low-degree polynomials in the non-degenerate case

Revisions: 1

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as
$$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$
where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = ... more >>> TR20-044 | 8th April 2020 Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan #### Cryptography from Information Loss Revisions: 1 Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is lossy'' reductions, where the reduction loses some information about the input ... more >>> TR20-043 | 29th March 2020 Dorit Aharonov, Alex Bredariol Grilo #### A combinatorial MA-complete problem Revisions: 2 Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>> TR20-042 | 31st March 2020 Pranav Bisht, Nitin Saxena #### Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox ... more >>> TR20-041 | 29th March 2020 Mrinal Kumar, Ben Lee Volk #### A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits Revisions: 2 We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field$\mathbb{F}$, there is a non-zero$n^2$-variate polynomial$P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$of degree ... more >>> TR20-040 | 25th March 2020 Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny #### Topology and adjunction in promise constraint satisfaction Revisions: 1 The approximate graph colouring problem concerns colouring a$k$-colourable graph with$c$colours, where$c\geq k$. This problem naturally generalises to promise graph homomorphism and further to promise constraint satisfaction problems. Complexity analysis of all these problems is notoriously difficult. In this paper, we introduce ... more >>> TR20-039 | 25th March 2020 Pranjal Dutta, Nitin Saxena, Thomas Thierauf #### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT We consider the univariate polynomial$f_d:=(x+1)^d$when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is$\Omega(d)$for$f_d$. We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>> TR20-038 | 15th March 2020 Ofer Grossman, Justin Holmgren #### Error Correcting Codes for Uncompressed Messages Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed. We ... more >>> TR20-037 | 18th March 2020 Michal Garlik #### Failure of Feasible Disjunction Property for$k$-DNF Resolution and NP-hardness of Automating It We show that for every integer$k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then ... more >>> TR20-036 | 9th March 2020 Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl #### Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new tautology-free DQBF dependency scheme that generalises the reflexive resolution path dependency scheme. We establish soundness of the tautology-free scheme, implying that it can be used in any ... more >>> TR20-035 | 23rd February 2020 Justin Holmgren #### No-Signaling MIPs and Faster-Than-Light Communication, Revisited We revisit one original motivation for the study of no-signaling multi-prover interactive proofs (NS-MIPs): specifically, that two spatially separated provers are guaranteed to be no-signaling by the physical principle that information cannot travel from one point to another faster than light. We observe that with ... more >>> TR20-034 | 12th March 2020 Erfan Khaniki #### On Proof complexity of Resolution over Polynomial Calculus Revisions: 1 The refutation system${Res}_R({PC}_d)$is a natural extension of resolution refutation system such that it operates with disjunctions of degree$d$polynomials over ring$R$with boolean variables. For$d=1$, this system is called${Res}_R({lin})$. Based on properties of$R$,${Res}_R({lin})$systems can be too strong to prove lower ... more >>> TR20-033 | 12th March 2020 Suryajith Chillara #### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree Revisions: 1 Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers$n$and$d$such that$d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree$\delta = o(d)$that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size$n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>> TR20-032 | 12th March 2020 Suryajith Chillara #### On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits Revisions: 2 In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of$r$(referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>> TR20-031 | 10th March 2020 Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh #### Algebraic Branching Programs, Border Complexity, and Tangent Spaces Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most$k$is Zariski-closed, an important property in ... more >>> TR20-030 | 9th March 2020 Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam #### Barriers for Rectangular Matrix Multiplication We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>> TR20-029 | 6th March 2020 Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam #### Geometric Rank of Tensors and Subrank of Matrix Multiplication Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the ... more >>> TR20-028 | 27th February 2020 Nikhil Gupta, Chandan Saha, Bhargav Thankey #### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits We show an$\widetilde{\Omega}(n^{2.5})$lower bound for general depth four arithmetic circuits computing an explicit$n$-variate degree$\Theta(n)$multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>> TR20-027 | 26th February 2020 Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan #### The Power of Many Samples in Query Complexity The randomized query complexity$R(f)$of a boolean function$f\colon\{0,1\}^n\to\{0,1\}$is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution$D_0$over$0$-inputs from a distribution$D_1$over$1$-inputs, maximized over all pairs$(D_0,D_1)$. We ask: Does this task become easier if we ... more >>> TR20-026 | 25th February 2020 Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman #### Spectral Sparsification via Bounded-Independence Sampling Revisions: 1 We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph$G$on$n$vertices described by a binary string of length$N$, an integer$k\leq \log n$and an error parameter$\varepsilon > 0$, our algorithm runs in space$\tilde{O}(k\log (N\cdot ... more >>>

TR20-025 | 20th February 2020
Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

#### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.

As a consequence, we obtain that deciding whether the ... more >>>

TR20-024 | 20th February 2020
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

#### Randomized and Symmetric Catalytic Computation

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

TR20-023 | 10th February 2020
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

#### Non-Malleability against Polynomial Tampering

Revisions: 1

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

TR20-022 | 19th February 2020
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

#### Interactive Error Resilience Beyond $\frac{2}{7}$

Revisions: 1

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?

For the non-adaptive channel, where the parties must agree ... more >>>

TR20-021 | 21st February 2020
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

#### NP-Hardness of Circuit Minimization for Multi-Output Functions

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

TR20-020 | 21st February 2020
Nikhil Mande, Justin Thaler, Shuchen Zhu

#### Improved Approximate Degree Bounds For $k$-distinctness

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

TR20-019 | 19th February 2020

#### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

more >>>

TR20-018 | 18th February 2020
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>

TR20-017 | 18th February 2020

#### Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

TR20-016 | 17th February 2020
Kuan Cheng, William Hoza

#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

TR20-015 | 18th February 2020
Emanuele Viola

#### New lower bounds for probabilistic degree and AC0 with parity gates

Revisions: 3

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in ... more >>>

TR20-014 | 16th February 2020
Gil Cohen, Shahar Samocha

#### Palette-Alternating Tree Codes

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>>

TR20-013 | 17th February 2020
Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code $\cC_0$ of length $d$, and a $d$-regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the expander code $\cC ... more >>> TR20-012 | 14th February 2020 Dmitry Sokolov #### (Semi)Algebraic Proofs over$\{\pm 1\}$Variables One of the major open problems in proof complexity is to prove lower bounds on$AC_0[p]$-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove lower bounds on the size for Polynomial Calculus over the$\{\pm 1\}$basis. In this ... more >>> TR20-011 | 9th February 2020 Dominik Scheder, Navid Talebanfard #### Super Strong ETH is true for strong PPSZ We construct$k$-CNFs with$m$variables on which the strong version of PPSZ$k$-SAT algorithm, which uses bounded width resolution, has success probability at most$2^{-(1 - (1 + \epsilon)2/k)m}$for every$\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>> TR20-010 | 12th February 2020 Lijie Chen, Hanlin Ren #### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization Revisions: 1 We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>> TR20-009 | 6th February 2020 Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra #### Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev ... more >>> TR20-008 | 26th January 2020 Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter #### Better Secret-Sharing via Robust Conditional Disclosure of Secrets Revisions: 1 A secret-sharing scheme allows to distribute a secret$s$among$n$parties such that only some predefined authorized'' sets of parties can reconstruct the secret, and all other unauthorized'' sets learn nothing about$s$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>> TR20-007 | 19th December 2019 Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang #### Practical Relativistic Zero-Knowledge for NP In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers ... more >>> TR20-006 | 22nd January 2020 Anup Rao, Amir Yehudayoff #### The Communication Complexity of the Exact Gap-Hamming Problem We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem. more >>> TR20-005 | 17th January 2020 Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan #### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution Revisions: 1 We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>> TR20-004 | 17th January 2020 Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny #### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs Revisions: 1 In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>> TR20-003 | 15th January 2020 Giuseppe Persiano, Kevin Yeo #### Tight Static Lower Bounds for Non-Adaptive Data Structures Revisions: 1 In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of$n$points from a universe consisting of$m=n^{1+\Omega(1)}$points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>> TR20-002 | 6th January 2020 Sophie Laplante, Reza Naserasr, Anupa Sunny #### Sensitivity lower bounds from linear dependencies Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we ... more >>> TR20-001 | 31st December 2019 Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende #### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling Revisions: 2 We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph$G$can be reversibly pebbled in time$t$and space$s$if and only if there is a Nullstellensatz refutation of the pebbling formula over$G$in size$t+1\$ ... more >>>

ISSN 1433-8092 | Imprint