Hardness amplification in proof complexity

DOI10.1145/1806689.1806703zbMath1293.03030OpenAlexW2160909640MaRDI QIDQ2875135

Toniann Pitassi, Trinh N. D. Huynh, P. W. 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)

Related Items (6)

Communication Lower Bounds via Critical Block Sensitivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Simulation theorems via pseudo-random properties

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