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

2:00 pm on Friday, March 28, 2014
4:00 pm on Friday, March 28, 2014
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.