School of Technology and Computer Science Seminars

Dual Polynomials and Communication Complexity of XOR Functions

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

Friday, April 14, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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)).