Rutgers/DIMACS Theory of Computing Seminar

Organizer: Sepehr Assadi
Place: Online (join the mailing list for the link)
Time: Wednesdays 11am–12pm ET

For Participants

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


Past Talks

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