Improved low-degree testing and its applications

DOI10.1007/S00493-003-0025-0zbMath1101.68572OpenAlexW2610313478MaRDI QIDQ2494418

No author found.

Publication date: 27 June 2006

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-003-0025-0

zbMATH Keywords

low-degree testing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (37)

Quantum information and the PCP theorem ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs ⋮ Can we locally compute sparse connected subgraphs? ⋮ Low-degree test with polynomially small error ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Derandomized parallel repetition via structured PCPs ⋮ A survey on the structure of approximation classes ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Non-interactive proofs of proximity ⋮ Symmetric LDPC codes and local testing ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Symmetric LDPC Codes and Local Testing ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Local Property Reconstruction and Monotonicity ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ A note on the hardness results for the labeled perfect matching problems in bipartite graphs ⋮ Testing low-degree polynomials over prime fields ⋮ Completeness in approximation classes beyond APX ⋮ Unnamed Item ⋮ Approximation algorithm for stochastic set cover problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Local to Robust Testing via Agreement Testing ⋮ Characterizing Arithmetic Read-Once Formulae ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Unnamed Item ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ High-rate codes with sublinear-time decoding ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ A combination of testability and decodability by tensor products ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem

This page was built for publication: Improved low-degree testing and its applications