- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Approximate Degree: A Survey
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Approximate Degree: A Survey Thaler, Justin
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.
Item Metadata
Title |
Approximate Degree: A Survey
|
Creator | |
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 | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Georgetown University
|
Series | |
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 | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Researcher
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International