On Testing Expansion in Bounded-Degree Graphs

By Oded Goldreich, Dana Ron. 2000

348 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

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

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, methodology): “Most pertinent to our work is uniformity testing [GR00, Pan08, DGPP17], the prototypical distribution testing problem with applications to many other property testing problems [BKR04, DKN15, Gol16, CDGR17].”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, methodology): “Most pertinent to our work is uniformity testing [30], [41], [22], the prototypical distribution testing problem for which the sample complexity was established to be Θ( √ k/ε2) in [41], [46]; as well as identity testing, shown to have order-wise similar sample complexity [11], [5], [46], [24], [29]”
Communication and Memory Efficient Testing of Discrete Distributions (2019, methodology): “We remind the reader that testing uniformity based on the number of pairwise collisions is the oldest algorithm in distribution testing Goldreich and Ron (2000), which is now known to be sample-optimal in the centralized setting Diakonikolas et al. (2016).”
Distributed Uniformity Testing (2018, background): “It was first considered implicitly in [13, 17], as part of a tester that estimated the expansion of a graph by testing whether the distribution of a short random walk in the graph is uniform, or far from uniform.”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “Starting with [32, 10, 8], this includes the testing of symmetric properties [45, 54, 51, 52], of structured families [11, 35, 3, 17, 4, 20, 19], as well as testing under some assumption on the unknown instance [47, 24, 27, 26].”
Pan-Private Uniformity Testing (2019, background): “In uniformity testing, a line of work [28, 39, 40] has established that uniformity testing (without privacy) has sample complexity Θ (√ k α(2) )”
Optimal Algorithms for Testing Closeness of Discrete Distributions (2013, methodology): “See Proposition 3.1 and the discussion following it for analysis of our algo-rithm as an estimator for (cid:96) 2 distance.”
Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates (2017, background): “Motivated by connections to property testing [26], there is also a recent literature developing in computer science; see [3, 10, 13, 30].”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, methodology): “To obtain a uniformity tester that works for the non-sparse regime, we develop our second algorithm: a private version of the collisions-based tester of (Goldreich & Ron, 2000).”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, methodology): “To be able to handle the entire range of parameters, we develop a private version of the collisions-based tester from [20].”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “In the past two decades there has been a lot of work from the computer science, information theory, and statistics community on various distribution testing problems in the non-asymptotic (small-sample) regime, where the domain size k could be potentially larger thanm (See [13, 12, 37, 10, 49, 4, 3,”
Taming big probability distributions (2012, methodology): “By Ronitt Rubinfeld DOI: 10.1145/2331042.2331052 T hese days, it seems that we are constantly bombarded by discussions of big data and our lack of tools for processing such vast quantities of information.”
Two Party Distribution Testing: Communication and Security (2018, background): “Distribution property testing is a sub-area of statistical hypothesis testing, which has enjoyed continuously growing interest in the theoretical computer science community, especially since the 2000 papers [GR00, BFR + 00].”
Introduction to Property Testing (2017, background): “Using random walks is most natural in the context of testing Expansion [149], but the analysis of such testers was successfully completed only in later works [175, 214].”
Testing that distributions are close (2000, methodology): “Goldreich and Ron [18] give methods allowing testing that the L2-distance between a given distribution and the uniform distribution is small in time O( √ n).”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, methodology): “Motived by a connection to testing the expansion of graphs, Goldreich and Ron [9] first considered the problem of distinguishing whether a set of samples was drawn from the uniform distribution of support n versus from a distribution that is least far from the uniform distribution, with the tight bo”