Handling Uncertainty When Getting Contradictory Advice from Experts

Suppose you want to solve a computational problem \(\Pi \) for an instance x, but your computational power is not sufficient to compute \(\Pi (x)\). You communicate with experts in \(\Pi \) who claim to know the value of \(\Pi \) for every instance. However, when you ask them about \(\Pi (x)\), their answers turn out to be different. How can you determine which of the answers are correct? A possible approach is to apply selectors recently introduced in [11]. Selectors use the interactive proof techniques and downward self-reducibility to identify errors in multi-oracle computations. This paper is a brief survey of complexity-theoretic concepts and results that underlie applications of selectors for handling uncertainty with expert advice.