Document Open Access Logo

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols

Authors Lijie Chen, Ruosong Wang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.23.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Author Details

Lijie Chen
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Ruosong Wang
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite As Get BibTex

Lijie Chen and Ruosong Wang. Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.23

Abstract

In recent years, the polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times (e.g., R. Williams's n^3 / 2^{Omega(sqrt{log n})} time algorithm for APSP). As observed in [Alman and Williams, STOC 2017], almost all applications of the polynomial method in algorithm design ultimately rely on certain (probabilistic) low-rank decompositions of the computation matrices corresponding to key subroutines. They suggest that making use of low-rank decompositions directly could lead to more powerful algorithms, as the polynomial method is just one way to derive such a decomposition.
Inspired by their observation, in this paper, we study another way of systematically constructing low-rank decompositions of matrices which could be used by algorithms - communication protocols. Since their introduction, it is known that various types of communication protocols lead to certain low-rank decompositions (e.g., P protocols/rank, BQP protocols/approximate rank). These are usually interpreted as approaches for proving communication lower bounds, while in this work we explore the other direction.
We have the following two generic algorithmic applications of communication protocols: 
- Quantum Communication Protocols and Deterministic Approximate Counting. Our first connection is that a fast BQP communication protocol for a function f implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. Applying known BQP communication protocols, we get fast deterministic additive approximate counting algorithms for Count-OV (#OV), Sparse Count-OV and Formula of SYM circuits. In particular, our approximate counting algorithm for #OV runs in near-linear time for all dimensions d = o(log^2 n). Previously, even no truly-subquadratic time algorithm was known for d = omega(log n). 
- Arthur-Merlin Communication Protocols and Faster Satisfying-Pair Algorithms. Our second connection is that a fast AM^{cc} protocol for a function f implies a faster-than-bruteforce algorithm for f-Satisfying-Pair. Using the classical Goldwasser-Sisper AM protocols for approximating set size, we obtain a new algorithm for approximate Max-IP_{n,c log n} in time n^{2 - 1/O(log c)}, matching the state-of-the-art algorithms in [Chen, CCC 2018].
We also apply our second connection to shed some light on long-standing open problems in communication complexity. We show that if the Longest Common Subsequence (LCS) problem admits a fast (computationally efficient) AM^{cc} protocol (polylog(n) complexity), then polynomial-size Formula-SAT admits a 2^{n - n^{1-delta}} time algorithm for any constant delta > 0, which is conjectured to be unlikely by a recent work [Abboud and Bringmann, ICALP 2018]. The same holds even for a fast (computationally efficient) PH^{cc} protocol.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • Quantum communication protocols
  • Arthur-Merlin communication protocols
  • approximate counting
  • approximate rank

Metrics

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

Related Versions

References

  1. Scott Aaronson and Andris Ambainis. Quantum Search of Spatial Regions. Theory of Computing, 1(1):47-79, 2005. Google Scholar
  2. Amir Abboud and Karl Bringmann. Tighter Connections Between Formula-SAT and Shaving Logs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 8:1-8:18, 2018. Google Scholar
  3. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Proc. of the 48th STOC, pages 375-388, 2016. Google Scholar
  4. Amir Abboud and Aviad Rubinstein. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 35:1-35:14, 2018. Google Scholar
  5. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP Theorems for Hardness of Approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 25-36, 2017. Google Scholar
  6. Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More Applications of the Polynomial Method to Algorithm Design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 218-230, 2015. Google Scholar
  7. Josh Alman. An Illuminating Algorithm for the Light Bulb Problem. In SOSA, 2019. Google Scholar
  8. Josh Alman, Timothy M. Chan, and R. Ryan Williams. Polynomial Representations of Threshold Functions and Algorithmic Applications. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 467-476, 2016. Google Scholar
  9. Josh Alman and R. Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 641-652, 2017. Google Scholar
  10. Josh Alman and Ryan Williams. Probabilistic Polynomials and Hamming Nearest Neighbors. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 136-150, 2015. Google Scholar
  11. Noga Alon. Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability and Computing, 18(1-2):3-15, 2009. Google Scholar
  12. Noga Alon, Troy Lee, and Adi Shraibman. The cover number of a matrix and its algorithmic applications. In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  13. Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix and its algorithmic applications: approximate rank. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 675-684. ACM, 2013. Google Scholar
  14. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. Google Scholar
  15. Andris Ambainis, Andrew M Childs, Ben W Reichardt, Robert Špalek, and Shengyu Zhang. Any AND-OR formula of size N can be evaluated in time N^1 / 2 + o(1) on a quantum computer. SIAM Journal on Computing, 39(6):2513-2530, 2010. Google Scholar
  16. Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, and Avi Wigderson. The Quantum Communication Complexity of Sampling. SIAM J. Comput., 32(6):1570-1585, 2003. Google Scholar
  17. 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
  18. Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 519-528. ACM, 2011. Google Scholar
  19. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. Classical Communication and Computation. In Proc. of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 63-68, 1998. Google Scholar
  20. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 63-68. ACM, 1998. Google Scholar
  21. Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Computational Complexity, 16th Annual IEEE Conference on, 2001., pages 120-130. IEEE, 2001. Google Scholar
  22. Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1246-1255, 2016. Google Scholar
  23. Lijie Chen. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 14:1-14:45, 2018. Google Scholar
  24. Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum, and Aviad Rubinstein. Fine-grained Complexity Meets IP = PSPACE. In SODA, 2019. Google Scholar
  25. Lijie Chen and Ryan Williams. An Equivalence Class for Orthogonal Vectors. In SODA, 2019. Google Scholar
  26. Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing, 11(3):467-471, 1982. Google Scholar
  27. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1046. SIAM, 2018. Google Scholar
  28. Shafi Goldwasser and Michael Sipser. Private Coins versus Public Coins in Interactive Proof Systems. Advances in Computing Research, 5:73-90, 1989. Google Scholar
  29. Mika Göös, Toniann Pitassi, and Thomas Watson. Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Algorithmica, 76(3):684-719, 2016. Google Scholar
  30. Mika Göös, Toniann Pitassi, and Thomas Watson. The Landscape of Communication Complexity Classes. Computational Complexity, 27(2):245-304, 2018. Google Scholar
  31. Parikshit Gopalan, Ryan O'Donnell, Yi Wu, and David Zuckerman. Fooling Functions of Halfspaces under Product Distributions. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 223-234, 2010. Google Scholar
  32. Prahladh Harsha, Adam R. Klivans, and Raghu Meka. An invariance principle for polytopes. J. ACM, 59(6):29:1-29:25, 2012. Google Scholar
  33. Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1283-1296, 2018. Google Scholar
  34. Ilan Kremer. Quantum communication. Citeseer, 1995. Google Scholar
  35. Troy Lee and Adi Shraibman. Lower Bounds in Communication Complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. Google Scholar
  36. Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu. Beating Brute Force for Systems of Polynomial Equations over Finite Fields. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2190-2202, 2017. Google Scholar
  37. Kurt Mehlhorn and Erik Meineche Schmidt. Las Vegas Is better than Determinism in VLSI and Distributed Computing (Extended Abstract). In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 330-337, 1982. Google Scholar
  38. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 890-901, 2018. Google Scholar
  39. Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan. Fooling Polytopes. CoRR, abs/1808.04035, 2018. Google Scholar
  40. Ramamohan Paturi and Janos Simon. Probabilistic Communication Complexity. J. Comput. Syst. Sci., 33(1):106-123, 1986. Google Scholar
  41. Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  42. Ben Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 560-569, 2011. Google Scholar
  43. Karthik C. S. and Pasin Manurangsi. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. In ITCS, 2019. Google Scholar
  44. Rocco A. Servedio and Li-Yang Tan. Fooling Intersections of Low-Weight Halfspaces. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 824-835, 2017. Google Scholar
  45. Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77-82, 1987. Google Scholar
  46. Zhao Song, David P Woodruff, and Peilin Zhong. Relative Error Tensor Low Rank Approximation. In SODA, 2019. Google Scholar
  47. Avishay Tal. #SAT algorithms from shrinkage. Electronic Colloquium on Computational Complexity (ECCC), 22:114, 2015. Google Scholar
  48. Richard Ryan Williams. The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, pages 47-60, 2014. Google Scholar
  49. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal on Computing, 42(3):1218-1244, 2013. Google Scholar
  50. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 664-673. ACM, 2014. Google Scholar
  51. Ryan Williams. Non-Uniform ACC circuit lower bounds. Journal of the ACM (JACM), 61(1):2, 2014. Google Scholar
  52. Huacheng Yu. Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.02078.
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