Alternation-trading proofs, linear programming, and lower bounds

DOI10.1145/2493246.2493249zbMATH Open1322.68091OpenAlexW2153788141MaRDI QIDQ2947580FDOQ2947580

Authors: Ryan Williams 

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2494/

Recommendations

• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Alternation Trading Proofs and Their Limitations
• Limits on alternation trading proofs for time-space lower bounds
• scientific article; zbMATH DE number 2156275
• Time-space lower bounds for satisfiability

zbMATH Keywords

linear programminglower boundsalternationtime-space trade-offs

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (4)

• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Conditional lower bounds for failed literals and related techniques
• Alternation Trading Proofs and Their Limitations
• Limits on alternation trading proofs for time-space lower bounds

This page was built for publication: Alternation-trading proofs, linear programming, and lower bounds

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