Rutgers/DIMACS Theory of Computing Seminar

Directions

For those arriving by train to New Brunswick station, the best way to get to the seminar room is by Rutgers bus. The directions are available by clicking here.

For those driving in, the best strategy is to pre-arrange to pick up a parking tag from one of the organizers upon arrival, and park in lot 64. For directions to Lot 64, click here.

For Participants

There is a mailing list where the announcements of talks and other related information appear. You can subscribe to this list here.

Calendar

Past Talks

Spring 2026

Date	Speaker	Affiliation	Title
04/08/26	Mehtaab Sawhney	Columbia/OpenAI	Quasipolynomial bounds for the corners theorem
04/01/26	Erik Waingarten	UPenn	A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
03/25/26	Chengyuan Deng	Rutgers	Locality Sensitive Hashing in Hyperbolic Space
03/11/26	Elena Gribelyuk	Princeton	Adversarial Robustness on Insertion-Deletion Streams
03/04/26	Romain Cosson	NYU	Online algorithms for multi-agent exploration
02/25/26	George Li	CMU	Bellman-Ford in Almost-Linear Time for Dense Graphs
02/18/26	Ani Sridhar	NJIT	New perspectives on learning networks from dynamics
02/11/26	Feyza Duman Keles	NYU	An Exact Algorithm for the Unanimous Vote Problem
02/04/26	Max Hopkins	IAS	As Hard as it Gets: Hardness Amplification and Local List Decoding from HDX
01/28/26	Aarushi Goel	Rutgers	Multiparty Distributed Point Functions
01/21/26	Akash Kumar Sengupta	Rutgers	Robust Local Testability of Tensor Products of Algebraic Geometry Codes

Fall 2025

Date	Speaker	Affiliation	Title
12/10/25	Rachit Garg	NYU	Succinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
12/03/25	Rahul Ilango	IAS	Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness
11/19/25	Chen Wang	RPI	Tree Reconstruction from Noisy Triplet Queries: Hierarchical Clustering and Beyond
11/12/25	Ashwin Padaki	UPenn	Sparse Navigable Graphs for Nearest Neighbor Search
11/05/25	Dor Minzer	MIT	Multi-Pass Streaming Lower Bound for Max-Cut
10/29/25	Tomer Ezra	Harvard	Algorithmic Contract Design
10/15/25	Meena Jagadeesan	UPenn	Power and Limitations of Aggregation in Compound AI Systems
10/08/25	Vikrant Ashvinkumar	Rutgers	Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
10/01/25	Shuangping Li	Yale	Some easy optimization problems have the overlap-gap property
09/24/25	Binghui Peng	Google	High dimensional online calibration in polynomial time
09/17/25	Kewen Wu	IAS	Locally Sampleable (Uniform) Symmetric Distributions
09/10/25	Yuhao Li	Columbia University	The Mysterious Query Complexity of Tarski Fixed Points
09/03/25	Emil Saucan	Braude College of Engineering	The Versatile Forman-Ricci curvature and its Networks Applications

Spring 2025

Date	Speaker	Affiliation	Title
05/12/25	Lance Fortnow	Illinois Institute of Technology	Complexity in the Era of AI and Data-Driven Computing
05/07/25	Tzvika Geft	Rutgers	Fully Packed and Ready to Go-Eliminating Rearrangement in High-density Grid-based Storage
04/30/25	Matheus V. X. Ferreira	U Virginia	Credible Decentralized Exchange Design via Verifiable Sequential Rules
04/23/25	Mark Squillante	IBM	Optimal Resource Capacity Management for Stochastic Networks
04/16/25	Amir Abboud	Weizmann Institute	All-Pairs Max-Flow vs. All-Pairs Shortest Paths
04/09/25	Hoai-An Nguyen	CMU	Maximum Coverage in Turnstile Streams with Applications to Fingerprint Measures
04/02/25	Aaron Bernstein	NYU	Communication Complexity of Load Balancing via Matching Contractors.
03/26/25	Gregory Kehne	WUSTL	A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
03/12/25	Xintong Wang	Rutgers	Designing Automated Market Makers for Combinatorial Securities, A Geometric Viewpoint
03/05/25	Vincent Cohen-Addad	Google	Sensitivity Sampling for Coreset-Based Data Selection
02/26/25	Matteo Russo	Sapienza University	A Tight VC-dimension Analysis of Clustering Coresets
02/19/25	Alessio Mazzetto	Brown University	Learning with Drifting Input Distributions
02/12/25	Noah Amsel	NYU	Nearly Optimal Approximation of Matrix Functions by the Lanczos Method
02/05/25	Shi Li	Nanjing University	Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
01/29/25	Mursalin Habib	Rutgers	Constant Rate Isometric Embedding of Hamming Metric into Edit Metric.
01/22/25	Bundit Laekhanukit	Independent	On the search to settle the complexity of approximating directed Steiner tree.

Fall 2024

Date	Speaker	Affiliation	Title
12/11/24	Nathan Klein	Boston University	Ghost Value Augmentation for k-Edge-Connectivity
12/04/24	Pedro Paredes	Princeton	Modern Expander-Based Error-Correcting Codes
11/20/24	Daniel Alabi	UIUC	Privately Estimating a Gaussian--Efficient, Robust and Optimal
11/13/24	Ainesh Bakshi	MIT	On the Sudden Death of Thermal Entanglement
11/06/24	Cherlin Zhu	Columbia	Online Mechanism Design with Predictions
10/30/24	Will Ma	Columbia	Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
10/23/24	Hanna Komlos	NYU	Nearly Optimal List Labeling
10/16/24	Sherry Sarkar	CMU	The Online Submodular Assignment Problem
10/09/24	Arpita Biswas	Rutgers	Fair Allocation of a Conflict Graph
10/02/24	Divyarthi Mohan	Boston University	Optimal Stopping with Interdependent Values
09/25/24	Mitali Bafna	MIT	Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders
09/18/24	Peter Manohar	IAS	New Spectral Techniques in Algorithms and Coding Theory, the Kikuchi Matrix Method
09/11/24	Andreas Maggiori	Columbia	Fair Secretaries with Unfair Predictions
09/04/24	Kangning Wang	Rutgers	Metric Distortion in Social Choice

Spring 2024

Date	Speaker	Affiliation	Title
05/01/24	Uma Girish	Princeton	Fourier Growth of Communication Protocols for XOR Functions
04/24/24	Surbhi Goel	UPenn	Beyond Worst-case Guarantees for Sequential Prediction: Robustness via Abstention
04/17/24	Zhongtian He	Princeton	Fast Algorithms for Cactus Representation of Minimum Cuts
04/10/24	Kevin Pratt	NYU	Application of Tensor Rank to Algorithm Design Beyond Fast Matrix Multiplication
04/03/24	Anupam Gupta	NYU	The Price of Explainability of Clustering
03/27/24	Chengyuan Deng	Rutgers	The Discrepancy of Shortest Paths
03/20/24	Eli Goldin	NYU	Extracting Randomness from Samplable Distributions, Revised
03/06/24	Shunhua Jiang	Columbia University	The Complexity of Dynamic Least-square Regression
02/28/24	Robert Andrews	IAS	Parallel Computation of Greatest Common Devisor of Polynomials
02/21/24	Pravesh K. Kothari	Princeton University	An Exponential Lower Bound on Tree Query, Linear Query, Linear Locally Correctable Codes
02/14/24	Sinho Chewi	IAS	Log-concave Sampling
02/07/24	Hengjie Zhang	Columbia University	Sub-quadratic (1+eps)-approximate Euclidean Spanners, with Applications
01/31/24	Michal Kouchy	Charles University	Locally Consistent Decomposition of Strings with Applications to Edit Distance
01/24/24	Roie Levin	Rutgers	Chasing Convex Bodies
01/17/24	Zongrui Zou	Nanjing University	Optimal Bounds on Private Graph Approximation

Fall 2023

Date	Speaker	Affiliation	Title
12/13/23	Yotam Dikstein	IAS	Agreement Testing and Small Set Mixing in High Dimension Expanders
12/06/23	Chen Wang	Rutgers	Recent Advances in Streaming Multi-armed Bandits
11/29/23	Jalaj Upadhyay	Rutgers	Some Recent Advances in Differentially Private Countinual Counting
11/15/23	Vincent Cohen-Addad	Google	Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
11/08/23	Sumegha Garg	Rutgers	Online Omniprediction
11/01/23	Yotam Gafni	Technion	Blockchain Transaction Fee Mechanisms - an Axiomatic and Non-Myopic Analysis
10/25/23	Cheng Xin	Rutgeres	Exploring the Shape of Data with Persistence Module and Topological Stable Representation
10/18/23	Victor Reis	IAS	Optimal Online Discrepancy Minimization
10/11/23	Tamalika Mukherjee	Columbia	How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
10/04/23	Pasin Manurangsi	Google	User-Level Differential Privacy With Few Examples Per User
09/27/23	Nathan Klein	IAS	Thin Trees for Laminar Families
09/20/23	Maoyuan Song	Purdue	Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+ lpha$-th Moments
09/13/23	Siqi Liu	IAS & DIMACS	2-dimensional spectral expansion of random geometric graphs

Spring 2023

Date	Speaker	Affiliation	Title
05/03/23	Xizhi Tan	Drexel	Mechanical Design with Predictions
04/26/23	Guy Moshkovitz	CUNY	Quasi-linear relation between structure and randomness
04/19/23	Sepehr Assadi	Rutgers	Recent Advances in Multi-Pass Graph Streaming Lower Bounds
04/12/23	Linda Cai	Princeton	Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
04/05/23	Janani Sundaresan	Rutgers	Random Order Streaming Lower Bounds for Connected Components
03/29/23	Huan Li	University of Pennsylvania	On Weighted Graph Sparsification by Linear Sketching
03/22/23	Greg Bodwin	University of Michigan	Recent progress on fault tolerant spanners and emulators
03/08/23	Mickael Saks	Rutgers	Simple, deterministic, and fast (but weak) approximation for Edit Distance and Dyck Edit Distance
03/01/23	Surya Teja Gavva	Rutgers	Graph Sparsification and Kadison-Singer Problem
02/22/23	Sophie Huiberts	Columbia	Smoothed Analysis of the Simplex Method
02/15/23	Shahrzad Haddadan	Rutgers	Estimating Parameters of a Network by Crawling
02/08/23	Tegan Wilson	Cornell	Optimal Oblivious Reconfigurable Networks
02/01/23	Shivam Nadimpalli	Columbia	Testing Convex Truncation
01/25/23	Bireswar Das	IIT Gandhinagar	Linear-space Data Structures for Finite Groups with Constant Query-time
01/18/23	Nicole Wein	DIMACS	Distance Estimation Algorithms and Hardness for Modern Graphs

Fall 2022

Date	Speaker	Affiliation	Title
12/14/22	Vladimir Podolskii	NYU	TBA
12/07/22	Mayank Guswami	CUNY	Universal Sorting: Finding a DAG with Priced Comparisons
11/30/22	Kunal Mittal	Princeton	Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs
11/16/22	Shahin Jabbari	Drexel	Post-hoc explanations: Unifications, Robustness and Disagreements
11/09/22	Bundit Laekhanukit	Shanghai University of Finance and Economics	Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
11/02/22	Jessica Sorrell	Upenn	Reproducibility in Learning
10/26/22	Pei Wu	IAS	Random restrictions on boolean functions with small influences
10/19/22	Yuval Efron	Columbia	Cut Query Algorithms Using Star Contraction
10/12/22	Prantar Ghosh	Rutgers/DIMACS	Adversarially Robust Coloring for Graph Streams
10/05/22	Xiong (Leo) Fan	Rutgers	Advanced Encryption Systems for RAMs
09/28/22	Zihan Tan	Rutgers/DIMACS	Near-Linear eps-Emulators for Planar Graphs
09/21/22	Harsha Tirumala	Rutgers	A New Characterization of Statistical Zero Knowledge
09/14/22	Aaron Bernstein	Rutgers	Negative-Weight Single-Source Shortest Paths in Near-linear Time

Spring 2022

Date	Speaker	Affiliation	Title
05/04/22	Magnús Halldórsson	Reykjavik University	Distributed Degree+1-Coloring and Applications
04/27/22	Nicole Wein	DIMACS	Online List Labeling: Breaking the log^2 n Barrier
04/20/22	Jakub Tetek	University of Copenhagen	Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs
04/13/22	Slobodan Mitrovic	UC Davis	Deterministic (1+ε)-Approximate Maximum Matching with 𝗉𝗈𝗅𝗒(1/ε) Passes in the Semi-Streaming Model and Beyond
04/06/22	Noga Ron-Zewi	University of Haifa	Highly-efficient Interactive Oracle Proofs & Cryptographic Applications
03/30/22	Tamalika Mukherjee	Purdue	Privately Estimating Graph Parameters in Sublinear time
03/23/22	Peilin Zhong	Google	Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
03/09/22	Nithin Varma	CMI	Strongly sublinear algorithms for testing pattern freeness
03/02/22	Mrinal Kumar	IIT Bombay	Fast multivariate multipoint evaluation over finite fields of small characteristic (and applications)
02/23/22	Mahsa Derakhshan	Berkeley	Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
02/16/22	Yeganeh Alimohammadi	Stanford	Algorithms using Local Graph Features to Predict Epidemics
02/09/22	Sai Sandeep	CMU	Almost optimal inapproximability of multidimensional packing problems
02/02/22	Joshua Brody	Swarthmore/DIMACS	Open Problems in NOF Communication Complexity
01/26/22	Ray Li	Stanford	The zero rate threshold for adversarial bit-deletions is less than 1/2
01/19/22	Alexei Ashikhmin	Bell Labs	Converse and Achievability Bounds for Finite Length Quantum Codes in Quantum Erasure Channel

Fall 2021

Date	Speaker	Affiliation	Title
12/08/21	Merav Parter	Weizmann	New Diameter Reducing Shortcuts: Breaking the O(sqrt{n}) Barrier
12/01/21	Sumegha Garg	Harvard	Tight Space Complexity of the Coin Problem
11/24/21	Zihan Tan	UChicago	Better Approximation of Graph Crossing Number
11/17/21	Divyarthi Mohan	Tel Aviv	Simplicity and Optimality in Multi-Item Auctions
11/10/21	Grant Schoenebeck	UMich	Eliciting Expert Information without Verification
11/03/21	David Tench	Rutgers	Making Graph Sketching Practical
10/27/21	Vasilis Gkzatkilis	Drexel	Deterministic Budget-Feasible Clock Auctions
10/20/21	Nicole Wein	DIMACS	Lower Bounds for Shortcut Sets and Additive Spanners
10/13/21	Soheil Behnezhad	Stanford	Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
10/06/21	Peng Zhang	Rutgers	Hardness for structured linear equations and linear programs
09/29/21	Roei Tell	DIMACS/IAS	Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
09/22/21	Karthik C.S.	Rutgers	Reversing Color Coding
09/15/21	Eric Allender	Rutgers	Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

Spring 2021

Date	Speaker	Affiliation	Title
05/05/21	Eric Balkanski	Columbia	An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
04/28/21	Sayan Bhattacharya	University of Warwick	Maintaining and rounding dynamic fractional matchings
04/21/21	Christian Wulff-Nilsen	University of Copenhagen	Distance Oracles for Planar Graphs
04/14/21	Saeed Seddighin	TTIC	Dynamic Longest Increasing Subsequence and the Erdos-Szekeres Partitioning Problem
04/07/21	Mina Dalirooyfard	MIT	New conditional lower bounds for approximating diameter in directed graphs
03/31/21	Or Zamir	IAS	Breaking the 2^n barrier for 5-coloring and 6-coloring
03/24/21	Santhoshini Velusamy	Harvard	Approximation algorithms for Max-CSPs in the streaming model
03/10/21	Vishwas Bhargava	Rutgers	Learning Low-Rank Tensors and Depth-3 Multilinear Circuits
03/03/21	Alex Andoni	Columbia	Approximating Edit Distance in Near-Linear Time
01/20/21	Aaron Bernstein	Rutgers	Near-Optimal Algorithms for Approximate Min-Cost Flow and Dynamic Shortest Paths

Fall 2020

Date	Speaker	Affiliation	Title
12/16/20	Jan van den Brand	KTH	From Interior Point Methods to Data Structures and Back
12/09/20	Christian Konrad	University of Bristol	Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
11/18/20	Martin Farach-Colton	Rutgers	Balls and Bins and Icebergs
11/11/20	Marshall Ball	Columbia	On Communicating over Networks without Revealing their Topology
11/04/20	Talya Eden	MIT	Faster k-clique counting in bounded arboricity graphs
10/28/20	Seth Pettie	UMich	Planar Distance Oracles
10/21/20	Thatchaphol Saranurak	TTIC/UMich	Recent Applications of Expanders to Graph Algorithms
10/14/20	Deeparnab Chakrabarty	Dartmouth	Graph Connectivity and Single Element Recovery via Linear and OR Measurements: Rounds v Query Trade-offs
10/07/20	David Wajc	Stanford	Network Coding Gaps for Completion Times of Multiple Unicasts
09/30/20	Nicole Wein	MIT	The Worker-Task Assignment Problem
09/23/20	Zach Langley	Rutgers	Improved Bounds for Distributed Load Balancing
09/16/20	Jie Gao	Rutgers	Range Query on Planar Graphs and Applications on Spatial Sensing with Privacy
09/09/20	Ariel Schvartzman	Rutgers/DIMACS	Optimal and Approximately Optimal Mechanism Design Beyond a Single Dimension

Interested in Giving a Talk?

Send an email to the organizers.

Previous iterations of the seminar: Spring 2020, Fall 2019, Spring 2018, Fall 2017