BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69ec2e72b861d
DTSTART;TZID=America/Toronto:20240319T090000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240319T100000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/quantum-tim
 e-complexity-divide-and-conquer
SUMMARY:On quantum time complexity of divide and conquer
CLASS:PUBLIC
DESCRIPTION:MATH CS SEMINAR - JINGE BAO\, NATIONAL UNIVERSITY OF SINGAPORE\
 n\n200 University Ave W. Waterloo - ZOOM\n\nWe initiate a systematic study
  of the time complexity of quantum\ndivide and conquer algorithms for clas
 sical problems. We establish\ngeneric conditions under which search and mi
 nimization problems with\nclassical divide and conquer algorithms are amen
 able to quantum\nspeedup and apply these theorems to an array of problems 
 involving\nstrings\, integers\, and geometric objects. They include LONGES
 T\nDISTINCT SUBSTRING\, KLEE'S COVERAGE\, several optimization problems on
 \nstock transactions\, and k-INCREASING SUBSEQUENCE. For most of these\nre
 sults\, our quantum time upper bound matches the quantum query lower\nboun
 d for the problem\, up to polylogarithmic factors.\n\nhttps://arxiv.org/ab
 s/2311.16401
DTSTAMP:20260425T030106Z
END:VEVENT
END:VCALENDAR