Computational Complexity - Bachelor's and Master's Theses
Moritz Hardt: Testing Polynomial Identities with Fewer Random Bits
Master's Thesis, 2007.
Advisor: Prof. Dr. Markus Bläser
- We give a simple deterministic identity test for sparse polynomials represented by arithmetic circuits. The runtime of this algorithm is polynomial in s and m, where s is the size of the circuit and m the number of monomials of the given polynomial. In particular, the runtime is logarithmic in the degree of the polynomial. Our technique applies to arbitrary polynomial rings. We can improve the runtime of our algorithm significantly with O(log ms) random bits.
- We give the first asymptotically optimal blackbox identity tests for multivariate polynomials. Specifically, our algorithms use (1+o(1))OPT random bits for dense polynomials as well as broad classes of sparse polynomials. The excess in random bits decreases in the inverse of a polynomial. Furthermore, the runtime of our algorithms is logarithmic in the degree of the input polynomial. The basis for our result results are several novel constructions of hitting set generators.
- We study the problem of finding short certificates to distinguish a given integer polynomial with bounded coefficients from the zero polynomial. For a 1 - o(1) fraction of the polynomials we exhibit certificates of size doubly logarithmic in the largest coefficient and logarithmic in the degree of the polynomial. We can find these certificates efficiently without any random bits when given only blackbox access to the polynomial. Our technique is a bijection between multivariate polynomials and integers combined with classical results on the average number of distinct prime divisors of an integer.
Asymptotically Optimal Hitting Sets Against Polynomials.
International Colloquium on Automata, Languages and Programming (ICALP) in Lecture Notes in Computer Science 5125:345-356. Springer, 2008.
Deterministically Testing Sparse Polynomial Identities of Unbounded Degree.
Information Processing Letters, 109(3):187-192, 2009.