2 citations · 3 across the 6 of their papers we have counts for
6 papers
Meta-Mathematics of Algebraic Complexity
Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu +2
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 lo…
The Weak Rank Principle: Lower Bounds and Applications
Michal Garl\'\ik, Svyatoslav Gryaznov, Hanlin Ren +1
Given two symbolic matrices and of dimensions and , the *weak rank principle* (WRank) states the equation is unsatisfiable when and ra…
Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
Svyatoslav Gryaznov, Sergei Ovcharov, Artur Riazanov
We consider the proof system Res() introduced by Itsykson and Sokolov (Ann. Pure Appl. Log.'20), which is an extension of the resolution proof system and operates with disj…
Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
Svyatoslav Gryaznov, Navid Talebanfard
A major open problem in proof complexity is to demonstrate that random 3-CNFs with a linear number of clauses require super-polynomial size refutations in bounded-depth Frege syste…
Linear Branching Programs and Directional Affine Extractors
Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard
A natural model of read-once linear branching programs is a branching program where queries are linear forms, and along each path, the queries are linearly independe…
A Variant of the VC-dimension with Applications to Depth-3 Circuits
Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard
We introduce the following variant of the VC-dimension. Given and a positive integer , we define to be the size of the largest subset…