Advances in Linear Sketching over Finite Fields

on YouTube ↗56m

" summary

Shows that when there are at least 10·m sequential players and each message is at most C bits one can convert the protocol into a randomized F2 linear sketch of dimension ~C with only a constant loss, so multiplayer protocols collapse to sketches of size C. Extends to Z_p by increasing players and losing a log p factor so Z_p adds a log p loss in bit complexity. Proves deterministic one-way complexity equals Fourier dimension, gives linear lower bounds for majority/tribes/recursive majority from Fourier nonconcentration, and ties approximate Fourier dimension to uniform-distribution streaming optimality.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 3:25Linear sketching over F2
3. 9:23Puzzle: Open Problem 78 on Sublinear.info Shared randomness
4. 13:33Multi-player version over 2p
5. 15:14Motivation: Distributed Computing
6. 16:34Motivation: Streaming . x generated through a sequence of updates
7. 19:05Frequently Asked Questions
8. 21:43Deterministic vs. Randomized
9. 25:09Fourier Analysis
10. 26:10"Main Characters" are Parities
11. 29:23Deterministic Sketching and Noise
12. 33:00How Randomization Handles Noise
13. 35:09Randomized Sketching: Hardness
14. 39:33Sketching over Uniform Distribution + Approximate Fourier Dimension
15. 44:38Deterministic 1-way Communication Complexity of XOR-functions
16. 47:581-way Communication Complexity of XOR-functions Shared randomness
17. 49:20Distributional 1-way Communication under Uniform Distribution
18. 50:36Communication for Uniform Distribution
19. 51:35Application: Random Streams
20. 53:06Approximate F2-Sketching [Y.'17]
21. 54:48Approximate F2-Sketching of Valuation Functions [Y.,Zhou'18]