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 >>>

Derandomization techniques are used to show that at least one of the
following holds regarding the size of the counting complexity class
SPP.
1. SPP has p-measure 0.
2. PH is contained in SPP.
In other words, SPP is small by being a negligible subset of
exponential time or large ... more >>>

In constraint satisfaction problems over finite domains, some variables
can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the
instances. We show that the complexity of ... more >>>