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]