9
$\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.

|cite|improve this question
$\endgroup$
  • 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.