Theory of Computation (TOC) Seminar
 |
Aaron Roth: Quantifying Tradeoffs Between Fairness and Accuracy in Online Learning Wednesday, February 22, 2017 - 4:00pm to 5:00pm Abstract:
|
 |
Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity Tuesday, February 14, 2017 - 4:00pm to 5:00pm Abstract: |
 |
Silvio Micali: ALGORAND: The True Public Ledger Tuesday, February 7, 2017 - 4:00pm to 5:00pm ABSTRACT |
 |
Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth Tuesday, December 13, 2016 - 4:00pm to 5:00pm Abstract: Extended formulations have received considerable amount of attention recently,
mostly for proving impossibility results. These are results of the following |
 |
Gil Cohen: Recent Advances in Randomness Extractors and Their Applications Tuesday, December 6, 2016 - 4:00pm to 5:00pm Abstract: |
 |
Tim Roughgarden: How Computer Science Informs Modern Auction Design Tuesday, November 29, 2016 - 4:00pm to 5:00pm Abstract : Economists have studied the theory and practice of auctions for decades. How can computer science contribute? Using the ongoing U.S. |
 |
Yuval Ishai: Succinct Secure Computation from DDH Tuesday, November 8, 2016 - 4:00pm to 5:00pm Abstract:
|
 |
Ronitt Rubinfeld: Local Computation Algorithms Tuesday, November 1, 2016 - 4:00pm to 5:00pm Abstract: |
 |
Muthuramakrishnana Venkitasubramaniam: Composable Adaptive Secure Protocols without Setup Under Polytime Assumptions Friday, October 28, 2016 - 10:30am to 12:00pm Abstract: All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions. |
 |
Jonathan Ullman: Algorithmic Stability for Adaptive Data Analysis Tuesday, October 18, 2016 - 4:00pm to 5:00pm Abstract: |
 |
Alexandr Andoni: Optimal Hashing for High-Dimensional Spaces Monday, October 3, 2016 - 4:00pm to 5:00pm Abstract:
We survey recent advances in the approximate nearest neighbor search
problem in high-dimensional Euclidean/Hamming spaces, which go beyond
the classic Locality Sensitive Hashing technique for the problem. The |
 |
Mohsen Ghaffari: Improved Local Distributed Graph Algorithms Tuesday, September 27, 2016 - 4:00pm to 5:00pm Abstract: How can the computers in a network interact and communicate to solve the network's graph problems efficiently? |
 |
Alina Ene: From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure Monday, September 19, 2016 - 4:00pm to 5:00pm |
 |
Boaz Barak: Computational Bayesianism, Sums of Squares, and Unicorns Tuesday, September 13, 2016 - 4:00pm to 5:00pm ABSTRACT: Can we make sense of quantities such as "the probability that 2^81712357 - 1 is prime" or "the probability that statement X is a logical contradiction"? |
 |
Sebastien Bubeck: New Results at the Crossroads of Convexity, Learning and Information Theory Tuesday, October 25, 2016 - 3:45pm to 5:15pm Abstract: I will present three new results (no background in optimization will be assumed, all concepts will be defined and motivated): (i) the Cramer transform of the uniform measure on a convex body is a universal self-concordant barrier; (ii) projected gradient descent with Gaussian |
 |
Ken Clarkson: More Near-Linear Linear Algebra, via Sketching Tuesday, May 3, 2016 - 4:00pm to 5:00pm Abstract: In recent years there have been significant improvements in matrix |
 |
Rocco Servedio: Two Circuit Lower Bounds Tuesday, April 26, 2016 - 4:00pm to 5:00pm Abstract:
|
 |
Madhu Sudan: Communication Amid Uncertainty Tuesday, May 10, 2016 - 4:00pm to 5:00pm Abstract: Computers and humans communicate in order to gain information about the state of the world around them, and to be able to determine how to act in the future. Effective communication relies on large shared context between the communicating parties: Such shared context tells the communi |
 |
David Zuckerman: Explicit Two-Source Extractors and Resilient Functions Tuesday, April 12, 2016 - 4:00pm to 5:00pm Abstract: We explicitly construct an extractor for two independent sources on n bits, |
 |
Omer Reingold: Constant-round Interactive-proofs for Delegating Computation Tuesday, March 8, 2016 - 4:00pm to 5:00pm Abstract: Interactive proofs, introduced by Goldwasser, |
 |
Ran Raz: Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning Tuesday, March 15, 2016 - 4:00pm to 5:00pm Abstract: We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.
|
 |
Avi Wigderson: Elementary Mathematical Problems Disguising Computational Hardness Thursday, February 11, 2016 - 4:00pm to 5:00pm Abstract: The theory of computation has done (and is doing) incredibly well on upper bounds - finding ingenious efficient algorithms for important problems. |
 |
Laszlo Babai: Graph Isomorphism in Quasipolynomial Time Tuesday, February 2, 2016 - 4:00pm to 5:00pm Abstract: The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools.
We outline the algorithm, with a focus on the core group theoretic routine ("Local Certificates").
|
 |
Li-Yang Tan: Unconditional Lower Bounds in Complexity Theory Tuesday, December 8, 2015 - 4:00pm to 5:00pm Abstract: I will present three recent results, each establishing new unconditional lower bounds in fundamental and well-studied models of computation:
|
 |
Nike Sun: The Exact k-SAT Threshold for Large k Tuesday, December 1, 2015 - 4:15pm to 5:15pm Abstract: |
 |
Elchanan Mossel: Corruption Detection and Shotgun Assembly of Networks Tuesday, November 3, 2015 - 4:00pm to 5:00pm Abstract: I will discuss two algorithmic problems on networks. The first problem is the classical and well studied problem of identifying faulty nodes in a network given reports of their neighbors. |
 |
Nati Linial: High-Dimensional Permutations Tuesday, November 24, 2015 - 4:00pm to 5:00pm Abstract: This talk starts from the realization that many of the basic combinatorial constructs that we use all the time are inherently one dimensional. Permutations are a case in point. |
 |
Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity Tuesday, October 27, 2015 - 4:00pm to 5:00pm Abstract: |
 |
Sanjeev Arora: The linear algebraic structure of word meanings Tuesday, September 15, 2015 - 4:15pm to 5:15pm Abstract: In Natural Language Processing (NLP), semantic word embeddings are used to capture the meanings of words as vectors. They are often constructed using nonlinear/nonconvex techniques such as deep nets and energy-based models. |
 |
Ravi Kannan: Topic Modeling and NMF using Soft Clustering Tuesday, September 22, 2015 - 4:15pm to 5:15pm Abstract: The model fitting problem in Topic Modeling is a special case of Non-Negative Matrix Factorization and both are computationally hard. Soft clustering, where, each datapoint can belong fractionally |
Pages
