2 papers
quant-ph2005
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, Mario Szegedy
We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has b…
quant-ph2003
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
Sophie Laplante, Frederic Magniez
We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmo…