Computer Science/Discrete Mathematics Seminar I

The dichotomy between structure and randomness plays an important role in areas such as combinatorics and number theory. I will discuss a similar dichotomy in complexity theory, and illustrate it with three examples of my own work: (i) An algorithmic result (with Igor Oliveira) showing how to probabilistically generate a fixed prime of length n in time sub-exponential in n, for infinitely many n (ii) A lower bound result showing that Promise-MA, the class of promise problems with short proofs that are verifiable efficiently by probabilistic algorithms, does not have circuits of size n^k for any fixed k (iii) A barrier result (with Jan Pich) showing that certain lower bounds in proof complexity are not themselves efficiently provable. What these results all have in common is that they are unconditional results in settings where such results are often surprising, and that the proofs are non-constructive. I will speculate on whether this non-constructivity is essential, and on the implications for complexity theory more broadly.