Skip to main content
eScholarship
Open Access Publications from the University of California

Estimating the distance from testable affine-invariant properties

  • Author(s): Hatami, H
  • Lovett, S
  • et al.

Published Web Location

https://arxiv.org/pdf/1306.0649v1.pdf
No data is associated with this publication.
Abstract

Let P be an affine invariant property of multivariate functions over a constant size finite field. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over the binary field. Our test is simple: Take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013]. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item