Rutgers/DIMACS Theory of Computing Seminar

Organizers: Sumegha Garg and Roie Levin
Place: CORE 301 (join the mailing list for more information)
Time: Wednesdays 11am–12pm ET

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 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+ps)-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/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