Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SVYATOSLAV GRYAZNOV:
All reports by Author Svyatoslav Gryaznov:

TR26-316 | 10th November 2026
Yaroslav Alekseev, Svyatoslav Gryaznov, Dmitry Itsykson, Toniann Pitassi, Robert Robere, Iddo Tzameret

Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]-Frege

We establish a collection of new size lower bounds against fairly strong algebraic-Boolean propositional proof systems, from depth-3 semantic polynomial calculus for CNFs, up to semantic $AC^0[2]$-Frege in the regime of deep formulas, as follows:

(1) $\Sigma\Pi\Sigma$-PC: Exponential lower bound against semantic $\Sigma\Pi\Sigma$-PC over $F_2$, namely, polynomial calculus operating with ... more >>>


TR26-277 | 26th October 2026
Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam, Iddo Tzameret

Meta-Mathematics of Algebraic Complexity

We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while ... more >>>


TR26-133 | 7th August 2026
Michal Garlik, Svyatoslav Gryaznov, Hanlin Ren, Iddo Tzameret

The Weak Rank Principle: Lower Bounds and Applications

Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, respectively, the *rank principle* states that when $m = n+1$ and $A$ is a scalar matrix of rank $n+1$, the equation $XY = A$ is unsatisfiable. When $m$ is arbitrarily larger than $n$ and $A$ has ... more >>>




ISSN 1433-8092 | Imprint