Skip to main navigation Skip to Content

Computer Science

University of Toronto
  • Quercus
  • Student Support
  • Contact
  • About
    • History of U of T Computer Science
    • Computer Science at U of T Mississauga
    • Computer Science at U of T Scarborough
    • Employment Opportunities for Faculty/Lecturers
    • How to Find Us
    • Contact
  • Undergraduate
    • Prospective Undergraduates
    • Current Undergraduates
  • Graduate
    • Prospective Graduate Students
    • Current Graduate Students
  • Research
    • Research Areas
    • Partner with us
  • People
    • Faculty
    • Staff
    • In Memoriam
    • Alumni and Friends
    • Honours & Awards
    • Women in Computer Science
    • Graduate Student Society
    • Undergraduate Student Union
    • Undergraduate Artificial Intelligence Group
    • Undergraduate Theory Group
  • News & Events
    • News
    • Events
    • @DCS Update
    • Alumni
    • Donate
You are viewing: > Home > News & Events > Events > Theory Seminar: Oct 30
  • About
  • Undergraduate
  • Graduate
  • Research
  • People
  • News & Events

Theory Seminar: Oct 30

Event date: Friday, October 30, 2015, at 11:10 AM
Location: GB 119

Speaker: Justin Thaler, Harvard University

Title: Approximate Degree and the Method of Dual Polynomials

Abstract:

The \eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error \eps. Approximate degree has wide-ranging applications in theoretical computer science, from computational learning theory to communication, query, and circuit complexity. Despite its importance, our understanding of approximate degree remains somewhat limited, with few general results known.

The focus of this talk will be on a relatively new method for proving lower bounds on approximate degree: specifying dual polynomials, which are dual solutions to a certain linear program capturing the approximate degree of any function. After surveying earlier work on approximate degree, I will describe how the method of dual polynomials has recently enabled progress on several open problems.

Based on joint work with Mark Bun.


All rights reserved copyright Computer Science, University of Toronto | Site Map