The Sketching Complexity of Graph and Hypergraph Counting
summary
Counts subgraphs in bounded-degree graphs using linear sketches and a colored vertex-sampling estimator, proving space Theta(m / T^{1/μ}) where μ is the fractional vertex cover of the query graph (triangle case gives m/T^{2/3}). Lower bounds come from a simultaneous three-player XOR-matching communication game and Fourier analysis and hypercontractivity, yielding an N^{1/3} barrier and showing the graph bounds are tight (hypergraph bounds lose a factor-two in the exponent).
AI-written summary · about
chapters (16)
- 0:00Start
- 2:32Linear Sketching
- 6:09The Sketching Complexity of Sub Graph Counting in Bounded Degree Graphs
- 8:15Estimator
- 11:08Sampling Vertices
- 13:11Results
- 14:41The Fractional Vertex Cover
- 16:07The Estimator
- 19:22Results for Hyper Graph
- 19:55Proof Techniques for for Trial Triangle Counting
- 20:36Communication Game
- 22:05Triangle Counting
- 26:49Intuition to Reason about General Protocols
- 28:54Convolution Theorem
- 29:50Hyper-Connectivity
- 32:26Summary