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-127 | 5th September 2025
Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche

Proof Systems That Tightly Characterise Model Counting Algorithms

Several proof systems for model counting have been introduced in recent years, mainly in an attempt to model #SAT solving and to allow proof logging of solvers. We reexamine these different approaches and show that: (i) with slight adaptations, the conceptually quite different proof models of the dynamic system MICE ... more >>>


TR25-126 | 2nd September 2025
Amey Bhangale, Silas Richelson

Plane vs. Plane Low Degree Test

In this work, we give an optimal analysis of the plane versus plane test of Raz and Safra (STOC'97). More specifically, consider a table $T$ that assigns every plane $P$ from $\mathbb{F}_q^m$ a bivariate degree $d$ polynomial. The goal is to check if these polynomials are restrictions of a global ... more >>>


TR25-125 | 20th August 2025
Yanyi Liu, Rafael Pass

Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF).
Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint