Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

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

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: 2

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: 1

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

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: 3

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

Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests

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

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

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

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

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: 1

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

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

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
Ronen Shaltiel, Jad Silbak

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

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: 1

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

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
Siddharth Bhandari, Prahladh Harsha

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
Alexander Kozachinskiy, Vladimir Podolskii

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

Linear-time Erasure List-decoding of Expander Codes

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