abrodnik@watdragon.waterloo.edu (Andrej Brodnik (Andy)) (11/26/90)
Hi there, 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? Thanx in advance Andrej
alopeziz@maytag.waterloo.edu (Alex Lopez-Ortiz) (11/26/90)
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