Alternation-trading proofs, linear programming, and lower bounds

DOI10.1145/2493246.2493249MaRDI QIDQ2947580zbMATH OpenOpenAlexFDO

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/

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)

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

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)