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

DOI10.1016/J.TCS.2014.06.006MaRDI QIDQ744093zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

online algorithmscompetitive analysisadvice complexityonline cliqueonline set cover

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 2079869 (Why is no real title available?)
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• Advice complexity and barely random algorithms
• Advice complexity of online coloring for paths
• How Much Information about the Future Is Needed?
• Information complexity of online problems
• On online algorithms with advice for the \(k\)-server problem
• On the Advice Complexity of Online Problems
• On the advice complexity of buffer management
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the knapsack problem
• On the advice complexity of the set cover problem
• Online bin packing with advice
• Online coloring of bipartite graphs with and without advice
• Online computation with advice
• The online set cover problem

Cited in

(25)

• The advice complexity of a class of hard online problems
• Advice complexity of adaptive priority algorithms
• Treasure hunt with advice
• On energy-efficient computations with advice
• The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
• Online bin packing with advice of small size
• Call admission problems on grids with advice
• Two-way and one-way quantum and classical automata with advice for online minimization problems
• Weighted Online Problems with Advice
• Advice complexity of online non-crossing matching
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Reordering buffer management with advice
• Weighted online problems with advice
• Priority algorithms with advice for disjoint path allocation problems
• Online graph coloring against a randomized adversary
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Call admission problems on trees
• No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
• Online bin packing with advice of small size
• The secretary problem with reservation costs
• Online bin covering with advice
• On the advice complexity of the \(k\)-server problem
• Advice complexity of the online search problem
• On the advice complexity of the online dominating set problem
• Online Minimum Spanning Tree with Advice

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)