License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.23
URN: urn:nbn:de:0030-drops-83839
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8383/
Chattopadhyay, Arkadev ;
Mande, Nikhil S.
A Lifting Theorem with Applications to Symmetric Functions
Abstract
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]
BibTeX - Entry
@InProceedings{chattopadhyay_et_al:LIPIcs:2018:8383,
author = {Arkadev Chattopadhyay and Nikhil S. Mande},
title = {{A Lifting Theorem with Applications to Symmetric Functions}},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages = {23:1--23:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-055-2},
ISSN = {1868-8969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8383},
URN = {urn:nbn:de:0030-drops-83839},
doi = {10.4230/LIPIcs.FSTTCS.2017.23},
annote = {Keywords: Symmetric functions, lifting, circuit complexity, communication com- plexity}
}
Keywords: |
|
Symmetric functions, lifting, circuit complexity, communication com- plexity |
Collection: |
|
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) |
Issue Date: |
|
2018 |
Date of publication: |
|
12.02.2018 |