(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely through the "method of approximations", which has also been refined/simplified over the years by many other researchers.

Then in 1989 he seemed to somewhat dramatically switch thinking & directions with the paper "on the method of approximations" showing that, roughly, in the form considered, at best it can prove $\Omega(n^2)$ lower bounds on any circuit computing a hard function. In some key ways this also foreshadows his important paper on Natural Proofs (eg in showing a barrier-type theorem on a technique instead of working to improve lower bounds).

However the ideas in the paper seem hard to follow, & they seem to be rarely cited. There is not any mention of this idea in the later famous paper Natural Proofs which is also a broad survey of techniques in the field. So the 1989 paper refers to a key barrier, of which there is much prominent consideration of in TCS, but it's an apparently more obscure barrier. And it doesn't seem to be much tied in with the other well-known barriers, e.g., it doesn't seem like it fits in with the framework of Natural Proofs (which is meant to be a comprehensive-as-possible framework).

Looking for a proof sketch/outline of why the method of approximations can do no better than $\Omega(n^2)$ lower bounds, ideally tying it in with other known barriers/results.

[The bigger motivation here is that [barrier-type/"no-go"] theorems can be notoriously tricky & the idea that maybe some basic change on the idea of the method of approximations not envisioned by Razborov could achieve new lower bounds. Of course, understood, this is "a long shot".]

  • $\begingroup$ What is the question here? Why don't you write Mr. Razborov and maybe he can clarify these concepts for you? $\endgroup$ Commented Nov 22, 2013 at 19:50
  • 6
    $\begingroup$ I don't think Sasha would bother replying. Rather, one should take the effort to read and understand the paper. By the way, Jan Krajíček has a similar result about lower bounds in proof complexity using the "non-standard model" approach in his red book. $\endgroup$ Commented Nov 22, 2013 at 19:56
  • 3
    $\begingroup$ See Mauricio Karchmer, "On proving lower bounds for circuit size", 1993. $\endgroup$
    – Kaveh
    Commented Nov 22, 2013 at 21:19
  • 1
    $\begingroup$ the question is related to "is the approximation method a natural proof"? k. thx for the ref, havent read it yet, but am expecting its a refinement of the method (of which there are many) rather than detail on the barrier aspects. a summary of its relevance would help $\endgroup$
    – vzn
    Commented Nov 23, 2013 at 22:13
  • 1
    $\begingroup$ @JoshuaGrochow The red book is the earlier book, which is essentially a compendium of papers. $\endgroup$ Commented Jul 2, 2017 at 7:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.