Finding orthogonal vectors in discrete structures

DOI10.1137/1.9781611973402.135MaRDI QIDQ5384097zbMATH OpenOpenAlexFDO

Authors Huacheng Yu, Ryan Williams

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.135

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• An equivalence class for orthogonal vectors
• Finding a vector orthogonal to roughly half a collection of vectors
• New lower bounds for Hopcroft's problem
• Faster Online Matrix-Vector Multiplication
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky

Cited in

(13)

• On the hardness of approximate and exact (bichromatic) maximum inner product
• When can graph hyperbolicity be computed in linear time?
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Orthogonal vectors indexing
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• Into the square: on the complexity of some quadratic-time solvable problems
• Lengths of words accepted by nondeterministic finite automata
• Efficiently correcting matrix products
• Finding a vector orthogonal to roughly half a collection of vectors
• An equivalence class for orthogonal vectors
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• Counting solutions to polynomial systems via reductions

This page was built for publication: Finding orthogonal vectors in discrete structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384097)