Robust Characterizations of Polynomials with Applications to Program Testing

By Ronitt Rubinfeld, Madhu Sudan. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, background): “First introduced by Batu et al. [BFR + 00] and Goldreich, Goldwasser, and Ron [GGR98], distribution testing is a branch of property testing [RS96, GGR98], a ﬁeld of theoretical computer science focusing on “ultra-fast” (sublinear-time) algorithms for decision problems.”
Robust pcps of proximity, shorter pcps and applications to coding (2004, background): “Such a gap problem corresponds to the notion of approximation in property testing [26, 15].”
Property Testing in Bounded Degree Graphs (2002, background): “The latter approach underlines all work on testing low-degree polynomials [7, 21, 13, 4, 3, 11, 1] and codes [3, 1, 5, 16], and its relevance to the construction of probabilistically checkable proofs [4, 3, 11, 2, 1] is well known.”
On exchangeable random variables and the statistics of large graphs and hypergraphs (2008, background): “The basic questions of property testing have attracted considerable attention during the last ten years, and we shall discuss them only very incompletely here; see, for example, the papers of Rubinfeld and Sudan [57], Alon and Shapira [8] and Alon, Fischer, Krivelevich and Szegedy [6], and the furth”
Short PCPs verifiable in polylogarithmic time (2005, background): “gold [DR04], suggests a more elegant characterization to capture the power of ecient verifiers — one that is similar to work in property testing [GGR98, RS96 ].”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “Distribution testing, as ﬁrst explicitly introduced in [9], is a branch of property testing [48, 31] concerned with the study of sublinear algorithms for making approximate decisions regarding probability distributions over massive domains.”
A quantitative Arrow theorem (2009, background): “shion to the distance from dictator or to other functions in F3(n). As noted in [10], there is an interesting connection between quantitative Arrow statements and the concept of testing introduced in [18, 9] which was studied and used extensively since. Roughly speaking a property of functions is te”