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