Composition for query complexity
Event details
| Date | 29.07.2021 |
| Hour | 14:00 › 16:00 |
| Speaker | Gilbert Maystre |
| Category | Conferences - Seminars |
EDIC candidacy exam
exam president: Prof. Michael Kapralov
thesis advisor: Prof. Mika Göös
co-examiner: Prof. Ola Svensson
Abstract
A fundamental problem in computational complexity
is to understand how the complexity of a problem scales
with respect to the number of instances to be solved. It would
be tempting to say that solving n unrelated instances requires
roughly n times the resources needed to solve a single instance.
While this holds in some settings, it remains a challenge in the
context of randomized query complexity. In this report, we survey
three articles tackling this challenge and the more general one of
query composition. We begin with an early negative result due to
Shaltiel [1] and then discuss a recent breakthrough of Ben-David
and Blais [2], [3] which introduce a new class of algorithms with
a powerful minimax theorem to avoid earlier limitations.
Background papers
[1] "Towards proving strong direct product theorems" Ronen Shaltiel (Computational Complexity 2003) https://link.springer.com/article/10.1007/s00037-003-0175-x
[2] "A New Minimax Theorem for Randomized Algorithms" Shalev Ben-David & Eric Blais (FOCS 2020) https://arxiv.org/abs/2002.10802
[3] "A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions" Shalev Ben-David & Eric Blais (FOCS 2020) https://arxiv.org/abs/2002.10809
exam president: Prof. Michael Kapralov
thesis advisor: Prof. Mika Göös
co-examiner: Prof. Ola Svensson
Abstract
A fundamental problem in computational complexity
is to understand how the complexity of a problem scales
with respect to the number of instances to be solved. It would
be tempting to say that solving n unrelated instances requires
roughly n times the resources needed to solve a single instance.
While this holds in some settings, it remains a challenge in the
context of randomized query complexity. In this report, we survey
three articles tackling this challenge and the more general one of
query composition. We begin with an early negative result due to
Shaltiel [1] and then discuss a recent breakthrough of Ben-David
and Blais [2], [3] which introduce a new class of algorithms with
a powerful minimax theorem to avoid earlier limitations.
Background papers
[1] "Towards proving strong direct product theorems" Ronen Shaltiel (Computational Complexity 2003) https://link.springer.com/article/10.1007/s00037-003-0175-x
[2] "A New Minimax Theorem for Randomized Algorithms" Shalev Ben-David & Eric Blais (FOCS 2020) https://arxiv.org/abs/2002.10802
[3] "A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions" Shalev Ben-David & Eric Blais (FOCS 2020) https://arxiv.org/abs/2002.10809
Practical information
- General public
- Free