Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Advice Complexity:
TR12-162 | 26th October 2012
Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock

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

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint