Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1993 Copyright 1993 Universität Bonn, Institut für Informatik, Abt. V
85106

Optimal Bounds for Testing Sparse Polynomials over F3
Kai Werter
[Download PostScript] [Download PDF]

We show that the size of a minimal zero test set for $t$-sparse $n$-variate polynomials over ${\mathbb F}_3$ is of order $(2n)^{\lfloor \log t \rfloor} (1 + \Theta(1/n))$, thereby significantly improving the best previously known lower bound ([5]).

Last Change: 09/01/04 at 07:48:30
 English
Universität Bonn -> Institut für Informatik -> Abteilung V