Any AND-OR Formula of Size N Can Be Evaluated in Time A Ambainis, AM Childs, BW Reichardt, R ©palek, S Zhang
SIAM Journal on Computing 39 (6), 2513-2530, 2010
207 * 2010 Negative weights make adversaries stronger P Hoyer, T Lee, R Spalek
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
176 2007 Quantum verification of matrix products H Buhrman, R Spalek
arXiv preprint quant-ph/0409035, 2004
149 2004 Quantum query complexity of state conversion T Lee, R Mittal, BW Reichardt, R ©palek, M Szegedy
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 344-353, 2011
128 2011 Span-program-based quantum algorithm for evaluating formulas BW Reichardt, R Spalek
Proceedings of the fortieth annual ACM symposium on Theory of computing, 103-112, 2008
121 2008 All quantum adversary methods are equivalent R ©palek, M Szegedy
International Colloquium on Automata, Languages, and Programming, 1299-1311, 2005
118 2005 Quantum and classical strong direct product theorems and optimal time-space tradeoffs H Klauck, R ©palek, R De Wolf
SIAM Journal on Computing 36 (5), 1472-1493, 2007
98 2007 Quantum fan-out is powerful P Høyer, R ©palek
Theory of computing 1 (1), 81-103, 2005
84 * 2005 A direct product theorem for discrepancy T Lee, A Shraibman, R ©palek
2008 23rd Annual IEEE Conference on Computational Complexity, 71-80, 2008
82 2008 Lower bounds on quantum query complexity. EATCS Bulletin, 87: 78–103, October 2005 P Høyer, R ©palek
arXiv preprint quant-ph/0509153, 0
63 Quantum algorithms for matching and network flows A Ambainis, R ©palek
Annual Symposium on Theoretical Aspects of Computer Science, 172-183, 2006
50 2006 A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs A Ambainis, R ©palek, R de Wolf
Algorithmica 55 (3), 422-461, 2009
34 2009 Adversary lower bound for the k-sum problem A Belovs, R Spalek
Proceedings of the 4th conference on Innovations in Theoretical Computer …, 2013
32 2013 The multiplicative quantum adversary R ©palek
2008 23rd Annual IEEE Conference on Computational Complexity, 237-248, 2008
25 2008 A dual polynomial for OR R Spalek
arXiv preprint arXiv:0803.4516, 2008
25 2008 Space complexity of quantum computation R ©palek, R ©palek
quantum 35 (37), 53, 2001
7 2001 Quantum algorithms, lower bounds, and time-space tradeoffs R Spalek
AmsterdamILLC, 2006
5 2006 Quantum circuits with unbounded fan-out R Spalek
3 2002 Adversary lower bound for the orthogonal array problem R Spalek
arXiv preprint arXiv:1304.0845, 2013
2 2013 Every NAND formula on N variables can be evaluated in time AM Childs, BW Reichardt, R ©palek, S Zhang
arXiv preprint quant-ph/0703015, 0
1 
Ben ReichardtUniversity of Southern CaliforniaE-mail megerősítve itt: usc.edu
