Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TRUE COMPLEXITY:
Reports tagged with True complexity:
TR10-181 | 21st November 2010
Hamed Hatami, Shachar Lovett

#### Higher-order Fourier analysis of \$\mathbb{F}_p^n\$ and the complexity of systems of linear forms

In this article we are interested in the density of small linear structures (e.g. arithmetic progressions) in subsets \$A\$ of the group \$\mathbb{F}_p^n\$. It is possible to express these densities as certain analytic averages involving \$1_A\$, the indicator function of \$A\$. In the higher-order Fourier analytic approach, the function \$1_A\$ ... more >>>

TR14-040 | 30th March 2014
Hamed Hatami, Pooya Hatami, Shachar Lovett

#### General systems of linear forms: equidistribution and true complexity

Revisions: 1

The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate ... more >>>

ISSN 1433-8092 | Imprint