BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/770
DTSTAMP:20230914T125937Z
SUMMARY:Dual Polynomials and Communication Complexity of XOR Functions
DESCRIPTION:Speaker: Nikhil S Mande\n\nAbstract: \nIn this talk\, we will s
 ee how certain "degree hardness" properties of a function (e.g approximate
  degree\, sign-degree) amplify to give us "monomial based" hardness proper
 ties of a certain "lift" (as defined by Krause and Pudlak (STOC '94)) of 
 the function. We list applications to symmetric functions\, resolving conj
 ectures of Ada et al. (APPROX-RANDOM '12) and Zhang ('91).\n\nWe will also
  see a connection between the polynomial margin of a function f\, and the 
 discrepancy of f of XOR via linear programming duality. Using this duality
 \, we demonstrate polynomial based techniques for understanding the bounde
 d error communication complexity and weakly-unbounded error communication 
 complexity of XOR functions. This allows us to prove a weak form of a conj
 ecture by Zhang and Shi (Quantum Information and Computation '09) and repr
 oves a result of Goldmann et al. (Computational Complexity '92) (based on 
 joint work with Arkadev Chattopadhyay (https://arxiv.org/abs/1704.02537)).
 \n
URL:https://www.tcs.tifr.res.in/web/events/770
DTSTART;TZID=Asia/Kolkata:20170414T160000
DTEND;TZID=Asia/Kolkata:20170414T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR