Rutgers/DIMACS Theory of Computing Seminar Jane Street Logo

Organizers: Karthik C.S. and Kangning Wang
Place: CORE 301 (join the mailing list for more information)
Time: Wednesdays 11am–12pm ET
Co-Sponsored by: Jane Street

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
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 ko(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