The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
From MaRDI portal
Publication:4925265
DOI10.1007/978-3-642-38768-5_44zbMath1382.68333OpenAlexW1785790694MaRDI QIDQ4925265
Jasmin Smula, Juraj Hromkovič, Andreas Sprock, Dennis Komm, Sacha Krug, Hans-Joachim Böckenhauer
Publication date: 11 June 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-38768-5_44
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items
Improved analysis of the online set cover problem with advice, A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey, On the advice complexity of online bipartite matching and online stable marriage, Advice complexity of online non-crossing matching, Fully Online Matching with Advice on General Bipartite Graphs and Paths, On the list update problem with advice, On the advice complexity of the online dominating set problem, Towards using the history in online computation with advice, On Advice Complexity of the k-server Problem under Sparse Metrics, Online bin packing with advice