Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > 2022:
All reports in year 2022:
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-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

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-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-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-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-071 | 13th May 2022
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

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-070 | 8th May 2022
Pranav Bisht, Ilya Volkovich

On Solving Sparse Polynomial Factorization Related Problems

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-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-068 | 5th May 2022
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

Sketching Approximability of (Weak) Monarchy Predicates

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-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-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-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-064 | 2nd May 2022
Deepanshu Kush, Shubhangi Saraf

Improved Low-Depth Set-Multilinear Circuit Lower Bounds

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

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-057 | 25th April 2022
Lijie Chen, Roei Tell

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

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-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-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-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-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-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-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-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-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-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-047 | 4th April 2022
Manik Dhar, Zeev Dvir

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

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-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-045 | 4th April 2022
Gil Cohen, Tal Yankovitz

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

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-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-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-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-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-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-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-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-037 | 10th March 2022
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

Robust Radical Sylvester-Gallai Theorem for Quadratics

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-036 | 10th March 2022
Agnes Schleitzer, Olaf Beyersdorff

Classes of Hard Formulas for QBF Resolution

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

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-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-031 | 16th February 2022
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Transparency Beyond VNP in the Monotone Setting

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-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-029 | 27th February 2022
Anthony Leverrier, Gilles Zémor

Quantum Tanner codes

Revisions: 1

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-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-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-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-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-024 | 17th February 2022
Louis Golowich, Salil Vadhan

Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

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-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-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-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-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-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-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-017 | 15th February 2022
Ron D. Rothblum, Prashant Nalini Vasudevan

Collision-Resistance from Multi-Collision-Resistance

Revisions: 1

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-016 | 15th February 2022
Artur Ignatiev, Ivan Mihajlin, Alexander Smal

Super-cubic lower bound for generalized Karchmer-Wigderson games

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-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-014 | 8th February 2022
Joshua Cook, Dana Moshkovitz

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

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-013 | 5th February 2022
Nader Bshouty, Oded Goldreich

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-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-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-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-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-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-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-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-005 | 11th January 2022
Anup Rao

Sunflowers: from soil to oil

Revisions: 2

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-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-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-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-001 | 28th December 2021
Yogesh Dahiya, Meena Mahajan

On (Simple) Decision Tree Rank

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




ISSN 1433-8092 | Imprint