Hardness of Approximate and Exact Maximum Inner Product

In this study by Lijie Chen from Massachusetts Institute of Technology, the hardness of approximate and exact maximum inner product problems, specifically in the context of Max-IP and Z-Max-IP, is explored. It delves into the challenges associated with finding the maximum inner product between sets of vectors and discusses the implications of approximate solutions in various scenarios. The research also presents new findings on the hardness of Z-Max-IP under the Strong Exponential Time Hypothesis (SETH) and its relevance in the realm of theoretical computer science.

• Approximate solutions
• Maximum inner product
• Theoretical computer science
• Hardness
• Computational complexity

hirs_sif Follow

Uploaded on Apr 12, 2025 | 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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

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.

Presentation Transcript

1. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product ????,? ? ? ? ? Lijie Chen (Massachusetts Institute of Technology)

2. Max-IP and Z-Max-IP (Boolean) Max-IP: Given sets ? and ? of Boolean vectors (each of size n) find ? in ? and ? in ? with maximum inner product: For sets ? and ?, set ????? ?,? max ?,? ? ? ?,? . Approx. version: find a r-multiplicative approximation to the answer: Want an ??? s.t. ?????(?,?) ???(?,?) ?????(?,?) ?. Z-Max-IP: Two sets of ? Integer vectors.

3. Max-IP and Z-Max-IP Basic problems, relevant in practice. Important theoretical implications as well. Approx. Boolean Max-IP: [ARW 17]: basis of the recent breakthrough result in Hardness for Approximation in P, implies hardness for many other problems. Bichromatic LCS Closest Pair over permutations, Approximate Regular Expression Matching, Diameter in Product Metric, Approximate Closest Pair in Euclidian Space [Rub 18] Z-Max-IP: [Wil 18]: Hardness for Z-Max-IP implies hardness for finding furthest pair in low dimension Euclidean space.

4. 1. New Hardness for Z-Max-IP (under SETH) Z-Max-IP for n vectors of ?? ??? ?dimensions requires ?2 ?(1) time under SETH. Z-Max-IP for ? vectors of ?? ??? ? in ?1.99 time. Max-IP for ? vectors of ?(log?) dim. in ?1.99 time. CNF-SAT for ? variables and ?(?) clauses in 20.995? time. SETH is false. [CIP 06] Z-Max-IP: Given sets ? and ? of Integer vectors (each of size n) find ? in ? and ? in ? with maximum inner product: Closer to the upper bound [Mat 92] : Z-Max-IP in n2 1/O(d) time. Upper Bound ?2 ? when ? = ?(1) [Mat 92] Lower Bound Lower Bound ?2 o(1) when ? = 2? log ? [This work] ?2 o(1) when ? = ?(log2log?) Implicit in [Wil 18] ?

5. New Hardness for Z-Max-IP (under SETH) Z-Max-IP: 1. New Hardness for Z-Max-IP (under SETH): Z-Max-IP for n vectors of ?? ??? ?dimensions requires ?2 ?(1) time. Given sets ? and ? of Integer vectors (each of size n) find ? in ? and ? in ? with maximum inner product: Separation for Boolean Max-IP / Z-Max-IP: Z-Max-IP is much harder than Boolean Max-IP. Progress on Open Problem 23 in Dagstuhl workshop on Structure and Hardness in P Z-Max-IP Boolean Max-IP ?2 ? when ? = ? log?. [AW15, ACW16] ?2 o(1) when ? = 2? log ? [This work] HARD EASY

6. New Hardness for Z-Max-IP (under SETH) Z-Max-IP: 1. New Hardness for Z-Max-IP (under SETH): Z-Max-IP for n vectors of ?? ??? ?dimensions require ?2 ?(1) time. Given sets ? and ? of Integer vectors (each of size n) find ? in ? and ? in ? with maximum inner product. New Hardness for 2-Furthest Pair in ??. (reductions from [Wil18]) Finding 2-Furthest Pair in ?? among ? points for ? = 2? log ? requires ?2 ?(1) time. Stronger separation between furthest and closest pair. 2-Furthest Pair ?2 o(1) when ? = 2? log ? [This work] 2-Furthest Pair 2-Closest Pair 2? ? ? ???????(?) [BS76, KM95, DHKP97] ?2 o(1) when ? = ?(log2log?) [Wil 18] HARD EASY

7. Characterization of Boolean Approx. Max-IP 2. Characterization of Approx. Max-IP: [ARW 17]: Finding 2(log1 o 1?) approximation to Max-IP with ?? 1 dimensions, requires ?2 ?(1) ????. Boolean Max-IP: For sets ? and ? with ? Boolean vectors, find ????? ?,? max ?,? ? ? ?,? . Approx. version: find a r- multiplicative approximation to the answer: ?????(?,?) ???(?,?) ?????(?,?) ?. A more refined question: For each vector dimension ? = ? ? , what is the smallest ? such that Max-IP can be ?-approximated in truly sub-quadratic time? d = d(n) : vector dimensions r = r(n) : approx. ratio

8. Characterization of Boolean Approx. Max-IP 2. Characterization of Approx. Max-IP: A more refined question: For each vector dimension ? = ? ? , what is the smallest ? such that Max-IP can be ?-approximated in truly sub-quadratic time? Boolean Max-IP: For sets ? and ? with ? Boolean vectors, find ????? ?,? max ?,? ? ? ?,? . Approx. version: find a r- multiplicative approximation to the answer: ?????(?,?) ???(?,?) ?????(?,?) ?. We obtain a characterization (under SETH)! For all ? satisfying ? log? < ? < ?? 1 (1) ? Truly sub-quadratic time for ? = EASY! log ? d = d(n) : vector dimensions r = r(n) : approx. ratio o(1) ? Requires ?2 ?(1) time for ? = HARD! log ?

9. Characterization of Boolean Approx. Max-IP 2. Characterization of Approx. Max-IP: We obtain a characterization! ? = log ? ? = log ? Boolean Max-IP: For sets ? and ? with ? Boolean vectors, find ????? ?,? max ?,? ? ? ?,? . (1) ? ?2 ? time. EASY! o(1) ? ?2 ? 1 time. HARD! Approx. version: find a r- multiplicative approximation to the answer: ?????(?,?) ???(?,?) ?????(?,?) ?. Example: ? = ? log?,?(1)-approximation is EASY. ? = log2?, ?(log0.1?) approximation is EASY. ? = log2? ,(log?(1)?)-approximation is HARD. Upper Bound via polynomial method. d = d(n) : vector dimensions r = r(n) : approx. ratio Lower Bound follows from [Rub 18].

10. New Merlin-Arthur Protocol for Set- Disjointness MA Communication Protocol: Alice holds x, Bob holds y, want to compute F(x,y). 3. A new MA Protocol for Set-Disjointness [AW 09]: An O( ?log?) MA protocol. [Kla 03]: ( ?) Lower Bound. This work: an O( ?log?loglog?) protocol. ( ?) O( ?log?) [Upper Bound] [AW 09] O( ?log?loglog?) [Upper Bound] [This work] F(x,y) = 1 exists a proof, Pr ??? 2 F(x,y) = 0 for all proofs, Pr ??? 1 Complexity = Proof Length + Communication 3 . 3 . ? [Lower Bound] [Kla 03]

11. New Connection with Communication Complexity 4. New Connection with Communication Complexity [ARW 17]: ?log? MA protocol for Set-Disjointness SETH-Hardness for Approx. Boolean Max-IP. Quantum! Open Question from [ARW 17]: There is a ? BQPprotocol for Set-Disjointness. Does it also imply some hardness results? { ?,?}-Max-IP: Given sets ? and ? of vectors with { 1,1} entries (each of size ?) find ? in ? and ? in ? with maximum inner product. [This work]: YES! ? BQPprotocol for Set-Disjointness SETH-Hardness for Approx. { 1,1}-Max-IP

12. Proof Overview: SETH-Hardness of Z-Max-IP Starting Point SETH implies OV Conjecture. Orthogonal Vectors (OV) Problem: Given two sets A,B of Boolean vectors, find an orthogonal pair between them. OV Conjecture: OV with sets of ? vectors, ?(log?) dimensions requires ?2 ?(1) time. Our Goal: A dimensionality reduction from ?(log?) dimensional OV to 2? log ? dimensional Z-Max-IP

13. Reduction RoadMap Orthogonal Vectors (OV) Problem: Two sets A,B of Boolean vectors, find an orthogonal pair between them. First cover a baby version which shows ? log2log? dimensional Z-Max-IP is hard. (same as [Wil 18]) Then outline the key ideas to get the 2? log ? dimensional hardness. An intermediate problem: Z-OV: Given two sets A,B of Integer vectors, find an orthogonal pair between them. Z-Max-IP: Two sets of ? Integer vectors. find a pair between them which maximize their inner product. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV

14. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV Easy Part: Z-OV Z-Max-IP Implicit in [Wil 18]. ?,? ??. (Squaring trick) ? ? = 0 ? ?2= 0 ? ? 0 ? ?2< 0 To solve Z-OV, it suffices to calculate the maximum value of ? ?2 for ?,? ? ?. ? ?2= ??? ?? ??,?= ?? ??, ??,?= ?? ??. Maximize ? ?, Z-Max-IP with ?2 dim. Z-OV: Two sets A,B of Integer vectors, find an orthogonal pair between them. Z-Max-IP: Given sets ? and ? of Integer vectors (each of size n) find ? in ? and ? in ? with maximum inner product. 2= ?,?????????

15. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV Hard Part: OV Z-OV OV: Want to reduce the dimension: E.g. use few integers to represent a long Boolean vector Key Idea: Chinese Remainder Theorem (CRT)! ? primes ?1,?2, ,??. ? remainders ?1,?2, ,??. CRT: exists a unique integer 0 ? < ???, s.t. ? ?? (??? ??). Two sets A,B of Boolean vectors, find an orthogonal pair between them. Z-OV: Two sets A,B of Integer vectors, find an orthogonal pair between them. Use a number to represent a vector ? ?1,?2, ,??

16. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV Chinese Remainder Theorem Fix ? primes ?1,?2, ,??. ? = ???(?1,?2, ,??), i.e. ? ??(??? ??). ? = ??? ?1,?2, ,??, i.e. b ??(??? ??). ??? ?1,?2, ,?? the unique integer 0 ? < ???, s.t. ? ?? (??? ??). crr: Chinese Remainder Representation ? ? ?? ????? ?? for 1 ? ?. simulate Multiplication between Two integers Multiplication between Two vectors Exactly what we want!

17. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV Hard Part: OV Z-OV The reduction: d : vector dimension (? = ?(log?)). ? = ? represent a vector ? in 0,1d by a ? table. Map each row into a single number using Chinese Remainder Theorem ??? ?1,?2, ,?? the unique integer 0 ? < ???, s.t. ? ?? (??? ??). crr: Chinese Remainder Representation ? columns ?1,1 ?1,2 ?1,? ???(?1,1,?1,2, ,?1,?) rows ? ,1 ? ,2 ? ,? ???(? ,1,? ,2, ,? ,?) ? 0,1? ?(?) ? Want to be as small as possible

18. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV Hard Part: OV Z-OV The reduction: d : vector dimension ? = ? represent a vector ? in 0,1d by a ? table. ? columns ?1,1 ?1,2 ?1,? ???(?1,1,?1,2, ,?1,?) rows ? ,1 ? ,2 ? ,? ???(? ,1,? ,2, ,? ,?) Map each row into a single number using Chinese Remainder Theorem ? 0,1? ?(?) ? For ? [ ] and ? [?], ? ?? ??,? (??? ??) ? ? ? ? ??? ?? Set all ??> . ? ? = 0 ? ? ? ? 0 (??? ??) for all ?. The inner product of ?-th column of ? and ?-th column of ?. = ? ?? ? ??(??? ??) ?=1 = ??,? ??,?(??? ??) ?=1

19. Hard Easy ? log2log? -dim. Z-Max-IP ? loglog? -dim. Z-OV ? log? -dim. OV ? ? ? ? ??? ?? Hard Part: OV Z-OV = ? ?? ? ??(??? ??) ?=1 = ??,? ??,?(??? ??) ?=1 2. ? all multiples of ??? between 0 and ??? Given an OV instance with sets ? and ?. ? ? = 0 ? ? ? ? 0 (??? ??) for all ? ? ? ? ? ?. Let ? ?, ? ? ? ? = ? [? ? , 1] ? ? ,? = 0. ?? { ? ? , 1 :? ?}. ?? ? ? ,? :? ? . The inner product of ?-th column of ? and ?-th column of ?. Set all ??> . ? ? = 0 ? ? ? ? 0 (??? ??) for all ?. Therefore, There is an orthogonal pair between ? and ? There exists ? s.t. there is an orthogonal pair between ?? and ??. In summary: One ?-dim. OV instance |?| instances of + 1 -dim. Z-OV

20. Hard Part: OV Z-OV Informal Analysis ? all multiplier of ??? between 0 and ??? ?? { ? ? , 1 :? ?}. ?? ? ? ,? :? ? . 2. Recall what we have: ?(log?)-dim. OV requires ?2 ?(1) time. To preserve hardness, want ? = ?? 1. ? = ??? Have to set ? = ? Therefore, There is an orthogonal pair between ? and ? There exists ? s.t. there is an orthogonal pair between ?? and ??. ? 1 = ?O(?). log ? log log ?. = ?(loglog?). Therefore, =? log ? ? Q.E.D. In summary: One ?-dim. OV instance |?| instances of + 1 -dim. Z-OV Easy ? log2log? -dim. Z-Max-IP ? log? -dim. OV ? loglog? -dim. Z-OV

21. 2? log?dim. Hardness: Sketch What is the bottleneck? Not enough small primes! ?? even if we only need them to be > . Idea: Use another CRT to embed small primes inside big primes. Recursive: Then pack even smaller primes inside small primes, and recurse. Pretend we have many small primes, even though we don t . Recall what we have: ?(log?)-dim. OV requires ?2 ?(1) time. ? are ? distinct primes, most of them ?, To preserve hardness, want ? = ?? 1. ? = ??? Have to set ? = ? ? 1 = ?O(?). log ? log log ?. = Therefore, =? log ? ?(loglog?). ? Q.E.D.

22. One Step of Recursion 2 < ?. Pick ? primes ?1,?2, ,??, such that ??? d : vector dimension (? = ?(log?)) ? = ? (want as small as possible) represent a vector ? in 0,1d by a (?/?) table, each entry is a vector in 0,1?. ? inner ????: CRT w.r.t small primes ?? outer ???: CRT w.r.t. big primes ?? s, ??> ?. ?/? columns ?1,1 ?1,2 ?1,?/? ???(????( ?1,1),????( ?1,2), ,????( ?1,?/?)) rows ? ,1 ? ,2 ? ,?/? ???(????( ? ,1),????( ? ,2), ,????( ? ,?/?)) ? 0,1? ?(?) ?

23. One Step of Recursion ? inner ????: CRT w.r.t small primes ?? outer crr: CRT w.r.t. big primes ?? s, ??> ?. ?/? columns ?1,1 ?1,2 ?1,?/? ???(????( ?1,1),????( ?1,2), ,????( ?1,?/?)) rows ? ,1 ? ,2 ? ,?/? ???(????( ? ,1),????( ? ,2), ,????( ? ,?/?)) ? 0,1? ?(?) ? For ? [ ] and ? [?/?], ? ?? ????( ??,?) (??? ??) ? ? ? ? ??? ?? Get to know: = ? ?? ? ??(??? ??) ????( ??,?) ????( ??,?) ?=1 ?=1 and whether for all ?, ??,? ??,?= 0. = ????( ??,?) ????( ??,?) (??? ??) ?=1 2 < ? ?=1 ??? ????( ??,?) ????( ??,?) < ??.

24. One Step of Recursion: Informal Analysis ? ? ? ? ??? ?? Get to know: = ? ?? ? ??(??? ??) ????( ??,?) ????( ??,?) ?=1 ?=1 and whether for all ?, ??,? ??,?= 0. = ????( ??,?) ????( ??,?) (??? ??) ?=1 2 < ? ?=1 ??? ????( ??,?) ????( ??,?) < ??. A recursive construction leads to the final 2?(log ?) dim. hardness. 2 = ??(?)= ? Set ??? w = (log?/loglog?). ? = ??? Want ? = ??(1), set ? = ?(log?/logloglog?). Therefore, =? log ? ? = ?(logloglog?). Improvement! ? 1 = ?O(?/?)= log??(?).

25. Open Questions Construct an O( ?)-bit MA protocol for Set-Disjointness. Show that Z-Max-IP for any? 1 dimensions requires ?2 ?(1) time under some plausible hypothesis. Implies same hardness for ?(1) dimensions 2-Furthest Pair NP UPP communication protocol: a potential approach NP UPP: a relaxation of MA, where Arthur's error can be arbitrary close to 0.5. Our results can be interpreted as a sub-linear proof length, O(log ?) communication NP UPP protocol for Set-Disjointness. O(log ?) to ? ? Z-Max-IP for 2?(?) dim. requires ?2 ?(1) under SETH.

26. Thanks Any Questions?