Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions
by Noga Alon and Shachar Lovett
Theory of Computing, Volume 9(15), pp. 559-577, 2013
Bibliography with links to cited articles
[1] Nir Ailon and Noga Alon: Hardness of fully dense problems. Inform. and Comput., 205(8):1117–1129, 2007. [doi:10.1016/j.ic.2007.02.006]
[2] Gorjan Alagic and Alexander Russell: Spectral concentration of positive functions on compact groups. J. Fourier Anal. Appl., 17(3):355–373, 2011. [doi:10.1007/s00041-011-9174-5]
[3] 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]
[4] Noga Alon, László Babai, and Alon Itai: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. [doi:10.1016/0196-6774(86)90019-2]
[5] Noga Alon, Oded Goldreich, and Yishay Mansour: Almost k-wise independence versus k-wise independence. Inform. Process. Lett., 88(3):107–110, 2003. [doi:10.1016/S0020-0190(03)00359-4]
[6] Per Austrin and Johan Håstad: Randomly supported independence and resistance. SIAM J. Comput., 40(1):1–27, 2011. Preliminary version in STOC’09. [doi:10.1137/100783534]
[7] Peter J. Cameron: Permutation groups. In Handbook of Combinatorics, Vol. 1, pp. 611–645. Elsevier, Amsterdam, 1995.
[8] Constantin Carathéodory: Über den Variabilitätsbereich der Fourier’schen Konstanten von positiven harmonischen Funktionen. Rendiconti del Circolo Matematico di Palermo, 32(1):193–217, 1911. [doi:10.1007/BF03014795]
[9] Hilary Finucane, Ron Peled, and Yariv Yaari: A recursive construction of t-wise uniform permutations. Technical report, 2012. Random Structures and Algorithms, to appear. [arXiv:1201.4960]
[10] William Fulton and Joe Harris: Representation Theory: A First Course. Volume 129 of Graduate Texts in Mathematics. Springer, 1st edition, 1991.
[11] Edward Frank Harding: The number of partitions of a set of N points in k dimensions induced by hyperplanes. Proc. Edinburgh Math. Soc. (2), 15(4):285–289, 1967. [doi:10.1017/S0013091500011925]
[12] Eyal Kaplan, Moni Naor, and Omer Reingold: Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113–133, 2009. Preliminary version in RANDOM’05. [doi:10.1007/s00453-008-9267-y]
[13] Richard M. Karp and Christos H. Papadimitriou: On linear characterizations of combinatorial optimization problems. SIAM J. Comput., 11(4):620–632, 1982. Preliminary version in FOCS’80. [doi:10.1137/0211053]
[14] Martin Kassabov: Symmetric groups and expander graphs. Inventiones Mathematicae, 170(2):327–354, 2007. [doi:10.1007/s00222-007-0065-y]
[15] Daphne Koller and Nimrod Megiddo: Constructing small sample spaces satisfying given constraints. SIAM J. Discrete Math., 7(2):260–274, 1994. Preliminary version in STOC’93. [doi:10.1137/S0895480192228140]
[16] Ka-Lam Kueh, Timothy Olson, Daniel Rockmore, and Ki-Seng Tan: Nonlinear approximation theory on compact groups. J. Fourier Anal. Appl., 7(3):257–281, 2001. [doi:10.1007/BF02511813]
[17] Greg Kuperberg, Shachar Lovett, and Ron Peled: Probabilistic existence of rigid combinatorial structures. In Proc. 44th STOC, pp. 1091–1106. ACM Press, 2012. [doi:10.1145/2213977.2214075]
[18] David Maslen: Efficient computation of Fourier transforms on compact groups. J. Fourier Anal. Appl., 4(1):19–52, 1998. [doi:10.1007/BF02475926]
[19] Aidan Roy and Andrew J. Scott: Unitary designs and codes. Designs, Codes and Cryptography, 53(1):13–31, 2009. [doi:10.1007/s10623-009-9290-2]
[20] Ronitt Rubinfeld and Ning Xie: Robust characterizations of k-wise independence over product spaces and related testing results. Random Structures & Algorithms, 2012 (online). Preliminary version in ICALP’10. [doi:10.1002/rsa.20423]
[21] Alexander Russell and Hong Wang: How to fool an unbounded adversary with a short key. IEEE Trans. Inform. Theory, 52(3):1130–1140, 2006. Preliminary version in EUROCRYPT’02. [doi:10.1109/TIT.2005.864438]
[22] Norbert Sauer: On the density of families of sets. J. Combin. Theory Ser. A, 13(1):145–147, 1972. [doi:10.1016/0097-3165(72)90019-2]
[23] Saharon Shelah: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41(1):247–261, 1972. Project Euclid.
[24] Vladimir N. Vapnik and Alexey Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16(2):264–280, 1971. [doi:10.1137/1116025]
[25] Serge Vaudenay: Provable security for block ciphers by decorrelation. In Proc. 15th Symp. Theoretical Aspects of Comp. Sci. (STACS’98), pp. 249–275. Springer, 1998. [doi:10.1007/BFb0028566]
[26] Serge Vaudenay: Adaptive-attack norm for decorrelation and super-pseudorandomness. In Proc. 6th Ann. Internat. Workshop on Selected Areas in Cryptography (SAC’99), pp. 49–61. Springer, 1999. [doi:10.1007/3-540-46513-8_4]
[27] Serge Vaudenay: Decorrelation: A theory for block cipher security. J. Cryptology, 16(4):249–286, 2003. [doi:10.1007/s00145-003-0220-6]