Lower bounds for local search by quantum arguments, Proc. STOC, pp.465-474, 2004. ,
Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Journal of the ACM, vol.51, issue.4, pp.595-605, 2004. ,
A new quantum lower bound method, with an application to strong direct product theorem for quantum search ,
Quantum lower bounds by quantum arguments, J. Comput. Syst. Sci, vol.64, issue.4, pp.750-767, 2002. ,
Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range, Theory of Computing, vol.1, issue.3, pp.37-46, 2005. ,
Sampling Algorithms: lower bounds and applications, Proc. STOC, pp.266-275, 2001. ,
Quantum lower bounds by polynomials, Journal of the ACM, vol.48, issue.4, pp.778-797, 2001. ,
Lower bounds for testing bipartiteness in dense graphs, Proc. 19th IEEE Annual Conference on Computational Complexity (CCC'04, 2004. ,
Extremal Graph Theory, 2004. ,
Permutation groups, vol.45, 1999. ,
Bounds on the power of constant-depth quantum circuits, Proc. 15th International Symposium on on Fundamentals of Computation Theory (FCT 2005), vol.3623, pp.44-55, 2005. ,
Hidden translation and orbit coset in quantum computing, STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003. ,
On the black-box complexity of Sperner's lemma, Proc. 15th International Symposium on on Fundamentals of Computation Theory (FCT 2005), vol.3623, pp.245-257, 2005. ,
Three theorems regarding testing graph properties. Random Structures and Algorithms, vol.23, pp.23-57, 2003. ,
A quantum lower bound for the query complexity of Simon's problem, Proc. ICALP 2005, vol.3580, pp.1287-1298, 2005. ,
The quantum query complexity of the abelian hidden subgroup problem, 2005. ,
URL : https://hal.archives-ouvertes.fr/hal-02101788
Quantum lower bound for the collision problem, 2003. ,
Quantum lower bound for the collision problem with small range. Theory of Computing, vol.1, pp.29-36, 2005. ,
Lower bounds for randomized and quantum query complexity using kolmogorov arguments, Proc. 19th IEEE Annual Conference on Computational Complexity (CCC'04, 2004. ,
CREW PRAMs and decision trees, SIAM J. Comput, vol.20, issue.6, pp.999-1007, 1991. ,
On the time required to check properties of graphs: A problem, pp.15-16, 1973. ,
On the power of quantum computation, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp.116-123, 1994. ,
On the power of quantum computation, SIAM Journal on Computing, vol.26, issue.5, pp.1474-1483, 1997. ,
All quantum adversary methods are equivalent, Proc. ICALP 2005, vol.3580, pp.1299-1311, 2005. ,