Dual Polynomials and Communication Complexity of XOR Functions

by Nikhil Mande (School of Technology and Computer Science, TIFR)

Friday 14 Apr 2017, 16:00 → 17:30 Asia/Kolkata

A-201 (STCS Seminar Room)

In this talk, we will see how certain "degree hardness" properties of a function (e.g approximate degree, sign-degree) amplify to give us "monomial based" hardness properties of a certain "lift" (as defined by Krause and Pudlak (STOC '94)) of the function. We list applications to symmetric functions, resolving conjectures of Ada et al. (APPROX-RANDOM '12) and Zhang ('91). We 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 bounded error communication complexity and weakly-unbounded error communication complexity of XOR functions. This allows us to prove a weak form of a conjecture by Zhang and Shi (Quantum Information and Computation '09) and reproves a result of Goldmann et al. (Computational Complexity '92) (based on joint work with Arkadev Chattopadhyay (https://arxiv.org/abs/1704.02537)).