Deterministic APSP, Orthogonal Vectors, and More
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Claims deterministic subquadratic algorithms for Orthogonal Vectors when d = c log n (randomized version runs in n^{2−ε}; deterministic matches up to constants) and a deterministic APSP in n^3 / 2^{Ω(√log n)} time. Key tools: convert the depth‑3 OR-AND circuit to a low-degree F2 polynomial with about n·binom(O(log d), O(log d)) monomials, evaluate that polynomial on Cartesian product blocks using rectangular matrix multiplication, and derandomize the XOR sampling with epsilon-biased sets plus mod‑amplifying integer polynomials to remove randomness. Methods run and succeed with the stated guarantees.
AI-written summary · about