English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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.

A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes