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

DOI10.1137/080715548zbMath1202.68178OpenAlexW2023194920MaRDI QIDQ3053157

Tali Kaufman, Ning Xie, Simon N. Litsyn

Publication date: 4 November 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080715548

zbMATH Keywords

Fourier analysiscoding theoryproperty testinglinearity test

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial codes (94B25)

Related Items (9)

Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions ⋮ Applying cube attacks to stream ciphers in realistic scenarios ⋮ Fault detection tests for stuck-at faults on parity counter inputs ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Short Locally Testable Codes and Proofs ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Unnamed Item ⋮ Direct Sum Testing

This page was built for publication: Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)