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
• Superpolynomial circuits, almost sparse oracles and the exponential hierarchy
• 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
• Superpolynomial circuits, almost sparse oracles and the exponential hierarchy
• Identifying an honest \(\mathrm{EXP}^{\mathrm{NP}}\) oracle among many
• Super-polynomial versus half-exponential circuit size in the exponential hierarchy
• 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)