15

In Razborov-Rudich's Natural Proofs 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"?

Kaveh
  • 21,577
  • 8
  • 82
  • 183

1 Answers1

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.

Karolina Sołtys
  • 1,354
  • 8
  • 13