BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1556
DTSTAMP:20250528T105344Z
SUMMARY:Communication complexity\, but everything is vectors
DESCRIPTION:Speaker: Suhail Sherif (University of Lisbon)\n\nAbstract: \nTh
 is talk is about replacing bits with vectors. Goemans and Williamson did t
 his for MAX-CUT and got the best known polynomial-time approximation algor
 ithm. We wanted to know whether moving to vectors will help us prove certa
 in communication complexity lower bounds (and hopefully circuit depth lowe
 r bounds too). Moving to vectors has a strong benefit (via duality\, "shor
 t" lower bound proofs are guaranteed for all lower bounds) but one downsid
 e (some hard functions may become easy). To analyze this question we creat
 e two natural vector variants of communication protocols (both phrased as 
 Semidefinite Programs)\, and we set out to prove lower bounds for the Equa
 lity function. Our results are as follows:\n- The natural vector variant o
 f the Pigeonhole Principle is true.- Nevertheless in both of these communi
 cation variants Equality is actually easy to compute! (This implies that t
 he circuit depth lower bounds are also not achievable.)\nAfter this work w
 e realized that a work of Austrin and Risse already show a no-go theorem: 
 circuit depth lower bounds can not be achieved through semidefinite progra
 ms! Given this we will focus on the parts of our paper that are not covere
 d by theirs: The Pigeonhole Principle variant\, and results about the comm
 unication variants that are not directly linked to the circuit no-go theor
 em.\nThis is joint work with Pavel Dvorák and Bruno Loff.\n
URL:https://www.tcs.tifr.res.in/web/events/1556
DTSTART;TZID=Asia/Kolkata:20250529T160000
DTEND;TZID=Asia/Kolkata:20250529T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR