The orthogonal vectors conjecture for branching programs and formulas

The orthogonal vectors conjecture for branching programs and formulas

© Daniel M. Kane and R. Ryan Williams. In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among n Boolean vectors in d dimensions. The OV Conjecture (OVC) posits that OV requires n2−o(1) time to solve, for all d = ω(log n). Assuming the OVC, optima...

Full description

Bibliographic Details
Main Authors: Kane, Daniel, Williams, Richard Ryan
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: 2021
Online Access:https://hdl.handle.net/1721.1/137484

Internet

https://hdl.handle.net/1721.1/137484

Similar Items