Theory Lunch

Every Friday 12pm at SAL 213 (lunch provided).

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