Finding orthogonal vectors in discrete structures

DOI10.1137/1.9781611973402.135zbMATH Open1422.68276OpenAlexW4253255388MaRDI QIDQ5384097FDOQ5384097

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

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

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)

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)