Fourier Sparsity and Dimension

by Swagato Sanyal

Theory of Computing, Volume 15(11), pp. 1-13, 2019

Bibliography with links to cited articles

[1]   Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf: Two new results about quantum exact learning. In Proc. 46th Internat. Colloq. on Automata, Languages and Programming (ICALP’19), pp. 16:1–16:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ICALP.2019.16, arXiv:1810.00481]

[2]   Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif: The log-approximate-rank conjecture is false. In Proc. 50th STOC, pp. 42–53. ACM Press, 2019. [doi:10.1145/3313276.3316353]

[3]   Dmitry Gavinsky, Naomi Kirshner, Alex Samorodnitsky, and Ronald de Wolf: Private communication, 2014.

[4]   Parikshit Gopalan, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer: Testing Fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075–1100, 2011. Preliminary version in ICALP’09. [doi:10.1137/100785429]

[5]   Tom Gur and Omer Tamuz: Testing Booleanity and the uncertainty principle. Chicago J. Theoret. Computer Sci., 2013(14), 2013. [doi:10.4086/cjtcs.2013.014, arXiv:1204.0944]

[6]   Hamed Hatami, Kaave Hosseini, and Shachar Lovett: Structure of protocols for XOR functions. SIAM J. Comput., 47(1):208–217, 2018. Preliminary version in FOCS’16. [doi:10.1137/17M1136869]

[7]   Ishay Haviv and Oded Regev: The list-decoding size of Fourier-sparse Boolean functions. ACM Trans. Comput. Theory, 8(3):10:1–10:14, 2016. Preliminary version in CCC’15. [doi:10.1145/2898439, arXiv:1504.01649]

[8]   Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev: Linear sketching over F2. In Proc. 33rd Computational Complexity Conf. (CCC’18), pp. 8:1–8:37. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.8, arXiv:1611.01879]

[9]   Andrei Vyacheslavovich Khalyavin, Mikhail Sergeevich Lobanov, and Yuriy Valerievich Tarannikov: On plateaued Boolean functions with the same spectrum support. Sib. Člektron. Mat. Izv., 13:1346–1368, 2016. [doi:10.17377/semi.2016.13.105]

[10]   Shachar Lovett: Communication is bounded by root of rank. J. ACM, 63(1):1:1–1:9, 2016. Preliminary version in STOC’14. [doi:10.1145/2724704, arXiv:1306.1877]

[11]   Ashley Montanaro and Tobias Osborne: On the communication complexity of XOR functions, 2009. [arXiv:0909.3392]

[12]   Swagato Sanyal: Near-optimal upper bound on Fourier dimension of Boolean functions in terms of Fourier sparsity. In Proc. 42nd Internat. Colloq. on Automata, Languages and Programming (ICALP’15), pp. 1035–1045. Springer, 2015. [doi:10.1007/978-3-662-47672-7_84]

[13]   Amir Shpilka, Avishay Tal, and Ben lee Volk: On the structure of Boolean functions with small spectral norm. Comput. Complexity, 26(1):229–273, 2017. Preliminary version in ITCS’14. [doi:10.1145/2591796.2591799, arXiv:1304.0371]

[14]   Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang: Fourier sparsity, spectral norm, and the Log-rank Conjecture. In Proc. 54th FOCS, pp. 658–667. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.76, arXiv:1304.1245]