A Simple Quantum Sketch With Applications to Graph Algorithms

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


Duration: 57:11
484 views
14

John Kallaugher (Sandia National Laboratories)
https://simons.berkeley.edu/talks/john-kallaugher-sandia-national-laboratories-2023-10-13
Sketching and Algorithm Design

I will talk about a quantum sketch for a set S ⊆ U that answers the following question: given a partition of U into pairs, how many of these pairs are in S? Originating in communication complexity, where a similar sketch was used to prove exponential advantage in one-way communication, this sketch can be used to construct space-efficient algorithms for graph problems, such as triangle counting (with polynomial space advantage over classical algorithms) and Max-Dicut (with exponential advantage).



Other Videos By Simons Institute for the Theory of Computing


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
2023-10-11Capacity Analysis of Vector Symbolic Architectures


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