Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$. The big open problem is to prove or disprove that there is an $f\in$ RAMSEY COLORING such that $f\in FP$. Is there anything known about smaller complexity classes, like an $f\in$ RAMSEY COLORING such that $f\in NC$ or $f\in LOGSPACE$?

I suppose $LOGSPACE$ is out of reach, but $f\notin AC_0$ seems to be trivial.

  • 1
    $\begingroup$ Are you asking for unconditional lower bounds? As I think you're already aware, we have very few proof techniques for unconditional lower bounds, aside from diagonalization (which would seem not to work here, unless you know of some universality result for Ramsey coloring) and for small classes like $\mathsf{AC}^0$ (many, starting with Furst-Saxe-Sipser) or $\mathsf{ACC}^0$ (Williams, although that also used diagonalization). Or if you'd be interested in conditional lower bounds you could ask more specifically something like: is RAMSEY COLORING $\mathsf{NL}$-hard? Is it $\mathsf{DET}$-hard? $\endgroup$ – Joshua Grochow Dec 20 '17 at 18:29
  • 2
    $\begingroup$ @Joshua Now being 3 years wiser, I agree these that these seem to be better questions. $\endgroup$ – domotorp Dec 21 '17 at 5:38

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.