BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Techniques for Proving Hardness of Problems
DTSTART:20180718T100000
DTEND:20180718T120000
DTSTAMP:20260407T051216Z
UID:0cc6b4812551b70a1bca2490b2c404918ac22169ad573d3234878f0a
CATEGORIES:Conferences - Seminars
DESCRIPTION:Paritosh Garg\nEDIC candidacy exam\nExam president: Prof. Rued
 iger Urbanke\nThesis advisor: Prof. Ola Svensson\nThesis co-advisor: Prof.
  Michael Kapralov\nCo-examiner: Prof. Michael Gastpar\n\nAbstract\n\nProvi
 ng the hardness of problems can give insight where one has failed to desig
 n better algorithms with provable guarantees. Not only that\, it may give 
 rise to new techniques or extend existing ones which are interesting in it
 s own right.\nIn recent years\, there has been exciting progress in provin
 g unconditional lower bounds for problems in learning theory\, communicati
 on complexity and sublinear algorithms using techniques from information t
 heory\, Fourier analysis and randomness extractors and conditional lower b
 ounds assuming SETH for several classical problems in P. However\, there a
 re different variants and models under which these problems remain largely
  unexplored. This thesis would focus on applying/extending these technique
 s or developing new ones to prove lower bounds for these problems.\n\n\nBa
 ckground papers\nDistributed PCP Theorems for Hardness of Approximation in
  P\, by Abboud\, A.\, et al.\nWelfare Maximization with Limited Interactio
 n\, by Alon\, N.\, et al.\nExtractor-Based Time-Space Lower Bounds for Lea
 rning\, by Garg\, S.\, et al.\n\n\n 
LOCATION:BC 02 https://plan.epfl.ch/?room==BC%2002
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR