Unconditional Lower Bounds against Advice

DOI10.1007/978-3-642-02927-1_18zbMath1248.68212OpenAlexW2170007444MaRDI QIDQ3638035

Rahul Santhanam, Harry Buhrman, Lance J. 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)

Related Items

Robust simulations and significant separations ⋮ Avoiding simplicity is complex ⋮ Natural Proofs versus Derandomization ⋮ Randomness and Intractability in Kolmogorov Complexity