Harry Lang: Coresets for kMeansType Problems on Streams Wednesday, June 28, 2017  4:00pm to 5:00pm Let f be a nonnegative symmetric dissimilarity measure. Given sets of points P (the input data) and C (a "query"), we define F(P,C) = \sum_{p \in P} \min_{c \in C} f(p,c). 

Conditional Hardness for Sensitivity Problems Wednesday, May 31, 2017  4:00pm to 5:00pm In recent years it has become popular to study dynamic problems in a 

Arnab Bhattacharyya: Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds Thursday, May 11, 2017  2:00pm to 3:00pm We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs), assuming Khot's Unique Games Conjecture (UGC). In particular, we prove that for any constants d in? the positive integers? 

Govind Ramnarayan: Relaxed Locally Correctable Codes Wednesday, May 10, 2017  4:00pm to 5:00pm Locally decodable codes (resp. locally correctable codes), or LDCs (resp. LCCs), are codes for which individual symbols of the message (resp. codeword) can be recovered by reading just a few bits from a noisy codeword. 

Ben Rossman:New separations of formula vs. circuit size Wednesday, April 12, 2017  4:00pm to 5:00pm I will present some recent results on the power of formulas vs. 

Richard Baraniuk: A Probabilistic Theory of Deep Learning Thursday, April 6, 2017  3:00pm to 4:00pm 

Tengyu Ma: Analyzing Nonconvex Optimization: Matrix Completion and Linear Residual Networks Wednesday, November 30, 2016  4:00pm to 5:00pm Nonconvex optimization is the main algorithmic technique behind 

Testable Bounded Degree Graph Properties Are Random Order Streamable Thursday, December 8, 2016  4:00pm to 5:00pm We study graph streaming problems. We transform known property testing algorithms into streaming ones. 

Solving Problems in P given Correlated Instances Wednesday, December 7, 2016  4:00pm to 5:00pm Abstract:Instances of computational problems do not arise in isolation. Often, correlations between the solutions of related instances arise in nature. We study the impact of having access to correlated instances on how fast we can solve a variety of problems. 

A& C Seminar: Huy L. Nguyen: Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality Wednesday, November 9, 2016  4:00pm to 5:00pm We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. 