Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!maverick.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cs.indiana.edu!maytag!alopeziz
From: alopeziz@maytag.waterloo.edu (Alex Lopez-Ortiz)
Newsgroups: comp.theory
Subject: Re: Alexander Razborov
Keywords: P versus NP
Message-ID: <1990Nov25.231205.25197@maytag.waterloo.edu>
Date: 25 Nov 90 23:12:05 GMT
References: <1990Nov25.223230.21366@watdragon.waterloo.edu>
Organization: University of Waterloo
Lines: 24

Andrej Brodnik (Andy) writes:
>
>in the AMS Notices I read that A.Razborov got a Nevanlinna Prize for his
>proof that the number of and- and or- gates required to compute certain
>natural monotone Boolean functions grows faster than any polynomial in the
>number of arguments. I'd like to get the reference to this proof (in English
>or Russian). I am sure that there are a lot of you who read it. Can you help
>me, please?
>

In Russian:

A.A. Razborov, Lower Bounds for the size of bounded depth networks
over a complete basis with logical addition, Matematischi Zametki, 41, 1981,
pp. 598-607.

In English:

Mathematical Notes of the Academy of Sciences of the USSR, 41, 1987, 
pp. 333-338.



Alex