Fetching the paper…
Reading the bibliography…
In this paper we introduce the study of quantum boolean functions, which are unitary operators f whose square is the identity: f^2 = I.
Walter Rudin, Trigonometric series with gaps , J. Math. Mech. 9
1960
Earlier work this paper cites.
Edward Nelson, A quartic interaction in two dimensions , Mathematical Theory of Elementary Particles (Proc. Conf., Dedham, Mass., 1965), M.I.T. Press, Cambridge, Mass., 1966, pp. 69–73. MR 0210416 (35 #1309)
1966
Earlier work this paper cites.
Aline Bonami, Ensembles Λ ( p ) \Lambda(p) dans le dual de D ∞ D^{\infty} , Ann. Inst. Fourier 18
1969
Earlier work this paper cites.
Elliott H. Lieb and Derek W. Robinson, The finite group velocity of quantum spin systems , Commun. math. Phys. 28
1972
Earlier work this paper cites.
A. S. Holevo, Statistical decision theory for quantum systems , Journal of Multivariate Analysis 3
1973
Earlier work this paper cites.
William Beckner, Inequalities in Fourier analysis , Ann. of Math. 102
1975
Earlier work this paper cites.
Leonard Gross, Logarithmic Sobolev inequalities , Amer. J. Math. 97
1975
Earlier work this paper cites.
C. W. Helstrom, Quantum detection and estimation theory , Academic Press, New York, 1976
1976
Earlier work this paper cites.
R. Zippel, Probabilistic algorithms for sparse polynomials , Proc. EUROSAM’79, Lecture Notes in Computer Science, vol. 72, Springer-Verlag, 1979, pp. 216–226
1979
Earlier work this paper cites.
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities , J. Assoc. Comput. Mach. 27
1980
Earlier work this paper cites.
J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions , Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS’88) (Los Alamitos, CA, USA), IEEE Computer Society, 1988, pp. 68–80
1988
Earlier work this paper cites.
Oded Goldreich and Leonid A. Levin, A hard-core predicate for all one-way functions , In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, 1989, pp. 25–32
1989
Earlier work this paper cites.
Manuel Blum, Michael Luby, and Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems , Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), vol. 47, 1993, pp. 549–595. MR 1248868 (94m:65020)
1993
Earlier work this paper cites.
E. Carlen and E. Lieb, Optimal hypercontractivity for Fermi fields and related non-commutative integration inequalities , Comm. Math. Phys 155
1993
Earlier work this paper cites.
E. Kushilevitz and Y. Mansour, Learning decision trees using the Fourier spectrum , Siam J. Comput. 22
1993
Earlier work this paper cites.
Noam Nisan and Mario Szegedy, On the degree of Boolean functions as real polynomials , Computational Complexity 4
1994
Earlier work this paper cites.
Michel Talagrand, On Russo’s approximate zero-one law , Ann. Prob. 23
1994
Cited alongside, same era.
Rajendra Bhatia, Matrix analysis , Springer-Verlag, New York, 1997. MR 98i:15003
1997
Cited alongside, same era.
Ethan Bernstein and Umesh Vazirani, Quantum complexity theory , SIAM J. Comput. 26
1997
Cited alongside, same era.
Ehud Friedgut, Boolean functions with low average sensitivity depend on few coordinates , Combinatorica 18
1998
Cited alongside, same era.
N. H. Bshouty and J. C. Jackson, Learning DNF over the uniform distribution using a quantum example oracle , SIAM J. Comput. 28
1999
Cited alongside, same era.
Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information , Cambridge University Press, Cambridge, 2000. MR 1 796 805
Iordanis Kerenidis and Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument , J. Comput. System Sci. 69
2004
Later among the works it cites.
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? , Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science held in Rome, Italy, October 17–19, 2004 (New York), IEEE Computer Society, 2004, pp. 146–154
2004
Later among the works it cites.
Elchanan Mossel, Stat 206A: Polynomials of Random Variables. Berkeley. http://www.stat.berkeley.edu/ mossel/teach/206af05/
2005
Later among the works it cites.
Jaikumar Radhakrishnan and Madhu Sudan, On Dinur’s proof of the PCP theorem , Bull. Amer. Math. Soc. 44
2006
Later among the works it cites.
Alp Atici and Rocco A. Servedio, Quantum algorithms for learning and testing juntas , Quantum Information Processing 6
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2000
Cited alongside, same era.
E. Fischer, The art of uninformed decisions: A primer to property testing , Bulletin of the European Association for Theoretical Computer Science 75
2001
Cited alongside, same era.
Johan Håstad, Some optimal inapproximability results , J. ACM 48
2001
Cited alongside, same era.
C. King and M. B. Ruskai, Minimal entropy of states emerging from noisy quantum channels , Comm. Math. Phys. 47
2001
Cited alongside, same era.
Mark Adcock and Richard Cleve, A quantum Goldreich-Levin Theorem with cryptographic applications , 19th Annual Symposium on Theoretical Aspects of Computer Science (Heidelberg, Berlin) (G. Goos, J. Hartmanis, and J. van Leeuwen, eds.), Lecture notes in computer science, no. 2285, Springer-Verlag, 2002, pp. 323–334
2002
Cited alongside, same era.
Jean Bourgain, On the distribution of the Fourier spectrum of Boolean functions , Isr. J. Math. 131
2002
Cited alongside, same era.
Ehud Friedgut, Gil Kalai, and Assaf Naor, Boolean functions whose Fourier transform is concentrated on the first two levels , Adv. in Appl. Math. 29
2002
Cited alongside, same era.
2007
Later among the works it cites.
Irit Dinur, The PCP theorem by gap amplification , Journal of the ACM 54
2007
Later among the works it cites.
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf, Exponential separations for one-way quantum communication complexity, with applications to cryptography , Proceedings of the 39th Annual ACM Symposium on Theory of Computing held in San Diego, CA, June 11–13, 2007 (New York), Association for Computing Machinery (ACM), 2007, pp. 516–525
2007
Later among the works it cites.
Ryan O’Donnell, 15-859S: Analysis of Boolean Functions. Carnegie Mellon University. http://www.cs.cmu.edu/ ∼ \sim odonnell/boolean-analysis/
2007
Later among the works it cites.
Dorit Aharonov, Pondering about QPCP’s , http://cnls.lanl
2008
Closest in time.
Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf, A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs , Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science held in Philadelphia, PA, October 25–28, 2008 (New York), IEEE Computer Society, 2008
2008
Closest in time.
M. B. Hastings, A counterexample to additivity of minimum output entropy , Nature Physics 5
2008
Closest in time.
Patrick Hayden and Andreas Winter, Counterexamples to the maximal p p -norm multiplicativity conjecture for all p > 1 p>1 , 2008
2008
Closest in time.
J. Kempe, O. Regev, F. Unger, and R. de Wolf, Upper bounds on the noise threshold for fault-tolerant quantum computing , Proc. 35 th International Colloquium on Automata, Languages and Programming (ICALP’08), 2008, p. 856
2008
Closest in time.
Ronald de Wolf, A brief introduction to Fourier analysis on the boolean cube , Theory of Computing Library, Graduate Surveys 1
2008
Closest in time.
Scott Aaronson, Quantum computing, postselection, and probabilistic polynomial-time , Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 461
2063
Closest in time.