BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Fast and Space Efficient Algorithms for Spectral Approximation
DTSTART:20180611T140000
DTEND:20180611T160000
DTSTAMP:20260407T102622Z
UID:7c98dadb0d42f843be6915ee0223e717eddd70f4fba993116814c5f1
CATEGORIES:Conferences - Seminars
DESCRIPTION:Navid Nouri\nEDIC candidacy exam\nExam president: Prof. Emre T
 elatar\nThesis advisor: Prof. Michael Kapralov\nCo-examiner: Prof. Ola Sve
 nsson\n\nAbstract\nGraphs and matrices are a common abstraction for repres
 enting real-world networks\, and efficient algorithms for graph problems a
 re at the core of large data analysis. The problem of designing compressed
  representations for graphs that preserve their structure has received a l
 ot of attention in the literature recently\, but many exciting directions 
 remain open. This thesis will focus on designing such compressed represent
 ations that can be efficiently maintained and queried. Specific directions
  include efficient graph sketches that preserve spectral structure of grap
 hs\, lower bounds for graph sketches that preserve shortest path distances
 \, as well spectral approximations to kernel matrices\n\nBackground papers
 \nLocalization of Electrical Flows\, by A. Schild\, S. Rao.\nOptimal Data-
 Dependent Hashing for Approximate Near Neighbors\, by A. Andoni\, I. Razen
 shteyn.\nEfficient \\tilde{O}(n/\\eps) Spectral Sketches for the Laplacian
  and its Pseudoinverse\, by A. Jambulapati\, A. Sidford\n\n\n 
LOCATION:BC 129 https://plan.epfl.ch/?room==BC%20129
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR