Understanding Orthogonal Vectors and Related Problems
Dive into the world of orthogonal vectors with this comprehensive discussion on the Orthogonal Vectors Problem, algorithms for solving it, and related conjectures and hypotheses. Discover techniques, fast algorithms, and their applications in this intriguing domain.
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.
E N D
Presentation Transcript
Orthogonal Vectors and Related Problems Deepanshu Kush Presenter: Yen-Yu Chen Date: Mar. 4, 2025
Abstract In the remainder of section 1, we define the Orthogonal Vectors problem and discuss its trivial algorithms. We also state the Orthogonal Vectors Conjecture and Strong Exponential Time Hypothesis and explore their connections. In section 2, we define Partial Match and Subset Query and show their equivalences to Orthogonal Vectors. Further, we discuss a novel generalization of such kinds of problems andprove a dichotomy result based on a graph theoretic characterization: in some casesthis generalized problem is at least as hard as Orthogonal Vectors and in the rest, it can be solved in almost linear time. In section 3, we discuss a faster-than-trivial algorithm for Orthogonal Vectors due to Abboud, Williams, and Yu [AWY15], motivating every step along the way. In section 4, we show that listing (almost) all orthogonal pairs is subquadratically equivalent to detecting even a single orthogonal pair. Finally in section 5, we discuss a few natural extensions that can be explored. 2
Orthogonal Given two vectors?,? 0,1?, we say that they are orthogonal if ?=1 ????= 0 ? 0 1 0 0 1 0 1 0 1 0 0 1
Orthogonal Vector Problem, OVP Input: Lists A, B of N d-dimensional 0-1 vectors each. Output: A pair ? ? and ? ? such that u and v are orthogonal, if such a pair exists.
Algorithm for solving OVP Algorithm 1 ?(?2?) ? > log? Algorithm 2 ?(2???) ? < log? Time complexity When to use
A fast algorithm for Orthogonal Vectors 1. Divide both lists A and B into ? =? ?1, ,??) of size ? each. 2. Construct small boolean circuits to solve subproblems that determine whether the pair (??,Bj) consists of orthogonal vectors. 3. Evaluate circuits using probabilistic polynomials (defined as a distribution over certain polynomials) of low degree. 4. Evaluate this polynomial over all possible ?2pairs (??,Bj) in ?(?2 time. ? many sub-lists (?1, ,??and ?2)
Step 2: Construct Boolean circuits ? and ? are orthogonal if and only if ? ??? ??= 0 ? ?,? = ? ? ?? ?? is the target boolean circuit for vector x and y The boolean circuit for the subproblem (? ,? ) is C A ,B = ?,?=1 ?(??,??) ?
Step 3: Evaluate circuits using probabilistic polynomials ? Evaluate Boolean circuit C A ,B = ?,?=1 polynomial by tool (Razborov and Smolensky) ?(??,??) to probabilistic
probabilistic polynomial Compute OR of the bits ?1, ,??by evaluating a polynomial over 2 d times multiplication
probabilistic polynomial example ? ? ???1, ,?? = ?=1 If all ??= 1???1, ,?? = 1 correctly with probability 1 If any ??= 0 1 + ?=1 ???1 + ?? for any d 1 + ?=1 ???1 + ?? ???(?1, ,??) = 0 correctly with probability 1 Only ??,? = 0 ? 2 ? ???+ ?? Only ??= 0 1 + ???1 + ?? ?=1 ? ??? 0+0 1 1 + ???1 + ?? ?=1 1+0 0 0 1 0+1 0 1 0 1+1 1
probabilistic polynomial Compute OR of the bits ?1, ,??by evaluating a polynomial over 2 1 + ?=1 1 + ?? ???1, ,?? = ?=1 1 + ?=1 ???1 + ?? ? ? ? ? for all ?1, ,?? 1 2 Pr ??????1, ,?? = ???(?1, ,??) 1 0,1? ???(?1, ,??) = ??(?1, ,??) ???1, ,?? = ?=1 ? ? ?=1 ?????
Coppersmith fast rectangular matrix multiplication for subproblem
