« Theoretical Computer Science Seminar
Theoretical Computer Science Seminar
January 01, 2007 - December 31, 2027
Location:
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Organizer(s):
Sepehr Assadi, Rutgers University
The primary website for the Theoretical Computer Science Seminar is here.
Monday, May 12, 2025
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 7, 2025
Fully Packed and Ready to Go: Eliminating Rearrangement in High-Density, Grid-based Storage
Tzvika Geft, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 30, 2025
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus V. X. Ferreira, University of Virginia
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 23, 2025
Optimal Resource Capacity Management for Stochastic Networks
Mark Squillante, IBM
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 16, 2025
All-Pairs Max-Flow vs. All-Pairs Shortest-Path
Amir Abboud, Weizmann Institute of Science
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 9, 2025
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Hoai-An Nguyen, Carnegie Mellon University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 2, 2025
Communication Complexity of Load Balancing via Matching Contractors
Aaron Bernstein, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 26, 2025
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Gregory Kehne, Washington University, St. Louis
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 12, 2025
Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint
Xintong Wang, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 5, 2025
Sensitivity Sampling for Coreset-Based Data Selection
Vincent Cohen-Addad, Google
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 26, 2025
A Tight VC-dimension Analysis of Clustering Coresets
Matteo Russo, Sapienza University of Rome
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 19, 2025
Learning with Drifting Input Distributions
Alessio Mazzetto, Brown University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 12, 2025
Nearly Optimal Approximation of Matrix Functions by the Lanczos Method
Noah Amsel, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 5, 2025
Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Shi Li, Nanjing University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 29, 2025
Constant Rate Isometric Embedding of Hamming Metric into Edit Metric
Mursalin Habib, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 22, 2025
On the Search to Settle the Complexity of Approximating Directed Steiner Tree
Bundit Laekhanukit, Shanghai University of Finance and Economics
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 11, 2024
Ghost Value Augmentation for k-Edge Connectivity
Nathan Klein, Boston University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 4, 2024
Modern Expander-Based Error-Correcting Codes
Pedro Paredes, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 20, 2024
Privately Estimating a Gaussian: Efficient, Robust and Optimal
Daniel Alabi, University of Illinois, Urbana-Champaign
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 13, 2024
On the Sudden Death of Thermal Entanglement
Ainesh Bakshi, Massachusetts Institute of Technology
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 6, 2024
Online Mechanism Design with Predictions
Cherlin Zhu, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 30, 2024
Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
Will Ma, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 23, 2024
Hanna Komlos, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 16, 2024
The Online Submodular Assignment Problem
Sherry Sarkar, Carnegie Mellon University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 9, 2024
Fair Allocation of a Conflict Graph
Arpita Biswas, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 2, 2024
Optimal Stopping with Interdependent Values
Divyarthi Mohan, Tel-Aviv University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 25, 2024
Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders
Mitali Bafna, Massachusetts Institute of Technology
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 18, 2024
New Spectral Techniques in Algorithms and Coding Theory: the Kikuchi Matrix Method
Peter Manohar, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 11, 2024
Fair Secretaries with Unfair Predictions
Andreas Maggiori, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 4, 2024
Metric Distortion in Social Choice
Kangning Wang, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 1, 2024
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 24, 2024
Beyond Worst-case Guarantees for Sequential Prediction: Robustness via Abstention
Surbhi Goel, University of Pennsylvania
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 17, 2024
Fast Algorithms for Cactus Representation of Minimum Cuts
Zhongtian He, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 10, 2024
Applications of Tensor Rank to Algorithm Design Beyond Fast Matrix Multiplication
Kevin Pratt, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 3, 2024
The Price of Explainability for Clustering
Anupam Gupta, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 27, 2024
The Discrepancy of Shortest Paths
Chengyuan Deng, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 20, 2024
Extracting Randomness from Samplable Distributions, Revisited
Eli Goldin, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 6, 2024
The Complexity of Dynamic Least-Squares Regression
Shunhua Jiang, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 28, 2024
Parallel Computation of Greatest Common Divisors of Polynomials
Robert Andrews, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 21, 2024
An Exponential Lower Bound on Three Query, Linear Locally Correctable Codes
Pravesh Kothari, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 14, 2024
Sinho Chewi, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 7, 2024
Sub-quadratic (1+eps)-approximate Euclidean Spanners, with Applications
Hengjie Zhang, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 31, 2024
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Michal Koucký, Charles University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 24, 2024
Roie Levin, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 17, 2024
Optimal Bounds on Private Graph Approximation
Zongrui Zou, Nanjing University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 13, 2023
Agreement Testing and Small Set Mixing in High Dimensional Expanders
Yotam Dikstein, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 6, 2023
Recent Advances in Streaming Multi-armed Bandits
Chen Wang, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 29, 2023
Some Recent Advances in Differentially Private Continual Counting
Jalaj Upadhyay, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 15, 2023
Vincent Cohen-Addad, Google
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 8, 2023
Sumegha Garg, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 1, 2023
Blockchain Transaction Fee Mechanisms - an Axiomatic and Non-Myopic Analysis
Yotam Gafni, Technion
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 25, 2023
Exploring the Shape of Data with Persistence Module and Topological Stable Representation
Cheng Xin, Purdue University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 18, 2023
Optimal Online Discrepancy Minimization
Victor Reis, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 11, 2023
Tamalika Mukherjee, Purdue University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 4, 2023
User-Level Differential Privacy With Few Examples Per User
Pasin Manurangsi, Google
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 27, 2023
Thin Trees for Laminar Families
Nathan Klein, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 20, 2023
Maoyuan (Raymond) Song, Purdue University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 13, 2023
2-Dimensional Spectral Expansion of Random Geometric Graphs
Siqi Liu, DIMACS
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 3, 2023
Mechanism Design with Predictions
Xizhi Tan, Drexel University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 26, 2023
Quasi-Linear Relation Between Structure and Randomness
Guy Moshkovitz, The City College and Graduate Center / CUNY
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 19, 2023
Recent Advances in Multi-Pass Graph Streaming Lower Bounds
Sepehr Assadi, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 12, 2023
Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Linda Cai, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 5, 2023
Random Order Streaming Lower Bounds for Connected Components
Janani Sundaresan, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 29, 2023
On Weighted Graph Sparsification by Linear Sketching
Huan Li, University of Pennsylvania
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 22, 2023
Recent Progress on Fault Tolerant Spanners and Emulators
Greg Bodwin, University of Michigan
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 8, 2023
Simple, Deterministic, and Fast (but Weak) Approximation for Edit Distance and Dyck Edit Distance
Mike Saks, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 1, 2023
Graph Sparsification and Kadison-Singer Problem
Surya Teja Gavva, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 22, 2023
Smoothed Analysis of the Simplex Method
Sophie Huiberts, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 15, 2023
Estimating Paramethers of a Network by Crawling
Shahrzad Haddadan, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 8, 2023
Optimal Oblivious Reconfigurable Networks
Tegan Wilson, Cornell University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 1, 2023
Shivam Nadimpalli, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 25, 2023
Linear Space Data Structures for Finite Groups with Constant Query-Time
Bireswar Das, Indian Institute of Technology, Gandhinagar
Online Event
Wednesday, January 18, 2023
Distance-Estimation Algorithms and Hardness for Modern Graphs
Nicole Wein, DIMACS
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 14, 2022
Constant-Depth Sorting Networks
Vladimir Podolskii, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 7, 2022
Universal Sorting: Finding a DAG with Priced Comparisons
Mayank Goswami, The City College and Graduate Center / CUNY
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 30, 2022
Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs
Kunal Mittal, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 16, 2022
Post-hoc Explanations: Unifications, Robustness and Disagreements
Shahin Jabbari, Drexel University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 9, 2022
Bundit Laekhanukit, Shanghai University of Finance and Economics
Online Event
Wednesday, November 2, 2022
Jessica Sorrell, University of Pennsylvania
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 26, 2022
Random Restrictions on Boolean Functions with Small Influences
Pei Wu, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 19, 2022
Cut Query Algorithms Using Star Contraction
Yuval Efron, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 12, 2022
Wednesday, October 5, 2022
Advanced Encryption Systems for RAMs
Xiong (Leo) Fan, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 28, 2022
Near-Linear eps-Emulators for Planar Graphs
Zihan Tan, DIMACS
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 21, 2022
A New Characterization of Statistical Zero Knowledge
Harsha Tiramula, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 14, 2022
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Aaron Bernstein, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 4, 2022
Distributed Degree+1-Coloring and Applications
Magnús Halldórsson, Reykjavik University
Online Event
Wednesday, April 27, 2022
Wednesday, April 20, 2022
Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs
Jakub Tetek, University of Copenhagen
Online Event
Wednesday, April 13, 2022
Slobodan Mitrovic, University of California, Davis
Online Event
Wednesday, April 6, 2022
Highly-efficient Interactive Oracle Proofs & Cryptographic Applications
Noga Ron-Zewi, University of Haifa
Online Event
Wednesday, March 30, 2022
Privately Estimating Graph Parameters in Sublinear Time
Tamalika Mukherjee, Purdue University
Online Event
Wednesday, March 23, 2022
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Peilin Zhong, Google
Online Event
Wednesday, March 9, 2022
Strongly Sublinear Algorithms for Testing Pattern Freeness
Nithin Varma, Chennai Mathematical Institute, India
Online Event
Wednesday, March 2, 2022
Mrinal Kumar, IIT Bombay
Online Event
Wednesday, February 23, 2022
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
Mahsa Derakhshan, University of California, Berkeley
Online Event
Wednesday, February 16, 2022
Algorithms Using Local Graph Features to Predict Epidemics
Yeganeh Alimohammadi, Stanford University
Online Event
Wednesday, February 9, 2022
Almost Optimal Inapproximability of Multidimensional Packing Problems
Sai Sandeep, Carnegie Mellon University
Online Event
Wednesday, February 2, 2022
Wednesday, January 26, 2022
The Zero Rate Threshold For Adversarial Bit-Deletions is Less Than 1/2
Ray Li, Stanford University
Online Event
Wednesday, January 19, 2022
Converse and Achievable Bounds for Finite Length Quantum Codes in Quantum Erasure Channel
Alexei Ashikhmin, Bell Labs
Online Event
Wednesday, December 8, 2021
New Diameter Reducing Shortcuts: Breaking the $O(sqrt{n})$ Barrier
Merav Pater, Weizmann Institute of Science
Online Event
Wednesday, December 1, 2021
Wednesday, November 24, 2021
Wednesday, November 17, 2021
Simplicity and Optimality in Multi-Item Auctions
Divyarthi Mohan, Tel-Aviv University
Online Event
Wednesday, November 10, 2021
Wednesday, November 3, 2021
Wednesday, October 27, 2021
Wednesday, October 20, 2021
Wednesday, October 13, 2021
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
Soheil Behnezhad, Northeastern University
Online Event
Wednesday, October 6, 2021
Hardness for Structured Linear Equations and Linear Programs
Peng Zhang, Rutgers University
Online Event
Wednesday, September 29, 2021
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
Roei Tell, DIMACS
Online Event
Wednesday, September 22, 2021
Wednesday, September 15, 2021
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity
Eric Allender, Rutgers University
Online Event
Wednesday, May 5, 2021
Eric Balkanski, Columbia University
Online Event
Wednesday, April 28, 2021
Maintaining and Rounding Dynamic Fractional Matchings
Sayan Bhattacharya, University of Warwick
Online Event
Wednesday, April 21, 2021
Distance Oracles for Planar Graphs
Christian Wulff-Nilsen, University of Copenhagen
Online Event
Wednesday, April 14, 2021
Dynamic Longest Increasing Subsequence and the Erdos-Szekeres Partitioning Problem
Saeed Seddighin, Toyota Technological Institute at Chicago (TTIC)
Online Event
Wednesday, April 7, 2021
New Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirooyfard, Massachusetts Institute of Technology
Online Event
Wednesday, March 31, 2021
Breaking the 2^n barrier for 5-coloring and 6-coloring
Or Zamir, Institute for Advanced Study
Online Event
Wednesday, March 24, 2021
Approximation Algorithms for Max-CSPs in the Streaming Model
Santhoshini Velusamy, Harvard University
Online Event
Wednesday, March 10, 2021
Learning Low-Rank Tensors and Depth-3 Multilinear Circuits
Vishwas Bhargava, Rutgers University
Online Event
Wednesday, March 3, 2021
Approximating Edit Distance in Near-Linear Time
Alexandr Andoni, Columbia University
Online Event
Wednesday, January 20, 2021
Near-Optimal Algorithms for Approximate Min-Cost Flow and Dynamic Shortest Paths
Aaron Bernstein, Rutgers University
Online Event
Wednesday, December 9, 2020
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graphs
Christian Konrad, University of Bristol
Online Event
Wednesday, November 18, 2020
Wednesday, November 11, 2020
On Communicating Over Networks Without Revealing Their Topology
Marshall Ball, Columbia University
Online Event
Wednesday, November 4, 2020
Faster K-clique Counting in Bounded Arboricity Graphs
Tayla Eden, Massachusetts Institute of Technology
Online Event
Wednesday, October 28, 2020
Wednesday, October 21, 2020
Recent Applications of Expanders to Graph Algorithms
Thatchaphol Saranurak, University of Michigan
Online Event
Wednesday, October 14, 2020
Deeparnab Chakrabarty, Dartmouth College
Online Event
Wednesday, October 7, 2020
Network Coding Gaps for Completion Times of Multiple Unicasts
David Wajc, Stanford University
Online Event
Wednesday, September 30, 2020
The Worker-Task Assignment Problem
Nicole Wein, Massachusetts Institute of Technology
Online Event
Wednesday, September 23, 2020
Wednesday, September 16, 2020
Range Query on Planar Graphs and Applications on Spatial Sensing with Privacy
Jie Gao, Rutgers University
Online Event
Wednesday, September 9, 2020
Optimal and Approximately Optimal Mechanism Design Beyond a Single Dimension
Ariel Schvartzman, DIMACS
Online Event
Wednesday, March 11, 2020
Chen Wang, Rutgers University
CoRE Building Room 431
Wednesday, March 4, 2020
Stochastic Local Search and the Lovasz Local Lemma
Fotis Iliopoulos, Institute for Advanced Study
CoRE Building Room 431
Wednesday, February 26, 2020
An Adaptive Step Toward the Multiphase Conjecture
Omri Weinstein, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 19, 2020
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
Ariel Schvartzman, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 12, 2020
Structure and Dynamics of Contagion in Financial Networks
Victor Amelkin, University of Pennsylvania
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 5, 2020
Scattering and Sparse Partitions, and their Applications
Arnold Filtser, Bar-Ilan University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 29, 2020
Ben Lund, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 22, 2020
Hardness of Generators for Invariant Rings
Visu Makam, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 11, 2019
Double-Samplers and Local-to-Global List Decoding
Irit Dinur, Weizmann Institute of Science
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 4, 2019
The Karger-Stein Algorithm is Optimal for k-cut
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
The Karger-Stein Algorithm is Optimal for k-cut
Euiwoong Lee, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 20, 2019
Online Vector Balancing and Geometric Discrepancy
Sahil Singla, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 13, 2019
Optimal Data Acquisition for Statistical Estimation
Juba Ziani, University of Pennsylvania
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 6, 2019
Mert Gürbüzbalaban, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Dor Minzer, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 30, 2019
An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices
Jarosław Błasiok, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 23, 2019
The Asymptotic Spectrum of Tensors and Barriers for Fast Matrix Multiplication
Jeroen Zuiddan, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 16, 2019
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Robert Robere, DIMACS
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 9, 2019
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
Shay Moran, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 2, 2019
Thodoris Lykouris, Microsoft Research
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Implicit Regularization for Optimal Sparse Recovery
Varun Kanade, University of Oxford
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 25, 2019
Huacheng Yu, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 18, 2019
On Multilinear Forms: Bias, Correlation, and Tensor Rank
Abhishek Bhrushundi, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 11, 2019
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Sepehr Assadi, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 4, 2019
Guy Moshkovitz , Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 8, 2019
Codes for Secure Distributed Matrix Multiplication
Salim El Rouayheb, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 1, 2019
A Sharper Bound for the Joints Problem
Ben Lund, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 24, 2019
A Triangle Algorithm for Semidefinite Version of Convex Hull Membership Problem
Bahman Kalantari, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 17, 2019
Strong Direct Sum for Randomized Query Complexity
Joshua Brody, Swarthmore College
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 10, 2019
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 3, 2019
Analyzing Optimization in Deep Learning via Trajectories
Cohen Nadav, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 27, 2019
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel
Xi Chen, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 13, 2019
Near Log-Convexity of Heat and the K-Hamming Distance Problem
Mert Saglam, University of Washington
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 27, 2019
Planarity, Exclusivity, and Unambiguity
Eric Allender, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 20, 2019
Bloom Filters, Adaptivity and the Dictionary Problem
Shikha Singh, Wellesley College
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 6, 2019
Samira Samadi, Georgia Institute of Technology
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 30, 2019
Torus Polynomials: an Algebraic Approach to ACC Lower Bounds
Abhishek Bhrushundi, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 23, 2019
Lifting with Simple Gadgets and Applications for Cutting Planes
Robert Robere, DIMACS
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 12, 2018
Approximating the Edit Distance to Within a Constant Factor in Truly Subquadratic Time
Mike Saks, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 14, 2018
Online Bipartite Matching with Amortized O(log^2 N) Replacements
Aaron Bernstein, Harvard University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 7, 2018
Efficient Algorithms for Tensor Scaline, Quantum Marginals, and Moment Polytopes
Cole Franks, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 24, 2018
Probing Algorithms for Combinatorial Optimization Under Uncertainty
Sahil Singla, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 10, 2018
On Communication Complexity of Classification Problems
Shay Moran, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, May 2, 2018
Sepideh Mahabadi, Columbia University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 25, 2018
Between Shannon and Hamming: the impact of delay on communication capacity
Anand Sarwate, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 18, 2018
Taking Control by Convex Optimization
Karan Singh, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 11, 2018
K-means Clustering with Optimization
Soledad Villar, New York University (NYU)
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, April 4, 2018
Madhu Sudan, Harvard University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, March 28, 2018
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Sumegha Garg, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 28, 2018
Complete Derandomization of Identity Testing of Read-Once Formulas
IIya Volkovich, University of Michigan
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 21, 2018
Some Closure Results for Polynomial Factorization
Mrinal Kumar, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 14, 2018
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Gil Cohen, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, February 7, 2018
Mina Ghashami, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 31, 2018
Monotonicity Problems in Graph Theory
Bhargav Narayanan, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, January 24, 2018
On the Expressiveness of Comparison Queries
Shay Moran, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 13, 2017
Classical and Quantum Walks: Similarities and Differences with Emphasis on Recurrence Properties
F. Alberto Grünbaum, University of California, Berkeley
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, December 6, 2017
Greg Bodwin, Massachusetts Institute of Technology
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 29, 2017
Toniann Pitassi, University of Toronto
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 15, 2017
Syndrome Decoding of Reed-Muller Codes and Tensor Decomposition over Finite Fields
Aditya Potukuchi, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 8, 2017
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Omri Weinstein, Columbia University
DIMACS Seminar Room
Rutgers University
CoRE Building, Room 431
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, November 1, 2017
The MMap Strikes Back: Conquering Cryptography using Weak Multilinear Maps
Mark Zhandry, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 25, 2017
Towards Optimal Randomness Extractors and Ramsey Graphs
Eshan Chattopadhyay, Institute for Advanced Study
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 18, 2017
A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
Steven Wu, University of Pennsylvania
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 11, 2017
Practical Data-Dependent Metric Compression with Provable Guarantees
Ilya Razenshteyn, Columbia University
DIMACS Seminar Room
Rutgers University
CoRE Building, Room 431
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, October 4, 2017
A Computer Scientist Thinks about the Brain
Christos Papadimitriou, University of California, Berkeley
SERC Room 111
Rutgers University
Science and Engineering Resource Center (SERC)
118 Frelinghuysen Road
Piscataway, NJ 08854-8019
Wednesday, September 27, 2017
On the Quantitative Hardness of CVP
Noah Stephens-Davidowitz, Princeton University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 20, 2017
Machine Learning in a Setting of Ordinal Distance Information
Matthäus Kleindessner, University of Tübingen
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Wednesday, September 13, 2017
Efficient PAC Learning from the Crowd
Pranjal Awasthi, Rutgers University
Conference Room 301
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854