BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Spectral Algorithms
DTSTART:20190828T150000
DTEND:20190828T170000
DTSTAMP:20260410T034203Z
UID:3582f4e0baaa8df3789bff0a79c4f6a3512624ad15aa992e989a01d8
CATEGORIES:Conferences - Seminars
DESCRIPTION:Grzegorz Adam Gluch\nEDIC candidacy exam\nExam president: Prof
 . Ola Svensson\nThesis advisor: Prof. Michael Kapralov\nThesis co-advisor:
  Prof. Rüdiger Urbanke\nCo-examiner: Prof. Friedrich Eisenbrand\n\nAbstra
 ct\nLinear algebraic approaches to graph processing have played a crucial 
 role in several recent developments in graph partitioning\, solving linear
  systems and more. In this research proposal we discuss several recent res
 ults in spectral graph partitioning together with promising directions for
  improving them to optimality. We also discuss space lower bounds for nume
 rical linear algebra in small space models\, namely lower bounds for solvi
 ng linear systems over reals from streams of i.i.d. samples in subquadrati
 c space. We also discuss an exciting conjecture that the sample complexity
  of the problem becomes worse if the underlying matrix has poor spectral p
 roperties (large condition number).\n\nBackground papers\nMulti-way spectr
 al partitioning and higher-order Cheeger inequalities\, by James R. Lee\, 
 et al.\nMemory-Sample Tradeoffs for Linear Regression with Small Error\, b
 y Vatsal Sharan\, et al.\nAlmost Optimal Local Graph Clustering Using Evol
 ving Sets\, by Reid Andersen\n 
LOCATION:BC 229 https://plan.epfl.ch/?room==BC%20229
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR