Sharp Bounds for Population Recovery

by Anindya De, Ryan O'Donnell, and Rocco A. Servedio

Theory of Computing, Volume 16(6), pp. 1-20, 2020

Bibliography with links to cited articles

[1]   Lucia Batman, Russell Impagliazzo, Cody Murray, and Ramamohan Paturi: Finding heavy hitters from lossy or noisy data. In Proc. 17th Internat. Workshop on Randomization and Computation (RANDOM’13), pp. 347–362. Springer, 2013. [doi:10.1007/978-3-642-40328-6_25]

[2]   Richard Bellman and Theodore Harris: Recurrence times for the Ehrenfest model. Pacific J. Math., 1(2):179–193, 1951. [doi:10.2140/pjm.1951.1.179]

[3]   Peter Borwein and Tamás Erdélyi: Littlewood-type problems on subarcs of the unit circle. Indiana Univ. Math. J., 46(4):1323–1346, 1997. [doi:10.1512/iumj.1997.46.1435]

[4]   Peter Borwein, Tamás Erdélyi, and Géza Kós: Littlewood-type problems on [0,1]. Proc. London Math. Soc., 79(1):22–46, 1999. [doi:10.1112/S0024611599011831]

[5]   Anindya De, Ryan O’Donnell, and Rocco A. Servedio: Optimal mean-based algorithms for trace reconstruction. Ann. Appl. Probab., 29(2):851–874, 2019. Preliminary version in STOC’17. [doi:10.1214/18-AAP1394]

[6]   Anindya De, Michael E. Saks, and Sijian Tang: Noisy population recovery in polynomial time. In Proc. 57th FOCS, pp. 675–684. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.77, arXiv:1602.07616]

[7]   Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff: Restriction access. In Innovations in Theoret. Computer Sci. (ITCS’12), pp. 19–33. ACM Press, 2012. [doi:10.1145/2090236.2090239]

[8]   Tamás Erdélyi: Coppersmith–Rivlin type inequalities and the order of vanishing of polynomials at 1. Acta Arithmetica, 172:271–284, 2016. [doi:10.4064/aa8129-11-2015, arXiv:1406.2560]

[9]   Oded Goldreich and Leonid A. Levin: A hard-core predicate for all one-way functions. In Proc. 21st STOC, pp. 25–32. ACM Press, 1989. [doi:10.1145/73007.73010]

[10]   Shachar Lovett and Jiapeng Zhang: Improved noisy population recovery, and reverse Bonami–Beckner inequality for sparse functions. In Proc. 47th STOC, pp. 137–142. ACM Press, 2015. [doi:10.1145/2746539.2746540]

[11]   Ankur Moitra and Michael Saks: A polynomial time algorithm for lossy population recovery. In Proc. 54th FOCS, pp. 110–116. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.20]

[12]   Fedor Nazarov and Yuval Peres: Trace reconstruction with exp(O(N13)) samples. In Proc. 49th STOC, pp. 1042–1046. ACM Press, 2017. [doi:10.1145/3055399.3055494, arXiv:1612.03599]

[13]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. [doi:10.1017/CBO9781139814782]

[14]   Yury Polyanskiy, Ananda Theertha Suresh, and Yihong Wu: Sample complexity of population recovery. In Proc. 30th Ann. Conf. on Learning Theory (COLT’17), pp. 1589–1618, 2017. Link at MLR Press. [arXiv:1702.05574]

[15]   Yury Polyanskiy and Yihong Wu: Personal communication, March 6, 2017.

[16]   H. A. F. Siegert: Note on the Ehrenfest problem. Technical Report LADC-438, Technical Information Division, Oak Ridge Operations, Oak Ridge, Tennesssee, 1947.

[17]   Avi Wigderson and Amir Yehudayoff: Population recovery and partial identification. Machine Learning, 102:29–56, 2016. Preliminary version in FOCS’12. [doi:10.1007/s10994-015-5489-9]