In what sense is the ``hard'' regime hard?
Statement
Can we formalize in what sense we believe that conjectured “hard” regions are hard? There are some caveats here because, for instance, statistical physics and the sum-of-squares hierarchy both predict a hard phase for XOR-SAT even though it can be solved efficiently by Gaussian elimination. However, Gaussian elimination fails in the presense of noise, so perhaps we have captured a “robust” notion of hardness.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.