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