Volume 9 (2013) Article 25 pp. 783-807
APPROX-RANDOM 2012 Special Issue
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes
by
Received: October 5, 2012
Revised: June 11, 2013
Published: October 2, 2013
Download article from ToC site:
[PDF (302K)]    [PS (1329K)]    [PS.GZ (340K)]
[Source ZIP]
Keywords: locally testable codes, affine-invariant codes, Reed-Muller codes, query complexity
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

$\newcommand{\F}{{\mathbb{F}}}$

Over a finite field $\F_q$, the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of central interest in complexity theory and property testing. The query complexity of this task is the minimal number of queries that a tester can make (minimum over all testers of the maximum number of queries over all random choices) while accepting all Reed-Muller codewords and rejecting words that are $\delta$-far from the code with probability $\Omega(\delta)$. (In this work we allow the constant in the $\Omega$ to depend on $d$.)

For codes over a prime field $\F_q$ the optimal query complexity is well-known and known to be $\Theta(q^{\lceil (d+1)/(q-1)\rceil})$, and the test consists of testing if $f$ is a degree-$d$ polynomial on a randomly chosen $(\lceil (d+1)/(q-1) \rceil)$-dimensional affine subspace of $\F_q^n$. If $q$ is not a prime, then the above quantity remains a lower bound, whereas the previously known upper bound grows to $O(q^{\lceil (d+1)/(q - q/p) \rceil})$ where $p$ is the characteristic of the field $\F_q$. In this work we give a new upper bound of $(c q)^{(d+1)/q }$ on the query complexity, where $c$ is a universal constant. Thus for every $p$ and sufficiently large $q$ this bound improves over the previously known bound by a polynomial factor.

In the process we also give new upper bounds on the “spanning weight” of the dual of the Reed-Muller code (which is also a Reed-Muller code). The spanning weight of a code is the smallest integer $w$ such that codewords of Hamming weight at most $w$ span the code. The main technical contribution of this work is the design of tests that test a function by not querying its value on an entire subspace of the space, but rather on a carefully chosen (algebraically nice) subset of the points from low-dimensional subspaces.

An earlier version of this paper appeared in the Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM'12), pages 639-650, 2012.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8758674,"math_prob":0.9935905,"size":2338,"snap":"2021-21-2021-25","text_gpt3_token_len":627,"char_repetition_ratio":0.1083976,"word_repetition_ratio":0.0,"special_character_ratio":0.27074423,"punctuation_ratio":0.06873614,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9988945,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-19T07:13:45Z\",\"WARC-Record-ID\":\"<urn:uuid:76d06fba-8bc5-4d41-90b2-361afe501cb4>\",\"Content-Length\":\"10606\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7c86bf11-e3a7-4ab3-8c83-1efb4050fa95>\",\"WARC-Concurrent-To\":\"<urn:uuid:a554b939-3faf-4ec5-881b-fd2bb14659eb>\",\"WARC-IP-Address\":\"195.111.2.4\",\"WARC-Target-URI\":\"https://toc.ilab.sztaki.hu/articles/v009a025/index.html\",\"WARC-Payload-Digest\":\"sha1:ZA5EEJHWL5H3GAHSYXJTADW5SRCI7XVI\",\"WARC-Block-Digest\":\"sha1:M6E2SHCCDSSCHUA33GX5X7QWE345KYQU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623487643703.56_warc_CC-MAIN-20210619051239-20210619081239-00329.warc.gz\"}"}