Title	Approximate Degree: A Survey
Creator	Thaler, Justin
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2018-08-14T15:02
Description	The epsilon-approximate degree of a Boolean function is the minimum degree of a real polynomial that pointwise approximates f to error epsilon. Approximate degree has wide-ranging applications in theoretical computer science, from computational learning theory to communication complexity, circuit complexity, oracle separations, and even cryptography. This talk will survey what is known about approximate degree and its many applications, including striking recent progress on proving approximate degree lower bounds. This survey will also function as a primer for Mark Bun's followup talk.
Extent	54.0
Subject	Mathematics; Computer science; Fourier analysis; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Georgetown University
Series	BIRS Workshop Lecture Videos (Oaxaca de Juárez (Mexico))
Date Available	2019-03-28
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0377631
URI	http://hdl.handle.net/2429/69315
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Researcher
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos