An Automatic Inequality Prover and Instance Optimal Identity Testing

By Gregory Valiant, Paul Valiant. 2014

242 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “3The sample complexity for a fixed q has been studied under the “instanceoptimal” setting (see [12], [50]): while the question is not fully resolved, nearly tight upper and lower bounds are known.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, methodology): “In this appendix, we explain how the existence of a distributed protocol for uniformity testing implies the existence of one for identity testing with roughly the same parameters, and further even implies one for identity testing in the massively parameterized sense16 (“instance-optimal” in the voca”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “…well understood in a variety of settings: for many properties of interest there exist sample-efficient testers Paninski (2008); Chan et al. (2014); Valiant and Valiant (2014); Diakonikolas et al. (2015a); Acharya et al. (2015); Canonne et al. (2016); Diakonikolas and Kane (2016); Diakonikolas et…”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “After two decades of study, this “worst-case” regime is well-understood: for many properties of interest there exist sample-optimal testers (matched by information-theoretic lower bounds) [24, 10, 9, 26, 15, 14, 2, 13, 6, 11, 8, 16].”
Inference Under Information Constraints III: Local Privacy Constraints (2021, methodology): “3The sample complexity for a fixed q, without privacy constraints, has been studied under the “instance-optimal” setting (see [18], [46]); and under local privacy constraints by [17].”
Minimax optimal conditional independence testing (2020, methodology): “The Poissonization trick has been used often in the recent hypothesis testing literature [5, 10, 35].”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “In a recent and influential work, Valiant and Valiant [55] showed that the sample complexity of the aforementioned problem is closely related to the 2/3-quasinorm of p.”
Competitive Distribution Estimation: Why is Good-Turing Good (2015, methodology): “In data compression it is called twice-redundancy [15, 16, 17, 18], while in statistics it is often called adaptive or local minmax [19, 20, 21, 22, 23], and recently in property testing it is referred as competitive [24, 25, 26] or instance-by-instance [27].”
Instance optimal learning of discrete distributions (2016, unknown): “…of p , deciding whether a set of samples was drawn from p versus some distribution with (cid:96) 1 distance at least (cid:15) from p —recent work gave an algorithm and an explicit function of p and (cid:15) that represents the precise sample complexity of this task, for each distribution p [35].”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, background): “…there exist sample-optimal testers (matched by information-theoretic lower bounds) (Paninski, 2008; Daskalakis et al., 2013; Chan et al., 2014; Valiant & Valiant, 2014; Diakonikolas et al., 2015b;c; Acharya et al., 2015; Diakonikolas & Kane, 2016; Canonne et al., 2016; Diakonikolas et al.,…”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “This line of work culminated in efficient and sample-optimal testing algorithms (Paninski, 2008; Valiant and Valiant, 2017; Acharya et al., 2015; Goldreich, 2016; Diakonikolas et al., 2018); we refer the reader to the surveys (Rubinfeld, 2012; Canonne, 2015; Balakrishnan and Wasserman, 2018), as wel”
Property Testing For Differential Privacy (2018, background): “There is a large body of work exploring lower bounds and algorithmic upper bounds for tolerant testing using standard distances (TV, KL, χ 2 , etc.) with both a = 0 and a > 0 (Daskalakis et al., 2018, Paninski, 2008, Batu et al., 2013, Acharya et al., 2015, Valiant and Valiant, 2014).”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “It was recently shown that O( √ k α2 ) [49, 56, 26, 2] samples are necessary and sufficient for identity testing without privacy constraints.”
Test without Trust: Optimal Locally Private Distribution Testing (2018, methodology): “We now propose our testing mechanism based on Rappor, which, in essence, uses a privatized version of a χ2-type statistic of [12, 4, 32].”