3 papers
cs.CC2026
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…
cs.CC2024
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…
cs.CC2024
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…