Skip to Content

Theory Seminar (archive)

Theory Seminar (Archive)

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


Winter 2014

January 8th-10th, 2014 (no seminar; Complexity and Coding Theory workshop)

Valeria Nokolaenko (Stanford)
"Fully Key Homomorphic Encryption and Applications: Compressed Garbled Circuits and Arithmetic ABE with Short Keys"
Monday, January 13th, 2014, 2:00pm
Details

Monday, January 20th, 2014: No Seminar (MLK holiday)

Sasha Rubin (TU Wien & IST Austria)
"Memoryless Determinacy of Cycle Games"
Wednesday, January 22nd, 2014, 2:00pm
Details

Timon Hertli (ETH Zurich)
"Breaking the PPSZ Barrier for Unique 3-SAT"
Monday, January 27th, 2014, 2:00pm
Details

Russell Impagliazzo (UCSD)
"Fourier Concentration from Shrinkage"
Monday, February 3rd, 2014, 2:00pm
Details

Alexandr Andoni (Microsoft Research)
"Parallel Algorithms for Geometric Graph Problems"
Monday, February 10th, 2014, 2:00pm
Details

Monday, February 17th, 2014: No Seminar (President's day)

Moritz Hardt (IBM Research)
"On the Provable Convergence of Alternating Minimization for Matrix Completion"
Tueday, February 18th, 2014, 2:00pm
Details

Klim Efremenko (U. Chicago)
"List and Unique Coding of Interactive Communication"
Monday, February 24th, 2014, 2:00pm
Details

Shang-Hua Teng (USC)
"The Laplacian Paradigm: Emerging Algorithms for Massive Graphs"
Monday, March 3rd, 2014, 2:00pm
Details


Fall 2013

Leo Ducas (UCSD)
"The Chaitin's Constant"
Monday, September 30th, 2013, 2:00pm
Details

Mohan Paturi (UCSD)
"Exact Complexity and Satisfiability"
Monday, October 7th, 2013, 2:00pm

Shachar Lovett (UCSD)
"Communication is Bounded by Root of Rank"
Monday, October 14th, 2013, 2:00pm
Details

Bjorn Tackmann (ETH Zurich)
"Constructive Cryptography - Introduction and Applications"
Monday, October 21th, 2013, 2:00pm
Details

Monday, October 28th, 2013 No seminar (FOCS)

Daniel Moeller (UCSD)
"Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching"
Monday, November 4th, 2013, 2:00pm
Details

Marco Carmosino (UCSD)
"Counting Solutions to Problems in NL, and the Computational Complexity of Linear Algebra"
Monday, November 18th, 2013, 2:00pm

Daniele Micciancio (UCSD)
"Locally Dense Codes"
Monday, November 25th, 2013, 2:00pm

Mohammad Hajiabadi (U. Victoria)
"How encryption with standard security copes under stronger forms of attack, with applications to computational soundness"
Monday, December 2, 2013, 2:00pm
Details


Summer 2013

Jordi Levy (IIIA)
"The Nature of Industrial SAT Instances"
Monday, July 29, 2013, 2:00pm
Details

Chris Beck (Princeton)
"Strong ETH holds for regular resolution"
Thursday, August 1, 2013, 11:00am
Details

Russell Impagliazzo (UCSD)
"Finding Heavy Hitters from Lossy or Noisy Data"
Monday, August 5, 2013, 2:00pm
Details

Valentine Kabanets (Simon Fraser University)
"Mining Circuit Lower Bound Proofs for Meta-Algorithms"
Monday, August 12, 2013, 2:00pm
Details


Spring 2013

Ankur Moitra (IAS and Princeton)
"New Algorithms for Nonnegative Matrix Factorization and Beyond"
Monday, April 1, 2013, 11:00pm

Ankur Moitra (IAS and Princeton)
"Disentangling Gaussians"
Monday, April 1, 2013, 2:00pm
Details

Daniele Micciancio (UCSD)
"An equational approach to secure multiparty computation"
Monday, April 8, 2013, 2:00pm
Details

Shweta Agrawal (UCLA)
"Discrete Gaussian Leftover Hash Lemma over Infinite Domains"
Monday, April 15, 2013, 2:00pm
Details

Shachar Lovett (UCSD)
"Non-Malleable Codes from Additive Combinatorics"
Monday, April 22, 2013, 2:00pm
Details

Yi-Kai Liu (NIST)
"Building one-time memories from isolated qubits"
Thursday, April 25, 2013, 2:00pm
Details

Chris Peikert (Georgia Tech)
"Practical Bootstrapping with Polylogarithmic Overhead"
Monday, April 29, 2013, 2:00pm
Details

Daniel Dadush (NYU)
"On the Lattice Smoothing Parameter Problem"
Monday, May 6, 2013, 2:00pm
Details

Benny Sudakov (UCLA)
"The phase transition in random graphs - a simple proof"
Wednesday, May 15, 2013, 11:00pm
Details

Mihir Bellare (UCSD)
"Semantic Security for the Wiretap Channel"
Monday, May 20, 2013, 2:00pm
Details

Russell Impagliazzo (UCSD)
"Simultaneons security and reliability amplification for unknown channels"
Wednesday, May 29, 2013, 12:00pm
Details


Spring 2012

Paul Valiant (UC, Berkeley)
''Central Limit Theorems and Tight Lower Bounds for Entropy Estimation''
Monday, April 2, 2012, 2:00 pm
Details

Shachar Lovett (Institute for Advanced Studies)
''Subspace-evasive sets''
Monday, April 9, 2012, 2:00 pm
Details

Shayan Oveis Gharan (Stanford)
''Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities''
Monday, April 16, 2012, 2:00 pm
Details

Madhur Tulsiani (Toyota Technological Institute)
''Towards An Optimal Query Efficient PCP?''
Monday, April 23, 2012, 2:00 pm
Details

Zvika Brakerski (Stanford University)
''Fully Homomorphic Encryption from LWE''
Monday, April 30, 2012, 2:00 pm
Details

Eva Tardos (Cornell University)
''Near-Optimal Greedy Mechanisms''
Monday, May 7, 2012, 11:00 am
Details

Andrew Drucker (MIT)
''New Limits to Instance Compression for Hard Problems''
Monday, May 14, 2012, 2:00 pm
Details

Alexandra Kolla (UIUC)
''Maximal Inequality for Spherical Means on the Hypercube''
Monday, June 4, 2012, 2:00 pm
Details

Russell Impagliazzo (UCSD)
''Pseudorandomness from Shrinkage''
Monday, June 11, 2012, 2:00 pm
Details

Winter 2012

Sandy Irani (UC, Irvine)
''Generating Quantum Gibbs States''
Monday, March 12, 2012, 2:00 pm
Details

Virginia Williams (UC, Berkeley)
''Multiplying matrices faster''
Wednesday, March 21, 2012,11:00 am
Details


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



research | about seo