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)).
