11
$\begingroup$

Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994).

Has there been any result that has avoided the natural proofs' barrier? More formally, has there been any result where the concept of natural proofs makes sense and we provably know that there cannot be a natural proof for the result?

$\endgroup$
  • 4
    $\begingroup$ Results that use Geometric Complexity Theory avoid naturalization. $\endgroup$ – MCH May 31 '13 at 17:52
  • 6
    $\begingroup$ @MCH: While I agree with you philosophically, what you say isn't quite true (yet). 1) There are very few results that follow the "full" GCT program (e.g. the recent lower bound by Burgisser and Ikenmeyer on matrix multiplication). 2) Those results apply to questions where even their Boolean analogues are not known to have a natural proofs barrier (such as matrix mult). 3) There isn't yet a well-established theory of natural proofs in the algebraic setting. OTOH, a proof which really used characterization by symmetries as suggested in GCT would indeed avoid natural proofs by avoiding largeness. $\endgroup$ – Joshua Grochow May 31 '13 at 18:05
  • 3
    $\begingroup$ Of course I didn't mean any result that uses GCT; obviously saying "any result in which X appears avoids Y" is generally meaningless, and on the other hand GCT is more than just Boolean complexity. My point was that results that use Geometric Complexity Theory have the potential of avoiding naturalization. $\endgroup$ – MCH May 31 '13 at 18:50
  • 3
    $\begingroup$ @vzn: maybe you'll find a better explanation in this: cstheory.stackexchange.com/questions/170/… $\endgroup$ – MCH May 31 '13 at 18:58
  • 5
    $\begingroup$ Look, AFAIK, you are not an expert in complexity theory. If you are making claims about complexity theorist and complexity theory, it is your job to provide sources for those claims. And I can assure you, leaving such comment out of your posts will not hurt your questions. ps: I removed my earlier comments about the question to clean up the thread, I would suggest that you also remove the non-technical ones. pps: We have had enough meta discussions about your general behavior, I don't think we need another one. $\endgroup$ – Kaveh Jun 5 '13 at 22:30

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.