Theory of Computation (TOC) Seminar

	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 (empirical risk) that is written as a sum of losses associated to each data point (each example).
	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 diﬃcult is it to ﬁnd 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. In retrospect, agreement testing theorems are a key combinatorial component in nearly all PCPs.
	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.

Pages