Theory of Computation (TOC) Seminar

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 ?

Pages

Subscribe to Theory of Computation (TOC) Seminar