Answering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations
summary
Presents a single algorithmic framework that expresses sum‑product queries (FAQs) over hypergraphs and specializes to joins, exact inference in PGMs, FFT and matrix–vector products, proving worst‑case optimal join runtimes via Loomis‑Whitney style bounds (output ≤ (r·s·t)^{1/2}) and yielding the FFT case at n^{4/3} runtime (extendable to n log n). Uses listing representation of factors, combines variable‑elimination with join subroutines, and implements a system that outperforms several engines by 10x–100x. Notes computing optimal variable order is NP‑hard.
AI-written summary · about
chapters (17)
- 0:00Intro
- 2:18In case you were afraid to ask
- 3:50Baby FAQs are very expressive
- 6:25What is "grown up" FAQ?
- 7:54Morally the join problem
- 11:36Discrete Fourier Transform
- 14:50Algorithms for (baby) FAQs
- 15:14How are functions represented?
- 15:43Trivial algorithm for (baby) FAQs
- 16:21Matrix vector multiplication H
- 17:11Fast(er) Fourier Transform
- 21:11Going back to representations
- 23:56Algorithmic Loomis-Whitney
- 28:43Algorithm for FAQ
- 29:17Simplicity leads to performance
- 29:52Further Reading
- 30:50Questions?
related talks
01h 00mAverage-case Complexity for Polynomials, and All That
01h 05mOn the Critical Point Method and Deciding Connectivity Queries in Real Algebraic Sets
01h 35mThe Twin Algorithms
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
54mConstraints, Gadgets, and Invariants
58mDichotomy Theorems for Counting Problems I
01h 07mPanel with Stephen Wolfram
01h 02mApproximate Counting I