Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs

on YouTube ↗23m

" summary

Shows that sparse Orthogonal Vectors implies hardness for first-order model checking: if two disjoint sets on m edges admits subquadratic time then model checking k+1‑quantifier FO formulas can be solved in n^{k-ε}, so under SETH/OV no such speedup exists. Proof uses randomized fine-grained reductions, universe shrinking via Bloom filters to complement sets while preserving sparsity, exhaustive search on O(1) high-degree vertices, and error probability exponentially small when target sets are small. Works for sparse graphs; several dense and dynamic extensions remain open.

AI-written summary · about

" chapters (13)

1. 0:00Orthogonal vectors problem
2. 1:09Reductions and problem classes
3. 3:08Two disjoint sets problem
4. 5:11Model checking properties
5. 6:55Sparse vs dense graphs
6. 8:19Main results and theorems
7. 8:57Fine-grained reduction methods
8. 9:59Quantifier structure analysis
9. 11:29Equivalence of basic problems
10. 12:38Universe shrinking techniques
11. 14:50Constructing hybrid problems
12. 18:50Conclusion and open problems
13. 21:22Q&A session