Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with randomizedalgorithm:
TR03-064 | 23rd June 2003
Vikraman Arvind, Piyush Kurur

Upper Bounds on the Complexity of some Galois Theory Problems

Given a polynomial f(X) with rational coefficients as input
we study the problem of (a) finding the order of the Galois group of
f(X), and (b) determining the Galois group of f(X) by finding a small
generator set. Assuming the generalized Riemann hypothesis, we prove
the following complexity bounds:

1. ... more >>>

ISSN 1433-8092 | Imprint