Computational Complexity - Bachelor's and Master's Theses
Christian Engels: Polynomial Identity Testing
Master's Thesis, 2010.
Advisor: Prof. Dr. Markus Bläser
Polynomial identity test is a very important problem as many results rely on efficient tests. In this hesis we consider the identity test problem of multivariate polynomials in the blackbox model. We present an efficient deterministic algorithm with running time O(m3 n2). This running time is independent of the degree.
We will also present a randomized algorithm with polynomial running time in log m, n and an error parameter . This algorithm needs O(log2 m + log2 m + log2 1/ε) random bits. As third algorithm we show an algorithm which needs O(log 1/ε (log m + log n + log 1/ε)) random bits. This is near the lower bound of randomness needed in the blackbox model. Sadly this algorithm is not efficient as its running time is polynomial in n, m and log 1/ε . However, the techniques used for this algorithm could lead to new improvements in this field.
Both randomized algorithms use a new technique. Instead of the normal reduction from multivariate polynomials to univariate polynomials we will reduce a multivariate polynomial to a multivariate polynomial with few vari- ables. The number of variables will, in our case, depend on the number of monomials. We will also stress in this thesis the notion of an identity test reduction. An identity test reduction will be a reduction we can use to de- crease the number of variables in a polynomial. The idea is not new, as many algorithm already use reductions. However, the viewpoint is new. We will formally define what properties a reduction has to fulfill in this thesis.
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals.
Symposium on Theoretical Aspects of Computer Science (STACS), 9:555-566, 2011.