Counting Subgraphs in Sublinear Time

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=4p2cq6Vy_9g


Duration: 1:01:38
54 views
3

C. Seshadhri (UC Santa Cruz)
https://simons.berkeley.edu/talks/c-seshadhri-uc-santa-cruz-2024-05-21
Sublinear Algorithms Boot Camp

Over the past decade, there have been a number of results of estimating subgraph counts without reading the whole graph. The aim of this talk is to bring out some key randomization techniques used in these results. These tools are simple enough to explain in a few slides, yet powerful enough to prove optimal results for estimating the average degree and triangle count. The hope is that the audience can understand all the details enough to recreate the results.



Other Videos By Simons Institute for the Theory of Computing


2024-05-29Testing Assumptions of Learning Algorithms
2024-05-29Adversarially Robust Streaming Algorithms
2024-05-29New Advances on Multi-Pass Graph Streaming Lower Bounds
2024-05-29Coresets and Their Applications to Design Sublinear Algorithms
2024-05-29An Overview on Data Streams Algorithms
2024-05-29Graph Coloring Through the Sublinear Lens
2024-05-29Conditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
2024-05-29Graph Algorithms in the MPC Model
2024-05-29An Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
2024-05-29Sampling Big Ideas in Sublinear Algorithms
2024-05-29Counting Subgraphs in Sublinear Time
2024-05-29Testing Boolean Functions
2024-05-29Property Testing for Graphs
2024-04-30Using chaos to characterize a programmable analog quantum simulator
2024-04-30Fundamental limits to quantum computation
2024-04-30Evidence for the utility of quantum computing before fault tolerance
2024-04-30High-fidelity and Fault-tolerant Teleportation of a Logical Qubit on a Trapped-ion Quantum Computer
2024-04-30An Overview of Quantum Algorithms
2024-04-30Certifying almost all quantum states with few single-qubit measurements
2024-04-30Learning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
2024-04-30A Quantum Speed-Up for Approximating the Top Eigenvector of aMatrix via Improved Tomography


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Sublinear Algorithms Boot Camp
C. Seshadhri