5
$\begingroup$

(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".]

$\endgroup$
  • $\begingroup$ What is the question here? Why don't you write Mr. Razborov and maybe he can clarify these concepts for you? $\endgroup$ – William Hird Nov 22 '13 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$ – Yuval Filmus Nov 22 '13 at 19:56
  • 3
    $\begingroup$ See Mauricio Karchmer, "On proving lower bounds for circuit size", 1993. $\endgroup$ – Kaveh Nov 22 '13 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 Nov 23 '13 at 22:13
  • 1
    $\begingroup$ @JoshuaGrochow The red book is the earlier book, which is essentially a compendium of papers. $\endgroup$ – Yuval Filmus Jul 2 '17 at 7:18

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.