Theory Seminars

Coin Toss: Game-Theoretic Fairness and Privacy.

Turán-type Problems and Graph Sparsification

Rate vs. Distance – Milestones and Obstacles Towards Improved Bounds

Testing Assumptions of Learning Algorithms

Maximum Matching in $O(\log \log n) $ Passes in Dynamic Streams

Worst-Case Approximation Ratios for Some Constraint Satisfaction Problems

Optimal Memory Allocation: The Dos and Don’ts of Request Fragmentation

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?

Deeparnab Chakrabarty: Parallel Submodular Function Minimization

Victor Reis: Optimal Online Discrepancy Minimization

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

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

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

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.

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

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

An Algorithm for Hypergraph k-Cut

Towards a Unified Theory of Matching Sparsifiers

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

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

Revisionist Simulations: A New Technique for Proving Space Lower Bounds

On the Quantitative Hardness of the Closest Vector Problem

Constant Time Coloring in the Congested Clique

Efficient Density Evaluation for Smooth Kernels

Dynamic Spanning Forest: Techniques and Connections to Other Fields

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

The Unreasonable Effectiveness of Almost Optimal Hardness

Nearly complete graphs decomposable into large induced matchings and their applications

Why Extension-based Proofs Fail

The Power of Natural Properties as Oracles

The Structure of Unique Shortest Paths in Graphs

Recent Progress in Bipartite Matching Problems

Linear Sketching for Functions over the Boolean Hypercube

Theory Seminar Kick-off

Distributed Edge Coloring

Near-optimal linear decision trees for k-SUM and related problems

Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts

Eliciting Expert Information without Verification

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

Property testing in the presence of erased data

Graph Matchings in the Data Stream Model: A Survey

Open Problem Session

Secure delegation of quantum computation

Efficient Massively Parallel Methods for Dynamic Programming

Consistency Thresholds for the Planted Bisection Model

Bayesian estimation from few samples: community detection and related problems

Planar Graph Perfect Matching is in NC

Distributed Exact Weighted All-Pairs Shortest Paths

Instance Optimal Learning

Generalization and Equilibrium in Generative Adversarial Nets (GANs)

Core sets and streaming algorithms for MAX CUT

Pseudorandomness of Ring-LWE for Any Ring and Modulus

Lower bounds for estimating matching size in streaming models

Cake Cutting: Fairness and Efficiency

Quantum hashing is maximally secure against classical leakage

Fully Dynamic Connectivity in O(log n(log log n)^2) Amortized Expected Time

Strategies for Extensive Form Games

Spookily Homomorphic Encryption

Population Recovery in polynomial time

Do Prices Coordinate Markets?

Polynomial Identity Testing for Read Once Polynomials

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

Differentially private analysis of graphs

Optimal Compression of Graph Metrics

Noise stability of functions with low influences: invariance and optimality

Better Outcomes from More Rationality

Recent progress on two-source randomness extractors

Multi-Key FHE from LWE, Revisited

Complex Contagions on Social Networks

Random number generation with untrusted quantum devices

Quantum Conditional Mutual Information and Ability to Recover

Using Expander Graphs to Find Vertex Connectivity

The 4/3 Additive Spanner Exponent is Tight

Counting perfect matchings via random matrices

Popularity Signals in Optimizing Trial-Offer Markets

Impact of community structure on cascades

Exploration of Bell test experiments for building an untrusted-device quantum number generator

Peer Prediction and Mechanism Design

Representation power of neural networks

Weighted Matching on General Graphs: Faster and Simpler

Streaming Interactive Protocols for Graphs

Theory Seminar Fall Kick-off

Quantile Search for Minimum-Time Sampling

On the equivalence between simulated annealing and Interior Point Methods

Higher lower bounds from the 3SUM conjecture

How to Prove Lower Bounds from the Strong Exponential Time Hypothesis

The optimal absolute ratio for online bin packing

Recent Progress on the Sparse Polynomial Factorization Problem

Randomized Primal-Dual analysis of Ranking for Online Bipartite Matching

Midwest Theory Day

Title: Approximate Version of Caratheodorys Theorem and Its Algorithmic Applications

Fast matrix completion without the condition number

Characterizing Arithmetic Read-Once Formulae

Price of Anarchy for Auction Revenue

Isotonic Regression As a Function of Comments

FOCS Round Up!

Distributed Algorithms for the Lovász Local Lemma and Graph Coloring

Information (or inferential) limits and computational limits

Tensor rank and stability in representation theory

Robust Quantum Random Number Generation

Event: 3SUM is Subquadratic

Energy Efficient Multicommodity Routing

Theory Seminar Kick Off

On Learning, Lower Bounds and (un)Keeping Promises

Impossibility Theorems and the Universal Algebraic Toolkit

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Primal dual gives optimal energy efficient online algorithms

Electricity Pooling Markets with Strategic Producers Possessing Asymmetric Information

Interlacing Families and Kadison–Singer

Physical Randomness Extractors

Diffuse Scattering on Graphs and Combinatorial Inverse Problems

Graph Isomorphism and the Lasserre Hierarchy

Diffuse Scattering on Graphs and Combinatorial Inverse Problems

List decodability of randomly punctured codes

Scalable Sparse Approximation of a Sample Mean

For-all Sparse Recovery in Near-Optimal Time

Learning with Noisy Labels

General truthfulness characterizations via convex analysis

Modal Analysis with Compressive Measurements

Better Approximation Algorithms for Graph Diameter

Pricing, Market Making, Scoring Rules, and Exponential Families

What can a bit tell us? Forays into information scalability.

Theory Seminar Introduction

Coding, Complexity, and Sparsity Workshop

Coding, Complexity, and Sparsity Workshop

Coding, Complexity, and Sparsity Workshop

Byzantine Agreement in Polynomial Expected Time

Dynamic Graph Connectivity in Polylogarithmic Worst Case Time

What gaussian processes can do for you: applications of probability and geometry in theoretical computer science

High-degree graphs cannot be used for a quantum PCP

Every locally characterized affine-invariant property is testable

Recent Progress on Parallel Repetition

Sketching For Big Data Recommender Systems Using Fast Pseudo-Random Fingerprints

Distributed Oblivious RAM for Secure Two-Party Computation

On the Decodability of Primitive Reed-Solomon Codes

One algorithm to rule them all: One join query at a time

Characterizing Strategic Cascades on Networks

The Locality of Distributed Symmetry Breaking

Locally-Decodable Codes

Constructive Discrepancy Minimization by Walking on the Edges

New Approaches to Constructing Locally Decodable Codes

Bankruptcy in Byzantium

Symmetry and Satisfiability: An Update

TBD–possibly cancelled

Unconditional hardness results for semi-definite programs: integrality gaps for the Lasserre hierarchy

Introductions, continued

Introductions and organizational meeting

High-dimensional covariance estimation based on Gaussian graphical models

Debmalya Panigrahi: Survivable Network Design with Node and Edge Costs

Theory Seminar

Theory Seminar

Theory Seminar

Overview of Theory Research

Distributed Deterministic Graph Coloring

Bisimulation for quantum processes

The Complexity of Monotone Graph Properties

Holographic algorithms without matchgates

Denny VandenBerg–Theoretical Computer Science Seminar

Patrick Poon–Theoretical Computer Science Seminar

Carl Miller–The Longest Common Subsequence Problem

Ran Duan–Theoretical Computer Science Seminar

Quentin Stout– Going Up: Isotonic Regression Algorithms

Compressed Sensing Meets Information Theory

On the Computation and Approximation of Two-Player Nash Equilibria

Exchange Market Equilibria with Leontief ’s Utility: Freedom of Pricing Leads to Rationality

Theory Seminar Introductory Talks – R. Sami & S. Pettie

Theory Seminar: Organizational meeting & introductions

The Unbounded-Error Communication Complexity of Symmetric Functions

CSPL/Theory Seminar: Zero-error classical capacity of noisy quantum channels

Leontief Economies Encode Nonzero Sum Two-Player Games

Power, Time, and Location: Parallel algorithms addressing them all

Codeword Stabilized Quantum Codes

Codeword Stabilized Quantum Codes

On the Perfect Distinguishability of Unitary Operations

tba

Recent results in the search for new quantum algorithms

A Global Geometric Framework for Nonlinear Dimensionality Reduction

Publish and Perish

An Optimal Binary Search Tree?

Max-stable Random Sketches: Estimation of Distances, Norms and Dominance Norms

Sublinear Algorithms for Compressed Sensing

Large-scale phylogenetic reconstruction and the Tree of Life

Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance, by Jonathan L. Bredin, Erik D. Demaine, MohammadTaghi Hajiaghayi and Daniela Rus.

Gowers Uniformity, influence of variables, and PCPs

On the Complexity of Numerical Analysis

Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance by Jonathan L. Bredin, Erik D. Demaine, MohammadTaghi Hajiaghayi and Daniela Rus

The search for a quantum algorithm for Graph Isomorphism

FRAIG: A new datastructure for formal verification and circuit synthesis

Quadratic Lower Bounds on Matrix Rigidity

Opt vs. Load in Dynamic Storage Allocation

A Combinatorial Approach to Designing RNA Secondary Structures and DNA Code Words

The Graphics Card As A Stream Computer

A Novel Matrix Decomposition with Applications to Algorithm Design and Massive Data Set Analysis

Fast Monte Carlo Algorithms for Large Matrices and Massive Data Sets

Data Stream Algorithms and Applications

Geometric control in quantum operation generation

From Quantum Cheating to Quantum Security

Neighborhood Structures with Approximation Guarantees

Lower Bounds for Local Search by Quantum Arguments

TBA

Polynomial approximations and quantum lower bounds

Probabistic Transforms in the Analysis of Algorithms