BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Quantum Strong Exponential-Time Hypothesis - Harry Buhrman
DTSTART:20191126T160000Z
DTEND:20191126T170000Z
UID:TALK133735@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:The strong exponential-time hypothesis (SETH) is a widely beli
 eved conjecture in the field of(classical) complexity theory. It states th
 at CNF formulas cannot be analyzed for satisfiability with a speedup over 
 exhaustive search. This hypothesis and its variants gave rise to a fruitfu
 l fieldof research\, fine-grained complexity\, obtaining (mostly tight) lo
 wer bounds for many problems in P whose unconditional lower bounds we are 
 unable to prove. In this work\, we introduce a framework of Quantum Strong
  Exponential-Time Hypotheses\, as quantum analogues to SETH. We provide a 
 series of hypotheses that allow for obtaining conditional quantum-time low
 er bounds for many problems in BQP: the QSETH framework. As an example\, w
 e illustrate the use of the QSETH by providing a conditional quantum time 
 lower bound of (almost) Ω(n^1.5) for the Edit-Distance problem.\n\nThis 
 is joint work with Florian Speelman en Subhasree Patro.
LOCATION:MR13\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR