Dimension-Free $L_2$ Maximal Inequality for Spherical Means in the Hypercube

by Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman

Theory of Computing, Volume 10(3), pp. 55-75, 2014

Bibliography with links to cited articles

[1]   Sanjeev Arora, Boaz Barak, and David Steurer: Subexponential algorithms for Unique Games and related problems. In Proc. 51st FOCS, pp. 563–572. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.59]

[2]   Sanjeev Arora, Russell Impagliazzo, William Matthews, and David Steurer: Improved algorithms for Unique Games via divide and conquer. Electron. Colloq. on Comput. Complexity (ECCC), 17:41, 2010. ECCC.

[3]   Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi: Unique Games on expanding constraint graphs are easy. In Proc. 40th STOC, pp. 21–28. ACM Press, 2008. [doi:10.1145/1374376.1374380]

[4]   Per Austrin: Towards sharp inapproximability for any 2-CSP. SIAM J. Comput., 39(6):2430–2463, 2010. Preliminary version in FOCS’07. [doi:10.1137/070711670]

[5]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for Unique Games. In Proc. 38th STOC, pp. 205–214. ACM Press, 2006. [doi:10.1145/1132516.1132547]

[6]   Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar: On the hardness of approximating MULTICUT and SPARSEST-CUT. Comput. Complexity, 15(2):94–114, 2006. Preliminary version in CCC’05. [doi:10.1007/s00037-006-0210-9]

[7]   Eden Chlamtáč, Konstantin Makarychev, and Yury Makarychev: How to play Unique Games using embeddings. In Proc. 47th FOCS, pp. 687–696. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.36]

[8]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Series in Telecommunication. John Wiley and Sons, New York, 1991.

[9]   Diego Dominici: Asymptotic analysis of the Krawtchouk polynomials by the WKB method. The Ramanujan Journal, 15(3):303–338, 2008. See also at arXiv. [doi:10.1007/s11139-007-9078-9]

[10]   Per Enflo: On the nonexistence of uniform homeomorphisms between Lp-spaces. Ark. Mat., 8(2):103–105, 1970. [doi:10.1007/BF02589549]

[11]   Philip Feinsilver and Jerzy Kocik: Krawtchouk matrices from classical and quantum walks. In Algebraic Methods in Statistics and Probability, volume 287 of Contemporary Mathematics, pp. 83–96. AMS, 2001. See also at arXiv. [doi:10.1090/conm/287]

[12]   Adriano Garsia: A simple proof of E. Hopf’s maximal ergodic theorem. Indiana Univ. Math. J. (J. Math. Mech.), 14(3):381–382, 1965. [doi:10.1512/iumj.1965.14.14027]

[13]   Anupam Gupta and Kunal Talwar: Approximating Unique Games. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 99–106. ACM Press, 2006. [ACM:1109569]

[14]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[15]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/S0097539705447372]

[16]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ε. J. Comput. System Sci., 74(3):335–349, 2008. Preliminary version in CCC’03. [doi:10.1016/j.jcss.2007.06.019]

[17]   Subhash Khot and Nisheeth K. Vishnoi: The Unique Games conjecture, integrality gap for cut problems and embeddability of negative type metrics into 1. In Proc. 46th FOCS, pp. 53–62. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.74]

[18]   Bo’az Klartag and Oded Regev: Quantum one-way communication can be exponentially stronger than classical communication. In Proc. 43rd STOC, pp. 31–40. ACM Press, 2011. See also at ECCC and arXiv. [doi:10.1145/1993636.1993642]

[19]   Alexandra Kolla: Spectral algorithms for Unique Games. Comput. Complexity, 20(2):177–206, 2011. Preliminary version in CCC’10. See also at ECCC. [doi:10.1007/s00037-011-0011-7]

[20]   Alexandra Kolla, Konstantin Makarychev, and Yury Makarychev: How to play Unique Games against a semi-random adversary: Study of semi-random models of Unique Games. In Proc. 52nd FOCS, pp. 443–452. IEEE Comp. Soc. Press, 2011. See also at arXiv. [doi:10.1109/FOCS.2011.78]

[21]   Ilia Krasikov: Nonnegative quadratic forms and bounds on orthogonal polynomials. Journal of Approximation Theory, 111(1):31–49, 2001. [doi:10.1006/jath.2001.3570]

[22]   Ben Krause: Dimension-free maximal inequalities for spherical means in the hypercube. Technical report, 2013. [arXiv:1309.4466]

[23]   Ulrich Krengel: Ergodic Theorems. Walter de Gruyter, 1985.

[24]   Vladimir I. Levenshtein: Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces. IEEE Trans. Inform. Theory, 41(5):1303–1321, 1995. [doi:10.1109/18.412678]

[25]   Nathan Linial and Avner Magen: Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders. J. Combin. Theory Ser. B, 79(2):157–171, 2000. [doi:10.1006/jctb.2000.1953]

[26]   Konstantin Makarychev and Yury Makarychev: How to play Unique Games on expanders. In Proc. 8th Internat. Workshop on Approximation and Online Algorithms (WAOA’10), pp. 190–200, 2010. See also at ECCC. [doi:10.1007/978-3-642-18318-8_17]

[27]   Assaf Naor and Terence Tao: Random martingales and localization of maximal inequalities. Journal of Functional Analysis, 259(3):731–779, 2010. See also at arXiv. [doi:10.1016/j.jfa.2009.12.009]

[28]   Amos Nevo and Elias M. Stein: A generalization of Birkhoff’s pointwise ergodic theorem. Acta Mathematica, 173(1):135–154, 1994. [doi:10.1007/BF02392571]

[29]   Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]

[30]   Prasad Raghavendra and David Steurer: Graph expansion and the Unique Games conjecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]

[31]   Elias M. Stein: On the maximal ergodic theorem. Proc. Natl. Acad. Sci. USA, 47(12):1894–1897, 1961. PNAS.

[32]   Luca Trevisan: Approximation algorithms for Unique Games. Theory of Computing, 4(5):111–128, 2008. Preliminary version in FOCS’05. See also at ECCC. [doi:10.4086/toc.2008.v004a005]

[33]   Antoni Zygmund: On a theorem of Marcinkiewicz concerning interpolation of operations. J. Math. Pures Appl., 9(35):223–248, 1956.