Resizable Sketches

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


Duration: 42:32
279 views
4

Rasmus Pagh (University of Copenhagen)
https://simons.berkeley.edu/talks/rasmus-pagh-university-copenhagen-2023-10-13
Sketching and Algorithm Design

Sketches usually have a space parameter that is fixed for the lifetime of the sketch. However, the accuracy of estimates based on the sketch often deteriorates as size parameters grow. This talk discusses the question: what happens if, instead, we want a fixed guarantee on accuracy but allow the size of the sketch to grow?



Other Videos By Simons Institute for the Theory of Computing


2023-10-17Lower Bounds for Tractable Arithmetic Circuits
2023-10-17Tractable Bounding of Counterfactual Queries by Knowledge Compilation
2023-10-17Combined Approximations for Probabilistic Query Evaluation: An Intensional Approach
2023-10-17First-Order Model Counting and Sampling
2023-10-17AND/OR Search Spaces for Anytime Probabilistic Reasoning
2023-10-17Credal Models for Uncertainty and Logic Treatment
2023-10-16Model Counting Meets Distinct Estimation
2023-10-16The Intensional-Extensional Problem in Probabilistic Databases
2023-10-16Compiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
2023-10-13Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
2023-10-13Resizable Sketches
2023-10-13A Simple Quantum Sketch With Applications to Graph Algorithms
2023-10-12Insights from Engineering Sketches for Production and Using Sketches at Scale
2023-10-12A Near-Linear Time Algorithm for the Chamfer Distance
2023-10-12Robustness of Sketches to Adaptive nputs
2023-10-12Tight Bounds for Volumetric Spanners in All Norms
2023-10-12A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching
2023-10-11Sketching Algorithms for Max-DICUT and other CSPs
2023-10-11Error Correction for Streaming Messages
2023-10-11Streaming Lower Bounds for the Needle Problems
2023-10-11Streaming Euclidean k-median and k-means with o(log n) Space


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Sketching and Algorithm Design
Rasmus Pagh