Seminars

An Almost Logarithmic Approximation for Cutwidth

On the Existence of Seedless Condensers: Exploring the Terrain

Exact Emulators for Planar Graphs

Recent progresses on Correlation Clustering

New techniques for convex optimization and sparsification

New Approximation Bounds for Small-Set Vertex Expansion

Gaussian Polytope Approximators

Separating MAX 2-AND, MAX DI-CUT and MAX CUT

Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation

Are there graphs whose shortest path structure requires large edge weights?

20th Annual CSE Graduate Honors Competition

Deeparnab Chakrabarty: Parallel Submodular Function Minimization

Victor Reis: Optimal Online Discrepancy Minimization

Lars Rohwedder: Simpler and stronger approximation algorithms for flow time scheduling

Simulation-based Approaches for Evaluating Information Elicitation and Information Aggregation Mechanisms

Zihan Tan: Almost-Optimal Sublinear Additive Spanners

Or Zamir: Algorithmic Applications of Hypergraph and Partition Containers

Sasha Golovnev: Polynomial formulations as a barrier for reduction-based hardness proofs

Min Jae Song: Continuous LWE

Manik Dhar: ℓ∞ linear hashing and two-sided Kakeya bounds

Sophie Huiberts: Smoothed analysis of the simplex method

Liren Shan: Higher-Order Cheeger Inequality for Partitioning with Buffers

DNA Punch-Cards: Implementations and Coding-Theoretic Questions

William Hoza: Recent Progress on Derandomizing Space-Bounded Computation

Jessica Sorrell: Replicability in Learning

Yang Liu: Lessons on Algorithmic Graph Theory from Maxflow

Aaron Bernstein: Negative-Weight Single-Source Shortest Paths in Near-linear Time

Sorrachai Yingchareonthawornchai: Deterministic Small Vertex Connectivity in Almost Linear Time

Vincent Cohen-Addad: Sublinear time algorithms for Euclidean clustering coresets and correlation clustering

Haotian Jiang: Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank

Zeyu Guo: Fast Multivariate Multipoint Evaluation over All Finite Fields

Fernando Granha Jeronimo: Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

Haotian Jiang: Minimizing Convex Functions with Integral/Rational Minimizers

Dynamic Connectivity, Hopsets, and Byzantine Agreement

Mitali Bafna: Playing Unique Games on Certifiable Small-Set Expanders and High-Dimensional Expanders

Parth Mittal: Brooks’ Theorem in Graph Streams

Huacheng Yu: TBD

Max Hopkins: Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

Ryan Williams: Constructive Separations and Their Consequences

Santhoshini Velusamy: Approximating CSPs in the streaming setting

Robert Robere: Pseudorandom Self-Reductions for NP-Complete Problems

Deeksha Adil: Fast Algorithms for l_p-Regression and Other Problems

Michael Dinitz: Faster Matchings via Learned Duals

Ce Jin: Fast Low-Space Algorithms for Subset Sum

Arun Jambulapati: Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Vera Traub: Better-Than-2 Approximations for Weighted Tree Augmentation

A Characterization of Approximability for Biased CSPs

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

Arnold Filtser: Clan Embeddings into Trees, and Low Treewidth Graphs

Optimization-friendly generic mechanisms without money.

18th Annual CSE Graduate Honors Competition

Breaking the 2^n barrier for 5-coloring and 6-coloring

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

On the Complexity of Consensus-Halving and Necklace Splitting

Accelerating Sampling Algorithms via Domain Sparsification

The Complexity of Gradient Descent: CLS = PPAD∩PLS

k-Forrelation Optimally Separates Quantum and Classical Query Complexity

Negative probabilities: what are they for?

The zero-rate threshold of adversarial bit-deletions is less than 1/2

Reversing Color Coding

Information theoretic limits of cardinality estimation: Fisher meets Shannon

Approximation Algorithms for Fair Clustering

Adaptive gradient descent methods for constrained optimization

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

(a biased selection of) Recent Developments in Combinatorial Auctions

Approximation Algorithms and Hardness for Strong Unique Games

Adversarial Streaming, Differential Privacy, and Adaptive Data Analysis

Prophet and Secretary Online Algorithms for Matching in General Graphs

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

Deterministic Mincut in Almost-Linear Time

Fooling Constant-Depth Threshold Circuits

Improved Analysis of Higher Order Random Walks

New algorithms and lower bounds for all-pairs max flow

Accidental Research: Scalable Algorithms for Graph Automorphism and Canonical Labeling

Approximating the Diameter of a Graph

Fast algorithms for linear programs and bipartite matching via new data structures and interior-point methods

New Analysis of the Factor Refinement Algorithm with Applications

Impartial selection, additive approximation guarantees, and priors

A Unified and Fine-Grained Approach for Light Spanners

17th Annual CSE GRADUATE HONORS COMPETITION

Algebraic Frameworks for Cryptographic Primitives

Edge-Weighted Online Bipartite Matching

Coloring and Maximum Weight Independent Set of Rectangles

Towards Optimal Separations between Quantum and Randomized Query Complexities

Computational Hardness of Optimal Fair Computation

Aggregating Inconsistent Information in Ranking, Clustering and Phylogenetic Trees

New Techniques for Proving Fine-Grained Average-Case Hardness

Hypergraph k-cut for fixed k in deterministic polynomial time

Non-Adaptive Adaptive Sampling in Turnstile Streams

The Menu-Size of Approximately Optimal Auctions

Efficiency in Machine Learning with Focus on Deep Learning and Recommender Systems

Towards the First Practical Applications of Quantum Computers

A Parallel Tensor Network Contraction Algorithm and Its Applications in Quantum Computation

An Algorithm for Hypergraph k-Cut

Learning from Societal Data: Theory and Practice

Algorithmic Paradigms for Dynamic Graphs

Towards a Unified Theory of Matching Sparsifiers

Security Games: Quasi-Regular Sequences, and a new version of TSP

Sketching Graphs and Matrices

On Sunflowers and Its Friends in Computer Science and Mathematics

Data Structures Meet Circuits and Cryptography

The Complexity of Finding S-factors in Regular Graphs

Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else)

An Adaptive Step Toward the Multiphase Conjecture

Cup Emptying Games and I/O Scheduling

Parallelizing Greedy for Submodular Set Function Maximization

The polymorphic gateway between structure and algorithms: Constraint Satisfaction and Beyond

Expander Decompositions: Fast Algorithms and Applications