Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

A source is compressible if we can efficiently compute short
descriptions of strings in the support and efficiently
recover the strings from the descriptions. In this paper, we
present a technique for proving lower bounds on
compressibility in an oracle setting, which yields the
following results:

- We ... more >>>

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