Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2022:
All reports in year 2022:
TR22-001 | 28th December 2021
Yogesh Dahiya, Meena Mahajan

#### On (Simple) Decision Tree Rank

Revisions: 1

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>

TR22-002 | 11th December 2021
Sravanthi Chede, Anil Shukla

#### Extending Merge Resolution to a Family of Proof Systems

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player within the proofs. Every line of this proof system consists of existential clauses along with countermodels. MRes stores ... more >>>

TR22-003 | 4th January 2022
Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

#### On Semi-Algebraic Proofs and Algorithms

Revisions: 1

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>

TR22-004 | 3rd January 2022
Silas Richelson, Sourya Roy

#### Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>

TR22-005 | 11th January 2022
Anup Rao

#### Sunflowers: from soil to oil

Revisions: 3

A \emph{sunflower} is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erd\H{o}s and Rado, made by Alweiss, Lovett, Wu and Zhang.

more >>>

TR22-006 | 12th January 2022
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

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$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

TR22-007 | 14th January 2022
Halley Goldberg, Valentine Kabanets

#### A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information

We give a simplified proof of Hirahara's STOC'21 result showing that $DistPH \subseteq AvgP$ would imply $PH \subseteq DTIME[2^{O(n/\log n)}]$. The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that $NP$ is easy on average, which is interesting in ... more >>>

TR22-008 | 14th January 2022
Gil Cohen, Dean Doron, Ori Sberlo

#### Approximating Large Powers of Stochastic Matrices in Small Space

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>

TR22-009 | 17th January 2022
C. Ramya, Anamay Tengse

#### On Finer Separations between Subclasses of Read-once Oblivious ABPs

Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials ... more >>>

TR22-010 | 18th January 2022
Marshall Ball, Dana Dachman-Soled, Julian Loss

#### (Nondeterministic) Hardness vs. Non-Malleability

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ... more >>>

TR22-011 | 25th January 2022
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

#### Public-Key Encryption from Continuous LWE

The continuous learning with errors (CLWE) problem was recently introduced by Bruna
et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian
mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus
asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and
LWE ... more >>>

TR22-012 | 2nd February 2022
Anup Rao, Oscar Sprumont

#### On List Decoding Transitive Codes From Random Errors

We study the error resilience of transitive linear codes over $F_2$. We give tight bounds on the weight distribution of every such code $C$, and we show how these bounds can be used to infer bounds on the error rates that $C$ can tolerate on the binary symmetric channel. Using ... more >>>

TR22-013 | 5th February 2022

#### On properties that are non-trivial to test

In this note we show that all sets that are neither finite nor too dense are non-trivial to test in the sense that, for every $\epsilon>0$, distinguishing between strings in the set and strings that are $\epsilon$-far from the set requires $\Omega(1/\epsilon)$ queries.
Specifically, we show that if, for ... more >>>

TR22-014 | 8th February 2022
Joshua Cook, Dana Moshkovitz

#### Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

Revisions: 1

We prove for some constant $a > 1$, for all $k \leq a$,
$$\mathbf{MATIME}[n^{k + o(1)}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})],$$
for some specific $o(1)$ function. This improves on the Santhanam lower bound, which says there exists constant $c$ such that for all $k > 1$:
$$\mathbf{MATIME}[n^{c k}] / 1 ... more >>> TR22-015 | 12th February 2022 Mika Göös, Stefan Kiefer, Weiqiang Yuan #### Lower Bounds for Unambiguous Automata via Communication Complexity We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. \textbf{Complement:} There is a language L recognised by an n-state UFA such that the complement language \overline{L} requires NFAs with n^{\tilde{\Omega}(\log n)} states. This improves on ... more >>> TR22-016 | 15th February 2022 Artur Ignatiev, Ivan Mihajlin, Alexander Smal #### Super-cubic lower bound for generalized Karchmer-Wigderson games Revisions: 1 In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for some explicit function f: \{0,1\}^n\to \{0,1\}^{\log n}. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. ... more >>> TR22-017 | 15th February 2022 Ron D. Rothblum, Prashant Nalini Vasudevan #### Collision-Resistance from Multi-Collision-Resistance Revisions: 2 Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>> TR22-018 | 15th February 2022 Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao #### Further Collapses in TFNP We show \text{EOPL}=\text{PLS}\cap\text{PPAD}. Here the class \text{EOPL} consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse ... more >>> TR22-019 | 17th February 2022 Guangxu Yang, Jiapeng Zhang #### Simulation Methods in Communication Lower Bounds, Revisited The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). ... more >>> TR22-020 | 18th February 2022 Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar #### Worst-Case to Average-Case Reductions via Additive Combinatorics We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time \widetilde{O}(T) that are correct on ... more >>> TR22-021 | 19th February 2022 Xin Lyu #### Improved Pseudorandom Generators for \mathrm{AC}^0 Circuits We give PRG for depth-d, size-m \mathrm{AC}^0 circuits with seed length O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m)). Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on \frac{1}{\varepsilon} and is only one “\log\log(m)” away from the lower bound barrier. For the case of d=2, the seed length tightly ... more >>> TR22-022 | 18th February 2022 Vikraman Arvind, Pushkar Joglekar #### On Efficient Noncommutative Polynomial Factorization via Higman Linearization Revisions: 3 In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result: Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>> TR22-023 | 19th February 2022 Erfan Khaniki #### Nisan--Wigderson generators in Proof Complexity: New lower bounds A map g:\{0,1\}^n\to\{0,1\}^m (m>n) is a hard proof complexity generator for a proof system P iff for every string b\in\{0,1\}^m\setminus Rng(g), formula \tau_b(g) naturally expressing b\not\in Rng(g) requires superpolynomial size P-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>> TR22-024 | 17th February 2022 Louis Golowich, Salil Vadhan #### Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs Revisions: 1 We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. We show that expander walks fool symmetric functions up to a O(\lambda) error in ... more >>> TR22-025 | 15th February 2022 Oliver Korten #### Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle Revisions: 3 A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of incompressible strings,'' i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the compression problem,'' where we are given ... more >>> TR22-026 | 17th February 2022 James Cook, Ian Mertz #### Trading Time and Space in Catalytic Branching Programs An m-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of m distinct branching programs for f which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>> TR22-027 | 22nd February 2022 Guy Blanc, Dean Doron #### New Near-Linear Time Decodable Codes Closer to the GV Bound Revisions: 1 We construct a family of binary codes of relative distance \frac{1}{2}-\varepsilon and rate \varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)} for \alpha \approx \frac{1}{2} that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>> TR22-028 | 23rd February 2022 Dan Karliner, Roie Salama, Amnon Ta-Shma #### The plane test is a local tester for Multiplicity Codes Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a low-degree polynomial and all of its directional derivatives up to order s. Multi-variate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a ... more >>> TR22-029 | 27th February 2022 Anthony Leverrier, Gilles Zémor #### Quantum Tanner codes Revisions: 2 Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser ... more >>> TR22-030 | 18th February 2022 Aniruddha Biswas, Palash Sarkar #### On The ''Majority is Least Stable'' Conjecture. Revisions: 1 We show that the ''majority is least stable'' conjecture is true for n=1 and 3 and false for all odd n\geq 5. more >>> TR22-031 | 16th February 2022 Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse #### Transparency Beyond VNP in the Monotone Setting Revisions: 4 Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be ... more >>> TR22-032 | 1st March 2022 Iftach Haitner, Noam Mazor, Jad Silbak #### Incompressiblity and Next-Block Pseudoentropy A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear. ... more >>> TR22-033 | 1st March 2022 Ivan Mihajlin, Anastasia Sofronova #### A better-than-3\log{n} depth lower bound for De Morgan formulas with restrictions on top gates Revisions: 2 , Comments: 2 We prove that a modification of Andreev's function is not computable by (3 + \alpha - \varepsilon) \log{n} depth De Morgan formula with (2\alpha - \varepsilon)\log{n} layers of AND gates at the top for any 1/5 > \alpha > 0 and any constant \varepsilon > 0. In order to do ... more >>> TR22-034 | 3rd March 2022 Chin Ho Lee, Edward Pyne, Salil Vadhan #### Fourier Growth of Regular Branching Programs We analyze the Fourier growth, i.e. the L_1 Fourier weight at level k (denoted L_{1,k}), of read-once regular branching programs. We prove that every read-once regular branching program B of width w \in [1,\infty] with s accepting states on n-bit inputs must have its L_{1,k} bounded by$$
\min\left\{ ... more >>>

TR22-035 | 7th March 2022
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff

#### A Characterization of Multiclass Learnability

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability ... more >>>

TR22-036 | 10th March 2022
Agnes Schleitzer, Olaf Beyersdorff

#### Classes of Hard Formulas for QBF Resolution

Revisions: 1

To date, we know only a few handcrafted quantified Boolean formulas (QBFs) that are hard for central QBF resolution systems such as Q and QU, and only one specific QBF family to separate Q and QU.

Here we provide a general method to construct hard formulas for Q and ... more >>>

TR22-037 | 10th March 2022
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20].
More precisely, given a parameter $0 < \delta \leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a ... more >>>

TR22-038 | 13th March 2022
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

#### Lower bounds for Polynomial Calculus with extension variables over finite fields

Revisions: 1

For every prime p > 0, every n > 0 and ? = O(logn), we show the existence
of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at ... more >>>

TR22-039 | 14th March 2022
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

#### Parallel Repetition For All 3-Player Games Over Binary Alphabet

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the ... more >>>

TR22-040 | 10th March 2022
Benjamin Böhm, Tomáš Peitl, Olaf Beyersdorff

#### Should decisions in QCDCL follow prefix order?

Quantified conflict-driven clause learning (QCDCL) is one of the main solving approaches for quantified Boolean formulas (QBF). One of the differences between QCDCL and propositional CDCL is that QCDCL typically follows the prefix order of the QBF for making decisions.
We investigate an alternative model for QCDCL solving where decisions ... more >>>

TR22-041 | 23rd March 2022
TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

#### Boolean functions with small approximate spectral norm

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

TR22-042 | 31st March 2022
Vikraman Arvind, Pushkar Joglekar

#### Matrix Polynomial Factorization via Higman Linearization

In continuation to our recent work on noncommutative
polynomial factorization, we consider the factorization problem for
matrices of polynomials and show the following results.
\begin{itemize}
\item Given as input a full rank $d\times d$ matrix $M$ whose entries
$M_{ij}$ are polynomials in the free noncommutative ring
more >>>

TR22-043 | 2nd April 2022
Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

#### Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

TR22-044 | 4th April 2022
Meghal Gupta, Naren Manoj

#### An Optimal Algorithm for Certifying Monotone Functions

Given query access to a monotone function $f\colon\{0,1\}^n\to\{0,1\}$ with certificate complexity $C(f)$ and an input $x^{\star}$, we design an algorithm that outputs a size-$C(f)$ subset of $x^{\star}$ certifying the value of $f(x^{\star})$. Our algorithm makes $O(C(f) \cdot \log n)$ queries to $f$, which matches the information-theoretic lower bound for this ... more >>>

TR22-045 | 4th April 2022
Gil Cohen, Tal Yankovitz

#### Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Revisions: 1

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted ... more >>>

TR22-046 | 4th April 2022
Dmitry Itsykson, Artur Riazanov

#### Automating OBDD proofs is NP-hard

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>

TR22-047 | 4th April 2022
Manik Dhar, Zeev Dvir

#### Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

Revisions: 1

We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_\infty$ sense. More concretely, consider a set $S \subset \mathbb{F}_q^n$ and a randomly chosen linear map $L : \mathbb{F}_q^n \to \mathbb{F}_q^t$ with $q^t$ taken to be sufficiently smaller than $|S|$. Let ... more >>>

TR22-048 | 4th April 2022
Hanlin Ren, Rahul Santhanam, Zhikun Wang

#### On the Range Avoidance Problem for Circuits

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

TR22-049 | 4th April 2022
Xinyu Mao, Noam Mazor, Jiapeng Zhang

#### Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Revisions: 1

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

TR22-050 | 12th April 2022
Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

#### Circuits Resilient to Short-Circuit Errors

Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

TR22-051 | 18th April 2022
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

#### Low Degree Testing over the Reals

We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast ... more >>>

TR22-052 | 18th April 2022
Tal Herman, Guy Rothblum

#### Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... more >>>

TR22-053 | 24th April 2022
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

#### On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC^0 circuits
for division, matrix powering, and related problems, where the improvement is in terms of ... more >>>

TR22-054 | 21st April 2022
Anastasia Sofronova, Dmitry Sokolov

#### A Lower Bound for $k$-DNF Resolution on Random CNF Formulas via Expansion

Random $\Delta$-CNF formulas are one of the few candidates that are expected to be hard to refute in any proof system. One of the frontiers in the direction of proving lower bounds on these formulas is the $k$-DNF Resolution proof system (aka $\mathrm{Res}(k)$). Assume we sample $m$ clauses over $n$ ... more >>>

TR22-055 | 23rd April 2022
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

#### Simple Hard Instances for Low-Depth Algebraic Proofs

We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically, we show that the subset-sum variant $\sum_{i,j,k,l\in[n]} z_{ijkl}x_ix_jx_kx_l-\beta = 0$, for Boolean variables, does not have polynomial-size IPS refutations where the refutations are multilinear and written as ... more >>>

TR22-056 | 18th April 2022
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

#### Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that ... more >>>

TR22-057 | 25th April 2022
Lijie Chen, Roei Tell

#### When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems

Revisions: 2

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of *derandomizing interactive proofs systems*.

... more >>>

TR22-058 | 26th April 2022
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

#### Separations in Proof Complexity and TFNP

Revisions: 1

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT ... more >>>

TR22-059 | 27th April 2022
Siddhesh Chaubal, Anna Gal

#### Diameter versus Certificate Complexity of Boolean Functions

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we ... more >>>

TR22-060 | 27th April 2022
Nikolay Vereshchagin

#### How much randomness is needed to convert MA protocols to AM protocols?

The Merlin-Arthur class of languages MA is included into Arthur-Merlin class AM, and into PP. For a standard transformation of a given MA protocol with Arthur's message (= random string) of length $a$ and Merlin's message of length $m$ to a PP machine, the latter needs $O(ma)$ random bits. The ... more >>>

TR22-061 | 30th April 2022
Amey Bhangale, Subhash Khot, Dor Minzer

#### On Approximability of Satisfiable $k$-CSPs: I

We consider the $P$-CSP problem for $3$-ary predicates $P$ on satisfiable instances. We show that under certain conditions on $P$ and a $(1,s)$ integrality gap instance of the $P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\varepsilon$, for every constant $\varepsilon>0$. ... more >>>

TR22-062 | 2nd May 2022
Paolo Liberatore

#### Superredundancy: A tool for Boolean formula minimization complexity analysis

A superredundant clause is a clause that is redundant in the resolution closure of a formula. The converse concept of superirredundancy ensures membership of the clause in all minimal CNF formulae that are equivalent to the given one. This allows for building formulae where some clauses are fixed when minimizing ... more >>>

TR22-063 | 30th April 2022
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

#### Fast Multivariate Multipoint Evaluation Over All Finite Fields

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of ... more >>>

TR22-064 | 2nd May 2022
Deepanshu Kush, Shubhangi Saraf

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega ... more >>> TR22-065 | 3rd May 2022 Madhu Sudan #### Streaming and Sketching Complexity of CSPs: A survey Revisions: 1 In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain ... more >>> TR22-066 | 4th May 2022 Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy #### On sketching approximations for symmetric Boolean CSPs A Boolean maximum constraint satisfaction problem, Max-CSP$$(f)$$, is specified by a predicate $$f:\{-1,1\}^k\to\{0,1\}$$. An $$n$$-variable instance of Max-CSP$$(f)$$ consists of a list of constraints, each of which applies $$f$$ to $$k$$ distinct literals drawn from the $$n$$ variables. For $$k=2$$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>> TR22-067 | 4th May 2022 Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay #### Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem ... more >>> TR22-068 | 5th May 2022 Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy #### Sketching Approximability of (Weak) Monarchy Predicates Revisions: 1 We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>> TR22-069 | 28th April 2022 Silas Richelson, Sourya Roy #### List-Decoding Random Walk XOR Codes Near the Johnson Bound Revisions: 1 In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance$\frac{1-\varepsilon}{2}$and rate$\Omega\bigl(\varepsilon^{2+o(1)}\bigr)$and thus it almost achieves the Gilbert-Varshamov bound, except for the$o(1)$term in the exponent. The prior best list-decoding algorithm for (a variant of) ... more >>> TR22-070 | 8th May 2022 Pranav Bisht, Ilya Volkovich #### On Solving Sparse Polynomial Factorization Related Problems Revisions: 6 In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most$s$terms and individual degree bounded by$d$can itself have at most$s^{O(d^2\log ... more >>>

TR22-071 | 13th May 2022

#### Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>

TR22-072 | 15th May 2022
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

TR22-073 | 18th May 2022
Itay Kalev, Amnon Ta-Shma

#### Unbalanced Expanders from Multiplicity Codes

In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a basic building block in many constructions, and, in particular, is behind the state of the art extractor constructions.

We give an alternative construction that is based on ... more >>>

TR22-074 | 20th May 2022
Michael Saks, Rahul Santhanam

#### On Randomized Reductions to the Random Strings

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

TR22-075 | 21st May 2022

#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

TR22-076 | 16th May 2022
Hunter Monroe

#### Average-Case Hardness of Proving Tautologies and Theorems

We consolidate two widely believed conjectures about tautologies---no optimal proof system exists, and most require superpolynomial size proofs in any system---into a $p$-isomorphism-invariant condition satisfied by all paddable $\textbf{coNP}$-complete languages or none. The condition is: for any Turing machine (TM) $M$ accepting the language, $\textbf{P}$-uniform input families requiring superpolynomial time ... more >>>

TR22-077 | 13th May 2022
Max Hopkins, Ting-Chun Lin

#### Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares

We construct an explicit family of 3-XOR instances hard for $\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness ... more >>>

TR22-078 | 8th May 2022
Dan Karliner, Amnon Ta-Shma

#### Improved local testing for multiplicity codes

Multiplicity codes are a generalization of Reed-Muller codes which include derivatives as well as the values of low degree polynomials, evaluated in every point in $\mathbb{F}_p^m$.
Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing.
Recently, the authors and ... more >>>

TR22-079 | 25th May 2022
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

#### Lower Bound Methods for Sign-rank and their Limitations

The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>

TR22-080 | 25th May 2022
Meena Mahajan, Gaurav Sood

#### QBF Merge Resolution is powerful but unnatural

The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for this approach was to overcome the limitations encountered in long-distance Q-Resolution proof system (LD-Q-Res), where the syntactic side-conditions, while prohibiting all unsound resolutions, also end ... more >>>

TR22-081 | 26th May 2022
Zhenjian Lu, Igor Oliveira

#### Theory and Applications of Probabilistic Kolmogorov Complexity

Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants ... more >>>

TR22-082 | 27th May 2022
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

#### Low-Degree Polynomials Extract from Local Sources

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

TR22-083 | 2nd June 2022
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

#### Hardness of Maximum Likelihood Learning of DPPs

Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fitted to match the data; typically, we ... more >>>

TR22-084 | 2nd June 2022
Yanyi Liu, Rafael Pass

#### Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>

TR22-085 | 8th June 2022
Andrzej Lingas

#### A Note on Lower Bounds for Monotone Multilinear Boolean Circuits

A monotone Boolean circuit is a restriction of a Boolean circuit
allowing for the use of disjunctions, conjunctions, the Boolean
constants, and the input variables. A monotone Boolean circuit is
multilinear if for any AND gate the two input functions have no
variable in common. We ... more >>>

TR22-086 | 9th June 2022
Lijie Chen, Jiatu Li, Tianqi Yang

#### Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Revisions: 1

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by ... more >>>

TR22-087 | 8th June 2022
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

#### Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees

Revisions: 1

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>

TR22-088 | 15th June 2022
Anthony Leverrier, Gilles Zémor

#### Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes

Revisions: 1

We introduce and analyse an efficient decoder for the quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n \log n})$. We also work on the link between quantum Tanner codes and the Lifted ... more >>>

TR22-089 | 18th June 2022
Ilario Bonacina, Neil Thapen

#### A separation of PLS from PPP

Recently it was shown that PLS is not contained in PPADS (ECCC report TR22-058). We show that this separation already implies that PLS is not contained in PPP. These separations are shown for the decision tree model of TFNP and imply similar separations in the type-2, relativized model.

Important note. ... more >>>

TR22-090 | 24th June 2022
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

#### On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

TR22-091 | 2nd July 2022
Harm Derksen, Emanuele Viola

#### Quasirandom groups enjoy interleaved mixing

Let $G$ be a group such that any non-trivial representation has dimension
at least $d$. Let $X=(X_{1},X_{2},\ldots,X_{t})$ and $Y=(Y_{1},Y_{2},\ldots,Y_{t})$
be distributions over $G^{t}$. Suppose that $X$ is independent from
$Y$. We show that for any $g\in G$ we have
$\left|\mathbb{P}[X_{1}Y_{1}X_{2}Y_{2}\cdots X_{t}Y_{t}=g]-1/|G|\right|\le\frac{|G|^{2t-1}}{d^{t-1}}\sqrt{\mathbb{E}_{h\in G^{t}}X(h)^{2}}\sqrt{\mathbb{E}_{h\in G^{t}}Y(h)^{2}}.$
Our results generalize, improve, and ... more >>>

TR22-092 | 2nd July 2022
Peter Ivanov, Liam Pavlovic, Emanuele Viola

#### On correlation bounds against polynomials

We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over $\mathbb{F}_{2}$. Our main contributions include:

1. In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their ... more >>>

TR22-093 | 28th June 2022
Joshua Cook

#### More Verifier Efficient Interactive Protocols For Bounded Space

Revisions: 4

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>

TR22-094 | 3rd July 2022
Stasys Jukna

#### Notes on Monotone Read-k Circuits

Revisions: 2

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... more >>>

TR22-095 | 5th July 2022
Meghal Gupta, Rachel Zhang

#### Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. ... more >>>

TR22-096 | 8th July 2022
Mika Göös, Siddhartha Jain

#### Communication Complexity of Collision

The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,x_n)\in[n]^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of ... more >>>

TR22-097 | 3rd July 2022
Lijie Chen, Ron D. Rothblum, Roei Tell

#### Unstructured Hardness to Average-Case Randomness

The leading technical approach in uniform hardness-to-randomness in the last two decades faced several well-known barriers that caused results to rely on overly strong hardness assumptions, and yet still yield suboptimal conclusions.

In this work we show uniform hardness-to-randomness results that *simultaneously break through all of the known barriers*. Specifically, ... more >>>

TR22-098 | 12th July 2022

We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive ... more >>>

TR22-099 | 14th July 2022
Nikhil Gupta, Chandan Saha, Bhargav Thankey

#### Equivalence Test for Read-Once Arithmetic Formulas

We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two $n$-variate polynomials $f, g \in \mathbb{F}[\mathbf{x}]$ are equivalent, denoted ... more >>>

TR22-100 | 14th July 2022
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

#### Streaming complexity of CSPs with randomly ordered constraints

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely Max-DICUT, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of DICUT requires $\Omega(\sqrt{n})$ space with ... more >>>

TR22-101 | 15th July 2022
Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x = C(b)$ on at most $q$ coordinates. Existing constructions of $2$-LDCs achieve $n = ... more >>> TR22-102 | 15th July 2022 Venkatesan Guruswami, Xin Lyu, Xiuhan Wang #### Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>> TR22-103 | 15th July 2022 Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman #### Almost Chor--Goldreich Sources and Adversarial Random Walks Revisions: 1 A Chor--Goldreich (CG) source [CG88] is a sequence of random variables$X = X_1 \circ \ldots \circ X_t$, each$X_i \sim \{0,1 \{^d$, such that each$X_i$has$\delta d$min-entropy for some constant$\delta > 0$, even conditioned on any fixing of$X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>> TR22-104 | 18th July 2022 Nader Bshouty #### On One-Sided Testing Affine Subspaces Revisions: 1 We study the query complexity of one-sided$\epsilon$-testing the class of Boolean functions$f:F^n\to \{0,1\}$that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where$F$is any finite field. We give a polynomial-time$\epsilon$-testers that ask$\tilde O(1/\epsilon)$queries. This improves the query complexity$\tilde O(|F|/\epsilon)$... more >>> TR22-105 | 18th July 2022 Ilario Bonacina, Nicola Galesi, Massimo Lauria #### On vanishing sums of roots of unity in polynomial calculus and sum-of-squares Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size. more >>> TR22-106 | 21st July 2022 Suryajith Chillara, Coral Grichener, Amir Shpilka #### On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts We say that two given polynomials$f, g \in R[x_1, \ldots, x_n]$, over a ring$R$, are equivalent under shifts if there exists a vector$(a_1, \ldots, a_n)\in R^n$such that$f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>> TR22-107 | 20th July 2022 Shachar Lovett, Jiapeng Zhang #### Fractional certificates for bounded functions A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold ... more >>> TR22-108 | 18th July 2022 Shuichi Hirahara, Nobutaka Shimizu #### Hardness Self-Amplification from Feasible Hard-Core Sets We consider the question of hardness self-amplification: Given a Boolean function$f$that is hard to compute on a$o(1)$-fraction of inputs drawn from some distribution, can we prove that$f$is hard to compute on a$(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>> TR22-109 | 27th July 2022 Siddharth Iyer, Michael Whitmeyer #### Searching for Regularity in Bounded Functions Given a function$f:\mathbb F_2^n \to [-1,1]$, this work seeks to find a large affine subspace$\mathcal U$such that$f$, when restricted to$\mathcal U$, has small nontrivial Fourier coefficients. We show that for any function$f:\mathbb F_2^n \to [-1,1]$with Fourier degree$d$, there exists an affine subspace ... more >>> TR22-110 | 1st August 2022 Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit #### Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks. Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known ... more >>> TR22-111 | 1st August 2022 Robert Andrews #### On Matrix Multiplication and Polynomial Identity Testing We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting$\underline{R}(n)$denote the border rank of$n \times n \times n$matrix multiplication, we construct a hitting set generator with seed length$O(\sqrt{n} \cdot ... more >>>

TR22-112 | 12th August 2022
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

#### Randomised Composition and Small-Bias Minimax

We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, ... more >>>

TR22-113 | 11th August 2022
Yanyi Liu, Rafael Pass

#### Leakage-Resilient Hardness v.s. Randomness

A central open problem in complexity theory concerns the question of
whether all efficient randomized algorithms can be simulated by
efficient deterministic algorithms. The celebrated hardness
v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84),
Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness
assumptions under which $\prBPP = \prP$, but these hardness ... more >>>

TR22-114 | 16th August 2022
Hao Wu

#### Direct Sum Theorems From Fortification

We revisit the direct sum theorems in communication complexity which askes whether the resource to solve $n$ communication problems together is (approximately) the sum of resources to solve these problems separately. Our work starts with the observation that Meir and Dinur's fortification lemma for protocol size over rectangles can be ... more >>>

TR22-115 | 17th August 2022
Dieter van Melkebeek, Andrew Morgan

#### Polynomial Identity Testing via Evaluation of Rational Functions

We introduce a hitting set generator for Polynomial Identity Testing
based on evaluations of low-degree univariate rational functions at
abscissas associated with the variables. Despite the univariate
nature, we establish an equivalence up to rescaling with a generator
introduced by Shpilka and Volkovich, which has a similar structure but
uses ... more >>>

TR22-116 | 17th August 2022
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

#### Constant-Depth Sorting Networks

In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>>

TR22-117 | 23rd August 2022

#### Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.
Guruswami and ... more >>>

TR22-118 | 23rd August 2022
Huacheng Yu

#### Strong XOR Lemma for Communication with Bounded Rounds

In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\{0,1\}$, the $n$-fold XOR function $f^{\oplus n}:\mathcal{X}^n\times \mathcal{Y}^n\rightarrow\{0,1\}$ maps $n$ input pairs $(X_1,\ldots,X_n,Y_1,\ldots,Y_n)$ to the XOR of the $n$ output bits $f(X_1,Y_1)\oplus \cdots \oplus f(X_n, Y_n)$. We prove that if every ... more >>>

TR22-119 | 24th August 2022
Shuichi Hirahara

#### NP-Hardness of Learning Programs and Partial MCSP

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

TR22-120 | 24th August 2022
Jan Krajicek

#### On the existence of strong proof complexity generators

The working conjecture from K'04 that there is a proof complexity generator hard for all
proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions
as follows:
\begin{itemize}
\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>

TR22-121 | 27th August 2022
William Hoza

#### Recent Progress on Derandomizing Space-Bounded Computation

Revisions: 1

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>

TR22-122 | 29th August 2022
Young Kun Ko

#### Efficient Linearization Implies the Multiphase Conjecture

The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be linearized," with only a constant size blow-up. We ... more >>>

TR22-123 | 4th September 2022
Alexander A. Sherstov

#### The Approximate Degree of DNF and CNF Formulas

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This ... more >>>

TR22-124 | 9th September 2022
Oded Goldreich, Guy Rothblum, Tal Skverer

#### On Interactive Proofs of Proximity with Proof-Oblivious Queries

Revisions: 3

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make ... more >>>

TR22-125 | 9th September 2022
Shir Peleg, Amir Shpilka, Ben Lee Volk

#### Tensor Reconstruction Beyond Constant Rank

We give reconstruction algorithms for subclasses of depth-$3$ arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:

1. ... more >>>

TR22-126 | 12th September 2022
Andrei Krokhin, Jakub Opršal

#### An Invitation to the Promise Constraint Satisfaction Problem

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk.

TR22-127 | 12th September 2022
Eric Allender, Shuichi Hirahara, Harsha Tirumala

#### Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Revisions: 1

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to ... more >>>

TR22-128 | 11th September 2022
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach

#### PPP-Completeness and Extremal Combinatorics

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdos-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implicit" means that the collection is represented ... more >>>

TR22-129 | 15th September 2022
Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

#### Binary Codes with Resilience Beyond 1/4 via Interaction

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>

TR22-130 | 15th September 2022
Hamed Hatami, Kaave Hosseini, Xiang Meng

#### A Borsuk-Ulam lower bound for sign-rank and its application

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... more >>>

TR22-131 | 18th September 2022
Rafael Mendes de Oliveira, Akash Sengupta

Let $\mathcal{F} = \{F_1, \ldots, F_m\}$ be a finite set of irreducible homogeneous multivariate polynomials of degree at most $3$ such that $F_i$ does not divide $F_j$ for $i\neq j$.
We say that $\mathcal{F}$ is a cubic radical Sylvester-Gallai configuration if for any two distinct $F_i,F_j$ there exists a ... more >>>

TR22-132 | 18th September 2022
Harm Derksen, Emanuele Viola

#### Fooling polynomials using invariant theory

We revisit the problem of constructing explicit pseudorandom generators
that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables
over the field $F_q$, in the case of large $q$. Previous constructions
either have seed length at least $2^{d}\log q$, and thus are only non-trivial
when the degree is less than ... more >>>

TR22-133 | 20th September 2022
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

#### Downward Self-Reducibility in TFNP

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns
solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is
well studied and it is known that all downward self-reducible problems are in PSPACE. In this
paper, we initiate the study of ... more >>>

TR22-134 | 23rd September 2022
Greg McLellan, Alexey Milovanov

#### Some Games on Turing Machines and Power from Random Strings

Revisions: 1

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ... more >>>

TR22-135 | 18th September 2022
Rahul Chugh, Supartha Poddar, Swagato Sanyal

#### Decision Tree Complexity versus Block Sensitivity and Degree

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>

TR22-136 | 21st September 2022
Sepehr Assadi, Gillat Kol, Zhijun Zhang

#### Rounds vs Communication Tradeoffs for Maximal Independent Sets

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>

TR22-137 | 26th September 2022
Daniel Avraham , Amir Yehudayoff

#### On blocky ranks of matrices

A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>>

TR22-138 | 5th October 2022
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang

#### Robustness for Space-Bounded Statistical Zero Knowledge

We show that the space-bounded Statistical Zero Knowledge classes SZK_L and NISZK_L are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class. Coupled with other recent characterizations of these classes, this can be viewed as lending support to ... more >>>

TR22-139 | 15th October 2022
Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

#### On the VNP-hardness of Some Monomial Symmetric Polynomials

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>

TR22-140 | 10th October 2022
Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry

#### Commitments to Quantum States

Revisions: 1

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the ... more >>>

TR22-141 | 20th October 2022
Sam Buss, Noah Fleming, Russell Impagliazzo

#### TFNP Characterizations of Proof Systems and Monotone Circuits

Revisions: 2

Connections between proof complexity and circuit complexity have become major tools for obtaining lower bounds in both areas. These connections -- which take the form of interpolation theorems and query-to-communication lifting theorems -- translate efficient proofs into small circuits, and vice versa, allowing tools from one area to be applied ... more >>>

TR22-142 | 3rd November 2022
Emanuele Viola

#### Correlation bounds against polynomials

A survey on correlation bounds against polynomials.

more >>>

TR22-143 | 7th November 2022
Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

#### Certificate games

Revisions: 1

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

TR22-144 | 7th November 2022
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

#### Streaming beyond sketching for Maximum Directed Cut

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms.

... more >>>

TR22-145 | 4th November 2022
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study the black-box function inversion problem, which is the problem of finding $x \in [N]$ such that $f(x) = y$, given as input some challenge point $y$ in the image of a function $f : [N] \to [N]$, using $T$ oracle queries to $f$ and preprocessed advice $\sigma \in ... more >>> TR22-146 | 9th November 2022 Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai #### Interactive Coding with Small Memory In this work, we design an interactive coding scheme that converts any two party interactive protocol$\Pi$into another interactive protocol$\Pi'$, such that even if errors are introduced during the execution of$\Pi'$, the parties are able to determine what the outcome of running$\Pi$would be in an ... more >>> TR22-147 | 10th November 2022 Samir Datta, Chetan Gupta #### Evaluating Monotone Circuits on Surfaces Revisions: 3 In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>> TR22-148 | 11th November 2022 Peter Ivanov, Raghu Meka, Emanuele Viola #### Efficient resilient functions An$n$-bit boolean function is resilient to coalitions of size$q$if no fixed set of$q$bits is likely to influence the value of the function when the other$n-q$bits are chosen uniformly at random, even though the function is nearly balanced. We construct explicit functions resilient to ... more >>> TR22-149 | 7th November 2022 Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma #### Approximating Iterated Multiplication of Stochastic Matrices in Small Space Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the$\mathbf{BPL}$vs.$\mathbf{L}$problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>> TR22-150 | 7th November 2022 Aaron (Louie) Putterman, Edward Pyne #### Near-Optimal Derandomization of Medium-Width Branching Programs We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length$n$and width$w$in space $$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$ In particular, we obtain an almost optimal space$\tilde{O}(\log n)$derandomization of programs up to width$w=2^{\sqrt{\log n}}$. Previously, ... more >>> TR22-151 | 12th November 2022 Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey #### Low-depth arithmetic circuit lower bounds via shifted partials We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving ... more >>> TR22-152 | 10th November 2022 Toniann Pitassi, Morgan Shirley, Adi Shraibman #### The Strength of Equality Oracles in Communication It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires$\Omega(n)$deterministic communication complexity but has efficient randomized protocols. Previous work of Chattopadhyay, Lovett and Vinyals shows that randomized communication is strictly stronger than what can be solved by deterministic protocols ... more >>> TR22-153 | 8th November 2022 Eshan Chattopadhyay, Jyun-Jie Liao #### Hardness against Linear Branching Programs and More In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each node is allowed to make$\mathbb{F}_2$-linear queries, and are read-once in the ... more >>> TR22-154 | 6th November 2022 Gil Cohen, Itay Cohen #### Spectral Expanding Expanders Dinitz, Schapira, and Valadarsky (Algorithmica 2017) introduced the intriguing notion of expanding expanders -- a family of expander graphs with the property that every two consecutive graphs in the family differ only on a small number of edges. Such a family allows one to add and remove vertices with only ... more >>> TR22-155 | 15th November 2022 Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen #### Testing of Index-Invariant Properties in the Huge Object Model The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Computer Science, and in various real-life statistical tasks. The original distribution testing model relies on samples drawn independently from the distribution ... more >>> TR22-156 | 15th November 2022 Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro #### Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all$\ell_p$Norms We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>> TR22-157 | 16th November 2022 Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov #### Border complexity via elementary symmetric polynomials In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, ... more >>> TR22-158 | 18th November 2022 Ivan Hu, Andrew Morgan, Dieter van Melkebeek #### Query Complexity of Inversion Minimization on Trees We consider the following computational problem: Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It ... more >>> TR22-159 | 18th November 2022 Songhua He, Periklis Papakonstantinou #### Deep Neural Networks: The Missing Complexity Parameter Deep neural networks are the dominant machine learning model. We show that this model is missing a crucial complexity parameter. Today, the standard neural network (NN) model is a circuit whose gates (neurons) are ReLU units. The complexity of a NN is quantified by the depth (number of layers) and ... more >>> TR22-160 | 31st October 2022 Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran #### The Geometry of Rounding Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of$\mathbb{R}^d$are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given$k\in\mathbb{N}$(ideally small) and$\epsilon>0$(ideally large), is there a partition of ... more >>> TR22-161 | 9th November 2022 Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu #### Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, ... more >>> TR22-162 | 10th November 2022 Hadley Black, Deeparnab Chakrabarty, C. Seshadhri #### Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an$\widetilde{O}(n\sqrt{d})$Monotonicity Tester The problem of testing monotonicity for Boolean functions on the hypergrid,$f:[n]^d \to \{0,1\}$is a classic topic in property testing. When$n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making$\widetilde{O}(\varepsilon^{-2}\sqrt{d})$queries. Up to polylog ... more >>> TR22-163 | 16th November 2022 Gil Cohen, Gal Maor #### Random Walks on Rotating Expanders Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -- the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As ... more >>> TR22-164 | 20th November 2022 Shuichi Hirahara, Mikito Nanashima #### Learning versus Pseudorandom Generators in Constant Parallel Time A polynomial-stretch pseudorandom generator (PPRG) in NC$^0$(i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators ... more >>> TR22-165 | 22nd November 2022 TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley #### Separation of the factorization norm and randomized communication complexity In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate$\gamma_2$-factorization norm is a lower bound for these parameters and asked whether a stronger ... more >>> TR22-166 | 23rd November 2022 Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu #### Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly We study boolean constraint satisfaction problems (CSPs)$\mathrm{Max}\text{-}\mathrm{CSP}^f_n$for all predicates$f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer$v$and a list of constraints over$n$boolean variables, each obtained by applying$f$to a sequence of literals, we wish ... more >>> TR22-167 | 23rd November 2022 Mark Braverman, Subhash Khot, Dor Minzer #### Parallel Repetition for the GHZ Game: Exponential Decay We show that the value of the$n$-fold repeated GHZ game is at most$2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics. more >>> TR22-168 | 23rd November 2022 Zubayir Kazi #### A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture Revisions: 2 Abstract The Union Closed Set Conjecture states that if a set system X\subseteq\mathcal{P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower ... more >>> TR22-169 | 26th November 2022 Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman #### Extractors for Images of Varieties Revisions: 1 We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map$f : \mathbb{F}_q^r \to \mathbb{F}_q^n$to an element sampled uniformly at random from a$k$-dimensional variety$V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>> TR22-170 | 15th November 2022 Huck Bennett #### The Complexity of the Shortest Vector Problem Revisions: 1 Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the ... more >>> TR22-171 | 21st November 2022 ECCC Admin #### Record removed This record is a placeholder, replacing a record that was generated by mistake. more >>> TR22-172 | 2nd December 2022 Arkadev Chattopadhyay, Nikhil Mande, Swagato Sanyal, Suhail Sherif #### Lifting to Parity Decision Trees Via Stifling We show that the deterministic decision tree complexity of a (partial) function or relation$f$lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation$f \circ g$as long as the gadget$g$satisfies a property that we call stifling. We observe that several simple ... more >>> TR22-173 | 3rd December 2022 Paul Beame, Sajin Koroth #### On Disperser/Lifting Properties of the Index and Inner-Product Functions Revisions: 1 Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>> TR22-174 | 23rd November 2022 Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena #### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds Revisions: 2 Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric$f$-channels: In every round of the$f$-channel, each of its$n$parties decides to either ... more >>> TR22-175 | 16th November 2022 Samuel Epstein #### Derandomization Under Different Resource Constraints Revisions: 1 We provide another proof to the EL Theorem. We show the tradeoff between compressibility of codebooks and their communication capacity. A resource bounded version of the EL Theorem is proven. This is used to prove three instances of resource bounded derandomization. more >>> TR22-176 | 1st December 2022 Yaroslav Alekseev, Edward Hirsch #### The power of the Binary Value Principle The (extended) Binary Value Principle (eBVP, the equation$\sum x_i 2^{i-1} = -k$for$k > 0$and in the presence of$x_i^2=x_i$) has received a lot of attention recently, several lower bounds have been proved for it [Alekseev et al 20, Alekseev 21, Part and Tzameret 21]. Also ... more >>> TR22-177 | 7th December 2022 Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian #### Quantum Worst-Case to Average-Case Reductions for All Linear Problems We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>> TR22-178 | 8th December 2022 Ilias Diakonikolas, Christos Tzamos, Daniel Kane #### A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given {\em ... more >>> TR22-179 | 16th December 2022 Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang #### Round-vs-Resilience Tradeoffs for Binary Feedback Channels In a celebrated result from the$60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from$1/4$to$1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization ... more >>> TR22-180 | 15th December 2022 Aniruddha Biswas, Palash Sarkar #### A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture We describe a new construction of Boolean functions. A specific instance of our construction provides a 30-variable Boolean function having min-entropy/influence ratio to be 128/45 ? 2.8444 which is presently the highest known value of this ratio that is achieved by any Boolean function. Correspondingly, 128/45 is also presently the ... more >>> TR22-181 | 15th December 2022 Louis Golowich #### A New Berry-Esseen Theorem for Expander Walks We prove that the sum of$t$boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of$O(\lambda/t^{1/2-o(1)})$, where$\lambda$is the second largest eigenvalue of the random walk matrix in absolute value. To ... more >>> TR22-182 | 16th December 2022 Prahladh Harsha, Tulasi mohan Molli, A. Shankar #### Criticality of AC0-Formulae Revisions: 1 Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function$f : \{0, 1\}^n\to \{0, 1\}$is the minimum$\lambda \geq 1$such that for all positive integers$t$, $Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.$ . Håstad’s celebrated switching lemma ... more >>> TR22-183 | 19th December 2022 Lijie Chen #### New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity): 1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... more >>> TR22-184 | 28th December 2022 Oded Goldreich, Laliv Tauber #### Testing in the bounded-degree graph model with degree bound two Considering the bounded-degree graph model, we show that if the degree bound is two, then every graph property can be tested within query complexity that only depends on the proximity parameter. Specifically, the query complexity is${\rm poly}(1/\epsilon)$, where$\epsilon\$ denotes the proximity parameter.
The key observation is that a ... more >>>

TR22-185 | 29th December 2022

#### Randomized versus Deterministic Decision Tree Size

A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most the cube of its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been ... more >>>

TR22-186 | 31st December 2022
Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma

#### Power of Decision Trees with Monotone Queries

In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees – decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of ... more >>>

ISSN 1433-8092 | Imprint