Theory Lunch Schedule Archive
Fall 2023 (Every Thursday from 12:00pm to 1:30pm in SAL 213)
- 08/24 Logistics
- 08/31 Yu-Hsuan Huang Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium
- 09/07 Yusuf Kalayci Proportional Representation in Metric Spaces and Low-Distortion Committee Selection
- 09/14 David Lee Quality Diversity Optimization
- 09/21 Grayson York Nondeterministic Temperature 1 Self Assembly in 2 Dimensions is Undecidable
- 09/27 Shuo Wang Tight Streaming Lower Bounds for the Needle Problem and Its Applications
- 10/05 Matt Ferland What is an Algorithms Course? Survey Results of Introductory Undergraduate Algorithms Courses in the US
- 10/19 Sumeet Shigure A flaw in the NeurIPS unlearning challenge and an algorithmic framework for entropy regularization. Also: Dynamic point set problems in the plane.
- 10/26 Xinyu Mao Instantiating the Random Oracle in Fujisaki-Okamoto Transform via UCEs and ELFs
- 11/02 Aravind Srinivasan On various notions of negative dependence
- 11/16 Abhishek Shetty Optimal PAC Bounds without Uniform Convergence
- 11/30 Julian Asilis Regularization and Optimal Multiclass Learning
Spring 2023 (Every Thursday from 12:00pm to 1:30pm in SAL 213)
- 01/19 Jiapeng Zhang Streaming Lower Bounds and Asymmetric Set-Disjointness
- 01/26 Mi-Ying (Miryam) Huang Secure Multiparty Computation: A short introduction
- 02/02 Zihan An introduction to Stabilizer Algebra and Quantum Error Correction
- 02/09 Fatih Erdem Kizilkaya Matchings Witness Candidates in the Generalized Veto Core: A Practical Voting Rule with Optimal Metric Distortion
- 02/16 Neel Patel Stationary Combinatorial Prophet Inequalities
- 02/23 Chandra Sekhar Mukherjee Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms
- 03/02 Aditya Prasad and Ramiro Deo-Campo Vuong Supermodular Combinatorial Contracts
- 03/09 Daniel Reichman Computational problems arising from stopping contagious processes over networks
- 03/23 Xinyu Mao On the Communication Complexity of Key-Agreement Protocols (in Random Oracle Model)
- 03/30 David Kempe Allocating with Priorities and Quotas: Algorithms, Complexity, and Dynamics
- 04/13 Yusuf Kalayci Fairness in Committee Selection: A Metric Distortion Approach
- 04/20 Noam Mazor Incompressiblity and Next-Block Pseudoentropy
- 04/26 Misha Khodak New Directions in Algorithms with Predictions: Learning and Privacy
- 05/04 Matt Ferland We watched Matt compete on The Price is Right! He won a projector!
Fall 2022 (Every Thursday from 12:00pm to 1:30pm in SAL 213)
- 09/01 Haipeng Luo Near-Optimal No-Regret Learning for General Convex Games - The Role of Positive Regret
- 09/08 Shaddin Dughmi Delegated Probing in Stochastic Combinatorial Optimization
- 09/15 Guangxu Yang Communication lower Bounds via simulation methods
- 09/22 Xinyu Mao Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions
- 09/29 Yusuf Hakan Kalayci Sparsification of Stochastic Packing Problems
- 10/06 Vikram Kher Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling
- 10/13 Fall Recess
- 10/20 Mi-Ying Miryam Huang Public Verifiability: The long arm of quantum law
- 10/27 Tiancheng Jin Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs
- 11/17 Calvin Leng Generalised Binary Search
- 11/24 Thanksgiving
- 12/1 Sid Devic Fairness in Two-Sided Matching Markets with Uncertainty
Spring 2022 (Every Thursday at 2:00pm in SAL 213 and on Zoom)
- 01/27 Sid Devic Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions
- 02/03 Fatih Kizilkaya Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
- 02/10 Jack Depascale Branching Programs and How to Fool Them: An Introduction to Small-Space Derandomization
- 02/17 Shaddin Dughmi Matroid Secretary is Equivalent to Contention Resolution
- 02/24 Matt Ferland Nimber-Preserving Reduction: Game Secrets and Homomorphic Sprague-Grundy Theorem
- 03/03 Vatsal Sharan Omnipredictors
- 03/10 Yusuf Kalayci Sparse Stochastic Optimization
- 03/17 Spring Break
- 03/24 Neel Patel Stochastic Matching with a Few Queries: Existing Algorithms and Challenges
- 03/31 Chandra Sekhar Mukherjee Compressibility: Impact of PCA in Clustering Problems
- 04/07 Curtis Bechtel The Power of Two Choices in Load Balancing and Random Walks
- 04/14 Miryam Huang Multiparty Quantum Computation Secure with Identifiable Abort
- 04/21 Li Chen (Georgia Tech) Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
- 04/28 Eric Vigoda (UC Santa Barbara) Computational Phase Transition and MCMC Algorithms
- 05/05 Finals
- 05/10 Michał Godziszewski (University of Warsaw) Adversarial Link Prediction in Spatial Networks
Fall 2021 (Every Thursday at 10:30am in SAL 213 and on Zoom)
- 09/02 Vatsal Sharan Sample Amplification: Increasing Dataset Size even when Learning is Impossible
- 09/09 Curtis Bechtel On Separating Points From Lines
- 09/16 David Kempe Threshold Tests as Quality Signals: Optimal Strategies, Equilibria, and Price of Anarchy
- 09/23 Jiapeng Zhang Time-Space Lower Bounds via Entropy Compression
- 09/30 Calvin Leng An Automated Approach to the Collatz Conjecture
- 10/07 Ray Li (Stanford) Approximating Graph Diameter: Algorithms, Hardness, and Hardness of Hardness
- 10/14 Fall Recess
- 10/21 Matthew Ferland Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
- 10/28 Nikhil Garg (Cornell Tech) Combatting Gerrymandering with Social Choice: the Design of Multi-member Districts
- 11/04 Yusuf Hakan Kalayci The Demand Query Model for Bipartite Matching
- 11/11 Neel Patel Delegated Pandora's Box
- 11/18 Bhavya Vasudeva An Introduction to Causal Inference
- 11/25 Thanksgiving
- 12/02 Vaggos Chatziafratis (Northwestern) Hierarchical Clustering: Recent Progress and Open Questions
Spring 2021 (Every Friday 11:45am on Zoom)
- 02/05 Calvin Leng Counting Small Permutation Patterns
- 02/12 Joe Bebel Zero-knowledge proof systems: a new era of cryptography
- 02/19 Haifeng Xu Optimal Pricing of Information
- 02/26 Liyu Chen Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
- 03/05 Sahil Singla Algorithms and Uncertainty
- 03/12 USC Wellness Day
- 03/19 Shaddin Dughmi Matroid Secretary is Equivalent to Contention Resolution
- 03/26 Yu Cheng High-Dimensional Robust Statistics: Faster Algorithms and Optimization Landscape
- 04/02 Mengxiao Zhang Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
- 04/09 Rachel Cummings Attribute Privacy: Framework and Mechanisms
- 04/16 Henry Yuen A tale of Turing Machines, Quantum Entangled Particles and Operator Algebras
- 04/23 Tyler LaBonte The Distance Oracle for Convex Optimization
- 04/30 USC Wellness Day
Fall 2020 (Every Friday 12:00pm on Zoom)
- 09/11 Chen-Yu Wei Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
- 09/18 Yusuf Hakan Kalayci An optimal free-order online contention resolution scheme for bipartite matchings and possible applications
- 09/25 Chung-Wei Lee Linear Last-iterate Convergence for Matrix Games
- 10/02 Jiapeng Zhang DNFs and Related Questions
- 10/09 David Kempe Distortion-based Analysis of Voting: Limited Communication, and an Analysis Framework based on LP Duality
- 10/16 Haoming Li Classification with Strategically Withheld Data
- 10/23 Neel Patel The Price is (Probably) Right: Learning Market Equilibria from Samples
- 10/30 Curtis Bechtel Delegated Stochastic Probing
- 11/06 Cancelled
- 11/13 Matthew Ferland Quantum Combinatorial Games: Structures and Computational Complexity
Spring 2020 (Every Thursday 12:00pm at SAL 213)
- 01/26 Marek
- 01/23 Marek
- 01/30 Matt Ferland MIP*=RE
- 02/06 Kobbi Nissim Legal Theorem's of Privacy
- 02/13 Salil Vadhan Derandomization Beyond Connectivity: High-Precision Estimation of Random Walks and Laplacian Solvers in Small Space
- 02/20 Alana Shine Expander Graphs -- Both Local and Global
- 02/27 Basi Fairness and Utilization in Allocating Resources with Uncertain Demand
- 04/02 Prithvi Techniques Used in Quantum State Tomography
- 04/09 Hikaru PAC-Bayes and Flat Solution
- 04/16 Calvin
- 04/23 Yusuf
- 04/30 Marc
Fall 2019 (Every Thursday 12:00pm at SAL 213)
Fall 2018
- Every Tuesdays 11:50am at RTH cafe
Spring 2018
- 01/19 Ehsan Emamjomeh-Zadeh Cost Functions for Hierarchical Clustering
- 01/26 Alana Shine Robust Probabilistic Inference
- 02/02 Ruixin Qiang Approaching 3/2 for the s-t-path TSP
- 02/09 Haifeng Xu Information as A Double-Edged Sword in Strategic Interactions
- 02/16 No Meeting
- 02/23 Ehsan Emamjomeh-Zadeh A General Framework for Robust Interactive Learning
- 03/02 No Meeting
- 03/09 Joe Bebel On the Sensitivity Conjecture
- 03/16 Spring Break
- 03/23 Alana Shine On the ability of neural nets to express distributions
- 03/30 Ruixin Qiang Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
- 04/06 Anastasia Voloshinov Equality of Opportunity in Supervised Learning
- 04/13 Joseph Bebel
- 04/20 Shaddin Dughmi Bernoulli Factories and Black-Box Reductions in Mechanism Design
Fall 2017
- 09/01 Ilias Diakonikolas High-dimensional robust estimation @SSL150
- 09/08 Joe Bebel Cryptocurrency from a Theoretical Perspective
- 09/15 Alana Shine Equilibria in the Generative Adversarial Network Framework
- 09/22 Haifeng Xu Informational Substitutes
- 09/29 Jason Lee Matrix Completion, Saddle points, and Gradient Descent @SSL150
- 10/06 Ruixin Qiang Combinatorial Cost Sharing
- 10/13 Mahdi Soltanolkotabi Nonconvex Optimization for High-dimensional Learning: From ReLUs to Submodular Maximization @SSL150
- 10/20 Ehsan Emamjomeh-Zadeh Twenty (simple) questions
- 10/27 Meisam Razaviyayn Deep optimization: Learning Deep Models and Tuning Hyper-Parameters @SSL150
- 11/03 Li Han Train faster, generalize better: Stability of stochastic gradient descent
- 11/10 Haipeng Luo Towards Practical Contextual Bandits
- 11/17 Elizabeth Crosson Quantum annealing versus classical optimization
- 12/01 Yingying Fan RANK: Large-Scale Inference with Graphical Nonlinear Knockoffs
Spring 2017
- 01/20 Let's meet!
- 01/27 David Kempe Quasi-regular sequences and optimal schedules for security games 12:30@SSL150
- 02/03 Yu Cheng Settling the complexity of computing approximate two-player Nash equilibria
- 02/10 Ruixin Qiang The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
- 02/17 Shai Vardi On the probe complexity of Local Computation Algorithms
- 02/24 Li Han The Computational Power of Optimization in Online Learning
- 03/03 Haifeng Xu A Randomized Algorithm for Linear Equations over Prime Fields
- 03/24 Magnús M. Halldórsson Wireless network algorithms with performance guarantees
- 03/31 Joe Bebel Lovasz Local Lemma
- 04/07 Alana Shine Instance Optimal Learning
- 04/14 Yu Cheng Recursive Teaching Dimension of Finite VC Classes @SSL150
- 04/21 Ho Yee Cheung The 4/3 Additive Spanner Exponent is Tight
- 04/28 Jiapeng Zhang The Robust Sensitivity of Boolean Functions
- 05/05 Ehsan Emamjomeh-Zadeh Complexity Theoretic Limitations on Learning Halfspaces
Fall 2016
- 09/02 Let's meet!
- 09/09 Ehsan Emamjomeh-Zadeh A cost function for similarity-based hierarchical clustering
- 09/16 Puzzles
- 09/23 Yu Cheng Playing Anonymous Games using Simple Strategies
- 09/30 USC Machine Learning Retreat
- 10/07 Haifeng Xu Re-targeting in Ad Auctions
- 10/14 Xinran He Learning Influence Functions from Incomplete Observations
- 10/21 Ilias Diakonikolas Computational Efficiency and Robust Statistics
- 10/28 Alana Shine Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing
- 11/04 Southern California Symposium on Network Economics and Game Theory
- 11/11 Southern California Theory Day
- 11/18 Nicole Immorlica Maximizing the Social Good: Markets without Money @SGM123
- 11/25 Thanksgiving
- 12/02 Rui Chao A three-player game to test quantum theory
Spring 2016
- 01/22 Ho Yee Cheung Low Rank Approximation and Regression in Input Sparsity Time
- 01/29 Jelani Nelson Optimal space heavy hitters with fast query and update times @SSL150
- 02/05 Li Han The Matching Polytope has Exponential Extension Complexity
- 02/12 Ruixin Qiang Polynomiality for Bin Packing with a Constant Number of Item Types
- 02/19 Xinran He 2-Server PIR with Sub-Polynomial Communication
- 02/26 Haifeng Xu Approximating ATSP by Relaxing Connectivity @SSL150
- 03/04 No meeting
- 03/11 Puzzles and Open Problems
- 03/18 Spring Break
- 03/25 Omer Tamuz Convergence of majority dynamics @SSL150
- 04/01 Alex Eager Auctions, Public Projects, and extending Border’s Theorem
- 04/08 Joe Bebel Sum-of-squares Method
- 04/15 Raghu Meka Sum-of-Squares lower bounds for planted clique @SSL150
- 04/22 Yu Cheng Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games
- 04/29 Ehsan Emamjomeh-Zadeh Deterministic and Probabilistic Binary Search in Graphs
Fall 2015
- 08/28 Let's meet!
- 09/04 Mahdi Soltanolkotabi Solving Quadratic Equations via Non-convex Optimization: Theory and Algorithms
- 09/11 Open problems and puzzles
- 09/18 Stanislav Minsker Applications of the Geometric Median to Robust and Scalable Statistical Inference
- 09/25 Yu Cheng Nearly Maximum Flows in Nearly Linear Time
- 10/02 Eddie Nikolova The Burden of Risk Aversion in Selfish Routing
- 10/09 Yu Cheng Mixture Selection, Mechanism Design, and Signaling
- 10/16 No meeting
- 10/23 Lian Liu Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
- 10/30 SoCal NEGT
- 11/06 Bailan Li Dynamic Graph Connectivity in Polylogarithmic Worst Case Time
- 11/13 Elliot Anshelevich Approximating Optimal Social Choice under Metric Preferences @SSL 150
- 11/20 Ehsan Emamjomeh-Zadeh Bounds for Clique vs. Independent Set
- 11/27 Thanksgiving
- 12/03 Lirong Xia @SSL 150
Spring 2015
- 01/16 Lian Liu Spectral Graph Theory and Computational Group Theory
- 01/23 Lian Liu Spectral Graph Theory and Computational Group Theory (Part 2)
- 01/30 Rachel Cummings Privacy and Truthful Equilibrium Selection for Aggregative Games
- 02/06 Mahyar Salek Stock photography market through AGT lens
- 02/13 Li Han Incentivizing Exploration with Heterogeneous Value of Money
- 02/20 Joe Bebel Fun Puzzles
- 02/27 Georgios Piliouras Natural Selection, Game Theory and Genetic Diversity
- 03/06 PhD Visit Days
- 03/13 Yundi Qian Robust Strategy against Unknown Risk-averse Attackers in Security Games
- 03/20 Spring break
- 03/27 No meeting
- 04/03 Hamid Nazerzadeh Deals or no Deals: Contract Design for Selling Online Advertising
- 04/10 Xinran He Model-driven Optimization with Probes
- 04/17 Fei Fang Towards Addressing Spatio-Temporal Aspects in Security Games
- 04/24 Thanh Nguyen Confronting Uncertainties in Security Games: Advances and Algorithms
- 05/01 Nicole Immorlica Tilting at Windmills: The Economic Efficiency of Large Games
Fall 2014
- 09/05 Yu Cheng Signaling in Quasipolynomial Time
- 09/12 Justin Solomon Relating Discrete and Continuous Optimal Transportation
- 09/26 Yu Cheng, Ehsan Emamjomeh-Zadeh, Haifeng Xu Report from STOC and EC
- 10/03 Haifeng Xu Two-Stage Security Game -- Exploring Information Asymmetry
- 10/10 Li Han Re-incentivizing Discovery: Mechanisms for Partial-Progress Sharing in Research
- 10/17 SoCal Theory Day
- 10/24 Ehsan Emamjomeh-Zadeh, Li Han On revenue maximization
- 10/31 Yanting Pricing strategy for femtocell network access points
- 11/07 Siddharth Barman Approximate Version of Caratheodory’s Theorem and Its Algorithmic Applications
- 11/14 CS PhD Lunch
- 11/21 SoCal NEGT
- 12/05 Li Han Sampling and Representation Complexity of Revenue Maximization
Spring 2014
- 01/24 Keyvan Rezaei-Moghadam Controlling Data Dissemination in Mobile Vehicular Networks
- 01/31 Anand Kumar Narayanan Recent Advance in Discrete Logarithms
- 02/07 Haifeng Xu Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains
- 02/21 Ehsan Emamjomeh-Zadeh Identifying a Target Vertex in a Graph Using Vertex Queries
- 02/28 Ruixin Qiang Information Revelation
- 03/07 Ho Yee Cheung A new method to solve linear systems
- 03/14 Shaddin Dughmi On the hardness of signaling
- 03/28 Lian Liu A subexponential parameterized algorithm for Subset TSP on planar graphs
- 04/04 Shanghua Teng An Axiomatic Approach to Network Communities
- 04/11 Daniel Nagaj An Introduction to Quantum (Hamiltonian) Complexity
- 04/18 Nima Haghpanah Reverese Mechanism Design
- 04/25 GTHB Annual Symposium
- 05/02 David Kempe Incentivizing Exploration
- 05/09 Anand Kumar Narayanan The role of randomness in root finding modulo a prime
Fall 2013
- 08/29, Henry Yuen Randomness Testing
- 09/06, Mahyar Salek
- 09/13, Shang-Hua Teng Open problems in Smoothed analysis
- 09/20, Haifeng Xu Crowding sourcing contest
- 09/27, Ruixin Qiang Budget-feasible mechanism design with feasibility constraints
- 10/04, Mohammad and Huy
- 10/11, Moshe Babaioff Bertrand Networks
- 10/17, Brendan Lucier Pricing for Efficiency, With and Without Bundles
- 10/25, Ehsan Emamjomeh-Zadeh The Minimum Shared Edges Problem
- 11/01, Xinran He and Yu Cheng Price of Anarchy for the N-player Competitive Cascade Game with Submodular Activation Functions and Brief summary of interesting topics at FOCS'13
- 11/07 SoCal NEGT
- 11/21 Li Han single-buyer unit-demand mechanism design
- 12/06 Nicole Immorlica Simple Prices for Complex Markets