Theory Seminar

Friday, November 18, 2016 - 2:00pm to 3:00pm

Location:

8102 Gates & Hillman Centers

Speaker:

SUSHANT SACHDEVA, Research Scientist https://sachdevasushant.github.io/

Event Website:

http://theory.cs.cmu.edu/seminars/

For More Information, Contact:

nlc@cs.cmu.edu

In this talk, we'll discuss how to use observations on some vertices of a graph to draw inferences on the remaining vertices.
Given real-valued observations on some vertices, we seek a smooth extension of these observations to all vertices. We propose the absolutely minimal Lipschitz extension, which is the limit of p-Laplacian regularization for large p.
We'll present algorithmic results for computing these extensions efficiently. Our algorithms naturally apply to directed graphs, and run on graphs with millions of edges in a few minutes. These extensions are particularly suited for regularization and outlier removal, which is surprising since outlier removal is NP-hard for other natural extensions. We'll present some experimental results for detecting spam webpages using our algorithms.
Finally, we'll discuss how these extensions are particularly suited for regularization and  outlier removal, which is surprising since outlier removal is NP-hard for other natural extensions.
This is joint work with < Rasmus Kyng, Anup Rao, and Daniel Spielman .

Sushant Sachdeva is a research scientist at Google. He is interested in Algorithms, and its connections to optimization, machine learning, and statistics. His recent research focus has been the design of fast algorithms for graph problems.
He completed his postdoc at Yale with Dan Spielman (2016), his PhD from Princeton (2013) under Sanjeev Arora, and his BTech from IIT Bombay (2008). He is the recipient of Simons Berkeley Research Fellowship (2013), and the IITB President of India Gold Medal (2008).
Appointments

Keywords:

Seminar Series