CSE
CSE
CSE CSE

All Theory Seminars

Friday, Dec 8, 2017
Secure delegation of quantum computation
Speaker: Michael Newman
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 17, 2017
Efficient Massively Parallel Methods for Dynamic Programming
Speaker: Timothy Lewis
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Nov 10, 2017
Consistency Thresholds for the Planted Bisection Model
Speaker: Biaoshuai Tao
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Oct 27, 2017
A new result on exponential quantum speed-ups for SDP
Speaker: Cupjin Huang
Event Type: Theory Seminar
10:30am - 11:30am in EECS 3316

Friday, Oct 20, 2017
Bayesian estimation from few samples: community detection and related problems
Speaker: Fang-Yi Yu
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3901

Friday, Oct 13, 2017
Planar Graph Perfect Matching is in NC
Speaker: Dawei Huang
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in EECS 3725

Friday, Oct 6, 2017
An optimal no-go theorem on hidden variable theories
Speaker: Yuri Gurevich
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Sep 29, 2017
Distributed Exact Weighted All-Pairs Shortest Paths
Speaker: Yi-Jun Chang
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Sep 15, 2017
Instance Optimal Learning
Speaker: Yuqing Kong
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3901

Friday, Sep 8, 2017
Approximation algorithms for inventory problems with submodular or routing costs
Speaker: Viswanath Nagarajan
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Apr 7, 2017
Generalization and Equilibrium in Generative Adversarial Nets (GANs)
Speaker: Bo Li
Speaker Title: Post Doc
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Mar 24, 2017
An Information Theoretical View of Information Elicitation Mechanisms
Speaker: Yuqing Kong
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Mar 17, 2017
Core sets and streaming algorithms for MAX CUT
Speaker: Suresh Venkatasubramanian
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Mar 10, 2017
Pseudorandomness of Ring-LWE for Any Ring and Modulus
Speaker: Chris Peikert
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Tuesday, Feb 7, 2017
Lower bounds for estimating matching size in streaming models
Speaker: Dawei Huang
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Feb 3, 2017
: A (2+eps )-Approximation for Maximum Weight Matching in the Semi-Streaming Model
Speaker: Seth Pettie
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Jan 20, 2017
Cake Cutting: Fairness and Efficiency
Speaker: Biaoshuai Tao
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Jan 13, 2017
Quantum hashing is maximally secure against classical leakage
Speaker: Cupjin Huang
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Jan 6, 2017
Fully Dynamic Connectivity in O(log n(log log n)^2) Amortized Expected Time
Speaker: Shang-En Huang
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Dec 9, 2016
Strategies for Extensive Form Games
Speaker: Richard Stearns
Event Type: Theory Seminar
10:30am - 11:30am in BBB 4901

Friday, Dec 2, 2016
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
Speaker: Fang-Yi Yu
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Nov 4, 2016
Spookily Homomorphic Encryption
Speaker: Daniel Wichs
Speaker Title: Assistant Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Oct 28, 2016
Population Recovery in polynomial time
Speaker: Mike Saks
Speaker Title: Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Oct 21, 2016
Do Prices Coordinate Markets?
Speaker: Jamie Morgenstern
Speaker Title: Postdoc
Event Type: Theory Seminar
10:30am - 11:30am in 4901

Friday, Oct 7, 2016
Polynomial Identity Testing for Read Once Polynomials
Speaker: Daniel Minahan
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Sep 30, 2016
Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization
Speaker: Biaoshuai Tao
Speaker Title: Graduate Student
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Sep 23, 2016
Differentially private analysis of graphs
Speaker: Sofya Raskhodnikova
Speaker Title: Associate Professor
Event Type: Theory Seminar
Faculty Sponsor: Anna Gilbert
10:30am - 11:30am in BBB 4901

Friday, Sep 9, 2016
Optimal Compression of Graph Metrics
Speaker: Seth Pettie
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Apr 15, 2016
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Speaker: Yi-Jun Chang
Event Type: Theory Seminar
10:30am - 11:30am in 3725 BBB

Friday, Apr 8, 2016
Noise stability of functions with low influences: invariance and optimality
Speaker: Fang-Yi Yu
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Apr 1, 2016
Better Outcomes from More Rationality
Speaker: Yuqing Kong
Event Type: Theory Seminar
10:30am - 11:30am in 3725 BBB

Friday, Mar 25, 2016
Recent progress on two-source randomness extractors
Speaker: Yaoyun Shi
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in 3725 BBB

Friday, Mar 18, 2016
Multi-Key FHE from LWE, Revisited
Speaker: Sina Shiehian
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Mar 11, 2016
Complex Contagions on Social Networks
Speaker: Grant Schoenebeck
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3725

Friday, Feb 19, 2016
Random number generation with untrusted quantum devices
Speaker: Carl Miller
Speaker Title: Research Scientist
Event Type: Theory Seminar
10:30am - 11:30am in 3725 BBB

Friday, Feb 12, 2016
A cubic algorithm for computing the volume of a convex body
Speaker: Kevin Sung
Event Type: Theory Seminar
10:30am - 11:30am in 3725 BBB

Friday, Feb 5, 2016
Quantum Conditional Mutual Information and Ability to Recover
Speaker: Cupjin Huang
Event Type: Theory Seminar
10:30am - 11:30am in 3725 BBB

Friday, Jan 29, 2016
Using Expander Graphs to Find Vertex Connectivity
Speaker: Shang-En Huang
Event Type: Theory Seminar
10:00am - 11:00am in BBB 4941

Friday, Jan 22, 2016
The 4/3 Additive Spanner Exponent is Tight
Speaker: Seth Pettie
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:00am - 11:00am in BBB 3725

Friday, Jan 15, 2016
Counting perfect matchings via random matrices
Speaker: Mark Rudelson
Speaker Title: Professor
Event Type: Theory Seminar
10:00am - 11:00am in BBB 4941

Friday, Dec 11, 2015
Approximately envy-free mechanism for resource allocation problems with complementarities
Speaker: Vijay Subramanian
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:00am - 11:00am in BBB 3725

Friday, Dec 4, 2015
Approximation-Friendly Discrepancy Rounding
Speaker: Viswanath Nagarajan
Speaker Title: Assistant Professor
Event Type: Theory Seminar
10:00am - 11:00am in 3725 BBB

Friday, Nov 20, 2015
Popularity Signals in Optimizing Trial-Offer Markets
Speaker: Pascal Van Hentenryck
Speaker Title: Professor
Event Type: Theory Seminar
10:00am - 11:00am in 3725 BBB

Friday, Nov 13, 2015
Impact of community structure on cascades
Speaker: Mehrdad Moharrami
Speaker Title: PhD Student
Event Type: Theory Seminar
10:00am - 11:00am in 3725 BBB

Friday, Oct 30, 2015
Exploration of Bell test experiments for building an untrusted-device quantum number generator
Speaker: Wei-Zung Chang
Speaker Title: Postdoc
Event Type: Theory Seminar
10:00am - 11:00am in BBB 3725

Friday, Oct 23, 2015
Peer Prediction and Mechanism Design
Speaker: Yuqing Kong
Speaker Title: PhD Student
Event Type: Theory Seminar
10:00am - 11:00am in 3725 BBB

Friday, Oct 16, 2015
Representation power of neural networks
Speaker: Matus Telgarsky
Speaker Title: Postdoc
Event Type: Theory Seminar
10:00am - 11:00am in BBB 3725

Friday, Oct 2, 2015
Weighted Matching on General Graphs: Faster and Simpler
Speaker: Seth Pettie
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:00am - 11:00am in 3725 BBB

Friday, Sep 25, 2015
Streaming Interactive Protocols for Graphs
Speaker: Amir Abdullah
Event Type: Theory Seminar
10:00am - 11:15am in 3725 BBB

Friday, Sep 18, 2015
Theory Seminar Fall Kick-off
Speaker: Theory Group and Friends
Event Type: Theory Seminar
10:00am - 11:15am in 3725 BBB

Friday, Sep 11, 2015
An Overview of Lattice Cryptography
Speaker: Chris Peikert
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:00am - 11:15am in 3725 BBB

Friday, Apr 24, 2015
Quantile Search for Minimum-Time Sampling
Speaker: Laura Balzano
Speaker Title: Assistant Professor of Electrical Engineering and Computer Science
Event Type: Theory Seminar
10:30am - 11:30am in EECS 4122

Wednesday, Apr 15, 2015
Negative Probabilities
Speaker: Yuri Gurevich
Speaker Title: Principal Researcher
Event Type: Theory Seminar, Quantum Info Processing Seminar
3:00pm - 4:30pm in 2901 Beyster Bldg.

Friday, Apr 3, 2015
On the equivalence between simulated annealing and Interior Point Methods
Speaker: Jacob Abernethy
Event Type: Theory Seminar
10:30am - 11:30am in 4901 BBB

Friday, Mar 27, 2015
Approximation Algorithms for Stochastic Orienteering
Speaker: Viswanath Nagarajan
Event Type: Theory Seminar
10:30am - 11:30am in BBB 4901

Wednesday, Mar 18, 2015
Higher lower bounds from the 3SUM conjecture
Speaker: Tsvi Kopelowitz
Speaker Title: Postdoctoral Researcher
Event Type: Theory Seminar
Faculty Sponsor: Seth Pettie
10:00am - 11:00am in BBB 3941

Friday, Mar 13, 2015
How to Prove Lower Bounds from the Strong Exponential Time Hypothesis
Speaker: Seth Pettie
Event Type: Theory Seminar
2:30pm - 3:30pm in 3941

Friday, Feb 27, 2015
The optimal absolute ratio for online bin packing
Speaker: Sina Shiayan
Event Type: Theory Seminar
10:30am - 11:30am in 4901 BBB

Friday, Feb 20, 2015
Recent Progress on the Sparse Polynomial Factorization Problem
Speaker: Ilya Volkovich
Event Type: Theory Seminar
10:30am - 11:30am in 4901 BBB

Friday, Feb 13, 2015
Randomized Primal-Dual analysis of Ranking for Online Bipartite Matching
Speaker: Dawei Huang
Event Type: Theory Seminar
10:30am - 11:30am in BBB 4901

Friday, Jan 23, 2015
A 2/3-approximation algorithm for vertex-weighted matching in bipartite graphs
Speaker: Alex Pothen
Event Type: Theory Seminar
Faculty Sponsor: Seth Pettie
10:30am - 11:30am in BBB 4901 (NOTE NEW ROOM)

Friday, Jan 16, 2015
(2 Delta-1)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
Speaker: Hsin-Hao Su
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Saturday, Dec 6, 2014
Midwest Theory Day
Event Type: Theory Seminar
10:30am - 5:30pm in 1670 & 3725 BBB

Friday, Dec 5, 2014
Title: Approximate Version of Caratheodory’s Theorem and Its Algorithmic Applications
Speaker: Sid Barman
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 21, 2014
Fast matrix completion without the condition number
Speaker: Mary Wootters
Event Type: Women in Computing, Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 14, 2014
Characterizing Arithmetic Read-Once Formulae
Speaker: Ilya Volkovich
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Nov 7, 2014
Price of Anarchy for Auction Revenue
Speaker: Jason Hartline
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Oct 31, 2014
Isotonic Regression As a Function of Comments
Speaker: Quentin Stout
Speaker Title: Professor
Event Type: Theory Seminar
10:30am - 11:30am in 2733 BBB

Friday, Oct 24, 2014
FOCS Round Up!
Speaker: Theory Group and Friends
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Oct 17, 2014
Distributed Algorithms for the Lovász Local Lemma and Graph Coloring
Speaker: Hsin-Hao Su
Event Type: Theory Seminar
10:30am - 11:40am in BBB 3941

Friday, Oct 10, 2014
Information (or inferential) limits and computational limits
Speaker: Raj Rao
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Oct 3, 2014
Tensor rank and stability in representation theory
Speaker: Daniel Barter
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Sep 26, 2014
Robust Quantum Random Number Generation
Speaker: Carl Miller
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Sep 19, 2014
3SUM is Subquadratic
Speaker: Seth Pettie
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Sep 12, 2014
Energy Efficient Multicommodity Routing
Speaker: Viswanath Nagarajan
Speaker Title: Assistant Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Sep 5, 2014
Theory Seminar Kick Off
Speaker: Theory Faculty
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, May 23, 2014
Impossibility Theorems and the Universal Algebraic Toolkit
Speaker: Yixin Xu
Speaker Title: PhD student
Event Type: Theory Seminar
10:30am - 12:00pm in 3941 BBB

Friday, May 23, 2014
On Learning, Lower Bounds and (un)Keeping Promises
Speaker: Ilya Volkovich
Event Type: Theory Seminar
2:00pm - 3:00pm in 3941 BBB

Friday, Apr 25, 2014
Exponential Lower Bounds for Polytopes in Combinatorial Optimization
Speaker: Aaron Snook
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Apr 18, 2014
Primal dual gives optimal energy efficient online algorithms
Speaker: Jake Abernethy
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Apr 4, 2014
Electricity Pooling Markets with Strategic Producers Possessing Asymmetric Information
Speaker: Demosthenis Teneketzis
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Mar 21, 2014
Interlacing Families and Kadison--Singer
Speaker: Adam W. Marcus
Event Type: Theory Seminar
10:30am - 11:30am in 1360 East Hall

Friday, Mar 14, 2014
Physical Randomness Extractors
Speaker: Xiaodi Wu
Speaker Title: Post-doc & Simons Research Fellow
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Jan 31, 2014
Diffuse Scattering on Graphs and Combinatorial Inverse Problems
Speaker: Anna Gilbert
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Jan 24, 2014
Graph Isomorphism and the Lasserre Hierarchy
Speaker: Aaron Snook
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Jan 24, 2014
Diffuse Scattering on Graphs and Combinatorial Inverse Problems
Speaker: Anna Gilbert
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Jan 24, 2014
Diffuse Scattering on Graphs and Combinatorial Inverse Problems
Speaker: Anna Gilbert
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Jan 17, 2014
List decodability of randomly punctured codes
Speaker: Mary Wootters
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Dec 6, 2013
Scalable Sparse Approximation of a Sample Mean
Speaker: Clayton Scott
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Nov 22, 2013
For-all Sparse Recovery in Near-Optimal Time
Speaker: Martin Strauss
Speaker Title: Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Nov 8, 2013
Learning with Noisy Labels
Speaker: Ambuj Tewari
Speaker Title: Assistant Professor
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 1, 2013
A parallel repetition theorem for quantum games
Speaker: Yaoyun Shi
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Oct 25, 2013
General truthfulness characterizations via convex analysis
Speaker: Rafael Frongillo
Speaker Title: Postdoc
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Oct 18, 2013
Modal Analysis with Compressive Measurements
Speaker: Anna Gilbert
Speaker Title: Professor
Event Type: Theory Seminar
10:30am - 11:30am in BBB 3941

Friday, Oct 11, 2013
Better Approximation Algorithms for Graph Diameter
Speaker: Grant Schoenebeck
Speaker Title: Assistant Professor
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Sep 27, 2013
Pricing, Market Making, Scoring Rules, and Exponential Families
Speaker: Jacob Abernethy
Speaker Title: Assistant Professor
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Sep 20, 2013
What can a bit tell us? Forays into information scalability.
Speaker: Petros T. Boufounos
Speaker Title: Principal Member of Research Staff
Event Type: Theory Seminar
10:30am - 11:30am in 3316 EECS

Friday, Sep 13, 2013
Theory Seminar Introduction
Speaker: Theory faculty
Event Type: Theory Seminar
10:30am - 11:30am in 3741 BBB

Wednesday, Aug 7, 2013
Coding, Complexity, and Sparsity Workshop
Speaker: Various
Speaker Title: Various
Event Type: Theory Seminar
9:00am - 5:00pm in 1400 Chemistry

Tuesday, Aug 6, 2013
Coding, Complexity, and Sparsity Workshop
Speaker: Various
Speaker Title: Various
Event Type: Theory Seminar
9:00am - 5:00pm in 1400 Chemistry

Monday, Aug 5, 2013
Coding, Complexity, and Sparsity Workshop
Speaker: Various
Speaker Title: Various
Event Type: Theory Seminar
9:00am - 5:00pm in 1400 Chemistry

Friday, May 3, 2013
Byzantine Agreement in Polynomial Expected Time
Speaker: Jared Saia
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Wednesday, May 1, 2013
Dynamic Graph Connectivity in Polylogarithmic Worst Case Time
Speaker: Valerie King
Event Type: Theory Seminar
12:00pm - 1:00pm in 4941 BBB

Friday, Apr 19, 2013
What gaussian processes can do for you: applications of probability and geometry in theoretical computer science
Speaker: Mary Wootters
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Friday, Apr 12, 2013
High-degree graphs cannot be used for a quantum PCP
Speaker: Aram Harrow
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Friday, Apr 5, 2013
An Optimal Lower Bound on the Number of Variables for Graph Identification
Speaker: Aaron Snook
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Mar 22, 2013
Every locally characterized affine-invariant property is testable
Speaker: Arnab Bhattacharyya
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Monday, Mar 11, 2013
Recent Progress on Parallel Repetition
Speaker: Kai-Min Chung
Event Type: Theory Seminar
12:00pm - 1:30pm in BBB 3941

Friday, Mar 1, 2013
Sketching For Big Data Recommender Systems Using Fast Pseudo-Random Fingerprints
Speaker: Ely Porat
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Friday, Feb 15, 2013
Distributed Oblivious RAM for Secure Two-Party Computation
Speaker: Steve Lu
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Feb 8, 2013
On the Decodability of Primitive Reed-Solomon Codes
Speaker: Qi Cheng
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Friday, Feb 1, 2013
One algorithm to rule them all: One join query at a time
Speaker: Atri Rudra
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Friday, Jan 25, 2013
Characterizing Strategic Cascades on Networks
Speaker: Travis Martin
Event Type: Theory Seminar
10:00am - 11:00am in 411 West Hall

Friday, Jan 18, 2013
The Locality of Distributed Symmetry Breaking
Speaker: Seth Pettie
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Monday, Dec 3, 2012
Locally-Decodable Codes
Speaker: Brett Hemenway
Event Type: Theory Seminar
4:00pm - 5:00pm in 1360 East Hall

Friday, Nov 16, 2012
A multi-prover interactive proof for NEXP sound against entangled provers
Speaker: Xiaodi Wu
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 9, 2012
Constructive Discrepancy Minimization by Walking on the Edges
Speaker: Hsin-Hao Su
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 2, 2012
A recent result in algorithmic mechanism design: The exponential mechanism and privacy
Speaker: Travis Martin
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Oct 26, 2012
New Approaches to Constructing Locally Decodable Codes
Speaker: Brett Hemenway
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Oct 19, 2012
Bankruptcy in Byzantium
Speaker: Maxwell Young
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Oct 5, 2012
Symmetry and Satisfiability: An Update
Speaker: Karem A. Sakallah
Speaker Title: Prof.
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Sep 28, 2012
TBD--possibly cancelled
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Sep 21, 2012
Unconditional hardness results for semi-definite programs: integrality gaps for the Lasserre hierarchy
Speaker: Grant Schoenebeck
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Sep 14, 2012
Introductions, continued
Speaker: Theory faculty
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Sep 7, 2012
Introductions and organizational meeting
Speaker: Theory faculty
Event Type: Theory Seminar
10:30am - 11:30am in 3941 BBB

Friday, Nov 18, 2011
High-dimensional covariance estimation based on Gaussian graphical models
Speaker: Shuheng Zhou
Event Type: Theory Seminar
10:00am - 11:00am in East Hall B844

Friday, Nov 11, 2011
Debmalya Panigrahi: Survivable Network Design with Node and Edge Costs
Speaker: Debmalya Panigrahi
Speaker Title: Survivable Network Design with Node and Edge Costs
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Nov 4, 2011
Theory Seminar
Event Type: Theory Seminar
10:30am - 11:00am in 3941 Beyster Bldg.

Friday, Oct 21, 2011
Theory Seminar
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Oct 14, 2011
Theory Seminar
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Sep 23, 2011
Overview of Theory Research
Speaker: Theory Faculty
Event Type: Theory Seminar
10:30am - 12:00pm in 3941 Beyster Bldg.

Friday, Sep 16, 2011
Distributed Deterministic Graph Coloring
Speaker: Michael Elkin
Speaker Title: Prof
Event Type: Theory Seminar
10:30am - 11:30am in Beyster Bldg. 3941

Thursday, Aug 18, 2011
Bisimulation for quantum processes
Speaker: Yuan Feng
Speaker Title: Associate Professor
Event Type: Theory Seminar
10:30am - 12:00pm in Beyster Bldg. 3941

Friday, Oct 1, 2010
The Complexity of Monotone Graph Properties
Speaker: Carl Miller
Event Type: Theory Seminar
10:30am - 11:30am in Beyster Bldg. 3941

Friday, Jun 4, 2010
Holographic algorithms without matchgates
Speaker: Jason Morton
Speaker Title: Assistant Professor of Mathematics and Statistics
Event Type: Theory Seminar
10:30am - 11:30am in Beyster Bldg. 3941

Friday, Apr 16, 2010
Denny VandenBerg--Theoretical Computer Science Seminar
Speaker: Denny VandenBerg
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Apr 9, 2010
Patrick Poon--Theoretical Computer Science Seminar
Speaker: Patrick Poon
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Apr 2, 2010
Carl Miller--The Longest Common Subsequence Problem
Speaker: Carl Miller
Speaker Title: Prof.
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Mar 26, 2010
Ran Duan--Theoretical Computer Science Seminar
Speaker: Ran Duan
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Mar 12, 2010
Quentin Stout-- Going Up: Isotonic Regression Algorithms
Speaker: Quentin Stout
Speaker Title: Prof.
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Nov 6, 2009
Approximating covariance matrices
Speaker: Roman Vershynin
Speaker Title: Approximating covariance matrices
Event Type: Theory Seminar
10:30am - 11:30am in 3941 Beyster Bldg.

Friday, Oct 16, 2009
Compressed Sensing Meets Information Theory
Speaker: Dror Baron
Event Type: Theory Seminar
10:30am - 11:30am in Beyster Bldg. 3941

Friday, Oct 10, 2008
On the Computation and Approximation of Two-Player Nash Equilibria
Speaker: Xi Chen
Event Type: Theory Seminar
11:00am - 12:00pm in DOW 1018

Friday, Oct 3, 2008
Exchange Market Equilibria with Leontief ’s Utility: Freedom of Pricing Leads to Rationality
Speaker: Ye Du
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Sep 12, 2008
Theory Seminar Introductory Talks - R. Sami & S. Pettie
Speaker: Seth Pettie & Rahul Sami
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Sep 5, 2008
Theory Seminar: Organizational meeting & introductions
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Apr 4, 2008
The Unbounded-Error Communication Complexity of Symmetric Functions
Speaker: Alexander Sherstov
Event Type: Theory Seminar
11:00am - 12:00pm in DOW 1017

Friday, Mar 21, 2008
CSPL/Theory Seminar: Zero-error classical capacity of noisy quantum channels
Speaker: Runyao Duan
Event Type: Theory Seminar
11:00am - 12:00pm in DOW 1017

Friday, Mar 14, 2008
Leontief Economies Encode Nonzero Sum Two-Player Games
Speaker: Ye Du
Event Type: Theory Seminar
11:00am - 12:00pm in DOW 1017

Friday, Feb 8, 2008
Power, Time, and Location: Parallel algorithms addressing them all
Speaker: Quentin Stout
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Feb 1, 2008
Codeword Stabilized Quantum Codes
Speaker: Bei Zeng
Event Type: Theory Seminar
11:00am - 12:00pm in DOW 1018

Friday, Jan 11, 2008
Codeword Stabilized Quantum Codes
Speaker: Bei Zeng
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Nov 30, 2007
On the Perfect Distinguishability of Unitary Operations
Speaker: Runyao Duan
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Nov 9, 2007
tba
Speaker: Brian Wyman
Event Type: Theory Seminar
11:00am - 12:00pm in Beyster Bldg. 3941

Friday, Oct 27, 2006
Recent results in the search for new quantum algorithms
Speaker: Wim van Dam
Event Type: Theory Seminar
2:00pm - 3:00pm in 2311 EECS

Thursday, Oct 12, 2006
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Speaker: Ye Du, Graduate Student
Event Type: Theory Seminar
4:30pm - 5:30pm in 3941 Beyster Bldg. Building

Thursday, Oct 5, 2006
Publish and Perish
Speaker: Julia Lipman, Graduate Student
Event Type: Theory Seminar
4:30pm - 5:30pm in 3941 Beyster Bldg. Building

Thursday, Sep 28, 2006
An Optimal Binary Search Tree?
Speaker: Seth Pettie, PhD., Assistant Professor, EECS
Event Type: Theory Seminar
4:30pm - 5:30pm in 3941 Beyster Bldg. Building

Wednesday, Dec 7, 2005
Max-stable Random Sketches: Estimation of Distances, Norms and Dominance Norms
Speaker: Stillian Stoev
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Nov 30, 2005
Sublinear Algorithms for Compressed Sensing
Speaker: Joel A. Tropp
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Nov 2, 2005
Large-scale phylogenetic reconstruction and the Tree of Life
Speaker: Bernard Moret
Event Type: Theory Seminar
4:00pm - 5:00pm in Great Lakes South (4th Floor, Palmer Commons Build

Wednesday, Oct 26, 2005
Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance, by Jonathan L. Bredin, Erik D. Demaine, MohammadTaghi Hajiaghayi and Daniela Rus.
Speaker: Xuan Zheng
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Oct 19, 2005
Gowers Uniformity, influence of variables, and PCPs
Speaker: Alex Samorodnitsky
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Monday, Oct 3, 2005
On the Complexity of Numerical Analysis
Speaker: Eric Allender
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Sep 28, 2005
Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance by Jonathan L. Bredin, Erik D. Demaine, MohammadTaghi Hajiaghayi and Daniela Rus
Speaker: Xuan Zheng
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Sep 21, 2005
The search for a quantum algorithm for Graph Isomorphism
Speaker: Cristopher Moore
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Sep 14, 2005
FRAIG: A new datastructure for formal verification and circuit synthesis
Speaker: Igor Markov
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Apr 13, 2005
Quadratic Lower Bounds on Matrix Rigidity
Speaker: Satya Lokam
Event Type: Theory Seminar
4:30pm - 5:30pm in EWRE 153

Thursday, Nov 4, 2004
Opt vs. Load in Dynamic Storage Allocation
Speaker: HowardKarloff
Event Type: Theory Seminar
1:30pm - 2:30pm in 1301 EECS

Wednesday, Oct 13, 2004
A Combinatorial Approach to Designing RNA Secondary Structures and DNA Code Words
Speaker: Christine Heitsch
Event Type: Theory Seminar
4:30pm - 5:30pm in 3866 East Hall

Wednesday, Oct 6, 2004
The Graphics Card As A Stream Computer
Speaker: Suresh Venkatasubramanian
Event Type: Theory Seminar
4:30pm - 5:30pm in 1180 Media Union (Duderstadt ctr.)

Thursday, Sep 30, 2004
A Novel Matrix Decomposition with Applications to Algorithm Design and Massive Data Set Analysis
Speaker: Petros Drineas
Event Type: Theory Seminar
4:30pm - 5:30pm in 2866 East Hall

Wednesday, Sep 29, 2004
Fast Monte Carlo Algorithms for Large Matrices and Massive Data Sets
Speaker: Michael W. Mahoney
Event Type: Theory Seminar
4:30pm - 5:30pm in 3866 East Hall

Wednesday, Sep 22, 2004
Data Stream Algorithms and Applications
Speaker: S. Muthukrishnan
Event Type: Theory Seminar
4:30pm - 5:30pm in 1180 Media Union (Duderstadt ctr.)

Wednesday, Sep 15, 2004
Geometric control in quantum operation generation
Speaker: Jun Zhang
Event Type: Theory Seminar
4:30pm - 5:30pm in 3866 East Hall

Thursday, Apr 15, 2004
From Quantum Cheating to Quantum Security
Speaker: Professor Hoi-Kwong Lo - University of Toronto
Event Type: Theory Seminar
4:30pm - 5:30pm in 3437 EECS

Wednesday, Apr 7, 2004
Neighborhood Structures with Approximation Guarantees
Speaker: Dushyant Sharma
Event Type: Theory Seminar
4:30pm - 5:30pm in 3433 EECS

Wednesday, Jul 2, 2003
Lower Bounds for Local Search by Quantum Arguments
Speaker: Scott Aaronson/UC Berkeley
Event Type: Theory Seminar
4:00pm - 5:00pm in 1005 EECS

Monday, Oct 7, 2002
TBA
Speaker: TBA
Event Type: Theory Seminar
4:00pm - 5:00pm in 1500 EECS

Wednesday, Oct 2, 2002
Polynomial approximations and quantum lower bounds
Speaker: Yaoyun Shi
Event Type: Theory Seminar
4:30pm - 5:30pm in 3433 EECS

Wednesday, Sep 25, 2002
Probabistic Transforms in the Analysis of Algorithms
Speaker: Kevin Compton
Event Type: Theory Seminar
4:30pm - 5:30pm in 1018 Dow