What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing?

For example: In the draft version of Arora & Barak's book, it is mentioned that: Frontier 2.1: Exhibit a language in NEXP that is not in ACC0 (6) This was solved by Williams soon after that.

  • 6
    $\begingroup$ I believe Ryan mentioned in an interview that he worked on that despite his advisor's opinion. In any case, focusing a PhD on 60 year old open questions can be very risky. $\endgroup$ Oct 12, 2018 at 8:24
  • 1
    $\begingroup$ I wouldn't do anything in quantum computing until "quantum supremacy" has been proven. If Levin-Goldreich-Kalai are correct, there are going to be a lot of people with Egg-On-Face ! $\endgroup$ Oct 22, 2018 at 4:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.