Symmetric Sparse Boolean Matrix Factorization and Applications

on YouTube ↗29m

" summary

Average-case result recovers a K‑sparse Boolean factor W from M = W W^T when each row of W is an independent uniform K‑subset, with high probability and columns recovered up to permutation by a O(M^{ω+1}) algorithm that bootstraps a third‑order tensor from pairwise overlap counts and runs tensor decomposition. Linear independence holds with about sample size m ≥ max(R, R/K · log R) so the tensor method succeeds. Also gives a polynomial‑time ε‑approximate worst‑case algorithm via a 2‑CSP reduction and consequences for clique cover, hypergraph line graph reconstruction, and Instahide/Batched K‑vector‑sum attacks.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:16Outline
3. 0:54Nonnegative Matrix Factorization
4. 3:36TCS Motivation 1: Clique Decomposition
5. 4:49TCS Motivation 2: Line Graphs of Hypergraphs
6. 6:51ML Motivation: Attacks on InstaHide
7. 11:10Consequence: Batched-k-Vector Sum
8. 13:50High Level Idea
9. 15:21Bootstrapping the Tensor
10. 16:32Size of Triple Intersection
11. 18:57Main Algorithm
12. 20:36Nonsingularity of Random Boolean Matrix
13. 21:26Random Boolean Matrix with dependence
14. 24:46Case 2: When k Is Even
15. 27:02Nonsingularity of Sparse Boolean Random Matrix
16. 27:37Open Questions