Seminars

Negative probabilities: what are they for?

k-Forrelation Optimally Separates Quantum and Classical Query Complexity

The Complexity of Gradient Descent: CLS = PPAD∩PLS

Theory seminar: TBD

Yang P. Liu: TBD

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

Optimization-friendly generic mechanisms without money.

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