Solvability of a System of Bivariate Polynomial Equations over a Finite Field

Neeraj Kayal

July 2005

We study the following problem - given a finite field F and a set of polynomials p1(x), p2(x), ... , pm(x) in n variables x=(x1, ..., xn) over F, determine if the corresponding system of equations p1(x) = p2(x) = ... = pm(x) = 0 has a solution over F or not. We investigate the complexity of this problem when the number of variables is bounded. We show that for any fixed value of n, there is a deterministic algorithm for deciding solvability whose running time is bounded by a polynomial in d, m and log |F|. Previously, only a randomized polynomial-time algorithm was known (Huang and Wong, FOCS 1996). In particular, this result also leads to a deterministic algorithm for recognizing permutation functions, a problem which was previously known to be in ZPP (Ma and Gathen, STOC 1994) but not known to be in P.

Publication type | Inproceedings |

Published in | International Colloquium on Automata, Languages and Programming (ICALP) |

URL | http://dx.doi.org/10.1007/11523468_45 |

Pages | 551–562 |

Volume | 3580 |

Series | Lecture Notes in Computer Science |

ISBN | 3-540-27580-0 |

Publisher | Springer |

Awards | Best Student Paper Award |

- A super-polynomial lower bound for regular arithmetic formulas.
- Efficient Reconstruction of Random Multilinear Formulas
- Random Arithmetic Formulas can be Reconstructed Efficiently

> Publications > Solvability of a System of Bivariate Polynomial Equations over a Finite Field