Name
Abstract | ||
|---|---|---|
We use a technique of “lifting” functions introduced by Krause and Pudlak [Theor. Comput. Sci., 1997], to amplifydegree-hardness measures of a function to corresponding monomial-hardness properties of thelifted function. We then show that any symmetric function F projects onto a “lift” of anothersuitable symmetric function f . These two key results enable us to prove several results on thecomplexity of symmetric functions in various models, as given below:1. We provide a characterization of the approximate spectral norm of symmetric functions interms 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 Thresholdof 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 symmetricXOR functions, resolving a weak form of a conjecture by Shi and Zhang [Quantum Information u0026 Computation, 2009] |
Year | Venue | Field |
|---|---|---|
2017 | FSTTCS | Lift (force),Quantum,Symmetric function,Discrete mathematics,Computer science,Matrix norm,Communication complexity,Quantum information,Conjecture,Computation |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arkadev Chattopadhyay | 1 | 150 | 19.93 |
| Mande Nikhil S. | 2 | 5 | 4.13 |