Improved low-degree testing and its applications
From MaRDI portal
Publication:2494418
DOI10.1007/s00493-003-0025-0zbMath1101.68572OpenAlexW2610313478MaRDI QIDQ2494418
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
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
