scientific article; zbMATH DE number 1559564

MaRDI QIDQ4527016zbMATH OpenFDO

Authors Sanjeev Arora, Madhu Sudan

Publication date 28 February 2001

zbMATH Keywords

NP languages

Mathematics Subject Classification ID

Recommendations

• Improved low-degree testing and its applications
• scientific article; zbMATH DE number 1559563
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Sub-constant error low degree test of almost-linear size
• Robust Characterizations of Polynomials with Applications to Program Testing

Cited in

(31)

• Testing algebraic geometric codes
• On the minimum label spanning tree problem
• Interactive and probabilistic proof-checking
• Approximation algorithms for terrain guarding.
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Improved approximation algorithms for capacitated facility location problems
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• Algebraic testing and weight distributions of codes.
• On the hardness of the minimum height decision tree problem
• On membership comparable sets
• Noisy interpolation of sparse polynomials in finite fields
• Improved low-degree testing and its applications
• Three-player entangled XOR games are NP-hard to approximate
• Sub-constant error low degree test of almost-linear size
• Self-correctors for cryptographic modules
• 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 1559563 (Why is no real title available?)
• Cube vs. Cube Low Degree Test.
• Self-correcting for function fields of finite transcendental degree
• Simple analysis of graph tests for linearity and PCP
• Robust Characterizations of Polynomials with Applications to Program Testing
• scientific article; zbMATH DE number 1418270 (Why is no real title available?)
• Shorter arithmetization of nondeterministic computations
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Pseudorandom generators without the XOR lemma
• Approximate evaluations of characteristic polynomials of Boolean functions
• PCP characterizations of NP: toward a polynomially-small error-probability
• On the degree of polynomials computing square roots p
• Coboundary and cosystolic expansion without dependence on dimension or degree
• Budget constrained minimum cost connected medians

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4527016)