Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-162 | 4th February 2013 14:14

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

RSS-Feed




Revision #1
Authors: Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
Accepted on: 4th February 2013 14:15
Downloads: 2798
Keywords: 


Abstract:

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an advice bit string that may be accessed sequentially by the algorithm. The number of advice bits that are read to achieve some specific competitive ratio can then serve as a fine-grained complexity measure. The main contribution of this paper is to develop a new, powerful method to prove lower bounds on the number of advice bits necessary. To this end, we introduce the string guessing problem as a generic online problem and show a lower bound on the number of advice bits needed to obtain a small competitive ratio. We develop special reductions from string guessing to give a lower bound on the advice complexity of the online maximum clique problem and to improve the best known lower bound for the online set cover problem.


Paper:

TR12-162 | 26th October 2012 17:04

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity


Abstract:

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an advice bit string that may be accessed sequentially by the algorithm. The number of advice bits that are read to achieve some specific competitive ratio can then serve as a fine-grained complexity measure. The main contribution of this paper is to develop a new, powerful method to prove lower bounds on the number of advice bits necessary. To this end, we introduce the string guessing problem as a generic online problem and show a lower bound on the number of advice bits needed to obtain a small competitive ratio. We develop special reductions from string guessing to give a lower bound on the advice complexity of the online maximum clique problem and to improve the best known lower bound for the online set cover problem.



ISSN 1433-8092 | Imprint