All reports in year 2022:

__
TR22-076
| 16th May 2022
__

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

__
TR22-075
| 21st May 2022
__

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

__
TR22-074
| 20th May 2022
__

Michael Saks, Rahul Santhanam#### On Randomized Reductions to the Random Strings

__
TR22-073
| 18th May 2022
__

Itay Kalev, Amnon Ta-Shma#### Unbalanced Expanders from Multiplicity Codes

__
TR22-072
| 15th May 2022
__

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

__
TR22-071
| 13th May 2022
__

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay#### Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

__
TR22-070
| 8th May 2022
__

Pranav Bisht, Ilya Volkovich#### On Solving Sparse Polynomial Factorization Related Problems

__
TR22-069
| 28th April 2022
__

Silas Richelson, Sourya Roy#### List-Decoding Random Walk XOR Codes Near the Johnson Bound

Revisions: 1

__
TR22-068
| 5th May 2022
__

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy#### Sketching Approximability of (Weak) Monarchy Predicates

__
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

__
TR22-066
| 4th May 2022
__

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy#### On sketching approximations for symmetric Boolean CSPs

__
TR22-065
| 3rd May 2022
__

Madhu Sudan#### Streaming and Sketching Complexity of CSPs: A survey

Revisions: 1

__
TR22-064
| 2nd May 2022
__

Deepanshu Kush, Shubhangi Saraf#### Improved Low-Depth Set-Multilinear Circuit Lower Bounds

__
TR22-063
| 30th April 2022
__

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans#### Fast Multivariate Multipoint Evaluation Over All Finite Fields

__
TR22-062
| 2nd May 2022
__

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

__
TR22-061
| 30th April 2022
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: I

__
TR22-060
| 27th April 2022
__

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

__
TR22-059
| 27th April 2022
__

Siddhesh Chaubal, Anna Gal#### Diameter versus Certificate Complexity of Boolean Functions

__
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

__
TR22-057
| 25th April 2022
__

Lijie Chen, Roei Tell#### When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems

__
TR22-056
| 18th April 2022
__

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand#### Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

__
TR22-055
| 23rd April 2022
__

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret#### Simple Hard Instances for Low-Depth Algebraic Proofs

__
TR22-054
| 21st April 2022
__

Anastasia Sofronova, Dmitry Sokolov#### A Lower Bound for $k$-DNF Resolution on Random CNF Formulas via Expansion

__
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

__
TR22-052
| 18th April 2022
__

Tal Herman, Guy Rothblum#### Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

__
TR22-051
| 18th April 2022
__

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida#### Low Degree Testing over the Reals

__
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

__
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

__
TR22-048
| 4th April 2022
__

Hanlin Ren, Rahul Santhanam, Zhikun Wang#### On the Range Avoidance Problem for Circuits

__
TR22-047
| 4th April 2022
__

Manik Dhar, Zeev Dvir#### Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

__
TR22-046
| 4th April 2022
__

Dmitry Itsykson, Artur Riazanov#### Automating OBDD proofs is NP-hard

__
TR22-045
| 4th April 2022
__

Gil Cohen, Tal Yankovitz#### Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

__
TR22-044
| 4th April 2022
__

Meghal Gupta, Naren Manoj#### An Optimal Algorithm for Certifying Monotone Functions

__
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

__
TR22-042
| 31st March 2022
__

Vikraman Arvind, Pushkar Joglekar#### Matrix Polynomial Factorization via Higman Linearization

__
TR22-041
| 23rd March 2022
__

TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein#### Boolean functions with small approximate spectral norm

__
TR22-040
| 10th March 2022
__

Benjamin Böhm, Tomáš Peitl, Olaf Beyersdorff#### Should decisions in QCDCL follow prefix order?

__
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

__
TR22-038
| 13th March 2022
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### Lower bounds for Polynomial Calculus with extension variables over finite fields

Revisions: 1

__
TR22-037
| 10th March 2022
__

Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta#### Robust Radical Sylvester-Gallai Theorem for Quadratics

__
TR22-036
| 10th March 2022
__

Agnes Schleitzer, Olaf Beyersdorff#### Classes of Hard Formulas for QBF Resolution

__
TR22-035
| 7th March 2022
__

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff#### A Characterization of Multiclass Learnability

__
TR22-034
| 3rd March 2022
__

Chin Ho Lee, Edward Pyne, Salil Vadhan#### Fourier Growth of Regular Branching Programs

__
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

Comments: 2

__
TR22-032
| 1st March 2022
__

Iftach Haitner, Noam Mazor, Jad Silbak#### Incompressiblity and Next-Block Pseudoentropy

__
TR22-031
| 16th February 2022
__

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse#### Transparency Beyond VNP in the Monotone Setting

__
TR22-030
| 18th February 2022
__

Aniruddha Biswas, Palash Sarkar#### On The ''Majority is Least Stable'' Conjecture.

Revisions: 1

__
TR22-029
| 27th February 2022
__

Anthony Leverrier, Gilles Zémor#### Quantum Tanner codes

Revisions: 1

__
TR22-028
| 23rd February 2022
__

Dan Karliner, Roie Salama, Amnon Ta-Shma#### The plane test is a local tester for Multiplicity Codes

__
TR22-027
| 22nd February 2022
__

Guy Blanc, Dean Doron#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

__
TR22-026
| 17th February 2022
__

James Cook, Ian Mertz#### Trading Time and Space in Catalytic Branching Programs

__
TR22-025
| 15th February 2022
__

Oliver Korten#### Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

Revisions: 3

__
TR22-024
| 17th February 2022
__

Louis Golowich, Salil Vadhan#### Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

__
TR22-023
| 19th February 2022
__

Erfan Khaniki#### Nisan--Wigderson generators in Proof Complexity: New lower bounds

__
TR22-022
| 18th February 2022
__

Vikraman Arvind, Pushkar Joglekar#### On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revisions: 3

__
TR22-021
| 19th February 2022
__

Xin Lyu#### Improved Pseudorandom Generators for $\mathrm{AC}^0$ Circuits

__
TR22-020
| 18th February 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar#### Worst-Case to Average-Case Reductions via Additive Combinatorics

__
TR22-019
| 17th February 2022
__

Guangxu Yang, Jiapeng Zhang#### Simulation Methods in Communication Lower Bounds, Revisited

__
TR22-018
| 15th February 2022
__

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao#### Further Collapses in TFNP

__
TR22-017
| 15th February 2022
__

Ron D. Rothblum, Prashant Nalini Vasudevan#### Collision-Resistance from Multi-Collision-Resistance

Revisions: 1

__
TR22-016
| 15th February 2022
__

Artur Ignatiev, Ivan Mihajlin, Alexander Smal#### Super-cubic lower bound for generalized Karchmer-Wigderson games

__
TR22-015
| 12th February 2022
__

Mika Göös, Stefan Kiefer, Weiqiang Yuan#### Lower Bounds for Unambiguous Automata via Communication Complexity

__
TR22-014
| 8th February 2022
__

Joshua Cook, Dana Moshkovitz#### Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

__
TR22-013
| 5th February 2022
__

Nader Bshouty, Oded Goldreich#### On properties that are non-trivial to test

__
TR22-012
| 2nd February 2022
__

Anup Rao, Oscar Sprumont#### On List Decoding Transitive Codes From Random Errors

__
TR22-011
| 25th January 2022
__

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen#### Public-Key Encryption from Continuous LWE

__
TR22-010
| 18th January 2022
__

Marshall Ball, Dana Dachman-Soled, Julian Loss#### (Nondeterministic) Hardness vs. Non-Malleability

__
TR22-009
| 17th January 2022
__

C. Ramya, Anamay Tengse#### On Finer Separations between Subclasses of Read-once Oblivious ABPs

__
TR22-008
| 14th January 2022
__

Gil Cohen, Dean Doron, Ori Sberlo#### Approximating Large Powers of Stochastic Matrices in Small Space

__
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

__
TR22-006
| 12th January 2022
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

__
TR22-005
| 11th January 2022
__

Anup Rao#### Sunflowers: from soil to oil

Revisions: 2

__
TR22-004
| 3rd January 2022
__

Silas Richelson, Sourya Roy#### Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

__
TR22-003
| 4th January 2022
__

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere#### On Semi-Algebraic Proofs and Algorithms

Revisions: 1

__
TR22-002
| 11th December 2021
__

Sravanthi Chede, Anil Shukla#### Extending Merge Resolution to a Family of Proof Systems

__
TR22-001
| 28th December 2021
__

Yogesh Dahiya, Meena Mahajan#### On (Simple) Decision Tree Rank

Hunter Monroe

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

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

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

Michael Saks, Rahul Santhanam

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

Itay Kalev, Amnon Ta-Shma

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

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

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

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

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

Pranav Bisht, Ilya Volkovich

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

Silas Richelson, Sourya Roy

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

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

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

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

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

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

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

Madhu Sudan

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

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

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

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

Paolo Liberatore

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

Amey Bhangale, Subhash Khot, Dor Minzer

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

Nikolay Vereshchagin

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

Siddhesh Chaubal, Anna Gal

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

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

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

Lijie Chen, Roei Tell

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 >>>Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

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

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

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

Anastasia Sofronova, Dmitry Sokolov

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

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

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

Tal Herman, Guy Rothblum

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

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

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

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

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

Xinyu Mao, Noam Mazor, Jiapeng Zhang

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

Hanlin Ren, Rahul Santhanam, Zhikun Wang

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

Manik Dhar, Zeev Dvir

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

Dmitry Itsykson, Artur Riazanov

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

Gil Cohen, Tal Yankovitz

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

Meghal Gupta, Naren Manoj

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

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

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

Vikraman Arvind, Pushkar Joglekar

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

TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

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

Benjamin Böhm, Tomáš Peitl, Olaf Beyersdorff

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

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

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

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

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

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

Agnes Schleitzer, Olaf Beyersdorff

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

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff

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

Chin Ho Lee, Edward Pyne, Salil Vadhan

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

Ivan Mihajlin, Anastasia Sofronova

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

Iftach Haitner, Noam Mazor, Jad Silbak

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 >>>Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

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

Aniruddha Biswas, Palash Sarkar

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 >>>Anthony Leverrier, Gilles Zémor

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

Dan Karliner, Roie Salama, Amnon Ta-Shma

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

Guy Blanc, Dean Doron

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

James Cook, Ian Mertz

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

Oliver Korten

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

Louis Golowich, Salil Vadhan

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

Erfan Khaniki

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

Vikraman Arvind, Pushkar Joglekar

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

Xin Lyu

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

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

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

Guangxu Yang, Jiapeng Zhang

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

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

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

Ron D. Rothblum, Prashant Nalini Vasudevan

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

Artur Ignatiev, Ivan Mihajlin, Alexander Smal

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

Mika Göös, Stefan Kiefer, Weiqiang Yuan

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

Joshua Cook, Dana Moshkovitz

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

Nader Bshouty, Oded Goldreich

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

Anup Rao, Oscar Sprumont

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

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

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

Marshall Ball, Dana Dachman-Soled, Julian Loss

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

C. Ramya, Anamay Tengse

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

Gil Cohen, Dean Doron, Ori Sberlo

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

Halley Goldberg, Valentine Kabanets

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

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

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

Anup Rao

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 >>>Silas Richelson, Sourya Roy

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

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

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

Sravanthi Chede, Anil Shukla

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

Yogesh Dahiya, Meena Mahajan

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