Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols

Explore the Polynomial Method in classical algorithms, focusing on Orthogonal Vectors, All-Pair-Shortest-Path, and Approximate Closest Pair. Learn how the Polynomial Method works through batch evaluation for multi-variable polynomials and fast matrix multiplication. Discover insights on low-rank decomposition and constructing low-rank matrices. Dive into connections between communication protocols and rank measures for communication complexity.

• Classical Algorithms
• Polynomial Method
• Communication Protocols
• Batch Evaluation
• Matrix Multiplication

npatc Follow

Uploaded on Nov 14, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols Lijie Chen MIT Ruosong Wang CMU

2. The Polynomial Method The Polynomial Method - - A gift from A gift from circuit complexity circuit complexity to to algorithm algorithm Orthogonal Vectors (OV) [Abboud-R. Williams-Yu, 2015] - One of the most important problems in fine-grained complexity ?? ?/ ??? ?time for OV in ? ???? dims. All-Pair-Shortest-Path (APSP) [R. Williams, 2014] - A very basic graph problem with an ?3 time textbook algo (Floyd s algo) ??/???? ? time algo Approx.-Bichrom.-Closest-Pair [Alman-R. Williams-Chan, 2016] - A Fundamental Problem in Computational Geometry ?? ??/? time for (? + ?)approximation

3. How does Polynomial How does Polynomial Method Work? Method Work? An Algorithm Task A Find A Key Subroutine S of A approx Batch Evaluation for Multi-Variable Polynomials Subroutine S A Sparse Polynomial P Fast Rectangle Matrix Multiplication

4. Observation [ Observation [Alman Alman- -R.Williams R.Williams, 2017] , 2017] In fact, it ultimately relies on low-rank decomposition of the Subroutine S! An Algorithm Task A Find A Key Subroutine S of A approx Batch Evaluation for Multi-Variable Polynomials Subroutine S A Sparse Polynomial P Fast Rectangle Matrix Multiplication

5. Example : Orthogonal Vectors (OV) Example : Orthogonal Vectors (OV) OV Find an orthogonal pair, among ? vectors in 0,1?( ?,? = 0). Another Perspective on [Abboud- R. Williams-Yu, 2015] by [Alman-R. Williams, 2017] Key Subroutine S ????,? [ ?,? = 0?] ??? has small probabilistic rank, and an efficient (probabilistic) low- rank decomposition Corresponding Matrix ??? ??? : a 2? 2? matrix (Enough for algorithms!)

6. Motivation : Other ways to construct Motivation : Other ways to construct these low these low- -rank decomposition? rank decomposition? Communication Protocols! Deterministic Communication Protocols Rank log of Quantum Communication Protocols Approximate Rank Unbounded Error Communication Protocols Sign Rank

7. Connections between Communication Protocols Connections between Communication Protocols and different rank measures and different rank measures Original Perspective Approach to prove communication complexity lower bounds rank CC This Work rank Approach to Systematically Construct Efficient Low-Rank Decomposition (to get algorithms) CC

8. This Work : Two Generic Connections This Work : Two Generic Connections 1. (Classical) Approximate Counting Algorithms from Quantum Communication Protocols 2. (Classical) Satisfying Pair Algorithms from Arthur-Merlin or PH Communication Protocols

9. Approximate Counting Algorithms from Quantum Communication Protocols ?-Counting Pair Problem Given ?,? ?, how many ?,? ? ? such that ? ?,? = 1? Let ? ?,? be the answer. Our Theorem ? admits a quantum communication protocol of complexity ?, There is an ? ??(?) time deterministic algorithm, which approximates ?(?,?) within ? ? |?|.

10. Satisfying Pair Algorithms from Arthur-Merlin (AM) or PH Communication Protocols ?-Satisfying Pair Problem Given ?,? ?, ? ?,? ? ? such that ? ?,? = 1? Alice and Bob hold ? and ?, want to compute ?(?,?). Alice, Bob Merlin : some random bits Merlin Alice, Bob : a proof Alice, Bob: communicate & accept/reject (det.) AM Communication Protocols Our Theorem (Informal) ? admits a (computational-efficient) AM communication protocol of complexity ? and error ?, There is an ? (?? + ??) time algorithm for the ?- Satisfying Pair Problem.

11. Immediate Applications #OV Given sets A,B of ? vectors from 0,1d, count ?,? ? ? such that ?,? = 0. Max-IP Problem Given ?,? 0,1?, find ?,? ? ?, maximizing ?,? . Constant additive error approximation Apply BQP protocol for Set-Disjointness [Aaronson-Ambainis 2005] ??+?(?) time for ? = ? ????? . Apply AM protocol for Approximate Set-Size [Goldwasser-Sipser 1989] constant approximation to Max-IP in ?? ?/ ???(?/ ??? ?) time, matching [Chen 2018]. Other applications from BQP protocol for Element-Distinctness [Ambainis 2007], and BQP protocol Formula- Evaluation [Ambainis et al. 2010].

12. Applications in Computation Complexity Theorem Big Open Question in CC If ????? has an efficient AM protocol (???????(?)), then SAT of ???? ? size formula can be solved in ?? ?? ? time. (built on [Abboud-Hansen-V.Williams-R.Williams]) much faster than the state of the art and conjectured to be impossible by [Abboud and Bringmann, ICALP 2018] Prove a non-trivial lower bound on the AM communication complexity of an explicit function ????? Problem Alice and Bob have ? and ? and ?, want to determine whether ??? ?,? ?. The same holds for PH protocols, and for a similar Edit-Distance Problem, and even for approximate LCS. (LCS, Edit-Distance are ????????-complete)

13. Thanks! Questions?