Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR26-072 | 7th May 2026
Robert Andrews, Abhibhav Garg

An Improved Construction of Variety-Evasive Subspace Families

We study the question of explicitly constructing variety-evasive subspace families, a pseudorandom primitive introduced by Guo (Computational Complexity 2024) that generalizes both hitting sets and lossless rank condensers. Roughly speaking, a variety-evasive subspace family $\mathcal{H}$ is a collection of subspaces such that for every algebraic variety $V$ in a fixed ... more >>>


TR26-071 | 8th May 2026
Archit Chauhan, Rohit Gurjar, Kilian Rothmund, Thomas Thierauf

Planarizing Gadgets for $(k,l)$-tight Graphs Do Not Exist

The problem of recognizing $(k,l)$-tight graphs is a fundamental problem that has close connections to well studied problems
like graph rigidity. The problem is better understood for planar graphs as compared to general graphs. For example, deterministic
NC-algorithms for the problem are known for planar graphs, but no such ... more >>>


TR26-070 | 5th May 2026
Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Hard CNF Instances for Ideal Proof Systems

Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments. In particular, Forbes, Shpilka, Tzameret, and Wigderson (Theory Comput. 2021) developed the main lower-bound frameworks for restricted IPS fragments, ... more >>>



Next next


ISSN 1433-8092 | Imprint