Improved low-degree testing and its applications
From MaRDI portal
Publication:2494418
Recommendations
Cited in
(49)- Non-interactive proofs of proximity
- Approximation algorithm for stochastic set cover problem
- Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- 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
- Approximation algorithms and hardness results for labeled connectivity problems
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Completeness in approximation classes beyond APX
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Characterizing arithmetic read-once formulae
- Sub-constant error low degree test of almost-linear size
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- Testing low-degree polynomials over prime fields
- Low Rate Is Insufficient for Local Testability
- A note on the hardness results for the labeled perfect matching problems in bipartite graphs
- Sub-Constant Error Low Degree Test of Almost-Linear Size
- scientific article; zbMATH DE number 1003235 (Why is no real title available?)
- scientific article; zbMATH DE number 1559564 (Why is no real title available?)
- A survey on the structure of approximation classes
- A hierarchy theorem for interactive proofs of proximity
- 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
- Constant-round interactive proofs for delegating computation
- On axis-parallel tests for tensor product codes
- From Local to Robust Testing via Agreement Testing
- From local to robust testing via agreement testing
- scientific article; zbMATH DE number 7250157 (Why is no real title available?)
- scientific article; zbMATH DE number 7250164 (Why is no real title available?)
- On axis-parallel tests for tensor product codes
- Symmetric LDPC codes and local testing
- A combination of testability and decodability by tensor products
- High-rate codes with sublinear-time decoding
- Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
- Derandomized parallel repetition via structured PCPs
- Towards a proof of the 2-to-1 games conjecture
- Property testing with online adversaries
- Derandomizing multivariate polynomial factoring for low degree factors
- Proximity gaps for Reed-Solomon codes
- Property testing with online adversaries
- Locally computing edge orientations
- An approximation algorithm for generalized connectivity problem on planar graphs
- Characterizations of locally testable linear- and affine-invariant families
- Quantum information and the PCP theorem
- Distribution-free connectivity testing for sparse graphs
This page was built for publication: Improved low-degree testing and its applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494418)
