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

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