Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AFFINE INVARIANT PROPERTIES:
Reports tagged with affine invariant properties:
TR11-029 | 6th March 2011
Hamed Hatami, Shachar Lovett

Revisions: 1

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>> TR13-087 | 4th June 2013 Hamed Hatami, Shachar Lovett #### Estimating the distance from testable affine-invariant properties Let$\cal{P}$be an affine invariant property of functions$\mathbb{F}_p^n \to [R]$for fixed$p$and$R$. We show that if$\cal{P}$is locally testable with a constant number of queries, then one can estimate the distance of a function$f$from$\cal{P}\$ with a constant number of queries. This ... more >>>

ISSN 1433-8092 | Imprint