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:69e4802c58db6
DTSTART;TZID=America/Toronto:20240730T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240730T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/proper-vers
 us-improper-quantum-pac-learning
LOCATION:QNC - Quantum Nano Centre 200 University Avenue West ZOOM ONLY Wat
 erloo ON N2L 3G1 Canada
SUMMARY:Proper versus Improper Quantum PAC learning
CLASS:PUBLIC
DESCRIPTION:CS/MATH SEMINAR - PULKIT SINHA\, IQC\n\nQNC building\, 200 Univ
 ersity Ave. Online only\, Waterloo \n\nA basic question in the PAC model 
 of learning is whether proper\nlearning is harder than improper learning. 
 In the classical case\,\nthere are examples of concept classes with VC dim
 ension d that have\nsample complexity Ω(d/ϵ log (1/ϵ)) for proper learn
 ing with error\nϵ\, while the complexity for improper learning is O(d/ϵ)
 . One such\nexample arises from the Coupon Collector problem.\nMotivated b
 y the efficiency of proper versus improper learning with\nquantum samples\
 , Arunachalam\, Belovs\, Childs\, Kothari\, Rosmanis\, and\nde Wolf (TQC 2
 020) studied an analogue\, the Quantum Coupon Collector\nproblem. Curiousl
 y\, they discovered that for learning size k subsets\nof [n] the problem h
 as sample complexity Θ(k log (min{k\,n−k+1}))\,\nin contrast with the c
 omplexity of Θ(k log k) for Coupon Collector.\nThis effectively negates t
 he possibility of a separation between the\ntwo modes of learning via the 
 quantum problem\, and Arunachalam et al.\nposed the possibility of such a 
 separation as an open question.  \nIn this work\, we first present an al
 gorithm for the Quantum Coupon\nCollector problem with sample complexity t
 hat matches the sharper\nlower bound of (1−o(1)) k ln( min{k\,n−k+1} )
  shown recently by Bab\nHadiashar\, Nayak\, and Sinha (IEEE TIT 2024)\, fo
 r the entire range of\nthe parameter k. Next\, we devise a variant of the 
 problem\, the Quantum\nPadded Coupon Collector. We prove that its sample c
 omplexity matches\nthat of the classical Coupon Collector problem for both
  modes of\nlearning\, thereby exhibiting the same asymptotic separation be
 tween\nproper and improper quantum learning as mentioned above.
DTSTAMP:20260419T071140Z
END:VEVENT
END:VCALENDAR