Theory of Computation (TOC) Seminar
 |
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. |
Pages
