Unconditional Lower Bounds against Advice

DOI10.1007/978-3-642-02927-1_18MaRDI QIDQ3638035zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Rahul Santhanam, Lance Fortnow

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Nonuniform lower bounds for exponential time classes
• New non-uniform lower bounds for uniform classes
• scientific article; zbMATH DE number 1318518
• Circuit lower bounds for Merlin-Arthur classes
• Bounding the complexity of advice functions

Cited in

(11)

• Bounding the complexity of advice functions
• Nonuniform lower bounds for exponential time classes
• scientific article; zbMATH DE number 1318518 (Why is no real title available?)
• Identifying an honest \(\mathrm{EXP}^{\mathrm{NP}}\) oracle among many
• scientific article; zbMATH DE number 1405686 (Why is no real title available?)
• Randomness and intractability in Kolmogorov complexity
• New non-uniform lower bounds for uniform classes
• On the consistency of stronger lower bounds for \(\mathsf{NEXP}\)
• Avoiding simplicity is complex
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Languages to diagonalize against advice classes

This page was built for publication: Unconditional Lower Bounds against Advice

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