Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-077 | 4th May 2015 08:00

Using higher-order Fourier analysis over general fields

RSS-Feed




TR15-077
Authors: Arnab Bhattacharyya, Abhishek Bhowmick
Publication: 4th May 2015 08:04
Downloads: 2003
Keywords: 


Abstract:

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

* For any fixed finite field \mathbb{K}, we show that the list decoding radius of the generalized Reed Muller code over \mathbb{K} equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when |\mathbb{K}|-1 divides the order of the code [GKZ08].

* For any fixed finite field \mathbb{K}, we give a polynomial time algorithm to decide whether a given polynomial P: \mathbb{K}^n \to \mathbb{K} can be decomposed as a particular composition of lesser degree polynomials. This had been previously established over prime fields [Bha14, BHT15].

* For any fixed finite field \mathbb{K}, we prove that all locally characterized affine-invariant properties of functions f: \mathbb{K}^n \to \mathbb{K} are testable with one-sided error. The same result was known when \mathbb{K} is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field \mathbb{F}, an affine-invariant property of functions f: \mathbb{K}^n \to \mathbb{F}, where \mathbb{K} is a growing field extension over \mathbb{F}, is testable if it is locally characterized by constraints of bounded weight.



ISSN 1433-8092 | Imprint