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

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

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

(17)

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

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)