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.

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.