Fetching the paper…
Reading the bibliography…
We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938
1938
Earlier work this paper cites.
A. C. Yao, Some complexity questions related to distributive computing, in:Proceedings of the 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 209-213
1979
Earlier work this paper cites.
K. Mehlhorn and E. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing, in: Proceedings of the 14th annual ACM symposium on Theory of computing, 1982, pp 330-307
1982
Earlier work this paper cites.
L. Lovász and M. Saks, Lattices, Möbius functions and communication complexity, in:Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp 330-337
1988
Earlier work this paper cites.
A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, 106(2), 1992, pp 385-390
1992
Earlier work this paper cites.
A. C. Yao, Quantum circuit complexity, in:Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, 1993, pp. 352-361
1993
Earlier work this paper cites.
I. Newman and M. Szegedy, Public vs. private coin flips in one round communication games, in: Proceedings of the 28th annual ACM symposium on Theory of computing, 1996, pp 561-570
1996
Earlier work this paper cites.
E. Kushilevitz and N. Nisan, Communication complexity, Cambridge University Press, Cambridge, 1997
1997
Cited alongside, same era.
H. Buhrman, Quantum Computing and Communication Complexity. Current Trends in Theoretical Computer Science 2001: 664-679
2001
Cited alongside, same era.
A. Razborov, Quantum communication complexity of symmetric predicates, Izvestiya Math. 67(1)(2003)145-159 (English version);also in: quant-ph/0204025
2003
Cited alongside, same era.
A. C. Yao, On the power of quantum fingerprinting, in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 77-81
2003
Cited alongside, same era.
S. Aaronson, Limitations of Quantum Advice and One-way Communication, in: Proceedings of the 19th IEEE Annual Conference on Computational Complexity, 2004, pp 320-332
2004
Cited alongside, same era.
R. Lipton, E. Markakis, A. Mehta and K. Vishnoi, On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas, in: Proceedings of the 20th IEEE Annual Conference on Computational Complexity, 2005, pp 112- 119
2005
Later among the works it cites.
W. Huang, Y. Shi, S. Zhang and Y. Zhu, The communication complexity of the Hamming distance problem, information processing letter, 99(4):149-153, 2006
2006
Later among the works it cites.
2007
Later among the works it cites.
A. Sherstov, Unbounded-Error Communication Complexity of Symmetric Functions, in:Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2008
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
G. Brassard, Quantum Communication Complexity: A Survey, ISMVL 2004: 56
2004
Cited alongside, same era.
D. Gavinsky, J. Kempe and R. de Wolf, Quantum communication cannot simulate a public coin, quant-ph/0411051, 2004
2004
Cited alongside, same era.
R. O’Donnell, lecture notes on Analysis of Boolean Functions, available at http://www.cs.cmu.edu/~odonnell/boolean-analysis/
Cited in the paper.
A. Sherstov, The pattern matrix method for lower bounds on quantum communication, in: Proceedings of the 40th annual ACM symposium on Theory of computing, 2008, pp 85-94
2008
Closest in time.