Hardness amplification in proof complexity

DOI10.1145/1806689.1806703MaRDI QIDQ2875135zbMATH OpenOpenAlexFDO

Authors Trinh Huynh, Toniann Pitassi, Paul Beame

Publication date 13 August 2014

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

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

zbMATH Keywords

communication complexityproof complexity

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Rank bounds and integrality gaps for cutting planes procedures
• On the rank of cutting-plane proof systems
• Monotone circuit lower bounds from resolution
• scientific article; zbMATH DE number 1916823
• On the relative complexity of resolution refinements and cutting planes proof systems

Cited in

(12)

• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• Knowledge compilation languages as proof systems
• Simulation theorems via pseudo-random properties
• On uniform amplification of hardness in NP
• Communication lower bounds via critical block sensitivity
• Rank bounds for a hierarchy of Lovász and Schrijver
• DRAT and propagation redundancy proofs without new variables
• Stabbing planes
• Hardness Amplification Proofs Require Majority
• Using Nondeterminism to Amplify Hardness
• Superpolynomial lower bounds against low-depth algebraic circuits
• Improved hardness amplification in NP

This page was built for publication: Hardness amplification in proof complexity

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