Theory Seminar (archive)

Theory Seminar (Archive)

This is the  theory seminar archive. For the current theory seminar calendar click here.

Fall 2011

Title: Computational Complexity in Differential Privacy
Speaker: Salil Vadhan, Harvard (on sabbatical at Microsoft Research SVC and Stanford)
Date and Place: Tuesday, October 11, 2011, 2:00pm-3:00pm, CSE 1202

Title: Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
Speaker: Petros Mol, UCSD
Date and Place: Monday, October 3, 2011, 2:00pm-3:20pm, CSE 4140

Spring 2011

Title: Pseudorandom generators, the BQP vs. PH problem and beating the hybrid argument
Speaker: Chris Umans, CalTech
Date and Place: Monday, May 23, 2011, 2-3:20 PM, CSE 4140

Title: Higher Order Principal Components: Complexity and Applications
Speaker: Santosh Vempala, Georgia Tech
Date and Place: Monday, May 16, 2011, 2-3:20 PM, CSE 4140

Title: How to Compute on Encrypted Data: New Developments in Fully Homomorphic Encryption
Speaker: Vinod Vaikuntanathan, MSR and U. Toronto
Date and Place: Monday, May 2, 2011, 2-3:20 PM, CSE 4140

Title: Left Over Hash Lemma, Revisited
Speaker: Yevgeniy Dodis, NYU
Date and Place: Monday, April 25, 2011, 2-3:20 PM, CSE 4140

Title: Enumerative algorithms for the Shortest and Closest Lattice Vector Problems in any norm via M-Ellipsoid coverings
Speaker: Daniel Dadush, Georgia Tech
Date and Place: Monday, April 18, 2011, 2-3:20 PM, CSE 4140

Title: The many entropies of one-way functions
Speaker: Omer Reingold, Microsoft Research
Date and Place: Monday, April 11, 2011, 2-3:20 PM, CSE 4140

Title: General questions about extremal graphs
Speaker: Laszlo Lovasz
Date and Place: Thursday, April 7, 2011, 11:00 AM-12:00 PM, NSB (Natural Sciences Building)

Title: Kyoto Prize Lecture
Speaker: Laszlo Lovasz
Date and Place: Tuesday, April 5, 2011, 3:30-5:00 PM, Price Center West Ballroom

Title: TBA
Speaker: William Matthews, UCSD
Date and Place: Monday, April 4, 2011, 2-3:20 PM, CSE 4140

Title: Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
Speaker: Daniel Lokshtanov, UCSD
Date and Place: Monday, March 28, 2011, 2-3:20 PM, CSE 4140

Winter 2011

Title: Non-uniform ACC Circuit LowerBounds
Speaker: Ryan Williams, IBM
Date and Place: Tuesday, March 8, 2011, 3-4 PM, APM (MATH) 6402 (Halkin room)

Title: Matrix Rigidity -- Quadratic Lower Bounds and Open Questions
Speaker: Satya Lokam, Microsoft Research
Date and Place: Monday, March 7, 2011, 2-3:20 PM, CSE 4140

Title: Security proofs for RSA-OAEP in the Standard Model
Speaker: Adam O'Neil, UT Austin
Date and Place: Monday, February 28, 2011, 2-3:20 PM, CSE 4140

Title: Path, matrix and triangle problems -- subcubic algorithms and equivalences
Speaker: Virginia Vassilevska Williams
Date and Place: Wednesday, February 23, 2011, 11am-12pm, CSE 1202

Title: The Sparsification Lemma
Speaker: Mohan Paturi, UCSD
Date and Place: Monday, February 14, 2011, 2-3:20 PM, CSE 4140

Title: Efficient Learning Gaussian Mixtures
Speaker: Gregory Valiant, UC Berkeley
Date and Place: Monday, February 7, 2011, 2-3:20 PM, CSE 4140

Title: How the cryptanalysis of RSA is (not so) secretly coding theory
Speaker: Nadia Heninger, Princeton/MIT
Date and Place: Tuesday, February 1, 2011, 11am-12pm, CSE 4217

Title: Exact Complexity and Satisfiability
Speaker: Mohan Paturi, UCSD
Date and Place: Monday, January 31, 2011, 2-3:20 PM, CSE 4140

Title: The Permanents of Gaussian Matrices
Speaker: Scott Aaronson, MIT
Date and Place: Monday, January 24, 2011, 2-3:20 PM, CSE 4140

Title: The Computational Complexity of Linear Optics
Speaker: Scott Aaronson, MIT
Date and Place: Monday, January 24, 2011, 11am-12pm, CSE 1202

Title: Robust Simulations and Significant Separations
Speaker: Lance Fortnow, Northwestern
Date and Place: Monday, January 10, 2011, 2-3:20 PM, CSE 4140

Fall 2010

Title: Homomorphic Signatures for Polynomial Functions
Speaker: David Freeman, Stanford
Date and Place: Monday, November 22, 2010, 2-3:20 PM, CSE 4140

Title: Expressive encryption from hard lattice problems.
Speaker: Shweta Agarwal, UT Austin
Date and Place: Monday, November 8, 2010, 2-3:20 PM, CSE 4140
References: Lattice Basis Delegation in Fixed Dimension and Shorter Ciphertext HIBE, Agrawal, Boneh and Boyen (CRYPTO 2010)
Efficient Lattice (H)IBE in the Standard Model, Agrawal, Boneh and Boyen (Eurocrypt, 2010)

Title: The effects of diversity in aggregation games.
Speaker: Andrea Vattani, UCSD
Date and Place: Monday, November 1, 2010, 2-3:20 PM, CSE 4140
References: The effects of diversity in aggregation games , Mol, Vattani, and Voulgaris

Title: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations
Speaker: Panagiotis Voulgaris, UCSD
Date and Place: Monday, October 18, 2010, 2-3:20 PM, CSE 4140
References: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations, Micciancio and Voulgaris

Title: Linkage clustering and continuum percolation
Speaker: Sanjoy Dasgupta, UCSD
Date and Place: Monday, October 11, 2010, 2-3:20 PM, CSE 4140
References: Rates of convergence for the cluster tree, Chaudhuri and Dasgupta

Title: Uniquely Represented Data Structures with Applications to Privacy
Speaker: Daniel Golovin, CalTech
Date and Place: Monday, October 4, 2010, 2-3:20 PM, CSE 4140
References: Strongly History-Independent Hashing with Applications, Blelloch and Golovin

Title: Chromatic Coding
Speaker: Daniel Lokshtanov, UCSD Simons Foundation Postdoctoral Fellow
Date and Place: Monday, September 27, 2010, 2-3:20 PM, CSE 4140
References: Fast FAST, Alon, Lokshtanov and Saurabh
Color Coding, Alon, Yuster and Zwick