2 papers
cs.CC2026
Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries
Hanlin Ren, Ryan Williams
We prove a near-maximum () circuit lower bound for the complexity class , corresponding to exponential time with access to a promis…
cs.CC2026
A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira +1
In this work, we propose a new bounded arithmetic theory, denoted , designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer scie…