Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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



previous PreviousNext next


ISSN 1433-8092 | Imprint