The string guessing problem as a method to prove lower bounds on the advice complexity

DOI10.1016/j.tcs.2014.06.006zbMath1360.68908OpenAlexW2040556211MaRDI QIDQ744093

Dennis Komm, Jasmin Smula, Andreas Sprock, Sacha Krug, Juraj Hromkovič, Hans-Joachim Böckenhauer

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

zbMATH Keywords

competitive analysisonline algorithmsadvice complexityonline cliqueonline set cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items

Call admission problems on grids with advice, Online Bin Packing with Advice of Small Size, Two-way and one-way quantum and classical automata with advice for online minimization problems, Online Graph Coloring Against a Randomized Adversary, Treasure Hunt with Advice, On Energy-Efficient Computations With Advice, On the advice complexity of the \(k\)-server problem, Call admission problems on trees, Advice complexity of online non-crossing matching, The advice complexity of a class of hard online problems, Fully Online Matching with Advice on General Bipartite Graphs and Paths, Advice complexity of adaptive priority algorithms, The secretary problem with reservation costs, Reordering buffer management with advice, On the advice complexity of the \(k\)-server problem under sparse metrics, On the advice complexity of the online dominating set problem, Advice complexity of priority algorithms, Weighted online problems with advice, Online Minimum Spanning Tree with Advice, Online bin covering with advice, Weighted Online Problems with Advice, Advice Complexity of the Online Search Problem, Online bin packing with advice of small size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online computation with advice
• 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
• The Online Set Cover Problem
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• On the Advice Complexity of Buffer Management
• Advice Complexity and Barely Random Algorithms
• A full derandomization of schöning's k-SAT algorithm
• How Much Information about the Future Is Needed?