BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1708
DTSTAMP:20260417T050127Z
SUMMARY:Quantum Classical Equivalence for AND Functions
DESCRIPTION:Speaker: Sreejata Kishor  Bhattacharya (TIFR)\n\nAbstract: \nA 
 major open problem at the interface of quantum computing and communication
  complexity is whether quantum protocols can be exponentially more efficie
 nt than classical protocols for computing total Boolean functions\; the pr
 evailing conjecture is that they are not. In a seminal work\, Razborov (20
 02) resolved this question for AND-functions of the form\nF(x\, y)=f(x_1\,
  y_1\, ...\, x_n\, y_n)\n \nwhen the outer function f is symmetric\, by p
 roving that their bounded-error quantum and classical communication comple
 xities are polynomially related. Since then\, extending this result to all
  AND-functions has remained open and has been posed by several authors.\n
  \nIn this work\, we settle this problem. We show that for every Boolean 
 function f\, the bounded-error quantum and classical randomized communicat
 ion complexities of the AND-function f • AND_2 are polynomially related\
 , up to polylogarithmic factors in n. Moreover\, modulo such polylogarithm
 ic factors\, we prove that the bounded-error quantum communication complex
 ity of f • AND_2 is polynomially equivalent to its deterministic communi
 cation complexity\, and that both are characterized—up to polynomial los
 s—by the logarithm of the De Morgan sparsity of f.\n \nOur results buil
 d on the recent work of Chattopadhyay\, Dahiya\, and Lovett (2025) on stru
 ctural characterizations of non-sparse Boolean functions\, which we extend
  to resolve the conjecture for general AND functions.\n \nBased on joint 
 work with Farzan Byramji\, Arkadev Chattopadhyay\, Yogesh Dahiya\, and Sha
 char Lovett.\n
URL:https://www.tcs.tifr.res.in/web/events/1708
DTSTART;TZID=Asia/Kolkata:20260417T160000
DTEND;TZID=Asia/Kolkata:20260417T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR