The Complexity of Deciding Statistical Properties of Samplable Distributions

by Thomas Watson

Theory of Computing, Volume 11(1), pp. 1-34, 2015

Bibliography with links to cited articles

[1]   David J. Aldous: More uses of exchangeability: Representations of complex random structures. In Probability and Mathematical Genetics: Papers in Honour of Sir John Kingman, pp. 35–63. Cambridge Univ. Press, 2010. [arXiv:0909.4339]

[2]   Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie: Testing k-wise and almost k-wise independence. In Proc. 39th STOC, pp. 496–505. ACM Press, 2007. [doi:10.1145/1250790.1250863]

[3]   Sanjeev Arora and Boaz Barak: Computational Complexity – A Modern Approach. Cambridge Univ. Press, 2009.

[4]   Tuğkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld: The complexity of approximating the entropy. SIAM J. Comput., 35(1):132–150, 2005. Preliminary version in CCC’02. [doi:10.1137/S0097539702403645]

[5]   Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White: Testing random variables for independence and identity. In Proc. 42nd FOCS, pp. 442–451. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959920]

[6]   Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren Smith, and Patrick White: Testing closeness of discrete distributions. J. ACM, 4, 2013. Preliminary version in FOCS’00. [doi:10.1145/2432622.2432626, arXiv:1009.5397]

[7]   Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. In Proc. 36th STOC, pp. 381–390. ACM Press, 2004. [doi:10.1145/1007352.1007414]

[8]   Christopher Beck, Russell Impagliazzo, and Shachar Lovett: Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. In Proc. 53rd FOCS, pp. 101–110. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.82]

[9]   André Berthiaume and Gilles Brassard: The quantum challenge to structural complexity theory. In Proc. 7th IEEE Conf. on Structure in Complexity Theory (SCT’92), pp. 132–137, 1992. [doi:10.1109/SCT.1992.215388]

[10]   Andrej Bogdanov, Elchanan Mossel, and Salil P. Vadhan: The complexity of distinguishing Markov random fields. In Proc. 12th Internat. Workshop on Randomization and Computation (RANDOM’08), volume 5171, pp. 331–342, 2008. [doi:10.1007/978-3-540-85363-3_27]

[11]   Bernd Borchert, Lane A. Hemaspaandra, and Jörg Rothe: Restrictive acceptance suffices for equivalence problems. LMS Journal of Computation and Mathematics, 3:86–95, 2000. Preliminary version in FCT’99. [doi:10.1112/S146115700000022X]

[12]   Bernd Borchert and Frank Stephan: Looking for an analogue of Rice’s Theorem in circuit complexity theory. Mathematical Logic Quarterly, 46(4):489–504, 2000. Preliminary versions in KGC’97 and ECCC. [doi:10.1002/1521-3870(200010)46:4¡489::AID-MALQ489¿3.0.CO;2-F]

[13]   Siu On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant: Optimal algorithms for testing closeness of discrete distributions. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), volume 6, pp. 1193–1203. ACM Press, 2014. [doi:10.1137/1.9781611973402.88]

[14]   Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio, Gregory Valiant, and Paul Valiant: Testing k-modal distributions: Optimal algorithms via reductions. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1833–1852. ACM Press, 2013. [doi:10.1137/1.9781611973105.131]

[15]   Anindya De and Thomas Watson: Extractors and lower bounds for locally samplable sources. ACM Transactions on Computation Theory, 4(3), 2012. Preliminary versions in RANDOM’11 and ECCC. [doi:10.1145/2141938.2141941]

[16]   Perci Diaconis and David Freedman: Finite exchangeable sequences. Ann. Probab., 8(4):745–764, 1980. [doi:10.1214/aop/1176994663]

[17]   Zeev Dvir, Dan Gutfreund, Guy Rothblum, and Salil P. Vadhan: On approximating the entropy of polynomial mappings. In Proc. 2nd Innovations in Computer Science Conf. (ICS’11), pp. 460–475, 2011. Preliminary version in ECCC.

[18]   Stephen Fenner, Frederic Green, Steven Homer, and Randall Pruim: Quantum NP is hard for PH. In Proc. 6th Italian Conf. on Theoretical Computer Science, pp. 241–252, 1998. Expanded version in ECCC.

[19]   Oded Goldreich: Computational Complexity – A Conceptual Perspective. Cambridge Univ. Press, 2008.

[20]   Oded Goldreich, Amit Sahai, and Salil P. Vadhan: Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. In Proc. 19th Internat. Cryptology Conf., pp. 467–484, 1999. Preliminary version in ECCC. [doi:10.1007/3-540-48405-1_30]

[21]   Oded Goldreich and Salil P. Vadhan: Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In Proc. 14th IEEE Conf. on Computational Complexity (CCC’99), pp. 54–73, 1999. [doi:10.1109/CCC.1999.766262]

[22]   Oded Goldreich and Salil P. Vadhan: On the complexity of computational problems regarding distributions. In Studies in Complexity and Cryptography, volume 6650 of LNCS, pp. 390–405. Springer, 2011. Also available at ECCC. [doi:10.1007/978-3-642-22670-0_27]

[23]   Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997. [doi:10.1145/258533.258590]

[24]   Jesse Kamp, Anup Rao, Salil P. Vadhan, and David Zuckerman: Deterministic extractors for small-space sources. J. Comput. System Sci., 77(1):191–220, 2011. Preliminary version in STOC’06. [doi:10.1016/j.jcss.2010.06.014]

[25]   John Kingman: Uses of exchangeability. Ann. Probab., 6(2):183–197, 1978.

[26]   Reut Levi, Dana Ron, and Ronitt Rubinfeld: Testing properties of collections of distributions. Theory of Computing, 9:295–347, 2013. Preliminary versions in ICS’10 and ECCC. [doi:10.4086/toc.2013.v009a008]

[27]   Shachar Lovett and Emanuele Viola: Bounded-depth circuits cannot sample good codes. Comput. Complexity, 21(2):245–266, 2012. Preliminary versions in CCC’12 and ECCC. [doi:10.1007/s00037-012-0039-3]

[28]   Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith: Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput., 39(3):813–842, 2009. Preliminary version in FOCS’07. [doi:10.1137/070701649]

[29]   Ronitt Rubinfeld and Rocco Servedio: Testing monotone high-dimensional distributions. Random Structures Algorithms, 34(1):24–44, 2009. Preliminary version in STOC’05. [doi:10.1002/rsa.20247]

[30]   Ronitt Rubinfeld and Ning Xie: Testing non-uniform k-wise independent distributions over product spaces. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 565–581, 2010. [doi:10.1007/978-3-642-14165-2_48]

[31]   Amit Sahai and Salil P. Vadhan: A complete problem for statistical zero knowledge. J. ACM, 50(2):196–249, 2003. Preliminary versions in FOCS’97, ECCC and Cryptology ePrint Archive. [doi:10.1145/636865.636868]

[32]   Jun Tarui: Probabilistic polynomials, AC0 functions, and the polynomial-time hierarchy. Theoret. Comput. Sci., 113(1):167–183, 1993. Preliminary version in STACS’91. [doi:10.1016/0304-3975(93)90214-E]

[33]   Seinosuke Toda and Mitsunori Ogiwara: Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput., 21(2):316–328, 1992. Preliminary version in CCC’91. [doi:10.1137/0221023]

[34]   Luca Trevisan, Salil P. Vadhan, and David Zuckerman: Compression of samplable sources. Comput. Complexity, 14(3):186–227, 2005. Preliminary versions in CCC’04 and ECCC. [doi:10.1007/s00037-005-0198-6]

[35]   Paul Valiant: Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927–1968, 2011. Preliminary versions in STOC’08 and ECCC. [doi:10.1137/080734066]

[36]   Emanuele Viola: The complexity of distributions. SIAM J. Comput., 41(1):191–218, 2012. Preliminary version in FOCS’10. [doi:10.1137/100814998]

[37]   Emanuele Viola: Extractors for circuit sources. SIAM J. Comput., 43(2):655–672, 2014. Preliminary versions in FOCS’11 and ECCC. [doi:10.1137/11085983X]

[38]   Klaus W. Wagner: The complexity of combinatorial problems with succinct input representation. Acta Informatica, 23(3):325–356, 1986. [doi:10.1007/BF00289117]

[39]   Thomas Watson: The complexity of deciding statistical properties of samplable distributions. In Proc. 31st Symp. Theoretical Aspects of Comp. Sci. (STACS’14), pp. 663–674, 2014. (Preliminary version of this paper). [doi:10.4230/LIPIcs.STACS.2014.663]

[40]   Thomas Watson: The complexity of estimating min-entropy. Comput. Complexity, 2014 (online). Preliminary version in ECCC. [doi:10.1007/s00037-014-0091-2]