3 papers
cs.CC2026
Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
Jiawei Li, Yuhao Li, Hanlin Ren
We study the *refuter* problems for proof complexity lower bounds. Suppose is a hard tautology that does not admit any length- proof in some proof system . In the corres…
cs.CC2026
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
Hanlin Ren, Yichuan Wang, Yan Zhong
Given a circuit with , the *range avoidance* problem () asks to output a string that is not in the range of $G…
cs.CC2025
Total Search Problems in
Noah Fleming, Stefan Grosser, Siddhartha Jain +4
We initiate a systematic study of , the class of total search problems solvable by polynomial time randomized algorithms. contains a variety o…