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 - June 18
  • About
  • Undergraduate
  • Graduate
  • Research
  • People
  • News & Events

Theory Seminar - June 18

Event date: Thursday, June 18, 2015, at 11:10 AM
Location: PT266

Speaker: Antonina Kolokolova, Memorial University

Title: Axiomatic approach to complexity barriers

Abstract:

The main questions in complexity theory such as P vs. NP remain unresolved. Moreover, on a meta-level, there are several results that state that certain classes of techniques cannot be used to resolve these questions. A classic example of such "barrier" result is the relativization of Baker, Gill and Solovay'75: the statement that no technique such as diagonalization which is insensitive to access to extra information (oracles) can resolve the P vs. NP and similar questions. A more recent result along these lines is the algebrization barrier of Aaronson and Wigderson'2008, which shows that a large class of non-relativizing techniques such as arithmetization similarly cannot resolve the main open problems. Such barrier results resemble independence from a logical theory, however, even for relativization  this similarity was not studied much, except for an unpublished paper by Arora, Impagliazzo and Vazirani.

Here, I will talk about their approach and how we extend it to capture algebrization. Our framework avoids using different oracles on the two sides of inclusions/separations,  and allows for more complex statements, while formalizing most of AW'08 positive and negative results.  We also show that there is a known non-algebrizing complexity statement:  NEXP=MIP.

Based on joint work with Impagliazzo and Kabanets, in particular our STOC'09 paper.

 

 


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