Document Open Access Logo

A Lifting Theorem with Applications to Symmetric Functions

Authors Arkadev Chattopadhyay, Nikhil S. Mande

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.23.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Arkadev Chattopadhyay
Nikhil S. Mande

Cite As Get BibTex

Arkadev Chattopadhyay and Nikhil S. Mande. A Lifting Theorem with Applications to Symmetric Functions. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.23

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]

Subject Classification

Keywords
  • Symmetric functions
  • lifting
  • circuit complexity
  • communication com- plexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anil Ada, Omar Fawzi, and Hamed Hatami. Spectral norm of symmetric functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 338-349, 2012. Google Scholar
  2. Anil Ada, Omar Fawzi, and Raghav Kulkarni. On the spectral properties of symmetric functions. Arxiv, 2017. Google Scholar
  3. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 337-347, 1986. Google Scholar
  4. Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC^0 functions, and spectral norms. SIAM J. Comput., 21(1):33-42, 1992. Google Scholar
  5. Jin-yi Cai, Frederic Green, and Thomas Thierauf. On the correlation of symmetric functions. Mathematical Systems Theory, 29(3):245-258, 1996. Google Scholar
  6. Arkadev Chattopadhyay and Nikhil S. Mande. Dual polynomials and communication complexity of XOR functions. CoRR, abs/1704.02537, 2017. URL: http://arxiv.org/abs/1704.02537.
  7. Mikael Goldmann, Johan Håstad, and Alexander A. Razborov. Majority gates VS. general weighted threshold gates. Computational Complexity, 2:277-300, 1992. Google Scholar
  8. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1077-1088, 2015. Google Scholar
  9. Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. CoRR, abs/1703.07666, 2017. Google Scholar
  10. Hamed Hatami and Yingjie Qian. The unbounded-error communication complexity of symmetric xor functions. Arxiv, 2017. Google Scholar
  11. Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20-46, 2007. Google Scholar
  12. Matthias Krause. On the computational power of boolean decision lists. Computational Complexity, 14(4):362-375, 2006. Google Scholar
  13. Matthias Krause and Pavel Pudlák. On the computational power of depth-2 circuits with threshold and modulo gates. Theor. Comput. Sci., 174(1-2):137-156, 1997. Google Scholar
  14. Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. Google Scholar
  15. Marvin Minsky and Seymour Papert. Perceptrons - an introduction to computational geometry. MIT Press, 1987. Google Scholar
  16. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. Google Scholar
  17. Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 468-474, 1992. Google Scholar
  18. Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403-435, 1999. Google Scholar
  19. Alexander A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. Google Scholar
  20. Alexander A. Sherstov. The unbounded-error communication complexity of symmetric functions. Combinatorica, 31(5):583-614, 2011. Google Scholar
  21. Mario Szegedy. Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC. J. Comput. Syst. Sci., 47(3):405-423, 1993. Google Scholar
  22. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209-213, 1979. Google Scholar
  23. Shengyu Zhang. Efficient quantum protocols for XOR functions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1878-1885, 2014. Google Scholar
  24. Zhi-Li Zhang. Complexity of symmetric functions in perceptron-like models. Master’s thesis, University of Massachusetts at Amherst, 1992. Google Scholar
  25. Zhiqiang Zhang and Yaoyun Shi. Communication complexities of symmetric XOR functions. Quantum Information & Computation, 9(3):255-263, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact