Fetching the paper…
Reading the bibliography…
We study the problem of robustly estimating the parameter $p$ of an Erd\H{o}s-R\'enyi random graph on $n$ nodes, where a $\gamma$ fraction of nodes may be adversarially corrupted.
On random graphs i
Paul Erdős and Alfréd Rényi · 1959
Earlier work this paper cites.
Random graphs
Edgar N. Gilbert · 1959
Earlier work this paper cites.
A survey of sampling from contaminated distributions
John W. Tukey · 1960
Earlier work this paper cites.
Robust estimation of a location parameter
Peter J. Huber · 1964
Earlier work this paper cites.
Probabilistic analysis of some combinatorial search problems. traub, jf (ed.): Algorithms and complexity: New directions and recent results, 1976
Richard Karp · 1976
Earlier work this paper cites.
Mean, median and mode in binomial distributions
Rob Kaas and Jan M Buhrman · 1980
Earlier work this paper cites.
Large cliques elude the Metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
Expected complexity of graph partitioning problems
Luděk Kučera · 1995
Earlier work this paper cites.
Finding a large hidden clique in a random graph
Noga Alon, Michael Krivelevich, and Benny Sudakov · 1998
Earlier work this paper cites.
Binomial approximation to the poisson binomial distribution: The krawtchouk expansion
Bero Roos · 2001
Earlier work this paper cites.
Random graph models of social networks
Mark E. J. Newman, Duncan J. Watts, and Steven H. Strogatz · 2002
Earlier work this paper cites.
The probable value of the lovász–schrijver relaxations for maximum independent set
Uriel Feige and Robert Krauthgamer · 2003
Earlier work this paper cites.
Exact Kolmogorov and total variation distances between some familiar discrete distributions
José A. Adell and Pedro Jodrá · 2006
Earlier work this paper cites.
Robust estimators are hard to compute
Thorsten Bernholt · 2006
Earlier work this paper cites.
Learning halfspaces with malicious noise
Adam R Klivans, Philip M Long, and Rocco A Servedio · 2009
Earlier work this paper cites.
Robust principal component analysis?
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright · 2011
Earlier work this paper cites.
Rank-sparsity incoherence for matrix decomposition
Venkat Chandrasekaran, Sujay Sanghavi, Pablo A Parrilo, and Alan S Willsky · 2011
Earlier work this paper cites.
Robust matrix decomposition with sparse corruptions
Daniel Hsu, Sham M Kakade, and Tong Zhang · 2011
Earlier work this paper cites.
The power of localization for efficiently learning linear separators with noise
Pranjal Awasthi, Maria Florina Balcan, and Philip M. Long · 2014
Earlier work this paper cites.
Private graphon estimation for sparse graphs
Christian Borgs, Jennifer Chayes, and Adam Smith · 2015
Earlier work this paper cites.
Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
T. Tony Cai and Xiaodong Li · 2015
Earlier work this paper cites.
Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems
Yash Deshpande and Andrea Montanari · 2015
Earlier work this paper cites.
Randomized block Krylov methods for stronger and faster approximate singular value decomposition
Cameron Musco and Christopher Musco · 2015
Cited alongside, same era.
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, and Avi Wigderson · 2015
Cited alongside, same era.
Sharp nonasymptotic bounds on the norm of random matrices with independent entries
Afonso S. Bandeira and Ramon Van Handel · 2016
Cited alongside, same era.
Robust estimators in high dimensions without the computational intractability
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2016
Cited alongside, same era.
Agnostic estimation of mean and covariance
Kevin A. Lai, Anup B. Rao, and Santosh Vempala · 2016
Cited alongside, same era.
Learning communities in the presence of errors
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2016
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin · 2019
Later among the works it cites.
High-dimensional robust mean estimation in nearly-linear time
Yu Cheng, Ilias Diakonikolas, and Rong Ge · 2019
Later among the works it cites.
Faster algorithms for high-dimensional robust covariance estimation
Yu Cheng, Ilias Diakonikolas, Rong Ge, and David Woodruff · 2019
Later among the works it cites.
Quantum entropy scoring for fast robust mean estimation and improved outlier detection
Yihe Dong, Samuel Hopkins, and Jerry Li · 2019
Later among the works it cites.
Recent advances in algorithmic high-dimensional robust statistics
Ilias Diakonikolas and Daniel M. Kane · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
How robust are reconstruction thresholds for community detection?
Ankur Moitra, William Perry, and Alexander S Wein · 2016
Cited alongside, same era.
Computationally efficient robust sparse estimation in high dimensions
Sivaraman Balakrishnan, Simon S. Du, Jerry Li, and Aarti Singh · 2017
Cited alongside, same era.
Learning from untrusted data
Moses Charikar, Jacob Steinhardt, and Gregory Valiant · 2017
Cited alongside, same era.
Being robust (in high dimensions) can be practical
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2017
Cited alongside, same era.
Statistical algorithms and a lower bound for detecting planted cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao · 2017
Cited alongside, same era.
Revealing network structure, confidentially: Improved rates for node-private graphon estimation
Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik · 2018
Cited alongside, same era.
Robust estimators in high-dimensions without the computational intractability
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2019
Later among the works it cites.
Sever: A robust meta-algorithm for stochastic optimization
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart · 2019
Later among the works it cites.
Efficiently estimating Erdos-Renyi graphs with node differential privacy
Adam Sealfon and Jonathan Ullman · 2019
Later among the works it cites.
Generalized resilience and robust statistics
Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt · 2019
Later among the works it cites.
High-dimensional robust mean estimation via gradient descent
Yu Cheng, Ilias Diakonikolas, Rong Ge, and Mahdi Soltanolkotabi · 2020
Later among the works it cites.
Efficiently learning structured distributions from untrusted batches
Sitan Chen, Jerry Li, and Ankur Moitra · 2020
Later among the works it cites.
Learning structured distributions from untrusted batches: Faster and simpler
Sitan Chen, Jerry Li, and Ankur Moitra · 2020
Later among the works it cites.
A general method for robust learning from batches
Ayush Jain and Alon Orlitsky · 2020
Later among the works it cites.
Optimal robust learning of discrete distributions from batches
Ayush Jain and Alon Orlitsky · 2020
Later among the works it cites.
High dimensional robust sparse regression
Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis · 2020
Later among the works it cites.
On learning Ising models under Huber’s contamination model
Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar · 2020
Later among the works it cites.
Robust estimation via robust gradient estimation
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar · 2020
Later among the works it cites.
Local statistics, semidefinite programming, and community detection
Jess Banks, Sidhanth Mohanty, and Prasad Raghavendra · 2021
Closest in time.
Robust density estimation from batches: The best things in life are (nearly) free
Ayush Jain and Alon Orlitsky · 2021
Closest in time.
Robust regression with covariate filtering: Heavy tails and adversarial contamination
Ankit Pensia, Varun Jog, and Po-Ling Loh · 2021
Closest in time.
Robust estimation algorithms don’t need to know the corruption level
Ayush Jain, Alon Orlitsky, and Vaishakh Ravindrakumar · 2022
Closest in time.