BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Composition for query complexity
DTSTART:20210729T140000
DTEND:20210729T160000
DTSTAMP:20260407T184045Z
UID:ab6fa751ec55046363beb23dc5ec516decb785c09668da909fe420dc
CATEGORIES:Conferences - Seminars
DESCRIPTION:Gilbert Maystre\nEDIC candidacy exam\nexam president: Prof. Mi
 chael Kapralov\nthesis advisor: Prof. Mika Göös\nco-examiner: Prof. Ola 
 Svensson\n\nAbstract\nA fundamental problem in computational complexity\ni
 s to understand how the complexity of a problem scales\nwith respect to th
 e number of instances to be solved. It would\nbe tempting to say that solv
 ing n unrelated instances requires\nroughly n times the resources needed t
 o solve a single instance.\nWhile this holds in some settings\, it remains
  a challenge in the\ncontext of randomized query complexity. In this repor
 t\, we survey\nthree articles tackling this challenge and the more general
  one of\nquery composition. We begin with an early negative result due to\
 nShaltiel [1] and then discuss a recent breakthrough of Ben-David\nand Bla
 is [2]\, [3] which introduce a new class of algorithms with\na powerful mi
 nimax theorem to avoid earlier limitations.\n\nBackground papers\n[1] "Tow
 ards proving strong direct product theorems" Ronen Shaltiel (Computational
  Complexity 2003) https://link.springer.com/article/10.1007/s00037-003-01
 75-x\n[2] "A New Minimax Theorem for Randomized Algorithms" Shalev Ben-Dav
 id & Eric Blais (FOCS 2020) https://arxiv.org/abs/2002.10802\n[3] "A Tigh
 t Composition Theorem for the Randomized Query Complexity of Partial Funct
 ions" Shalev Ben-David & Eric Blais (FOCS 2020) https://arxiv.org/abs/200
 2.10809\n 
LOCATION:
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR