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

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

CC BY-SA 4.0
2018-10-12T08:24:32.733Z
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.
Michaël Cadilhac
CC BY-SA 4.0
2018-10-22T04:21:39.373Z
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 !
William Hird
<cc.complexity-theory><soft-question><quantum-computing>
Relatively low ambitious frontiers
Avi Tal
# Relatively low ambitious frontiers

(Asked by: username_0 on 2018-10-12)

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.

**Tags:** cc.complexity-theory, soft-question, quantum-computing

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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 !  

---

## 0 answers

