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.

Calendar

Upcoming Talks—Fall 2021

Date Speaker Affiliation Title
10/27/21 Vasilis Gkzatkilis Drexel Deterministic Budget-Feasible Clock Auctions
11/03/21 David Tench Rutgers TBA
11/10/21 Grant Schoenebeck UMich TBA
11/17/21 Divyarthi Mohan Tel Aviv TBA
11/24/21 Zihan Tan UChicago TBA
12/01/21 Sumegha Garg Harvard TBA
12/08/21 Merav Parter Weizmann TBA

Past Talks

Fall 2021

Date Speaker Affiliation Title
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