The one the sounds most surprising to have been solved to me (disclaimer: I don’t understand a lot of these) is the arithmetic circuit complexity of the permanent. Scott Aaronson suggested trying to analyze the circuit complexity of the permanent (in particular, finding the exact complexity for a small case like ) a while back:
More concretely, my proposal is to devote some of the world’s computing power to an all-out attempt to answer questions like the following: does computing the permanent of a 4-by-4 matrix require more arithmetic operations than computing its determinant?
I wonder if this result provides any more information about that? On the determinant side of things, there was some surprisingly recent progress here: https://arxiv.org/pdf/2301.06586
Ooh nice callout, I do remember that post of Scott’s. Unfortunately I too don’t understand enough to comment. I’ll just quote Scott to motivate the quote you highlighted:
lylebot: Yes, even pure mathematicians often resort to experiment (more often than they admit!) when they want to guess at the truth or falsity of a conjecture. But complexity theory is a special branch of mathematics — one that asks about the asymptotic behavior, not of some particular algorithm or a typical algorithm, but of the best algorithm that could possibly exist. And the set of possible algorithms is both huge beyond imagination and lacking in any simple characterization. That’s why, in the past, experimental work has not been a big help to complexity theory: because the amount of computation that you’d have to do to learn anything interesting is so astronomical. My “wild & crazy” proposal is that we at least ask ourselves whether that’s still true, given both the better understanding and the vastly increased computing power that we have today.
The one the sounds most surprising to have been solved to me (disclaimer: I don’t understand a lot of these) is the arithmetic circuit complexity of the permanent. Scott Aaronson suggested trying to analyze the circuit complexity of the permanent (in particular, finding the exact complexity for a small case like
I wonder if this result provides any more information about that? On the determinant side of things, there was some surprisingly recent progress here: https://arxiv.org/pdf/2301.06586
Ooh nice callout, I do remember that post of Scott’s. Unfortunately I too don’t understand enough to comment. I’ll just quote Scott to motivate the quote you highlighted: