ECCC-Report TR12-162https://eccc.weizmann.ac.il/report/2012/162Comments and Revisions published for TR12-162en-usMon, 04 Feb 2013 14:15:01 +0200
Revision 1
| The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity |
Hans-Joachim Boeckenhauer,
Juraj Hromkovic,
Dennis Komm,
Sacha Krug,
Jasmin Smula,
Andreas Sprock
https://eccc.weizmann.ac.il/report/2012/162#revision1The 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.Mon, 04 Feb 2013 14:15:01 +0200https://eccc.weizmann.ac.il/report/2012/162#revision1
Paper TR12-162
| The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity |
Hans-Joachim Boeckenhauer,
Juraj Hromkovic,
Dennis Komm,
Sacha Krug,
Jasmin Smula,
Andreas Sprock
https://eccc.weizmann.ac.il/report/2012/162The 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.Fri, 23 Nov 2012 09:01:45 +0200https://eccc.weizmann.ac.il/report/2012/162