Sketching Algorithms for Max-DICUT and other CSPs

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


Duration: 59:53
159 views
5

Santhoshini Velusamy (Toyota Technological Institute at Chicago)
https://simons.berkeley.edu/talks/santhoshini-velusamy-toyota-technological-institute-chicago-2023-10-11
Sketching and Algorithm Design

Given a directed graph, the Maximum Directed Cut (Max-DICUT) problem asks to estimate the size of the largest directed cut​​, an ordered partition of the vertex set whose size is given by the number of edges from one set to the other. The Max-DICUT problem has emerged as a central problem in the study of Constraint Satisfaction Problems (CSPs) in the streaming setting. In the talk, I will discuss sketching algorithms and lower bounds for Max-DICUT in various space regimes and will briefly touch upon generalizations to arbitrary CSPs. I will conclude with a discussion on open problems in this area.



Other Videos By Simons Institute for the Theory of Computing


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
2023-10-11Improved Frequency Estimation Algorithms with and without Predictions
2023-10-11Testing Positive Semidefiniteness and Eigenvalue Approximation
2023-10-11Sketching Techniques for Kernel Density Estimation or for Optimal Transport Computations
2023-10-11Sketching and Projecting
2023-10-10Lightning Talks
2023-10-10Memory-Regret Tradeoff for Online Learning


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