A Lifting Theorem with Applications to Symmetric Functions
From MaRDI portal
Publication:5136315
DOI10.4230/LIPIcs.FSTTCS.2017.23zbMath1491.68085OpenAlexW2790886750MaRDI QIDQ5136315
Arkadev Chattopadhyay, Nikhil S. Mande
Publication date: 25 November 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.23
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)
Related Items (1)
Cites Work
- Unnamed Item
- On the computational power of Boolean decision lists
- Majority gates vs. general weighted threshold gates
- On the computational power of depth-2 circuits with threshold and modulo gates
- Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
- On the degree of Boolean functions as real polynomials
- Separation of the monotone NC hierarchy
- The unbounded-error communication complexity of symmetric functions
- Spectral Norm of Symmetric Functions
- Lower Bounds in Communication Complexity
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- Quantum communication complexity of symmetric predicates
- On the correlation of symmetric functions
- Efficient quantum protocols for XOR functions
- Lower Bounds for Quantum Communication Complexity
This page was built for publication: A Lifting Theorem with Applications to Symmetric Functions
