From Bruno.Salvy@inria.fr Thu Aug 22 04:32:06 1996
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by euclid.math.temple.edu (8.7.4/8.6.12) with ESMTP id EAA04649 for <zeilberg@euclid.math.temple.edu>; Thu, 22 Aug 1996 04:32:05 -0400 (EDT)
Posted-Date: Thu, 22 Aug 1996 04:32:05 -0400 (EDT)
Received-Date: Thu, 22 Aug 1996 04:32:05 -0400 (EDT)
Received: from pommard.inria.fr (pommard.inria.fr [128.93.8.148]) by concorde.inria.fr (8.7.1/8.7.1) with ESMTP id KAA03075 for <zeilberg@euclid.math.temple.edu>; Thu, 22 Aug 1996 10:31:52 +0200 (MET DST)
Received: (from salvy@localhost) by pommard.inria.fr (8.6.10/8.6.6) id KAA29222; Thu, 22 Aug 1996 10:31:51 +0200
Date: Thu, 22 Aug 1996 10:31:51 +0200
Message-Id: <199608220831.KAA29222@pommard.inria.fr>
From: Bruno.Salvy@inria.fr (Bruno Salvy)
To: zeilberg@euclid.math.temple.edu
Subject: The Andrews Syndrome
Status: RO


Dear Doron, 

I've just read your nice paper on curing the Andrews syndrome. It is
not clear to me that you are aware of the body of litterature
concerned with algorithms and complexity estimates for proving that a
polynomial is 0 by plugging in values. So I thought you might be
interested in having a few of those. 

                                             Bruno.


M. Giusti, J. Heintz and J. Sabia: On the efficiency of effective
Nullstellens\"atze, Computational Complexity 3 (1993), 56--95.

J. Heintz and C. P. Schnorr: Testing polynomials which are easy to
compute. Proc. 12th Ann. ACM Symp. on Computing (1980) 262--268.

There are also numerous papers on probabilistic identity tests.