BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:d7965659-3661-4a7a-98e1-7784fbf2073e
X-WR-CALNAME:[ICQ] Daniel Szabo (IRIF) Quantum property testing in sparse d
 irected graphs
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20261025T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20241027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
RDATE:20260329T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:d7965659-3661-4a7a-98e1-7784fbf2073e
DTSTAMP:20260516T043429Z
CLASS:PUBLIC
DESCRIPTION:Having query access to a bounded degree directed graph in the u
 nidirectional model means that querying a vertex v reveals the list of ver
 tices u such that there is a directed edge from v to u. Quantum algorithms
  can make these queries in superposition. In this model\, we consider the 
 problem of property testing k-star-freeness\, i.e. the algorithm has to di
 stinguish\, with high probability\, between (1) the graph having no vertex
  with at least k incoming edges (k-star)\; (2) the graph being “far” from 
 this\, meaning that one has to delete a constant fraction of the edges to 
 make the graph free from k-stars.\n\nIn the classical unidirectional model
  the problem of testing k-star-freeness (and more generally k-source-subgr
 aph-freeness) is almost maximally hard for large (but constant) k\, i.e. t
 he query complexity is almost linear in the number of vertices. We give a 
 quantum algorithm to show that this problem has almost quadratic advantage
  in the quantum setting. Moreover\, we prove that this advantage is nearly
  tight\, by proving a quantum lower bound using the method of dual polynom
 ials on an intermediate problem that is a previously unstudied\, property 
 testing version of the k-collision problem.\n\nJoint work with Simon Apers
 \, Frédéric Magniez and Sayantan Sen.\n\n\nhttps://combalgo.labri.fr/pmwik
 i.php/Groupe/Info-Quantique\n\nImport automatique depuis https://webmel.u-
 bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.info-quantique.ics par sync_
 icals_to_drupal.py pour gt-iq
DTSTART;TZID=Europe/Paris:20241210T104500
DTEND;TZID=Europe/Paris:20241210T114500
LOCATION:Room 178
SEQUENCE:0
SUMMARY:[ICQ] Daniel Szabo (IRIF) Quantum property testing in sparse direct
 ed graphs
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
