All reports in year 2020:

__
TR20-082
| 23rd May 2020
__

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals#### MaxSAT Resolution and Subcube Sums

__
TR20-081
| 21st May 2020
__

Robert Andrews#### Algebraic Hardness versus Randomness in Low Characteristic

__
TR20-080
| 19th May 2020
__

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang#### Continuous LWE

__
TR20-079
| 15th May 2020
__

Hermann Gruber , Markus Holzer, Simon Wolfsteiner#### On Minimizing Regular Expressions Without Kleene Star

__
TR20-078
| 21st May 2020
__

Eric Allender#### The New Complexity Landscape around Circuit Minimization

__
TR20-077
| 19th May 2020
__

Amit Sinhababu, Thomas Thierauf#### Factorization of Polynomials Given by Arithmetic Branching Programs

__
TR20-076
| 17th May 2020
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

__
TR20-075
| 6th May 2020
__

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal#### Rigid Matrices From Rectangular PCPs

Revisions: 1

__
TR20-074
| 6th May 2020
__

Eric Allender, Archit Chauhan, Samir Datta#### Depth-First Search in Directed Graphs, Revisited

__
TR20-073
| 5th May 2020
__

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov#### Lower Bounds on OBDD Proofs with Several Orders

__
TR20-072
| 5th May 2020
__

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi#### Locally testable codes via high-dimensional expanders

__
TR20-071
| 4th May 2020
__

Iftach Haitner, Yonatan Karidi-Heller#### A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

__
TR20-070
| 4th May 2020
__

Ben Lund, Aditya Potukuchi#### On the list recoverability of randomly punctured codes

Revisions: 1

__
TR20-069
| 4th May 2020
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Optimal Error Pseudodistributions for Read-Once Branching Programs

__
TR20-068
| 3rd May 2020
__

Oded Goldreich, Dana Ron#### One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 1

__
TR20-067
| 30th April 2020
__

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin#### Computational and proof complexity of partial string avoidability

__
TR20-066
| 28th April 2020
__

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal#### Quantum Implications of Huang's Sensitivity Theorem

__
TR20-065
| 2nd May 2020
__

Lijie Chen, Ce Jin, Ryan Williams#### Sharp Threshold Results for Computational Complexity

__
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

__
TR20-063
| 29th April 2020
__

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### On the Existence of Algebraically Natural Proofs

__
TR20-062
| 29th April 2020
__

Clement Canonne, Karl Wimmer#### Testing Data Binnings

__
TR20-061
| 28th April 2020
__

Deepanshu Kush, Benjamin Rossman#### Tree-depth and the Formula Complexity of Subgraph Isomorphism

__
TR20-060
| 23rd April 2020
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols

__
TR20-059
| 16th April 2020
__

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma#### Pr-ZSUBEXP is not contained in Pr-RP

__
TR20-058
| 24th April 2020
__

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff#### Interactive Proofs for Verifying Machine Learning

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

__
TR20-056
| 17th April 2020
__

James Cook, Ian Mertz#### Catalytic Approaches to the Tree Evaluation Problem

__
TR20-055
| 22nd April 2020
__

Ashutosh Kumar, Raghu Meka, David Zuckerman#### Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

__
TR20-054
| 22nd April 2020
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Communication Complexity with Defective Randomness

__
TR20-053
| 16th April 2020
__

Olaf Beyersdorff, Benjamin Böhm#### Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution

__
TR20-052
| 14th April 2020
__

Yanyi Liu, Rafael Pass#### On One-way Functions and Kolmogorov Complexity

Revisions: 1

__
TR20-051
| 15th April 2020
__

Rafael Pass, Muthuramakrishnan Venkitasubramaniam#### Is it Easier to Prove Theorems that are Guaranteed to be True?

__
TR20-050
| 18th April 2020
__

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

__
TR20-049
| 17th April 2020
__

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi#### Automating Cutting Planes is NP-Hard

__
TR20-048
| 16th April 2020
__

Shachar Lovett, Raghu Meka, Jiapeng Zhang#### Improved lifting theorems via robust sunflowers

__
TR20-047
| 16th April 2020
__

Ronen Shaltiel, Jad Silbak#### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity

__
TR20-046
| 13th April 2020
__

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

__
TR20-045
| 15th April 2020
__

Ankit Garg, Neeraj Kayal, Chandan Saha#### Learning sums of powers of low-degree polynomials in the non-degenerate case

__
TR20-044
| 8th April 2020
__

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan#### Cryptography from Information Loss

__
TR20-043
| 29th March 2020
__

Dorit Aharonov, Alex Bredariol Grilo#### A combinatorial MA-complete problem

__
TR20-042
| 31st March 2020
__

Pranav Bisht, Nitin Saxena#### Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

__
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

__
TR20-040
| 25th March 2020
__

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny#### Topology and adjunction in promise constraint satisfaction

__
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

__
TR20-038
| 15th March 2020
__

Ofer Grossman, Justin Holmgren#### Error Correcting Codes for Uncompressed Messages

__
TR20-037
| 18th March 2020
__

Michal Garlik#### Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It

__
TR20-036
| 9th March 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl#### Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths

__
TR20-035
| 23rd February 2020
__

Justin Holmgren#### No-Signaling MIPs and Faster-Than-Light Communication, Revisited

__
TR20-034
| 12th March 2020
__

Erfan Khaniki#### On Proof complexity of Resolution over Polynomial Calculus

Revisions: 1

__
TR20-033
| 12th March 2020
__

Suryajith Chillara#### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree

Revisions: 1

__
TR20-032
| 12th March 2020
__

Suryajith Chillara#### On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

__
TR20-031
| 10th March 2020
__

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

__
TR20-030
| 9th March 2020
__

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam#### Barriers for Rectangular Matrix Multiplication

__
TR20-029
| 6th March 2020
__

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

__
TR20-028
| 27th February 2020
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

__
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

__
TR20-026
| 25th February 2020
__

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman#### Spectral Sparsification via Bounded-Independence Sampling

Revisions: 1

__
TR20-025
| 20th February 2020
__

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari#### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

__
TR20-024
| 20th February 2020
__

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Randomized and Symmetric Catalytic Computation

__
TR20-023
| 10th February 2020
__

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan#### Non-Malleability against Polynomial Tampering

__
TR20-022
| 19th February 2020
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Error Resilience Beyond $\frac{2}{7}$

__
TR20-021
| 21st February 2020
__

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira#### NP-Hardness of Circuit Minimization for Multi-Output Functions

__
TR20-020
| 21st February 2020
__

Nikhil Mande, Justin Thaler, Shuchen Zhu#### Improved Approximate Degree Bounds For $k$-distinctness

__
TR20-019
| 19th February 2020
__

Siddharth Bhandari, Prahladh Harsha#### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

__
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

__
TR20-017
| 18th February 2020
__

Alexander Kozachinskiy, Vladimir Podolskii#### Multiparty Karchmer-Wigderson Games and Threshold Circuits

__
TR20-016
| 17th February 2020
__

Kuan Cheng, William Hoza#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

__
TR20-015
| 18th February 2020
__

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

Revisions: 2

__
TR20-014
| 16th February 2020
__

Gil Cohen, Shahar Samocha#### Palette-Alternating Tree Codes

__
TR20-013
| 17th February 2020
__

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor#### Linear-time Erasure List-decoding of Expander Codes

__
TR20-012
| 14th February 2020
__

Dmitry Sokolov#### (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables

__
TR20-011
| 9th February 2020
__

Dominik Scheder, Navid Talebanfard#### Super Strong ETH is true for strong PPSZ

__
TR20-010
| 12th February 2020
__

Lijie Chen, Hanlin Ren#### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

__
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

__
TR20-008
| 26th January 2020
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter#### Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Revisions: 1

__
TR20-007
| 19th December 2019
__

Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang#### Practical Relativistic Zero-Knowledge for NP

__
TR20-006
| 22nd January 2020
__

Anup Rao, Amir Yehudayoff#### The Communication Complexity of the Exact Gap-Hamming Problem

__
TR20-005
| 17th January 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Revisions: 1

__
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

__
TR20-003
| 15th January 2020
__

Giuseppe Persiano, Kevin Yeo#### Tight Static Lower Bounds for Non-Adaptive Data Structures

Revisions: 1

__
TR20-002
| 6th January 2020
__

Sophie Laplante, Reza Naserasr, Anupa Sunny#### Sensitivity lower bounds from linear dependencies

__
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

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

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

Robert Andrews

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

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

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

Hermann Gruber , Markus Holzer, Simon Wolfsteiner

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

Eric Allender

We survey recent developments related to the Minimum Circuit Size Problem

more >>>Amit Sinhababu, Thomas Thierauf

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

Benny Applebaum, Eliran Kachlon, Arpita Patra

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

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

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

Eric Allender, Archit Chauhan, Samir Datta

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

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

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

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

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

Iftach Haitner, Yonatan Karidi-Heller

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

Ben Lund, Aditya Potukuchi

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

Eshan Chattopadhyay, Jyun-Jie Liao

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

Oded Goldreich, Dana Ron

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

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

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

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

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

Lijie Chen, Ce Jin, Ryan Williams

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

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende

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

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

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

Clement Canonne, Karl Wimmer

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

Deepanshu Kush, Benjamin Rossman

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

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

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

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

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

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

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

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

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

James Cook, Ian Mertz

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

Ashutosh Kumar, Raghu Meka, David Zuckerman

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

Marshall Ball, Oded Goldreich, Tal Malkin

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

Olaf Beyersdorff, Benjamin Böhm

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

Yanyi Liu, Rafael Pass

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

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

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

Shuichi Hirahara

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

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

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

Shachar Lovett, Raghu Meka, Jiapeng Zhang

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

Ronen Shaltiel, Jad Silbak

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

Srikanth Srinivasan

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

Ankit Garg, Neeraj Kayal, Chandan Saha

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

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan

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

Dorit Aharonov, Alex Bredariol Grilo

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

Pranav Bisht, Nitin Saxena

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

Mrinal Kumar, Ben Lee Volk

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

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

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

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

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

Ofer Grossman, Justin Holmgren

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

Michal Garlik

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

Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl

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

Justin Holmgren

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

Erfan Khaniki

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

Suryajith Chillara

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

Suryajith Chillara

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

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

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

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

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

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

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

Nikhil Gupta, Chandan Saha, Bhargav Thankey

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

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

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

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

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

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

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

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

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

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

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

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

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

Nikhil Mande, Justin Thaler, Shuchen Zhu

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

Siddharth Bhandari, Prahladh Harsha

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 >>>Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

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

Alexander Kozachinskiy, Vladimir Podolskii

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

Kuan Cheng, William Hoza

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

Emanuele Viola

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

Gil Cohen, Shahar Samocha

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

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

Dmitry Sokolov

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

Dominik Scheder, Navid Talebanfard

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

Lijie Chen, Hanlin Ren

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

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

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

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

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

Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang

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

Anup Rao, Amir Yehudayoff

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

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

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

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

Giuseppe Persiano, Kevin Yeo

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

Sophie Laplante, Reza Naserasr, Anupa Sunny

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

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende

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