Cheriton School of Computer Science Professors Shalev Ben-David and Eric Blais have received a prestigious best paper award at FOCS 2020, the 61st Annual IEEE Symposium on Foundations of Computer Science. FOCS and its counterpart — the Symposium on Theory of Computing — are the top international meetings in theoretical computer science.
Left
to
right:
Cheriton
School
of
Computer
Science
Professors
Shalev
Ben-David
and
Eric
Blais.
Professor
Ben-David’s
research
interests
are
in
classical
and
quantum
complexity
theory.
Professor
Blais’s
research
interests
span
theoretical
computer
science
with
a
special
focus
on
sublinear-time
algorithms,
randomness
in
computation,
and
complexity
theory.
Both
are
members
of
the
School’s
Algorithms
and
Complexity
Research
Group.
Their award-winning paper, A New Minimax Theorem for Randomized Algorithms, extends the minimax theorem, a seminal contribution to computer science by Andrew Yao, the 2000 Turing Award laureate. Yao’s 1977 paper, “Probabilistic Computations: Toward a Unified Measure of Complexity,” introduced what is now known widely among computer scientists as Yao’s min-max principle, which uses von Neumann’s minimax theorem from game theory to relate average-case complexity for deterministic algorithms to worst-case complexity for randomized algorithms.
Put simply, Yao’s minimax theorem allows randomized algorithms to be understood by analyzing deterministic algorithms, which is an easier task. This theorem has been used to solve countless problems across computer science.
“Our work on the minimax theorem came about because we came across a problem where Yao’s minimax theorem applied, but it was not strong enough to give the conclusion we needed,“ Professor Blais said. “That problem is known as the composition conjecture for randomized query complexity.” Professor Ben-David and Blais’s contributions to that conjecture are detailed in a separate paper titled “A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions” that was also presented at FOCS 2020.
“In our paper, we obtain a stronger version of Yao’s minimax theorem necessary for our intended application and show that it applies in many computational settings, just as Yao’s minimax theorem does,” Professor Ben-David said.
One important ingredient in the proof of Ben-David and Blais is a new notion called forecasting algorithms. The idea of using forecasting algorithms comes from the observation that measuring the error probability of randomized algorithms is not always the best way to measure the accuracy of an algorithm. “We can sometimes get much more insightful results by asking the algorithm to output a prediction of the correct output, along with a measure of the confidence the algorithm has in its prediction,” Professor Ben-David said.
Confidence in prediction is similar to what a weather forecaster does — the forecaster doesn’t simply say whether it will be rainy or sunny tomorrow; the forecaster states the expected weather with some probability attached to the prediction. “With these confidence levels, we can use a variety of different scoring rules to measure the accuracy of forecasting algorithms,” Professor Blais said. “What we’ve shown in our paper is that we can convert randomized algorithms to forecasting algorithms and vice versa. Forecasting algorithms also have lots of nice mathematical properties that enable us to prove results that simply can’t be obtained with a direct analysis of randomized algorithms.”
This year, FOCS 2020 is being held virtually from November 16 to 20. The annual symposium is sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing.
To learn more about their award-winning paper, please see Ben-David, Shalev and Blais, Eric, “A New Minimax Theorem for Randomized Algorithms” FOCS 2020, the 61st Annual IEEE Symposium on Foundations of Computer Science, November 16–19, 2020.