Separations and Equivalences Between Turnstile Streaming and Linear Sketching
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
Explore the distinctions and similarities between turnstile streaming and linear sketching algorithms in this 26-minute conference talk presented at an Association for Computing Machinery (ACM) event. Delve into streaming algorithms, models, and their limitations, examining the reduction requirements and stream conditions that impact algorithmic performance. Investigate separations between turnstile algorithms and linear sketching, with a focus on triangle counting in various scenarios, including bounded-degree, constant-degree, and insertion-only cases. Learn about the extension of insertion-only algorithms and the concept of separation constructivity. Conclude with insights into further research directions in this field of computational theory.
Syllabus
Intro
Streaming Algorithms
Streaming Models
Limitations on Equivalence
Our Results
Linear Sketching
Reduction Requirements
Stream Conditions
Separating Turnstile Algorithms and Linear Sketches
Bounded-Degree Triangle Counting
Constant-Degree Triangle Counting
Insertion-Only Triangle Counting
Extending the Insertion-Only Algorithm
Separation
Constructivity
Conclusion and Further Work
Taught by
Association for Computing Machinery (ACM)
Related Courses
Google Cloud Big Data and Machine Learning Fundamentals en EspañolGoogle Cloud via Coursera Big Data Emerging Technologies
Yonsei University via Coursera Building Resilient Streaming Systems on GCP em Português Brasileiro
Google Cloud via Coursera Building Resilient Streaming Systems on Google Cloud Platform en Español
Google Cloud via Coursera AWS Certified Data Analytics Specialty 2024 - Hands On!
Udemy