Algorithms and Complexity Seminar

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 Non-convex Optimization: Matrix Completion and Linear Residual Networks
Wednesday, November 30, 2016 - 4:00pm to 5:00pm

Non-convex optimization is the main algorithmic technique behind
many state-of-art results in machine learning. It has been conjectured that
the landscape of many training objectives has the nice geometric property

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.

A&C Seminar: Rati Gelashvili: Time-Space Trade-Offs in Molecular Computation
Wednesday, October 26, 2016 - 4:00pm to 5:00pm


Subscribe to Algorithms and Complexity Seminar