The Complexity of Nondeterminism: Lance Fortnow, Georgia Tech (Theory Seminar)

Starts:
2:00 pm on Friday, March 28, 2014
Ends:
4:00 pm on Friday, March 28, 2014
Location:
MCS 137
Abstract: We show several short results related to nondeterministic computation - Many NP-complete problems cannot be compressed to poly-size in their parameters unless the polynomial-time hierarchy collapses - A new proof of the nondeterministic time hierarchy and its application to robust simulations - A proof that NEXP is not contained in NP/n^c - An oracle relative to which NEXP is contained in NP for infinitely many input lengths. These results are from several recent papers co-authored with Rahul Santhanam and Harry Buhrman.