Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > 2025:
All reports in year 2025:
TR25-041 | 6th April 2025
Igor Carboni Oliveira

Meta-Mathematics of Computational Complexity Theory

We survey results on the formalization and independence of mathematical statements related to major open problems in computational complexity theory. Our primary focus is on recent findings concerning the (un)provability of complexity bounds within theories of bounded arithmetic. This includes the techniques employed and related open problems, such as the ... more >>>


TR25-040 | 6th April 2025
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

Parallel Repetition for 3-Player XOR Games

In a $3$-XOR game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \mu$ where $\mu$ is a probability distribution over $\Sigma\times\Gamma\times\Phi$, and a map $t\colon \Sigma\times\Gamma\times\Phi\to\mathcal{A}$ for a finite Abelian group $\mathcal{A}$ defining a constraint. The verifier sends the questions $x$, $y$ and $z$ to the players Alice, Bob and Charlie ... more >>>


TR25-039 | 31st March 2025
Klim Efremenko, Dmitry Itsykson

Amortized Closure and Its Applications in Lifting for Resolution over Parities

The notion of closure of a set of linear forms, first introduced by Efremenko, Garlik, and Itsykson [EGI-STOC-24], has proven instrumental in proving lower bounds on the sizes of regular and bounded-depth Res($\oplus)$ refutations [EGI-STOC-24, AI-STOC-25]. In this work, we present amortized closure, an enhancement that retains the properties of ... more >>>


TR25-038 | 4th April 2025
Nikolai Chukhin, Alexander Kulikov, Ivan Mihajlin, Arina Smirnova

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond

Revisions: 1

Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing ... more >>>


TR25-037 | 31st March 2025
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

Uniform Bounds on Product Sylvester-Gallai Configurations

Revisions: 1

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let $\mathbb{K}$ be an algebraically closed field of characteristic zero, and let $\mathcal{F} = \{F_1, \ldots, F_m\} \subset \mathbb{K}[x_1, \ldots, x_N]$ denote a collection of irreducible homogeneous polynomials of degree at most $d$, where each $F_i$ is ... more >>>


TR25-036 | 29th March 2025
Siddharth Iyer

Lifting for Arbitrary Gadgets

We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions $f: \{0,1\}^n\to \{0,1\}$ and $g : \mathcal{X} \times \mathcal{Y}\to \{0,1\}$, denote $f\circ g(x,y) := f(g(x_1,y_1),\ldots,g(x_n,y_n))$. We show that for any $f$ with sensitivity $s$ and any $g$,
\[D(f\circ g) \geq s\cdot \bigg(\frac{\Omega(D(g))}{\log rk(g)} - \log rk(g)\bigg),\]
where ... more >>>


TR25-035 | 25th March 2025
Abhibhav Garg, Rafael Mendes de Oliveira, Nitin Saxena

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals

A central question in mathematics and computer science is the question of determining whether a given ideal $I$ is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible. The case of principal ideals (i.e., $m=1$) corresponds to the more familiar absolute irreducibility testing of polynomials, ... more >>>


TR25-034 | 20th March 2025
Neha Kuntewar, Jayalal Sarma

Range Avoidance in Boolean Circuits via Turan-type Bounds

Given a circuit $C : \{0,1\}^n \to \{0,1\}^m$ from a circuit class $F$, with $m > n$, finding a $y \in \{0,1\}^m$ such that $\forall x \in \{0,1\}^n$, $C(x) \ne y$, is the range avoidance problem (denoted by $F$-AVOID). It is known that deterministic polynomial time algorithms (even with access ... more >>>


TR25-033 | 18th March 2025
Bruno Pasqualotto Cavalar, Igor Oliveira

Boolean Circuit Complexity and Two-Dimensional Cover Problems

We reduce the problem of proving deterministic and nondeterministic Boolean circuit size lower bounds to the analysis of certain two-dimensional combinatorial cover problems. This is obtained by combining results of Razborov (1989), Karchmer (1993), and Wigderson (1993) in the context of the fusion method for circuit lower bounds with the ... more >>>


TR25-032 | 21st March 2025
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erd?s-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on ... more >>>


TR25-031 | 19th March 2025
Shuichi Hirahara, Nobutaka Shimizu

Error-Correction of Matrix Multiplication Algorithms

Given an efficient algorithm that correctly computes a tiny fraction of the entries of the matrix multiplication of a small fraction of two matrices, can one design an efficient algorithm that computes matrix multiplication exactly for all the matrices? In this paper, we present such ``worst-case exact to average-case approximate'' ... more >>>


TR25-030 | 15th March 2025
Oliver Korten, Toniann Pitassi, Russell Impagliazzo

Stronger Cell Probe Lower Bounds via Local PRGs

In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... more >>>


TR25-029 | 14th March 2025
Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach ... more >>>


TR25-028 | 12th March 2025
Satyadev Nandakumar, Subin Pulari, Akhil S, Suronjona Sarma

One-Way Functions and Polynomial Time Dimension

This paper demonstrates a duality between the non-robustness of polynomial time dimension and the existence of one-way functions. Polynomial-time dimension (denoted $\mathrm{cdim}_\mathrm{P}$) quantifies the density of information of infinite sequences using polynomial time betting algorithms called $s$-gales. An alternate quantification of the notion of polynomial time density of information is ... more >>>


TR25-027 | 9th February 2025
Kuan Cheng, Ruiyang Wu

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions

We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs), which are key problems towards answering the fundamental open question $\mathbf{BPL} ?{=} \mathbf{L}$.
Denote $n$ and $w$ as the length and the width of a ROBP.
We have the following results.

For standard ROBPs, there exists an ... more >>>


TR25-026 | 25th February 2025
Siu On Chan, Hiu Tsun Ng

How Random CSPs Fool Hierarchies: II

Relaxations for the constraint satisfaction problem (CSP) include bounded width (BW), linear program (LP), semidefinite program (SDP), affine integer program (AIP), and their combinations. Tightening relaxations systematically leads to hierarchies and stronger algorithms. For LP+AIP and SDP+AIP hierarchies, various lower bounds were shown by Ciardo and Živný (STOC 2023, STOC ... more >>>


TR25-025 | 10th March 2025
Hugo Aaronson, Gaia Carenini, Atreyi Chanda

Property Testing in Bounded Degree Hypergraphs

We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex ... more >>>


TR25-024 | 9th March 2025
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Lower Bounds Beyond DNF of Parities

We consider a subclass of $\mathbf{AC}^0[2]$ circuits that simultaneously captures $\mathrm{DNF} \circ \mathrm{Xor}$ and depth-$3$ $\mathbf{AC}^0$ circuits. For this class we show a technique for proving lower bounds inspired by the top-down approach. We give lower bounds for the middle slice function, inner product function, and affine dispersers.

more >>>

TR25-023 | 24th February 2025
Benny Applebaum, Eliran Kachlon

How to Share an NP Statement or Combiners for Zero-Knowledge Proofs

In Crypto'19, Goyal, Jain, and Sahai (GJS) introduced the elegant notion of *secret-sharing of an NP statement* (NPSS). Roughly speaking, a $t$-out-of-$n$ secret sharing of an NP statement is a reduction that maps an instance-witness pair to $n$ instance-witness pairs such that any subset of $(t-1)$ reveals no information about ... more >>>


TR25-022 | 3rd March 2025
Harm Derksen, Chin Ho Lee, Emanuele Viola

Boosting uniformity in quasirandom groups: fast and simple

We study the communication complexity of multiplying $k\times t$
elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead
model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$.
This is an exponential improvement over previous work, and matches
the state-of-the-art in the area.

Relatedly, we show that the convolution ... more >>>


TR25-021 | 3rd March 2025
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

Pseudorandomness, symmetry, smoothing: II

We prove several new results on the Hamming weight of bounded uniform and small-bias distributions.

We exhibit bounded-uniform distributions whose weight is anti-concentrated, matching existing concentration inequalities. This construction relies on a recent result in approximation theory due to Erdéyi (Acta Arithmetica 2016). In particular, we match the classical tail ... more >>>


TR25-020 | 3rd March 2025
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

Pseudorandomness, symmetry, smoothing: I

We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that

... more >>>

TR25-019 | 27th February 2025
Michal Koucky, Ian Mertz, Edward Pyne, Sasha Sami

Collapsing Catalytic Classes

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, ... more >>>


TR25-018 | 27th January 2025
Neekon Vafa, Vinod Vaikuntanathan

Symmetric Perceptrons, Number Partitioning and Lattices

The symmetric binary perceptron ($\mathrm{SBP}_{\kappa}$) problem with parameter $\kappa : \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq ... more >>>


TR25-017 | 24th February 2025
Ryan Williams

Simulating Time in Square-Root Space

We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time $t$ in $O(t/\log t)$ space from 50 years ago [FOCS 1975, ... more >>>


TR25-016 | 9th February 2025
James Cook

Another way to show $\mathrm{BPL} \subseteq \mathrm{CL}$ and $\mathrm{BPL} \subseteq \mathrm{P}$

We present a new technique for using catalytic space to simulate space-bounded randomized algorithms.
Allocate one bit on the catalytic tape for each configuration of a randomized machine.
Simulate the machine several times.
Each time it requests a random bit, use the bit from the catalytic tape corresponding to its ... more >>>


TR25-015 | 20th February 2025
Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Ashutosh Shankar

An exposition of recent list-size bounds of FRS Codes

In the last year, there have been some remarkable improvements in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes. Starting from the work on Kopparty, Ron-Zewi, Saraf and Wootters (and subsequent simplifications due to Tamo), we have had dramatic improvements in the list-size bounds of FRS ... more >>>


TR25-014 | 18th February 2025
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena

Information Dissemination via Broadcasts in the Presence of Adversarial Noise

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where $n$ parties, each holding an input bit, wish to know each other's input. For this, they communicate in rounds, where, in each round, one designated party sends ... more >>>


TR25-013 | 18th February 2025
Raghuvansh Saxena, Yael Tauman Kalai

Polynomial Size, Short-Circuit Resilient Circuits for NC

We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to $\epsilon d$ gates on every root-to-leaf path ... more >>>


TR25-012 | 17th February 2025
Dean Doron, Ori Fridman

Bit-Fixing Extractors for Almost-Logarithmic Entropy

An oblivious bit-fixing source is a distribution over $\{0,1\}^n$, where $k$ bits are uniform and independent and the rest $n-k$ are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity ... more >>>


TR25-011 | 17th February 2025
Oded Goldreich, Roei Tell

Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems

Pseudodeterministic algorithms are probabilistic algorithms that solve search problems but do so by always providing the same (``canonical'') solution to a given instance, except with small probability.
While the complexity theoretic implications of pseudodeterministic algorithms were explored in the past, we suggest to conduct this exploration within the framework ... more >>>


TR25-010 | 11th February 2025
Marshall Ball, Lijie Chen, Roei Tell

Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)

The question of optimal derandomization, introduced by Doron et. al (JACM 2022), garnered significant recent attention. Works in recent years showed conditional superfast derandomization algorithms, as well as conditional impossibility results, and barriers for obtaining superfast derandomization using certain black-box techniques.

Of particular interest is the extreme high-end, which ... more >>>


TR25-009 | 7th February 2025
Marco Aldi, Sevag Gharibian, Dorian Rudolph

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash ... more >>>


TR25-008 | 9th February 2025
Shubhangi Saraf, Devansh Shringi

Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$

In this paper, we give the first subexponential (and in fact quasi-polynomial time) reconstruction algorithm for depth 3 circuits of top fan-in 3 ($\Sigma\Pi\Sigma(3)$ circuits) over the fields $\mathbb{R}$ and $\mathbb C$. Concretely, we show that given blackbox access to an $n$-variate polynomial $f$ computed by a $\Sigma\Pi\Sigma(3)$ circuit of ... more >>>


TR25-007 | 5th February 2025
Amir Shpilka

Improved Debordering of Waring Rank

We prove that if a degree-$d$ homogeneous polynomial $f$ has border Waring rank $\underline{\mathrm{WR}}({f}) = r$, then its Waring rank is bounded by
\[
{\mathrm{WR}}({f}) \leq d \cdot r^{O(\sqrt{r})}.
\]
This result significantly improves upon the recent bound ${\mathrm{WR}}({f}) \leq d \cdot 4^r$ established in [Dutta, Gesmundo, Ikenmeyer, Jindal, ... more >>>


TR25-006 | 4th February 2025
Subhash Khot, Kunal Mittal

Biased Linearity Testing in the 1% Regime

We study linearity testing over the $p$-biased hypercube $(\{0,1\}^n, \mu_p^{\otimes n})$ in the 1% regime. For a distribution $\nu$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \text{ (mod 2)} \}$, with marginal distribution $\mu_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(\nu)$ proceeds as follows: Given query access to a function ... more >>>


TR25-005 | 31st January 2025
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

SDPs and Robust Satisfiability of Promise CSP

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be ... more >>>


TR25-004 | 17th January 2025
Songhua He

A note on a hierarchy theorem for promise-BPTIME

We prove a time hierarchy theorem for the promise-BPTIME. This is considered to be a folklore problem and was thought to follow from the existence of complete problems or through direct diagonalization. We observe that neither argument carries through in some immediate way in the promise version. However, the hierarchy ... more >>>


TR25-003 | 16th January 2025
William Hoza

Fooling Near-Maximal Decision Trees

For any constant $\alpha > 0$, we construct an explicit pseudorandom generator (PRG) that fools $n$-variate decision trees of size $m$ with error $\epsilon$ and seed length $(1 + \alpha) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$. For context, one can achieve seed length $(2 + o(1)) \cdot ... more >>>


TR25-002 | 14th January 2025
Vinayak Kumar

New Pseudorandom Generators and Correlation Bounds Using Extractors

We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalizations of structured low-degree $F_2$-polynomials that we did not have correlation bounds for before. In particular:

1. We construct a PRG for width-2 $poly(n)$-length branching programs which read $d$ bits ... more >>>


TR25-001 | 12th January 2025
Benny Applebaum, Oded Nir

The Meta-Complexity of Secret Sharing

A secret-sharing scheme allows the distribution of a secret $s$ among $n$ parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about $s$. The collection of authorized/unauthorized sets is defined by a monotone function $f: \{0,1\}^n \rightarrow \{0,1\}$. ... more >>>




ISSN 1433-8092 | Imprint