Source author record

Thái Hoàng Lê

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.NT math.CO math.GR

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Additive bases in groups

In this paper, we study the problem of removing an element from an additive basis in a general abelian group. We introduce analogues of the classical functions $X$ , $S$ and $E$ (defined in the case of the integers) and obtain bounds on them. Our estimates on the functions $S_G$ and $E_G$ are valid for general abelian groups $G$ while in the case of $X_G$ we show that distinct types of behaviours may occur depending on the group $G$ .

preprint2014arXiv

Deterministic Extractors for Additive Sources

We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both $\mathbb{Z}_p$ and $\mathbb{Z}_p^n$ , for large prime $p$ , although our results over $\mathbb{Z}_p^n$ require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over $\mathbb{Z}_p^n$ require the list-decodability condition. We further explore special cases of additive sources. We improve previous constructions of line sources (affine sources of dimension 1), requiring a field of size linear in $n$ , rather than $Ω(n^2)$ by Gabizon and Raz. This beats the non-explicit bound of $Θ(n \log n)$ obtained by the probabilistic method. We then generalize this result to APs and GAPs.

preprint2014arXiv

On primitive elements in finite fields of low characteristic

We discuss the problem of constructing a small subset of a finite field containing primitive elements of the field. Given a finite field, $\mathbb{F}_{q^n}$ , small $q$ and large $n$ , we show that the set of all low degree polynomials contains the expected number of primitive elements. The main theorem we prove is a bound for character sums over short intervals in function fields. Our result is unconditional and slightly better than what is known (conditionally under GRH) in the integer case and might be of independent interest.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.