Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXACT AND APPROXIMATE COUNTING:
Reports tagged with exact and approximate counting:
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