The string guessing problem as a method to prove lower bounds on the advice complexity
Authors:
- Hans-Joachim BöckenhauerHBHans-Joachim Böckenhauer
- Juraj HromkovičJHJuraj Hromkovič
- Dennis KommDKDennis Komm
- Sacha KrugSKSacha Krug
- Jasmin SmulaJSJasmin Smula
- Andreas SprockASAndreas Sprock
- 1 October 2014
- journal article
- conference paper
- Published by Elsevier in Theoretical Computer Science
- Vol. 554, 95-108
Abstract
No abstract availableKeywords
Funding Information
- Statens Naturvidenskabelige Forskningsrad (200021–141089)
This publication has 3 references indexed in Scilit:
- Online computation with adviceTheoretical Computer Science, 2011
- The Online Set Cover ProblemSIAM Journal on Computing, 2009
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985