Skip to Content

Theory Seminar (archive)

Theory Seminar (Archive)

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


Spring 2014

Leo Ducas (UCSD)
"The Versatility of Discrete Gaussians over Lattices"
Monday, April 7, 2014, 2:00pm
Details

Mario Szegedy (Rutgers)
"Impossibility Theorems and the Universal Algebraic Toolkit"
Monday, April 14, 2014, 2:00pm
Details

Victor Vianu (UCSD)
"Query determinacy and rewriting"
Monday, April 21, 2014, 2:00pm
Details

Vineet Bafna (UCSD)
"Algorithms Strategies for genomics and genetics"
Monday, April 28, 2014, 2:00pm
Details

Michael Walter (UCSD)
"Fast Lattice Point Enumeration with Minimal Overhead"
Monday, May 5, 2014, 2:00pm
Details

Jacques Verstraete (UCSD)
"Extremal Problems for Linear Dependencies"
Monday, May 12, 2014, 2:00pm
Details

Sourav Chakraborty (Chennai Mathematical Institute)
"Testing of Boolean Function Isomorphism"
Monday, May 19, 2014, 2:00pm
Details

Monday, May 26, 2014, 2:00pm (no seminar, memorial day)

Monday, June 2, 2014, 2:00pm (no seminar, STOC)


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