BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:The Quantum Strong Exponential-Time Hypothesis - H
arry Buhrman
DTSTART;TZID=Europe/London:20191126T160000
DTEND;TZID=Europe/London:20191126T170000
UID:TALK133735AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/133735
DESCRIPTION:The strong exponential-time hypothesis (SETH) is a
widely believed conjecture in the field of(classi
cal) complexity theory. It states that CNF formula
s cannot be analyzed for satisfiability with a spe
edup over exhaustive search. This hypothesis and i
ts variants gave rise to a fruitful fieldof resear
ch\, fine-grained complexity\, obtaining (mostly t
ight) lower bounds for many problems in P whose un
conditional lower bounds we are unable to prove. I
n this work\, we introduce a framework of Quantum
Strong Exponential-Time Hypotheses\, as quantum an
alogues to SETH. We provide a series of hypotheses
that allow for obtaining conditional quantum-time
lower bounds for many problems in BQP: the QSETH
framework. As an example\, we illustrate the use o
f the QSETH by providing a conditional quantum tim
e lower bound of (almost) Ω(n^1.5) for the Edit-Di
stance problem.\n\nThis is joint work with Florian
Speelman en Subhasree Patro.
LOCATION:MR13\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Johannes Bausch
END:VEVENT
END:VCALENDAR