On the virtue of succinct proofs

DOI10.1145/2213977.2214000zbMath1286.68234OpenAlexW2021972008MaRDI QIDQ5415478

Trinh N. D. Huynh, Jakob Nordström

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2213977.2214000

zbMATH Keywords

sizecutting planeslengthresolutionpolynomial calculusproof complexityspacetrade-offsPCR

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Related Items (17)

Cumulative Space in Black-White Pebbling and Resolution ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Deterministic Communication vs. Partition Number ⋮ Dag-like communication and its applications ⋮ Space Complexity in Polynomial Calculus ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Extension Complexity of Independent Set Polytopes ⋮ Simulation theorems via pseudo-random properties ⋮ Adventures in monotone complexity and TFNP ⋮ Unnamed Item ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Resolution over linear equations modulo two ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Large clique is hard on average for resolution

This page was built for publication: On the virtue of succinct proofs