BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Sublinear Algorithms for Graph Processing
DTSTART:20170718T130000
DTEND:20170718T150000
DTSTAMP:20260407T162246Z
UID:305a8d58cfa36e00e8bb26538268085721bcc8e417b4d45107979da2
CATEGORIES:Conferences - Seminars
DESCRIPTION:Aidasadat Mousavifar\nEDIC Candidacy Exam:\nExam president: Pr
 of. Rüdiger Urbanke\nThesis director: Prof. Michael Kapralov\nCo-examiner
 : Prof. Ola Svensson\n\nAbstract:\nThe goal of the thesis is to design eff
 icient sublinear (time\, space\, communication) algorithms for fundamental
  graph problems. In particular\, a major direction that I would like to ex
 plore is the design of sublinear time\, or local\, graph exploration primi
 tives for approximating solution cost of combinatorial optimisation proble
 ms.  Examples include approximating matching size\, testing cluster struc
 ture of graphs using carefully designed randomised exploration processes t
 hat can be implemented in sublinear time\, space or communication. Recent 
 years have seen significant progress on several of the questions above\, b
 ut many exciting directions remain largely unexplored.\n\nBackground paper
 s:\nYoshida\, Yuichi\, Masaki Yamamoto\, and Hiro Ito. "Improved constant-
 time approximation algorithms for maximum matchings and other optimization
  problems." SIAM Journal on Computing 41.4 (2012): 1074-1093.\n Czumaj\, 
 Artur\, Pan Peng\, and Christian Sohler. "Testing cluster structure of gra
 phs." Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory o
 f Computing. ACM\, 2015.\n Raz\, Ran. "Fast learning requires good memory
 : A time-space lower bound for parity learning." Foundations of Computer S
 cience (FOCS)\, 2016 IEEE 57th Annual Symposium on. IEEE\, 2016.\n\n 
LOCATION:BC 129 https://plan.epfl.ch/?room==BC%20129
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR