Theory of Computation (TOC) Seminar
 |
Avishay Tal: Oracle Separation of BQP and the Polynomial Hierarchy Tuesday, November 27, 2018 - 4:00pm to 5:00pm Abstract: In their seminal paper, Bennett, Bernstein, Brassard and Vazirani [SICOMP, 1997] showed that relative to an oracle, quantum algorithms are unable to solve NP-complete problems in sub-exponential time |
 |
Dean Doron: Probabilistic logspace algorithms for Laplacian solvers Tuesday, December 11, 2018 - 4:00pm to 5:00pm Abstract: A series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system Lx = b, where L is the Laplacian of an undirected graph. |
 |
Aaron Sidford: Perron-Frobenius Theory in Nearly Linear Time Tuesday, November 13, 2018 - 4:00pm to 5:00pm
|
 |
Vijay Vazirani: Planar Graph Perfect Matching is in NC Tuesday, November 6, 2018 - 4:00pm to 5:00pm Abstract: Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? |
 |
Xiao Wang (MIT): Covert Security with Public Verifiability: Simpler, Faster, and Leaner Friday, October 12, 2018 - 10:30am to 12:00pm Abstract: |
 |
Suresh Venkatasubramanian: Towards a theory (or theories) of fairness in automated decision-making Tuesday, October 2, 2018 - 4:00pm to 5:00pm Abstract: |
 |
Sasha Razborov: Grand Challanges in Complexity Theory through the Lens of Proof Theory Tuesday, September 25, 2018 - 4:00pm to 5:00pm Abstract: Given our current inability to even formulate a coherent program towards |
 |
Costis Daskalakis: Improving Generative Adversarial Networks using Game Theory and Statistics Tuesday, September 18, 2018 - 4:00pm to 5:00pm Abstract: Generative Adversarial Networks (aka GANs) are a recently proposed approach for learning samplers of high-dimensional distributions with intricate structure, such as distributions over natural images, given samples from these distributions. |
 |
Urmila Mahadev: Classical Verification of Quantam Computation Tuesday, October 23, 2018 - 4:00pm to 5:00pm Abstract: We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. |
 |
Dor Minzer: 2-to-2 Games is NP-hard Wednesday, April 11, 2018 - 4:15pm to 5:15pm |
 |
Benny Applebaum: Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions Tuesday, April 10, 2018 - 4:00pm to 5:00pm Abstract:
Is it possible to approximate the value of a 3-CNF formula to within a small constant factor in sub-exponential time? |
 |
Ohad Shamir: Is Depth Needed for Deep Learning? Circuit Complexity in Neural Networks Tuesday, March 20, 2018 - 4:15pm to 5:15pm Abstract
======
|
 |
Amnon Ta-Shma: Parity samplers and explicit, epsilon-Balanced codes close to the GV Bound Tuesday, February 13, 2018 - 4:00pm to 5:00pm Abstract: |
 |
Asaf Shapira: Efficient graph property testing Tuesday, February 6, 2018 - 4:00pm to 5:00pm Abstract: Results from around 10 years ago more or less determined which graph properties can be tested with a constant number of queries. However, in most cases the “constants” involves were enormous. |
 |
Barna Saha: Space & Time Efficient Algorithms for "Bounded Difference" Problems Tuesday, December 12, 2017 - 4:00pm to 5:00pm |
 |
Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares Tuesday, December 5, 2017 - 4:00pm to 5:00pm Abstract: |
 |
Kasper Green Larsen: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds Tuesday, November 28, 2017 - 4:00pm to 5:00pm |
 |
Venkatesan Guruswami: Promise Constraint Satisfaction Tuesday, November 14, 2017 - 4:00pm to 5:00pm Abstract: Given a 5-SAT instance admitting an assignment satisfying at least 2 literals in each clause, can one efficiently find a satisfying assignment that sets at least one literal to true in each clause? |
 |
Omer Paneth: On the round Complexity of Zero-Knowledge Protocols and Compressing Collisions Tuesday, November 7, 2017 - 4:00pm to 5:00pm |
 |
Noga Alon: Structure, randomness and universality Tuesday, October 31, 2017 - 4:00pm to 5:00pm Abstract: What is the minimum possible number of vertices of a graph that contains every k-vertex graph as an induced subgraph ? What is the minimum possible number of edges in a graph that contains every k-vertex graph with maximum degree 3 as a subgraph ? |
 |
Sanjam Garg: Identity-Based Encryption from the Diffie-Hellman Assumption Tuesday, September 19, 2017 - 4:00pm to 5:00pm In this talk, I will describe a new construction of identity-based encryption based on the hardness |
|
|
Russell Impagliazzo: Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity Tuesday, September 12, 2017 - 4:00pm to 5:00pm Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity |
 |
Yuval Peres: Trace reconstruction for the deletion channel Tuesday, May 2, 2017 - 4:00pm to 5:00pm Abstract: In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability $q$, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconst |
 |
Cynthia Dwork: What's Fair? Tuesday, April 25, 2017 - 4:00pm to 5:00pm Abstract: Data, algorithms, and systems have biases embedded within them reflecting designers’ explicit and implicit choices, historical biases, and societal priorities. |
 |
Andrea Montanari: The landscape of some statistical problems Wednesday, April 19, 2017 - 4:30pm to 5:30pm Abstract: Most high-dimensional estimation and prediction methods propose to minimize a cost function |
 |
Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding Tuesday, April 11, 2017 - 4:00pm to 5:00pm Abstract: The distance product of two matrices A and B is the matrix C defined as C[i,j]=min_k A[i,k]+B[k,j]. |
 |
Moni Naor: White-box vs. Black-box Search Problems: A Cryptographic Perspective Tuesday, March 21, 2017 - 4:00pm to 5:00pm Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? |
 |
Irit Dinur: Grassmann agreement testing and the 2:1 conjecture Tuesday, March 14, 2017 - 4:00pm to 5:00pm Abstract: I will describe the notion of agreement testing, which allows to deduce global structure from local agreement checks. |
 |
Vasilis Syrgkanis: Oracle efficient Learning and Auction Design Tuesday, February 28, 2017 - 4:00pm to 5:00pm Abstract. We consider the design of online no-regret algorithms that are computationally efficient, given access to an offline optimization oracle. |
 |
Nikhil Bansal: A fast polynomial space algorithm for Subset Sum Tuesday, March 7, 2017 - 4:00pm to 5:00pm Abstract: I will describe an algorithm for the subset sum problem that
runs in 2^{0.86n} time and uses polynomial space. Previously, all
algorithms with running time less than 2^n used exponential space, and
obtaining such a guarantee was open. Our algorithm is based on Floyd's |
Pages
