10
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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$ – Michaël Cadilhac Oct 12 '18 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$ – William Hird Oct 22 '18 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.