Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1993 Copyright 1993 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V