<p>(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/<a href="http://en.wikipedia.org/wiki/Nevanlinna_Prize" rel="nofollow noreferrer">award winning</a> 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.</p>

<p>Then in 1989 he seemed to somewhat dramatically switch thinking &amp; directions with the paper <a href="http://people.cs.uchicago.edu/~razborov/files/approx.pdf" rel="nofollow noreferrer">"on the method of approximations"</a> 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 <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="nofollow noreferrer">Natural Proofs</a> (eg in showing a barrier-type theorem on a technique instead of working to improve lower bounds).</p>

<p>However the ideas in the paper seem hard to follow, &amp; 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 <a href="http://intractability.princeton.edu/programs/workshops/barriers-workshop/" rel="nofollow noreferrer">much prominent consideration of in TCS</a>, 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).</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>[The bigger motivation here is that [barrier-type/"no-go"] theorems can be <a href="http://rjlipton.wordpress.com/2013/03/13/no-go-theorems/" rel="nofollow noreferrer">notoriously tricky</a> &amp; 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".]</p>

CC BY-SA 3.0
2013-11-22T19:50:40.463Z
What is the question here? Why don't you write Mr. Razborov and maybe he can clarify these concepts for you?
William Hird
CC BY-SA 3.0
2013-11-22T19:56:32.193Z
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.
Yuval Filmus
CC BY-SA 3.0
2013-11-22T21:19:06.327Z
See Mauricio Karchmer, "[On proving lower bounds for circuit size](http://dx.doi.org/10.1109/SCT.1993.336535)", 1993.
Kaveh
CC BY-SA 3.0
2013-11-23T22:13:38.947Z
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
vzn
CC BY-SA 3.0
2017-07-02T02:31:59.047Z
@YuvalFilmus: Is Krajicek's result you mention *in* that book, or just about the non-standard models method from that book? If the latter, can you point me to the reference?
Joshua Grochow
CC BY-SA 3.0
2017-07-02T07:18:00.623Z
@JoshuaGrochow The red book is the earlier book, which is essentially a compendium of papers.
Yuval Filmus
CC BY-SA 4.0
2019-01-14T23:00:53.800Z
Related: https://gowers.files.wordpress.com/2009/05/razborov2.pdf
TT_ stands with Russia
<cc.complexity-theory><circuit-complexity><lower-bounds><big-picture><circuits>
Sketch of Razborov's paper "On the method of approximations"
vzn
# Sketch of Razborov's paper "On the method of approximations"

(Asked by: username_0 on 2013-11-22)

(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/[award winning](http://en.wikipedia.org/wiki/Nevanlinna_Prize) 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"](http://people.cs.uchicago.edu/~razborov/files/approx.pdf) 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](http://en.wikipedia.org/wiki/Natural_proof) (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](http://intractability.princeton.edu/programs/workshops/barriers-workshop/), 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](http://rjlipton.wordpress.com/2013/03/13/no-go-theorems/) & 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".]

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, big-picture, circuits
> **Comments:**
> **username_1**: What is the question here? Why don't you write Mr. Razborov and maybe he can clarify these concepts for you?  
> **username_2**: 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.  
> **username_3**: See Mauricio Karchmer, "[On proving lower bounds for circuit size](http://dx.doi.org/10.1109/SCT.1993.336535)", 1993.  
> **username_0**: 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  
> **username_4**: @YuvalFilmus: Is Krajicek's result you mention *in* that book, or just about the non-standard models method from that book? If the latter, can you point me to the reference?  
> **username_2**: @JoshuaGrochow The red book is the earlier book, which is essentially a compendium of papers.  
> **username_5**: Related: https://gowers.files.wordpress.com/2009/05/razborov2.pdf  

---

## 0 answers

