Lower bounds for regular resolution over parities

DOI10.1137/24M1696640MaRDI QIDQ6939714zbMATH OpenFDO

Authors Klim Efremenko, Michal Garlík, Dmitry Itsykson

Publication date 21 August 2025

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsproof complexityregular resolutionresolution over linear equationsbinary pigeonhole principle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

This page was built for publication: Lower bounds for regular resolution over parities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6939714)