Name
Abstract | ||
|---|---|---|
We characterize the approximate monomial complexity, sign monomial complexity , and the approximate L 1 norm of symmetric functions in terms of simple combinatorial measures of the functions. Our characterization of the approximate L 1 norm solves the main conjecture in [AFH12]. As an application of the characterization of the sign monomial complexity, we prove a conjecture in [ZS09] and provide a characterization for the unbounded-error communication complexity of symmetric-xor functions. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Computational Complexity | Spectral properties,Discrete mathematics,Symmetric function,Combinatorics,Communication complexity,Monomial,Conjecture,Mathematics |
DocType | Volume | Citations |
Journal | abs/1704.03176 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anil Ada | 1 | 47 | 3.88 |
| Omar Fawzi | 2 | 261 | 17.96 |
| Raghav Kulkarni | 3 | 172 | 19.48 |