The DOI matches its Crossref record; 56 of the 59 references it cites were found in a registry or an index.
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction
Open accessAbstract
Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels W, which can be instantiated to capture, among others, both the communication and privacy-constrained settings. The referee uses the players' messages to solve an inference problem on the unknown distribution that generated the samples. We derive lower bounds for the sample complexity of learning and testing discrete distributions in this informationconstrained setting. Underlying our bounds is a characterization of the contraction in chi-square distance between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both publicand privatecoin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“This can enable differentially private protocols with far smaller error than what is possible in the local model, while relying on weaker trust assumptions than in the central model, e.g., [120, 178, 45, 201, 204, 200, 202, 203, 110].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [178]
Experimental — accuracy not yet measuredThe check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“shuffling models of differential privacy can use broader classes of local randomizers, and can even select these local randomizers adaptively [178]”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [178]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542 · cited 1×
“[21], [35], [9], [19]): For ρ > 0, W (y | x1) W (y | x2) ≤ e, ∀x1, x2 ∈ [k],∀y ∈ {0, 1}∗.”
A Mathematical Introduction to Compressive Sensing
Foucart, S., & Rauhut, H. (2013) · Applied and Numerical Harmonic Analysis · doi:10.1007/978-0-8176-4948-7 · Cited by 2,548 · cited 1×
“where the first inequality is by the decoupling inequality E e T Mθ ≤ E e T Mθ (used in [27] as well) and the second uses sub-Gaussianity once again.”
MethodConcentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768 · cited 1×
“…where V 1 , . . . , V k/ 2 are independent and distributed uniformly over {− 1 , +1 , so that we can bound the decoupled chi-square fluctuation using Hoeffding’s Lemma ( cf. [12]) as Thus, Lemma III.6 implies that Ω( √ k/ε 2 ) samples are needed for testing (in particular, for uniformity testing).”
MethodInformation Theory: Coding Theorems for Discrete Memoryless Systems
Csiszár, I., & Körner, J. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921889 · Cited by 1,308
Distributed detection with multiple sensors I. Fundamentals
Viswanathan, R., & Varshney, P. K. (1997) · Proceedings of the IEEE · doi:10.1109/5.554208 · Cited by 1,066 · cited 1×
“Interestingly, such setups have received a lot of attention in the sensor network literature where a fusion center combines local decisions using simple rules such as majority; see [51] for an early review.”
BackgroundLocal Privacy and Statistical Minimax Rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.53 · Cited by 954 · cited 3×
“Distribution learning under LDP constraints has been studied in [4], [21], [37], [52], [56], all providing sample-optimal schemes with different merits.”
BackgroundDistributed detection with multiple sensors I. Advanced topics
Blum, R. S., Kassam, S. A., & Poor, H. V. (1997) · Proceedings of the IEEE · doi:10.1109/5.554209 · Cited by 727
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Yu, B. (1997) · Festschrift for Lucien Le Cam · doi:10.1007/978-1-4612-1880-7_29 · Cited by 309 · cited 1×
“We can relate the accuracy of a probability estimate to the probability of error for the multiple hypothesis testing problem with hypotheses given by p z using the standard Fano’s method ( cf. [55]).”
MethodOn the Choice of the Number of Class Intervals in the Application of the Chi Square Test
Mann, H. B., & Wald, A. (1942) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177731569 · Cited by 275 · cited 2×
“[39]), with particular interest on the large-support and small-sample case where the usual normal approximations of statistics do not apply (cf.”
Background
Research works printed but not linked: 6
- ingster, 1986, A minimax test of nonparametric hypotheses on the density of a distribution in $L_{p}$ metrics, Teor Veroyatnost i Primenen, 31, 384
- han, 2018, Geometric lower bounds for distributed parameter estimation under communication constraints, Proc 31st Conf Learn Theory COLT, 75, 3163
- acharya, 2019, Inference under information constraints III: Local privacy constraints, arXiv 2007 10979
- cover, 2006, Elements of Information Theory
- tsitsiklis, 1993, Decentralized detection, Advances in Statistical Signal Processing, 2, 297
- pollard, 2003, Asymptopia
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Communication-Efficient Federated Learning via Optimal Client Sampling
Ribero, M., & Vikalo, H. (2020) · LatinX in AI at International Conference on Machine Learning (LXAI) · doi:10.52591/lxai2020071310 · Cited by 131
Breaking the Communication-Privacy-Accuracy Trilemma
Chen, W., Kairouz, P., & Özgür, A. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3218772 · Cited by 94
“If we further assume X are drawn from some discrete distribution p, then the problem falls into distribution estimation under local differential privacy [9], [13], [34], [36], [42], [43], [44], [45], [46] and limited communication [11], [25], [45], [46], [47], [48], [49], [50].”
BackgroundGeometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints
Han, Y., Özgür, A., & Weissman, T. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3108952 · Cited by 73
Communication-Efficient Federated Learning With Binary Neural Networks
Yang, Y., Zhang, Z., & Yang, Q. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3118415 · Cited by 63
“Therefore, many research efforts have been made to theoretically characterize the fundamental trade-offs between the performance of the trained models and the communication costs of the FL framework[5][6][7][8][9].”
Topics and Techniques in Distribution Testing: A Biased but Representative Sample
Canonne, C. L. (2022) · Foundations and Trends® in Communications and Information Theory · doi:10.1561/0100000114 · Cited by 106
Self-citationOn Sparse Linear Regression in the Local Differential Privacy Model
Wang, D., & Xu, J. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3040406 · Cited by 49
“[35] proved lower bounds for various testing and estimation problems under local differential privacy using a notion of chi-squared contractions based on Le Cam’s method and Fano’s inequality.”
MethodInference Under Information Constraints II: Communication Constraints and Shared Randomness
Acharya, J., Canonne, C. L., & Tyagi, H. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3028439 · Cited by 48
Self-citationUnified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints
Acharya, J., Canonne, C. L., Sun, Z., & Tyagi, H. (2023) · neural information processing systems · doi:10.52202/075280-2226 · Cited by 65
Self-citationMinimax Estimation of Divergences Between Discrete Distributions
Han, Y., Jiao, J., & Weissman, T. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.3041036 · Cited by 41
“Besides the KL divergence, the Hellinger distance [11] plays key roles in the classical asymptotic theory [12], [13] and pairwise tests [14], [15] in statistics, and the Pearson χ2-divergence is an important measure in goodness-of-fit tests [16], [17].”
BackgroundCommunication Complexity in Locally Private Distribution Estimation and Heavy HittersPreprint
Acharya, J., & Sun, Z. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.11888 · Cited by 62
“This `1 risk is optimal over all protocols, even while allowing public-coins [26, 32, 24].”
BackgroundSelf-citationLower bounds for learning distributions under communication constraints via Fisher information
Barnes, L. P., Han, Y., & Ozgur, A. (2019) · arXiv · doi:10.48550/arxiv.1902.02890 · Cited by 40
Interactive Inference Under Information Constraints
Acharya, J., Canonne, C. L., Liu, Y., Sun, Z., & Tyagi, H. (2021) · IEEE Transactions on Information Theory · doi:10.1109/isit45174.2021.9518069 · Cited by 55
Self-citationInference Under Information Constraints III: Local Privacy Constraints
Acharya, J., Canonne, C. L., Freitag, C., Sun, Z., & Tyagi, H. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3053569 · Cited by 50
“Furthermore, this is asymptotically optimal from the result of [2], and the mechanism only uses one bit of communication from each player, making it as communication-efficient as possible.”
BackgroundMethodInfluentialSelf-citationDistributed Learning with Sublinear CommunicationPreprint
Acharya, J., De, C., Foster, D. J., & Sridharan, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.11259 · Cited by 31
“…correlations, and independence testing (Shamir, 2014; Duchi et al., 2014; Garg et al., 2014; Steinhardt and Duchi, 2015; Braverman et al., 2016; Steinhardt et al., 2016; Acharya et al., 2018a,b; Raz, 2018; Han et al., 2018; Sahasranand and Tyagi, 2018; Dagan and Shamir, 2018; Dagan et al., 2019).”
BackgroundSelf-citationLocal Differential Privacy Is Equivalent to Contraction of an $f$-Divergence
Asoodeh, S., Aliakbarpour, M., & Calmon, F. P. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517999 · Cited by 44
Ni, Q., Li, X., Chen, Z., Zhao, Z., & Lai, L. L. (2023) · IEEE Transactions on Industrial Electronics · doi:10.1109/tie.2023.3260356 · Cited by 27
“Therefore, the threshold value can be obtained by approximate chi-square distribution [25].”
BackgroundBAFFLE: A Baseline of Backpropagation-Free Federated Learning
Feng, H., Pang, T., Du, C., Chen, W., Yan, S.-C., & Lin, M. (2023) · European Conference on Computer Vision · doi:10.1007/978-3-031-73226-3_6 · Cited by 17
“[ 47] introduces sparsification and quantization to reduce the communication cost, where several theoretical works investigate the optimal trade-off between the communication cost and model accuracy [2,7,15,30,102].”
BackgroundLimits on Gradient Compression for Stochastic Optimization
Mayekar, P., & Tyagi, H. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174075 · Cited by 28
“In the [1, 2) range, we divide the vector into two parts with small and large coordinates.”
BackgroundMethodSelf-citationRATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization
Mayekar, P., & Tyagi, H. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3058663 · Cited by 33
Self-citationAn invitation to the sample complexity of quantum hypothesis testing
Cheng, H., Datta, N., Liu, N., Nuradha, T., Salzmann, R., & Wilde, M. M. (2025) · npj Quantum Information · doi:10.1038/s41534-025-00980-8 · Cited by 32
Contraction of Locally Differentially Private Mechanisms
Asoodeh, S., & Zhang, H. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3397305 · Cited by 30
“…formal introduction [36], [45], LDP has been extensively incorporated into statistical problems, e.g., locally private mean estimation problem [2], [3], [4], [10], [14], [15], [20], [26], [32], [33], [34], [39], [40], [41], [51], [54], and locally private distribution estimation problem [2], [7],…”
BackgroundBerrett, T. B., & Butucea, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.12601 · Cited by 23
“The problem has also been considered in the non-local differentially private setting [Wang et al., 2015, Gaboardi et al., 2016, Cai et al., 2017, Aliakbarpour et al., 2018, Acharya et al., 2018].”
BackgroundFisher Information for Distributed Estimation under a Blackboard Communication Protocol
Barnes, L. P., Han, Y., & Özgür, A. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849821 · Cited by 18
Communication Efficient Federated Learning
Jin, Y., Zhu, H., Xu, J., & Chen, Y. (2022) · Machine learning · doi:10.1007/978-981-19-7083-2_2 · Cited by 17
Pensia, A., Jog, V., & Loh, P. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3334024 · Cited by 16
“…inference has been extensively studied under constraints such as memory [2], [3], [4], [5], [6], [7], privacy [8], [9], [10], [11], [12], communication [13], [14], [15], [16], or a combination thereof [17], [18], [19], [20], [21], [22], typically designed to model physical or economic constraints.”
BackgroundSimple Binary Hypothesis Testing Under Local Differential Privacy and Communication Constraints
Pensia, A., Asadi, A. R., Jog, V., & Loh, P. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3461361 · Cited by 15
“…this line of research considers problems of interest such as distribution estimation [19], [20], [21], [22], identity or independence testing [23], [24], [25], and parameter estimation [13], [26], [27], [28], [29], [30], [31], and identifies minimax-optimal bounds on the error or sample…”
Communication and Memory Efficient Testing of Discrete DistributionsPreprint
Diakonikolas, I., Gouleakis, T., Kane, D. M., & Karingula, S. R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.04709 · Cited by 14
Cai, T., Chakraborty, A., & Vuursteen, L. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2406.06749 · Cited by 14
“The observation that shared randomness can improve performance in our problem has been noted in other contexts involving distributed privacy and communication constraints, see for example [4, 5, 3, 76, 77].”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-FitPreprint
Acharya, J., Canonne, C. L., Han, Y., Sun, Z., & Tyagi, H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.08743 · Cited by 13
Self-citationLocal Differential Privacy Is Equivalent to Contraction of $E_γ$-DivergencePreprint
Asoodeh, S., Aliakbarpour, M., & Calmon, F. P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.01258 · Cited by 14
Research on Model Optimization Technology of Federated Learning
Dai, H., & Hong, Y. (2023) · IEEE International Conference on Big Data Analytics (ICBDA) · doi:10.1109/icbda57405.2023.10104736 · Cited by 12
“In literature [37-41], in order to make a trade-off between communication cost and model accuracy, researchers have conducted a lot of theoretical research and analysis.”
BackgroundOptimal high-dimensional and nonparametric distributed testing under communication constraints
Szabó, B., Vuursteen, L., & van Zanten, H. J. (2023) · The Annals of Statistics · doi:10.1214/23-aos2269 · Cited by 12
“In [1], the authors consider a setting in which each machine obtains a single observation from a distribution on a finite sample space and derive lower bounds for testing uniformity of this distribution.”
BackgroundInteraction is Necessary for Distributed Learning with Privacy or Communication Constraints
Dagan, Y., & Feldman, V. (2020) · Journal of Privacy and Confidentiality · doi:10.1145/3357713.3384315 · Cited by 20
Locally Private Learning without Interaction Requires SeparationPreprint
Daniely, A., & Feldman, V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.09165 · Cited by 13
“[1] implicitly give a separation between interactive and noninteractive protocols for the problem of identity testing for a discrete distribution over k elements, albeit a relatively weak one (O(k) vs Ω(k) samples).”
BackgroundContinual Mean Estimation Under User-Level Privacy
George, A. J., Ramesh, L., Singh, A. V., & Tyagi, H. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3366086 · Cited by 9
“Many works have looked at the effect of local differential privacy on statistical estimation rates, e.g., [31], [32], [33], [34], [35], [36], [37], [38], [39].”
BackgroundSelf-citationOptimal Distributed Composite Testing in High-Dimensional Gaussian Models With 1-Bit Communication
Szabó, B., Vuursteen, L., & van Zanten, H. J. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3150599 · Cited by 9
“In [2], theoretical guarantees are derived for distributed uniformity testing of a discrete distribution in the case that a collection of machines each receive one observation.”
BackgroundPauli Measurements Are Not Optimal for Single-Copy Tomography
Acharya, J., Dharmavarapu, A., Liu, Y., & Yu, N. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718248 · Cited by 8
Self-citationStrong Data Processing Inequalities for Locally Differentially Private Mechanisms
Zamanlooy, B., & Asoodeh, S. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206578 · Cited by 23
Distributed Nonparametric Estimation under Communication ConstraintsPreprint
Zaman, A., & Szabó, B. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2204.10373 · Cited by 8
Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior
Ramesh, L., Murthy, C. R., & Tyagi, H. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3111992 · Cited by 7
Self-citationBreaking The Dimension Dependence in Sparse Distribution Estimation under Communication ConstraintsPreprint
Chen, W., Kairouz, P., & Özgür, A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.08597 · Cited by 7
“…constraints, the optimal convergence rate for discrete distribution estimation was established in (Han et al., 2018b,a; Barnes et al., 2019; Acharya et al., 2019a,b; Chen et al., 2020) for the non-interactive setting, and (Barnes et al., 2019; Acharya et al., 2020) for general interactive…”
InfluentialThe Role of Interactivity in Structured EstimationPreprint
Acharya, J., Canonne, C. L., Sun, Z., & Tyagi, H. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.06870 · Cited by 18
“Distributed mean estimation under both communication and privacy constraints has been extensively considered [36, 26, 23, 29, 14, 16, 43, 3, 1].”
BackgroundSelf-citationSample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior
Ramesh, L., Murthy, C. R., & Tyagi, H. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849704 · Cited by 6
“Also, our setting is closely related to the recently proposed inference under local information constraints setting of [1].”
BackgroundSelf-citationBayesian‐MLE signal detection for multi‐antenna ambient backscatter communication
Feng, J., Zhang, H., Gao, M., & Xue, B. (2022) · IET Communications · doi:10.1049/cmu2.12366 · Cited by 6
Feature Engineering Framework based on Secure Multi-Party Computation in Federated Learning
Sun, L., Du, R., He, D., Zhu, S., Wang, R., & Chan, S. (2021) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc-dss-smartcity-dependsys53884.2021.00088 · Cited by 6
“Thus, two adjacent intervals can be merged if they have very similar class distributions, otherwise, they should remain separate [19], [20].”
BackgroundFundamental Limits of Over-the-Air Optimization: Are Analog Schemes Optimal?
Jha, S. K., Mayekar, P., & Tyagi, H. (2022) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2022.3177582 · Cited by 8
“In the second channel-use, the gain of the subgra-dient vector is transmitted after scaling it appropriately to satisfy the power constraint. where the first inequality is Markov’s inequality and the second can be shown using the results 9 in [6, Lemma 3, 4] established using the Assouad’s method.”
MethodSelf-citationAccuracy-Memory Tradeoffs and Phase Transitions in Belief PropagationPreprint
Jain, V., Koehler, F., Liu, J., & Mossel, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.10031 · Cited by 6
“(2018); Acharya et al. (2018)). For example, Barnes et al. (2018) proved the contraction of the Fisher information in the Gaussian location model via a geometric analysis of the quantization of the score function (which is a high dimensional Gaussian vector).”
MethodMinimax Bounds for Distributed Logistic RegressionPreprint
Barnes, L. P., & Özgür, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.01625 · Cited by 6
“In other works, the statistical task of interest is estimating a high-dimensional discrete distribution (Diakonikolas et al., 2017; Han et al., 2018a) or distributed property testing (Acharya et al., 2018a,b).”
BackgroundStatistical Inference With Limited Memory: A Survey
Berg, T., Ordentlich, O., & Shayevitz, O. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3481296 · Cited by 4
“In these type of problems, the samples observed by the agents are from the same distribution and the regime of interest is typically where the dimension of the problem is high compared to the number of local samples, see, e.g., [3], [62], [63], [64], [65], [66], [67], [68], [69], [70], [71], [72].”
BackgroundUniformity Testing in the Shuffle Model: Simpler, Better, Faster
Canonne, C. L., & Lyu, H. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977066.13 · Cited by 8
Self-citationSimpler Distribution Testing with Little Memory
Canonne, C. L., & Yang, J. Q. (2024) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977936.37 · Cited by 4
Self-citationUniformity Testing Under User-Level Local Privacy
Canonne, C. L., Gentle, A., & Singhal, V. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2026.33 · Cited by 4
Self-citationPrivate Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine
Canonne, C. L., & Sun, Y. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.3929/ethz-b-000659609 · Cited by 4
Self-citationWu, J., Xu, D., Gui, W., & Yang, C. (2023) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2023.3338364 · Cited by 3
“Using the Gabor filter to extract MGFF for the metal solution images before coarse slagging and fine slagging, the MGFF are modeled using an extreme value distribution and compared with the Chi-square distribution [30] and F distribution [31].”
MethodOptimal Communication Rates and Combinatorial Properties for Common Randomness Generation
Han, Y., Tatwawadi, K., Kurri, G. R., Zhou, Z., Prabhakaran, V. M., & Weissman, T. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3119976 · Cited by 3
“Another closely-related problem is distributed inference under communication constraints [46], where distributed simulation of common randomness is useful for distributed learning and property testing [47], [48].”
BackgroundDifferentially Private Sampling from Distributions
Raskhodnikova, S., Sivakumar, S., Smith, A., & Swanberg, M. (2025) · SIAM Journal on Computing · doi:10.1137/22m1538703 · Cited by 3
Simple Binary Hypothesis Testing under Communication Constraints
Pensia, A., Loh, P., & Jog, V. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834363 · Cited by 3
“Statistical inference has been studied under various constraints such as memory, privacy, and communication [2]– [10], designed to model physical or economical constraints.”
BackgroundTesting Distributions of Huge Objects
Goldreich, O., & Ron, D. (2022) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2022.78 · Cited by 3
Locally differentially private two-sample testing
Kent, A., Berrett, T. B., & Yu, Y. (2026) · Biometrika · doi:10.1093/biomet/asag034 · Cited by 3
Prediction with Noisy Expert Advice
Bhatt, A., & Kostina, V. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619637 · Cited by 2
“The line of work [28]–[30] considers sequential statistical inference under constraints, designing optimal policies and well as establishing fundamental converse bounds.”
BackgroundFundamental limits of over-the-air optimization: Are analog schemes optimal?
Jha, S. K., Mayekar, P., & Tyagi, H. (2021) · Globecom · doi:10.1109/globecom46510.2021.9685770 · Cited by 3
Self-citationIndependence Testing for Bounded Degree Bayesian NetworkPreprint
Bhattacharyya, A., Canonne, C. L., & Yang, J. Q. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2204.08690 · Cited by 2
“This theorem considerably generalizes the lower bound of ⌦ ( n/ " 2 ) established in Canonne et al. [2020] for the case of trees 3 ( d = 1 ).”
BackgroundMethodInfluentialSelf-citationTesting Distributions of Huge Objects
Goldreich, O., & Ron, D. (2023) · TheoretiCS · doi:10.46298/theoretics.23.12 · Cited by 1
Online Informing about Consumer Rights: Correspondence Analysis of Age, Education and Occupation
Ćurlin, T., Nikolić, H., & Miloloža, I. (2021) · International Convention on Information and Communication Technology, Electronics and Microelectronics · doi:10.23919/mipro52101.2021.9597105 · Cited by 1
“It measures how close observed frequencies are from the expected frequencies of the selected variables [37].”
BackgroundEstablishing the Parameters of a Decentralized Neural Machine Learning Model
Ioste, A. R., & Finger, M. (2022) · doi:10.5753/eniac.2022.227342 · Cited by 1
“Trade-offs between communication and accuracy in federated learning have received a lot of interest from a modeling point of view [Han et al. 2021, Acharya et al. 2020, Tang et al. 2019].”
MethodLocally Private Histograms in All Privacy RegimesPreprint
Canonne, C. L., & Gentle, A. (2024) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2025.25 · Cited by 1
Self-citationDistributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State CertificationPreprint
Chen, K. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.31753 · Cited by 1
Over-the-Air Statistical Estimation of Sparse Models
Lee, C.-Z., Barnes, L. P., Zhan, W., & Özgür, A. (2021) · Globecom · doi:10.1109/globecom46510.2021.9685768
Communication-Constrained Distributed Mean Estimation of Log-Concave Distributions
Kumar, R., & Vatedka, S. (2023) · National Conference on Communications · doi:10.1109/ncc56989.2023.10067942
“See [5], [6], [7], [8] and the references therein for a more extensive list of references.”
BackgroundThe Construction and Experimental Technologies of Anonymous Network Analysis and Control Platform
Zhao, Y., Yang, B., Tian, B., & Yang, Y. (2024) · International Conference on Pattern Recognition and Artificial Intelligence (PRAI) · doi:10.1109/prai62207.2024.10827379
“Distinguished from normal encryption protocol flows or single encrypted data, the paper adopts the method of detecting encrypted abnormal packet flows with the same chi-square distribution characteristics [17].”
Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
Tasnim, N., Gilani, A., Sankar, L., & Kosut, O. (2025) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw62417.2025.11240274
“Husain et al. [10] considers DP sampling in the local setting, where the central aggregator cannot be trusted and each user must produce a single data record privately.”
Dubey, P., & Huo, X. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.29642
“Prior work [Dubey and Huo, 2026] develops the full FPLD protocol (recapped as Algorithm 1), the inference-time conformal coverage results (FC-RAG), and the proof of Theorem 3.”
Influential
Metadata
- Authors
- Acharya, J., Canonne, C. L., & Tyagi, H.
- Affiliations
- Cornell University (US)
- Robert Bosch (India) (IN)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2020-12
- Volume
- 66
- Issue
- 12
- Pages
- 7835-7855
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2907436114
- Cited by
- 59
- References
- 59
- Citations by year
- 2025: 4 · 2024: 7 · 2023: 9 · 2022: 10 · 2021: 15 · 2020: 7
- FWCI
- 4.03
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) (acceptedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- NSF-CCF (NSF-CCF-1846300 (CAREER), NSF-CCF-1815893)
- Google Faculty Fellowship
- Motwani Postdoctoral Fellowship at Stanford University
- Research Grant from the Robert Bosch Center for Cyberphysical Systems (RBCCPS), Indian Institute of Science, Bengaluru
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Sensor Networks and Detection Algorithms
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Keywords
- information constraints, sample complexity, distribution testing, public-coin protocols, lower bounds
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.