Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
From MaRDI portal
Publication:3541815
DOI10.1007/978-3-540-85363-3_39zbMath1159.68006OpenAlexW2108860006MaRDI QIDQ3541815
Ning Xie, Tali Kaufman, Simon N. Litsyn
Publication date: 27 November 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_39
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Self-testing/correcting with applications to numerical problems
- Handbook of randomized computing. Vols. 1, 2
- Algebraic testing and weight distributions of codes.
- Improved non-approximability results
- Gowers uniformity, influence of variables, and PCPs
- Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
- Testing low-degree polynomials over prime fields
- Linearity testing in characteristic two
- Property testing and its connection to learning and approximation
- A PCP characterization of NP with optimal amortized query complexity
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Interactive proofs and the hardness of approximating cliques
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Simple analysis of graph tests for linearity and PCP
- Robust Characterizations of Polynomials with Applications to Program Testing
- Efficient probabilistically checkable proofs and applications to approximations
- Some optimal inapproximability results
- Derandomizing Homomorphism Testing in General Groups
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Linear-consistency testing.
