<p>I'm not sure, but I think that the problem here is the fact that we don't have any strong assumptions about pseudorandom monotone function generators (at least none that I know of). The idea of the proof in Razborov-Rudich paper is as follows: </p>

<blockquote>
  <p><em>if there is a natural property of functions (i.e. an efficiently
  decidable property that holds for
  sufficiently large subset of functions
  and implies that the function needs
  big circuits), then it can be used to
  break pseudorandom function generators
  (which breaks also pseudorandom
  generators and one-way functions).</em></p>
</blockquote>

<p>If we were to restate the theorem in terms of monotone functions and monotone circuits, we would like it to say </p>

<blockquote>
  <p><em>if there is a natural property of <strong>monotone</strong> functions (i.e. an efficiently decidable property that
  holds for sufficiently large subset of
  <strong>monotone</strong> functions and implies that
  the function needs big <strong>monotone</strong>
  circuits), then it can be used to
  break pseudorandom function generators
  (which breaks also pseudorandom
  generators and one-way functions),</em></p>
</blockquote>

<p>but now the proof from the paper stops to work, because our pseudorandom generator outputs general functions, not necessarily monotone ones, and we cannot use our natural property to break it, because even a relatively large subset of monotone functions will not be large relative to general functions, for the set of monotone functions itself isn't large relative to the set of all functions ( <a href="http://en.wikipedia.org/wiki/Dedekind_number" rel="nofollow">http://en.wikipedia.org/wiki/Dedekind_number</a> ). We could define some pseudorandom monotone function generator and use the natural property to break it, but we probably would not have the equivalence between this generator and one-way functions, so the theorem would not be so interesting.  </p>

<p>Maybe this difficulty can be fixed (but I don't think it follows from the proof in the paper in a straightforward way) and maybe the problem with the monotone functions lies somewhere else. I would really like someone more experienced than me to confirm my answer or to show where I am wrong.</p>

CC BY-SA 2.5
2010-10-18T23:24:01.593Z
2010-10-19T15:59:15.120Z
2010-10-19T15:59:15.120Z
Karolina Sołtys
<p>In Razborov-Rudich's <a href="http://people.cs.uchicago.edu/%7Erazborov/files/int.ps" rel="nofollow">Natural Proofs</a> paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against <em>monotone</em> circuit models" and how they fit into the picture, there are the following sentences:</p>

<blockquote>
  <p>Here the issue is not constructivity - the properties used in these proofs are all feasible - but that there appears to be no good formal analogue of the largeness condition. In particular, no one has formulated <strong>a workable definition of a "random monotone function."</strong></p>
</blockquote>

<p>Isn't it easy to distinguish the outputs of a monotone function from a random string? 
Isn't the existence of strong lowerbounds telling us that there are no such things? </p>

<p>My question is:</p>

<blockquote>
  <p>What do they mean by <em>a workable definition of a "random monotone function"</em>? </p>
</blockquote>

CC BY-SA 3.0
2012-10-04T03:45:16.663Z
not exactly sure what they had in mind. there is actually a very natural way to define random monotone slice functions. also [rossman's paper on the monotone complexity of k-clique on random graphs](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526) uses erdos-renyi graphs which are actually quite natural also. keep in mind the natural proofs paper is over 1.5decade old now.
vzn
CC BY-SA 2.5
2010-10-31T21:03:40.153Z
A related question: http://cstheory.stackexchange.com/questions/1484/barriers-and-monotone-circuit-complexity
Gil Kalai
<cc.complexity-theory><circuit-complexity><randomness><natural-proofs><boolean-functions>
Random monotone function
Kaveh
# Random monotone function

(Asked by: username_0 on 2010-10-18)

In Razborov-Rudich's [Natural Proofs](http://people.cs.uchicago.edu/%7Erazborov/files/int.ps) paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against *monotone* circuit models" and how they fit into the picture, there are the following sentences:

> Here the issue is not constructivity - the properties used in these proofs are all feasible - but that there appears to be no good formal analogue of the largeness condition. In particular, no one has formulated **a workable definition of a "random monotone function."**

Isn't it easy to distinguish the outputs of a monotone function from a random string?
Isn't the existence of strong lowerbounds telling us that there are no such things?

My question is:

> What do they mean by *a workable definition of a "random monotone function"*?

**Tags:** cc.complexity-theory, circuit-complexity, randomness, natural-proofs, boolean-functions
> **Comments:**
> **username_2**: A related question: http://cstheory.stackexchange.com/questions/1484/barriers-and-monotone-circuit-complexity  
> **username_1**: not exactly sure what they had in mind. there is actually a very natural way to define random monotone slice functions. also [rossman's paper on the monotone complexity of k-clique on random graphs](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526) uses erdos-renyi graphs which are actually quite natural also. keep in mind the natural proofs paper is over 1.5decade old now.  

---

## 1 answers

### Answer by username_3 on 2010-10-18. Score: 12

I'm not sure, but I think that the problem here is the fact that we don't have any strong assumptions about pseudorandom monotone function generators (at least none that I know of). The idea of the proof in Razborov-Rudich paper is as follows:

> *if there is a natural property of functions (i.e. an efficiently
> decidable property that holds for
> sufficiently large subset of functions
> and implies that the function needs
> big circuits), then it can be used to
> break pseudorandom function generators
> (which breaks also pseudorandom
> generators and one-way functions).*

If we were to restate the theorem in terms of monotone functions and monotone circuits, we would like it to say

> *if there is a natural property of **monotone** functions (i.e. an efficiently decidable property that
> holds for sufficiently large subset of
> **monotone** functions and implies that
> the function needs big **monotone**
> circuits), then it can be used to
> break pseudorandom function generators
> (which breaks also pseudorandom
> generators and one-way functions),*

but now the proof from the paper stops to work, because our pseudorandom generator outputs general functions, not necessarily monotone ones, and we cannot use our natural property to break it, because even a relatively large subset of monotone functions will not be large relative to general functions, for the set of monotone functions itself isn't large relative to the set of all functions ( <http://en.wikipedia.org/wiki/Dedekind_number> ). We could define some pseudorandom monotone function generator and use the natural property to break it, but we probably would not have the equivalence between this generator and one-way functions, so the theorem would not be so interesting.

Maybe this difficulty can be fixed (but I don't think it follows from the proof in the paper in a straightforward way) and maybe the problem with the monotone functions lies somewhere else. I would really like someone more experienced than me to confirm my answer or to show where I am wrong.


---

