Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2021:
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

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

TR21-026 | 23rd February 2021
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

#### Conditional Dichotomy of Boolean Ordered Promise CSPs

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

TR21-025 | 15th February 2021
Sivakanth Gopi, Venkatesan Guruswami

#### Improved Maximally Recoverable LRCs using Skew Polynomials

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

TR21-024 | 15th February 2021
Mika Göös, Gilbert Maystre

#### A Majority Lemma for Randomised Query Complexity

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

TR21-023 | 20th February 2021
Jiatu Li, Tianqi Yang

#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

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

TR21-022 | 20th February 2021
Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

#### Depth lower bounds in Stabbing Planes for combinatorial principles

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

TR21-021 | 18th February 2021
Per Austrin, Kilian Risse

#### Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

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

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

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

TR21-019 | 17th February 2021

#### Pseudodistributions That Beat All Pseudorandom Generators

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

TR21-018 | 20th February 2021
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

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

TR21-017 | 19th February 2021
Timothy Gowers, Emanuele Viola

#### Mixing in non-quasirandom groups

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

TR21-016 | 16th February 2021
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

#### Unambiguous DNFs from Hex

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

TR21-015 | 15th February 2021
Chandan Saha, Bhargav Thankey

#### Hitting Sets for Orbits of Circuit Classes and Polynomial Families

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

TR21-014 | 15th February 2021
Dori Medini, Amir Shpilka

#### Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits

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

TR21-013 | 20th January 2021
Srinivasan Arunachalam, Penghui Yao

#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

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

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

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

TR21-011 | 13th February 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

#### Classification of the streaming approximability of Boolean CSPs

Revisions: 1

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

TR21-010 | 11th February 2021
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

#### Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

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

TR21-009 | 1st February 2021
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

#### One-way Functions and Partial MCSP

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

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

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

TR21-007 | 14th January 2021
Sai Sandeep

#### Almost Optimal Inapproximability of Multidimensional Packing Problems

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

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)

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

TR21-005 | 13th January 2021
Anindya De, Elchanan Mossel, Joe Neeman

#### Robust testing of low-dimensional functions

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

TR21-004 | 10th January 2021
Vishnu Iyer, Avishay Tal, Michael Whitmeyer

#### Junta Distance Approximation with Sub-Exponential Queries

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

TR21-003 | 6th January 2021
Lijie Chen, Xin Lyu

#### Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma

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

TR21-002 | 8th January 2021
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

#### Fooling Constant-Depth Threshold Circuits

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

TR21-001 | 1st January 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

#### Computation Over the Noisy Broadcast Channel with Malicious Parties

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

ISSN 1433-8092 | Imprint