The string guessing problem as a method to prove lower bounds on the advice complexity
DOI10.1016/J.TCS.2014.06.006zbMATH Open1360.68908OpenAlexW2040556211MaRDI QIDQ744093FDOQ744093
Authors: Hans-Joachim Böckenhauer, Juraj Hromkovič, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock 
Publication date: 6 October 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.006
Recommendations
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- On the complexity of infinite advice strings
- Bounding the complexity of advice functions
- Advice complexity and barely random algorithms
- Advice complexity and barely random algorithms
- scientific article; zbMATH DE number 1336330
- Unconditional Lower Bounds against Advice
- Computational and proof complexity of partial string avoidability
- scientific article; zbMATH DE number 6851884
- On the Exact Complexity of String Matching: Lower Bounds
Online algorithms; streaming algorithms (68W27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Advice complexity of online coloring for paths
- On the advice complexity of the knapsack problem
- On online algorithms with advice for the \(k\)-server problem
- On the advice complexity of the set cover problem
- Online coloring of bipartite graphs with and without advice
- On the advice complexity of the \(k\)-server problem
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Title not available (Why is that?)
- Advice complexity and barely random algorithms
- Online computation with advice
- Title not available (Why is that?)
- The online set cover problem
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- Title not available (Why is that?)
- On the advice complexity of buffer management
- How Much Information about the Future Is Needed?
- Online bin packing with advice
Cited In (26)
- Online bin packing with advice of small size
- On the advice complexity of the online dominating set problem
- The advice complexity of a class of hard online problems
- Online bin packing with advice of small size
- Weighted online problems with advice
- Call admission problems on grids with advice
- Fully Online Matching with Advice on General Bipartite Graphs and Paths
- Online graph coloring against a randomized adversary
- Online Minimum Spanning Tree with Advice
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- Weighted Online Problems with Advice
- On the advice complexity of the \(k\)-server problem
- Advice complexity of adaptive priority algorithms
- Advice complexity of priority algorithms
- No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
- Online bin covering with advice
- On energy-efficient computations with advice
- Priority algorithms with advice for disjoint path allocation problems
- Call admission problems on trees
- Advice complexity of online non-crossing matching
- On the advice complexity of the \(k\)-server problem under sparse metrics
- The secretary problem with reservation costs
- Reordering buffer management with advice
- Advice complexity of the online search problem
- Treasure hunt with advice
- Two-way and one-way quantum and classical automata with advice for online minimization problems
This page was built for publication: The string guessing problem as a method to prove lower bounds on the advice complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744093)
