Alternation Trading Proofs and Their Limitations

DOI10.1007/978-3-642-40313-2_1MaRDI QIDQ2849894zbMATH OpenOpenAlexFDO

Authors Samuel R. Buss

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40313-2_1

zbMATH Keywords

alternation tradingindirect diagonalizationlower boundssatisfiability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Limits on alternation trading proofs for time-space lower bounds
• Alternation-trading proofs, linear programming, and lower bounds
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Alternative trading
• Strategy-proofness, core, and sequential trade
• Provably linkable trading
• The fundamental theorem of derivative trading -- exposition, extensions and experiments
• Limits of semistatic trading strategies
• scientific article; zbMATH DE number 1066452
• Formalizing the trading theorem in Coq

Cited in

(4)

• Alternative trading
• Alternation-trading proofs, linear programming, and lower bounds
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Limits on alternation trading proofs for time-space lower bounds

This page was built for publication: Alternation Trading Proofs and Their Limitations

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