BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Sparse Polynomial Approximations and their applicat
 ions to  Quantum Advantage\, Parallel Computation\, and Pseudorandomness
DTSTART:20190307T101500
DTEND:20190307T111500
DTSTAMP:20260406T174450Z
UID:de1f390fe522801782e1c0d0ee79e06f52a99a3a50e1b9bbfa03407b
CATEGORIES:Conferences - Seminars
DESCRIPTION:By: Avishay Tal - Stanford University\nIC Faculty candidate\n\
 nAbstract:\nThis talk is motivated by three (seemingly unrelated) question
 s:\n1. For which tasks do quantum algorithms outperform classical computat
 ion?\n2. Does parallel computing always offer a speed-up\, or are some tas
 ks inherently sequential?\n3. Do randomized algorithms have deterministic 
 counterparts with similar memory footprint?\n\nWe make progress on all thr
 ee questions by exploiting a common phenomenon at the core of their analy
 sis: in all cases\, the studied computational devices can be well-approxim
 ated by sparse multivariate polynomials. As an application towards the fir
 st question above\, we show that relative to an oracle\, quantum algorithm
 s can efficiently solve tasks that are infeasible for the polynomial hiera
 rchy (that captures P\, NP\, coNP and their generalizations). This settles
  an open problem raised by Bernstein and Vazirani in 1993.\n\nLooking forw
 ard\, we conjecture that several other computational devices can be well-a
 pproximated by sparse multivariate polynomials.\nProving our conjecture wo
 uld resolve several big open questions in computational complexity that ha
 ve remained open since the 1980s.\n\nBio:\nAvishay Tal is a Motwani Postdo
 ctoral Research Fellow at Stanford University\, hosted by Omer Reingold. P
 rior to that\, he was a postdoctoral researcher at the Institute for Advan
 ced Study\, hosted by Avi Wigderson. He obtained his Ph.D. in 2015 from th
 e Weizmann Institute of Science\, under the guidance of Ran Raz. His resea
 rch interests include computational complexity theory\, analysis of Boolea
 n functions\, quantum computing\, pseudorandomness\, and learning theory.\
 n\nMore information\n 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR