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/

Zendy Plus

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

Zendy Tools

Zendy Open

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by REJ(epsilon) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549–595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for REJ(epsilon) were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781–1795]. They used Fourier analysis to show that REJ(epsilon)[geq]epsilon for every 0[leq]epsilon [leq]1/2. They also conjectured that this bound might not be tight for epsilon's which are close to 1/2. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of REJ(epsilon)[geq]epsilon by an additive constant that depends only on epsilon: REJ(epsilon)[geq] epsilon+min{1376epsilon[superscript 3](1-2epsilon)[superscript 12],[frac 1 over 4epsilon(1-2epsilon[superscript 4]}, for every 0[leq]epsilon[leq]1/2. Our analysis is based on a relationship between REJ(epsilon) and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution

Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)