2026-07-31T04:11:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8383 2024-03-06T10:41:57Z ddc:004 open_access

A Lifting Theorem with Applications to Symmetric Functions Chattopadhyay, Arkadev Mande, Nikhil S. Symmetric functions lifting circuit complexity communication com- plexity We use a technique of “lifting” functions introduced by Krause and Pudlak [Theor. Comput. Sci., 1997], to amplify degree-hardness measures of a function to corresponding monomial-hardness properties of the lifted function. We then show that any symmetric function F projects onto a “lift” of another suitable symmetric function f . These two key results enable us to prove several results on the complexity of symmetric functions in various models, as given below: 1. We provide a characterization of the approximate spectral norm of symmetric functions in terms of the spectrum of the underlying predicate, affirming a conjecture of Ada et al. [APPROX-RANDOM, 2012] which has several consequences. 2. We characterize symmetric functions computable by quasi-polynomial sized Threshold of Parity circuits. 3. We show that the approximate spectral norm of a symmetric function f characterizes the (quantum and classical) bounded error communication complexity of f o XOR. 4. Finally, we characterize the weakly-unbounded error communication complexity of symmetric XOR functions, resolving a weak form of a conjecture by Shi and Zhang [Quantum Information & Computation, 2009] Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arkadev Chattopadhyay and Nikhil S. Mande 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.23 urn:nbn:de:0030-drops-83839 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.23 eng https://creativecommons.org/licenses/by/3.0/legalcode