A new upper bound on the query complexity for testing generalized Reed-Muller codes

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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$.) 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. 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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A new upper bound on the query complexity for testing generalized Reed-Muller codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A new upper bound on the query complexity for testing generalized Reed-Muller codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new upper bound on the query complexity for testing generalized Reed-Muller codes will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-520707

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.