All reports in year 2021:

__
TR21-027
| 24th February 2021
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

__
TR21-026
| 23rd February 2021
__

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep#### Conditional Dichotomy of Boolean Ordered Promise CSPs

__
TR21-025
| 15th February 2021
__

Sivakanth Gopi, Venkatesan Guruswami#### Improved Maximally Recoverable LRCs using Skew Polynomials

__
TR21-024
| 15th February 2021
__

Mika Göös, Gilbert Maystre#### A Majority Lemma for Randomised Query Complexity

__
TR21-023
| 20th February 2021
__

Jiatu Li, Tianqi Yang#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

__
TR21-022
| 20th February 2021
__

Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin#### Depth lower bounds in Stabbing Planes for combinatorial principles

__
TR21-021
| 18th February 2021
__

Per Austrin, Kilian Risse#### Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

__
TR21-020
| 15th February 2021
__

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma#### Error Reduction For Weighted PRGs Against Read Once Branching Programs

__
TR21-019
| 17th February 2021
__

Edward Pyne, Salil Vadhan#### Pseudodistributions That Beat All Pseudorandom Generators

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

__
TR21-017
| 19th February 2021
__

Timothy Gowers, Emanuele Viola#### Mixing in non-quasirandom groups

__
TR21-016
| 16th February 2021
__

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari#### Unambiguous DNFs from Hex

__
TR21-015
| 15th February 2021
__

Chandan Saha, Bhargav Thankey#### Hitting Sets for Orbits of Circuit Classes and Polynomial Families

__
TR21-014
| 15th February 2021
__

Dori Medini, Amir Shpilka#### Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits

__
TR21-013
| 20th January 2021
__

Srinivasan Arunachalam, Penghui Yao#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

__
TR21-012
| 9th February 2021
__

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson#### On the Power and Limitations of Branch and Cut

__
TR21-011
| 13th February 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Classification of the streaming approximability of Boolean CSPs

Revisions: 1

__
TR21-010
| 11th February 2021
__

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle#### Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

__
TR21-009
| 1st February 2021
__

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich#### One-way Functions and Partial MCSP

Comments: 1

__
TR21-008
| 30th January 2021
__

Akash Kumar, C. Seshadhri, Andrew Stolman#### Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes

Revisions: 3

__
TR21-007
| 14th January 2021
__

Sai Sandeep#### Almost Optimal Inapproximability of Multidimensional Packing Problems

__
TR21-006
| 18th January 2021
__

Susanna de Rezende, Jakob Nordström, Marc Vinyals#### How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

__
TR21-005
| 13th January 2021
__

Anindya De, Elchanan Mossel, Joe Neeman#### Robust testing of low-dimensional functions

__
TR21-004
| 10th January 2021
__

Vishnu Iyer, Avishay Tal, Michael Whitmeyer#### Junta Distance Approximation with Sub-Exponential Queries

__
TR21-003
| 6th January 2021
__

Lijie Chen, Xin Lyu#### Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma

__
TR21-002
| 8th January 2021
__

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell#### Fooling Constant-Depth Threshold Circuits

__
TR21-001
| 1st January 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Computation Over the Noisy Broadcast Channel with Malicious Parties

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>>

Sivakanth Gopi, Venkatesan Guruswami

An $(n,r,h,a,q)$-Local Reconstruction Code is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies `$a$' local parity checks to recover from `$a$' erasures in that local group and there are further $h$ global parity ... more >>>

Mika Göös, Gilbert Maystre

We show that computing the majority of $n$ copies of a boolean function $g$ has randomised query complexity $\mathrm{R}(\mathrm{Maj} \circ g^n) = \Theta(n\cdot \bar{\mathrm{R}}_{1/n}(g))$. In fact, we show that to obtain a similar result for any composed function $f\circ g^n$, it suffices to prove a sufficiently strong form of the ... more >>>

Jiatu Li, Tianqi Yang

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>

Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

We prove logarithmic depth lower bounds in Stabbing Planes for the classes of combinatorial principles known as the Pigeonhole principle and the Tseitin contradictions. The depth lower bounds are new, obtained by giving almost linear length lower bounds which do not depend on the bit-size of the inequalities and in ... more >>>

Per Austrin, Kilian Risse

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and ... more >>>

Edward Pyne, Salil Vadhan

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ... more >>>

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Timothy Gowers, Emanuele Viola

We initiate a systematic study of mixing in non-quasirandom groups.

Let $A$ and $B$ be two independent, high-entropy distributions over

a group $G$. We show that the product distribution $AB$ is statistically

close to the distribution $F(AB)$ for several choices of $G$ and

$F$, including:

(1) $G$ is the affine ... more >>>

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(k^{1.5})$. Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of $1.22$. Our result is known to imply several other improved separations in query and communication ... more >>>

Chandan Saha, Bhargav Thankey

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set ... more >>>

Dori Medini, Amir Shpilka

In this paper we study polynomials in VP$_e$ (polynomial-sized formulas) and in $\Sigma\Pi\Sigma$ (polynomial-size depth-$3$ circuits) whose orbits, under the action of the affine group GL$^{aff}_n({\mathbb F})$, are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms.

As ... more >>>

Srinivasan Arunachalam, Penghui Yao

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT ... more >>>

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small ? > 0, one removes

?dn ...
more >>>

Sai Sandeep

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>

Susanna de Rezende, Jakob Nordström, Marc Vinyals

We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>

Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>

Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>

Lijie Chen, Xin Lyu

In this work we prove that there is a function $f \in \textrm{E}^\textrm{NP}$ such that, for every sufficiently large $n$ and $d = \sqrt{n}/\log n$, $f_n$ ($f$ restricted to $n$-bit inputs) cannot be $(1/2 + 2^{-d})$-approximated by $\textrm{F}_2$-polynomials of degree $d$. We also observe that a minor improvement ...
more >>>

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>