In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:
I think we should distinguish between major open problems that are viewed as fundamental problems, like $ P\neq NP $, and major open problems which will constitute a technical breakthrough, if solved, but are not necessarily as fundamental, e.g., exponential lower bounds on $ AC^0(6) $ circuits (i.e., $ AC^0+\mod 6 $ gates). So we should possibly open a new community wiki entitled "open problems in the frontiers of TCS", or the like.
Since Iddo did not start the thread, I thought I'll start this thread.
Often the main open problems of fields are known to researchers working in related fields, but the point at which current research is stuck is unknown to outsiders. The quoted example is a good one. As an outsider, it is clear that one of the biggest problems in circuit complexity is to show that NP requires super-polynomial size circuits. But outsiders may not be aware that the current point at which we are stuck is trying to prove exponential lower bounds for AC0 circuits with mod 6 gates. (Of course there could be other circuit complexity problems of similar difficulty which would describe where we are stuck. This is not unique.) Another example is to show time-space lower bounds for SAT better than n1.801.
This thread is for examples like this. Since it is hard to characterize such problems, I'll just give some examples of properties that such problems possess:
- Will often not be the big open problems of the field, but will be a big breakthrough if solved.
- Usually not unbelievably hard, in the sense that if someone told you that the problem was solved yesterday, this would not be too hard to believe.
- These problems will also often have numbers or constants that are not fundamental, but they arise because this happens to be where we are stuck.
- The problem at the frontiers of a particular field will keep changing from time to time, as opposed to the biggest problem in the field, which will remain the same for many many years.
- Often these problems are the easiest problems that are still open. For example we don't have exponential lower bounds for AC1 either, but since $AC^0$ is included in that class, it is formally easier to show lower bounds for $AC^0$, and thus that is at the current frontier of circuit complexity.
Please post one example per answer; standard big-list and CW conventions apply. If someone can explain what types of problems we're looking for better than I have, please feel free to edit this post and make appropriate changes.
EDIT: Kaveh suggested that answers also include an explanation as to why a given problem is at the frontier. For example, why are we looking for lower bounds against AC0 and not AC0? The answer is that we do have lower bounds against AC0. But then the obvious question is why do those methods fail for AC0. It would be nice if answers could explain this too.