%% Theory of Computing
%% File: v008a013.bib
%% Publication date: July 7, 2012
%% Authors: Ben Reichardt and Robert Spalek
%
%
%
%
%
@PREAMBLE{ {\providecommand{\noopsort}[1]{}} }

@string{acm      = "ACM Press"}
@string{ieee     = "IEEE Comp. Soc. Press"}
@string{springer = "Springer"}

@string{SIAMJComput="SIAM J. Comput."}
@string{tcs      = "Theoret. Comput. Sci."}
@string{combinatorica    = "Combinatorica"}
@string{ccomplex = "Comput. Complexity"}
@string{ipl      = "Inform. Process. Lett."}
@string{jcss="J. Comput. System Sci."}
@string{QuantumInfComput="Quantum Inf. Comput."}
@string{RandomStructuresAlgorithms="Random Structures Algorithms"}

@string{stoc96="Proc. 28th STOC"}
@string{stoc03="Proc. 35th STOC"}
@string{stoc07="Proc. 39th STOC"}
@string{stoc08="Proc. 40th STOC"}
@string{stoc12="Proc. 44th STOC"}

@string{focs86="Proc. 27th FOCS"}
@string{focs91="Proc. 32nd FOCS"}
@string{focs95="Proc. 36th FOCS"}
@string{focs03="Proc. 44th FOCS"}
@string{focs04="Proc. 45th FOCS"}
@string{focs07="Proc. 48th FOCS"}
@string{focs11="Proc. 52nd FOCS"}

@string{soda=" Ann. ACM-SIAM Symp. on Discrete Algorithms"}
@string{soda11= "Proc. 22nd" # soda  # " (SODA'11)"}

@string{ccc=" IEEE Conf. on Computational Complexity"}
@string{sct=" IEEE Conf. on Structure in Complexity Theory"}
@string{ccc91="Proc. 6th" # sct }
@string{ccc93="Proc. 8th" # sct }
@string{ccc03="Proc. 18th" # ccc # " (CCC'03)"}

@string{icalp=" Internat. Colloq. on Automata, Languages and Programming"}
@string{icalp11= "Proc. 38th" # icalp # " (ICALP'11)"}

@techreport{kimmel11adversary,
title = {Quantum adversary (upper) bound},
author = {Shelby Kimmel},
Eprint = {arXiv:1101.0797},
year = {2011},
keywords = {span programs},
}

@techreport{zhankimmelhassidim11spanprogram-original,
title = {Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure},
author = {Bohua Zhan and Shelby Kimmel and Avinatan Hassidim},
Eprint = {arXiv:1101.0796},
year = {2011},
keywords = {span programs},
}
%
%
@inproceedings{zhankimmelhassidim11spanprogram,
title = {Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure},
author = {Bohua Zhan and Shelby Kimmel and Avinatan Hassidim},
booktitle = {Innovations in Theoretical Computer Science 2012 (ITCM'12)},
publisher = acm,
year = {2012},
pages = {249-265},
doi = {10.1145/2090236.2090258},
Eprint = {arXiv:1101.0796},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@techreport{gavinskyito12graphcollision,
title = {A quantum query algorithm for the graph collision problem},
author = {Dmitry Gavinsky and Tsuyoshi Ito},
Eprint = {arXiv:1204.1527},
year = {2012},
keywords = {span programs},
}

@techreport{belovsreichardt12connectivity,
title = {Span programs and quantum algorithms for $st$-connectivity and claw detection},
author = {Aleksandrs Belovs and Ben W. Reichardt},
Eprint = {arXiv:1203.2603},
year = {2012},
keywords = {span programs},
}

@techreport{kitaev95phaseestimation,
title = {Quantum measurements and the {A}belian stabilizer problem},
author = {A. Yu. Kitaev},
Eprint = {arXiv:quant-ph/9511026},
year = {1995},
}

@inproceedings{grover96search,
title = {A Fast Quantum Mechanical Algorithm for Database Search},
author = {Lov K. Grover},
crossref = {pstoc96},
pages = {212-219},
Eprint = {arXiv:quant-ph/9605043},
doi = {10.1145/237814.237866},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{grover96searchtime,
title = {Tradeoffs in the quantum search algorithm},
author = {Lov K. Grover},
journal = {Phys. Rev. A},
volume = {66},
year = {2002},
pages = {052314},
Eprint = {arXiv:quant-ph/0201152},
doi = {10.1103/PhysRevA.66.052314},
}
%
@inproceedings{leemittalreichardtspalekszegedy11stateconversion,
title = {Quantum Query Complexity of State Conversion},
author = {Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert {\v S}palek and Mario Szegedy},
crossref = {pfocs11},
pages = {344-353},
Eprint = {arXiv:1011.3020},
doi = {10.1109/FOCS.2011.75},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@inproceedings{hoyerleespalek07negativeadv,
title = {Negative weights make adversaries stronger},
author = {Peter H{\o}yer and Troy Lee and Robert {\v S}palek},
crossref = {pstoc07},
pages = {526-535},
Eprint = {arXiv:quant-ph/0611054},
doi = {10.1145/1250790.1250867},
}

@techreport{belovs11triangle-original,
title = {Span programs for functions with constant-sized 1-certificates},
author = {Aleksandrs Belovs},
Eprint = {arXiv:quant-ph/0611054},
year = {2011},
keywords = {span programs},
}
%
@inproceedings{belovs11triangle,
title = {Span programs for functions with constant-sized 1-certificates: extended abstract},
author = {Aleksandrs Belovs},
crossref = {pstoc12},
Eprint = {arXiv:quant-ph/0611054},
doi = {10.1145/2213977.2213985},
}

@techreport{belovslee11learninggraph,
title = {Quantum algorithm for $k$-distinctness with prior knowledge on the input},
author = {Aleksandrs Belovs and Troy Lee},
Eprint = {arXiv:1108.3022},
year = {2011},
keywords = {span programs},
}

@techreport{leemagniezsantha11learninggraph,
title = {A learning graph based quantum query algorithm for finding constant-size subgraphs},
author = {Troy Lee and Fr{\'e}d{\'e}ric Magniez and Miklos Santha},
Eprint = {arXiv:1109.5135},
year = {2011},
keywords = {span programs},
}

@techreport{zhu11learninggraph,
title = {Quantum query complexity of subgraph containment with constant-sized certificates},
author = {Yechao Zhu},
Eprint = {arXiv:1109.4165},
year = {2011},
keywords = {span programs},
}

@inproceedings{amano11andorlower,
title = {Bounding the Randomized Decision Tree Complexity of Read-Once Boolean Functions},
author = {Kazuyuki Amano},
crossref = {psoda11},
pages = {1729-1744},
eprint = {acm:2133169},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{heimanwigderson91generalandor,
title = {Randomized VS. Deterministic Decision Tree Complexity for Read-Once {B}oolean Functions},
author = {Rafi Heiman and Avi Wigderson},
journal = ccomplex,
volume = {1},
year = {1991},
pages = {311-329},
doi = {10.1007/BF01212962},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SCT.1991.160258}{Structure in Complexity Theory'91}},
bibsource = {DBLP, http://dblp.uni-trier.de},
}
%
@inproceedings{heimanwigderson91generalandor-conference,
title = {Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions},
author = {Rafi Heiman and Avi Wigderson},
booktitle = ccc91,
publisher = ieee,
year = {1991},
pages = {172-179},
doi = {10.1109/SCT.1991.160258},
}

@inproceedings{reichardt09andorfaster,
title = {Faster quantum algorithm for evaluating game trees},
author = {\noopsort{Ben Reichardt11a}{Ben Reichardt}},
crossref = {psoda11},
pages = {546-559},
eprint = {acm:2133079, arXiv:0907.1623},
Eprint = {arXiv:0907.1623},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@techreport{belovs11rank,
title = {Span-program-based quantum algorithm for the rank problem},
author = {Aleksandrs Belovs},
Eprint = {arXiv:1103.0842},
year = {2011},
keywords = {span programs},
}


@inproceedings{magnieznayaksanthaxiao10majority,
title = {Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority},
author = {Fr{\'e}d{\'e}ric Magniez and Ashwin Nayak and Miklos Santha and David Xiao},
booktitle = icalp11,
publisher = springer,
year = {2011},
pages = {317-329},
doi = {10.1007/978-3-642-22006-7\_27},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@book{nielsenchuang00,
title = {Quantum computation and quantum information},
author = {Michael A. Nielsen and Isaac L. Chuang},
publisher = {Cambridge University Press},
year = {2000},
keywords = {textbook},
address = {Cambridge},
}


@article{nagajwocjanzhang09qma,
title = {Fast amplification of {QMA}},
author = {Daniel Nagaj and Pawel Wocjan and Yong Zhang},
journal = QuantumInfComput,
number = {11},
volume = {9},
year = {2011},
pages = {1053-1068},
eprint = {acm:2012106, arXiv:0904.1549},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@inproceedings{reichardtspalek08spanprogram,
title = {Span-program-based quantum algorithm for evaluating formulas},
author = {Ben W. Reichardt and Robert {\v S}palek},
rating = {5},
crossref = {pstoc08},
pages = {103-112},
Eprint = {arXiv:0710.2630v3},
doi = {10.1145/1374376.1374394},
}

@article{ambainischildsreichardtspalekzhang07andor,
title = {Any {AND-OR} formula of size {$N$} can be evaluated in time {${N}^{1/2+o(1)}$} on a quantum computer},
author = {Andris Ambainis and Andrew M. Childs and Ben W. Reichardt and Robert {\v S}palek and Shengyu Zhang},
volume = {39},
journal = SIAMJComput,
number = {6},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/FOCS.2007.10}{FOCS'07}},
year = {2010},
pages = {2513-2530},
doi = {10.1137/080712167},
}
%
@inproceedings{ambainischildsreichardtspalekzhang07andor-conference,
  author    = {Andris Ambainis and
               Andrew M. Childs and
               Ben Reichardt and
               Robert {\v S}palek and
               Shengyu Zhang},
  title     = {Any AND-OR Formula of Size N can be Evaluated in time N$^{\mbox{1/2+o(1)}}$
               on a Quantum Computer},
  crossref = {pfocs07},
  doi        = {10.1109/FOCS.2007.10},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@techreport{reichardt09spanprogram-arxivandfocs,
title = {Span programs and quantum query complexity: {T}he general adversary bound is nearly tight for every boolean function (70 pp.)},
author = {\noopsort{Ben Reichardt09}{Ben W. Reichardt}},
rating = {5},
pages  = {70},
eprint = {arxiv:0904.2759}, 
note = {Extended abstract in \href{http://dx.doi.org/10.1109/FOCS.2009.55}{FOCS'09}},
year = {2009},
keywords = {span programs},
}

@unpublished{reichardt09unbalancedformula,
title = {Span-program-based quantum algorithm for evaluating unbalanced formulas},
author = {\noopsort{Ben Reichardt11c}{Ben W. Reichardt}},
note = {6th Conf. Theory of Quantum Computation, Communication and Cryptography (TQC)},
Eprint = {arXiv:0907.1622},
year = {2011},
keywords = {span programs},
}

@inproceedings{reichardt10advtight,
title = {Reflections for quantum query algorithms},
author = {\noopsort{Ben Reichardt11b}{Ben Reichardt}},
crossref = {psoda11},
pages = {560-569},
eprint = {acm:2133080, arXiv:1005.1601},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{allenderbealsogihara99span,
title = {The Complexity of Matrix Rank and Feasible Systems of Linear Equations},
author = {Eric Allender and Robert Beals and Mitsunori Ogihara},
journal = ccomplex,
number = {2},
volume = {8},
year = {1999},
pages = {99-126},
doi = {10.1007/s000370050023},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/237814.237856}{STOC'96}},
bibsource = {DBLP, http://dblp.uni-trier.de},
}
%
@inproceedings{allenderbealsogihara99span-conference,
title = {The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract)},
author = {Eric Allender and Robert Beals and Mitsunori Ogihara},
crossref = {pstoc96},
pages = {161-167},
doi = {10.1145/237814.237856},
}

@article{babaigalwigderson99superpolyspanprogram,
title = {Superpolynomial Lower Bounds for Monotone Span Programs},
author = {L{\'a}szl{\'o} Babai and Anna G{\'a}l and Avi Wigderson},
journal = combinatorica,
number = {3},
volume = {19},
year = {1999},
pages = {301-319},
doi = {10.1007/s004930050058},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/237814.238010}{STOC'96}},
bibsource = {DBLP, http://dblp.uni-trier.de},
}
%
@inproceedings{babaigalwigderson99superpolyspanprogram-conference,
title = {Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs},
author = {L{\'a}szl{\'o} Babai and Anna G{\'a}l and J{\'a}nos Koll{\'a}r and Lajos R{\'o}nyai and Tibor Szab{\'o} and Avi Wigderson},
crossref = {pstoc96},
pages = {603-611},
doi = {10.1145/237814.238010},
}

@article{beimelgalpaterson96spanprogram,
title = {Lower bounds for monotone span programs},
author = {Amos Beimel and Anna G{\'a}l and Mike Paterson},
volume = {6},
journal = ccomplex,
number = {1},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1995.492669}{FOCS'95}},
year = {1996},
pages = {29-45},
doi = {10.1007/BF01202040},
bibsource = {DBLP, http://dblp.uni-trier.de},
} 
%
@inproceedings{beimelgalpaterson96spanprogram-conference,
title = {Lower Bounds for Monotone Span Programs},
author = {Amos Beimel and Anna G{\'a}l and Mike Paterson},
crossref = {pfocs95},
pages = {674-681},
doi = {10.1109/SFCS.1995.492669},
}

@inproceedings{nikovnikovapreneel05spanprogram,
title = {On the Size of Monotone Span Programs},
author = {Ventzislav Nikov and Svetla Nikova and Bart Preneel},
booktitle = {4th Internat. Conf. on Security in Communication Networks (SCN'04)},
publisher = springer,
year = {2004},
pages = {249-262},
doi = {10.1007/978-3-540-30598-9\_18},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@inproceedings{cramerfehr02secretshare,
title = {Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups},
author = {Ronald Cramer and Serge Fehr},
booktitle = {22nd Ann. Internat. Cryptology Conf. (CRYPTO'02)},
publisher = springer,
year = {2002},
pages = {272-287},
doi = {10.1007/3-540-45708-9\_18},
bibsource = {DBLP, http://dblp.uni-trier.de},
}



@book{golubvanloan96matrixcomputations,
title = {Matrix Computations},
author = {Gene~H. Golub and Charles~F. {Van Loan}},
publisher = {Johns Hopkins},
edition = {3rd},
year = {1996},
address = {Baltimore},
}

@unpublished{hoyerleespalek07negativeadvurl,
Title = {Source codes of semidefinite programs for {ADV$^{\pm}$}},
author = {Peter H{\o}yer and Troy Lee and Robert {\v S}palek},
note = {\href{http://www.ucw.cz/~robert/papers/adv/}{[Link]}},
year = {2006},
}
%
@inproceedings{barnumsaksszegedy03adv,
title = {Quantum query complexity and semi-definite programming},
author = {Howard Barnum and Michael Saks and Mario Szegedy},
booktitle = ccc03,
publisher = ieee,
year = {2003},
pages = {179-193},
doi = {10.1109/CCC.2003.1214419},
}
%
@inproceedings{karchmerwigderson93span,
title = {On Span Programs},
author = {Mauricio Karchmer and Avi Wigderson},
booktitle = ccc93,
publisher = ieee,
year = {1993},
pages = {102-111},
doi = {10.1109/SCT.1993.336536},
}

@inproceedings{jayramkumarsivakumar03majority,
title = {Two applications of information complexity},
author = {T. S. Jayram and Ravi Kumar and D. Sivakumar},
crossref = {pstoc03},
pages = {673-682},
doi = {10.1145/780542.780640},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@inproceedings{szegedy04walkfocs,
title = {Quantum Speed-Up of {M}arkov Chain Based Algorithms},
author = {Mario Szegedy},
crossref = {pfocs04},
pages = {32-41},
Eprint = {arXiv:quant-ph/0401053},
doi = {10.1109/FOCS.2004.53},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{bb:size-depth,
title = {Size-depth tradeoffs for {Boolean} formulae},
author = {Maria~Luisa~Bonet and Samuel~R.~Buss},
journal = ipl,
number = {3},
volume = {49},
year = {1994},
pages = {151-155},
doi = {10.1016/0020-0190(94)90093-0},
}

@article{fgg:and-or,
title = {A Quantum Algorithm for the {H}amiltonian {NAND} Tree},
author = {Edward Farhi and Jeffrey Goldstone and Sam Gutmann},
journal = {Theory of Computing},
number = {1},
volume = {4},
year = {2008},
pages = {169-190},
doi = {10.4086/toc.2008.v004a008},
bibsource = {DBLP, http://dblp.uni-trier.de},
}


@article{ccjy:and-or,
title = {Discrete-Query Quantum Algorithm for {NAND} Trees},
author = {Andrew M. Childs and Richard Cleve and Stephen P. Jordan and David L. Yonge-Mallo},
journal = {Theory of Computing},
number = {1},
volume = {5},
year = {2009},
pages = {119-123},
doi = {10.4086/toc.2009.v005a005},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{bce:size-depth,
title = {Size-Depth Tradeoffs for Algebraic Formulas},
author = {Nader H. Bshouty and Richard Cleve and Wayne Eberly},
journal = SIAMJComput,
volume = {24},
number = {4},
year = {1995},
pages = {682-705},
doi = {10.1137/S0097539792232586},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1991.185387}{FOCS'91}},
}
%
@inproceedings{bce:size-depth-conf,
title = {Size-Depth Tradeoffs for Algebraic Formulae},
author = {Nader H. Bshouty and Richard Cleve and Wayne Eberly},
crossref = {pfocs91},
pages = {334-341},
doi = {10.1109/SFCS.1991.185387},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{bs:q-read-once,
title = {A lower bound on the quantum query complexity of read-once functions},
author = {Howard Barnum and Michael Saks},
journal = jcss,
number = {2},
volume = {69},
year = {2004},
pages = {244--258},
doi = {10.1016/j.jcss.2004.02.002},
Eprint = {arXiv:quant-ph/0201007},
bibsource = {DBLP, http://dblp.uni-trier.de},
} 

@article{santha:and-or,
  author    = {Miklos Santha},
  title     = {On the {M}onte {C}arlo Boolean Decision Tree Complexity of Read-Once
               Formulae},
  journal   = RandomStructuresAlgorithms,
  volume    = {6},
  number    = {1},
  year      = {1995},
  pages     = {75-88},
  doi = {10.1002/rsa.3240060108},
  Note = {Preliminary version in \href{http://dx.doi.org/10.1109/SCT.1991.160259}{Structure in Complexity Theory'91}},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
%
%
@inproceedings{santha:and-or-conference,
  author    = {Miklos Santha},
  title     = {On the Monte Carlo Boolean Decision Tree Complexity of Read-Once
               Formulae},
  booktitle = ccc91,
  publisher = ieee,
  year      = {1991},
  pages     = {180-187},
  doi       = {10.1109/SCT.1991.160259},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{snir:dec,
title = {Lower Bounds on Probabilistic Linear Decision Trees},
author = {Marc Snir},
journal = tcs,
volume = {38},
year = {1985},
pages = {69-82},
doi = {10.1016/0304-3975(85)90210-5},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@inproceedings{sw:and-or,
title = {Probabilistic {Boolean} Decision Trees and the Complexity of Evaluating Game Trees},
author = {Michael E. Saks and Avi Wigderson},
crossref = {pfocs86},
pages = {29-38},
doi = {10.1109/SFCS.1986.44},
bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{ambainis06polynomial,
title = {Polynomial degree vs. quantum query complexity},
author = {Andris Ambainis},
journal = jcss,
number = {2},
volume = {72},
year = {2006},
pages = {220-238},
doi = {10.1016/j.jcss.2005.06.006},
eprint = {arXiv:quant-ph/0305028},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.2003.1238197}{FOCS'03}},
bibsource = {DBLP, http://dblp.uni-trier.de},
}
%
@inproceedings{ambainis06polynomial-conference,
title = {Polynomial Degree vs. Quantum Query Complexity},
author = {Andris Ambainis},
crossref = {pfocs03},
pages = {230-239},
doi = {10.1109/SFCS.2003.1238197},
}

@proceedings{pstoc96,
  booktitle = stoc96,
  year      = {1996},
  publisher = acm,
}
@proceedings{pstoc03,
  booktitle = stoc03,
  year      = {2003},
  publisher = acm,
}
@proceedings{pstoc07,
  booktitle = stoc07,
  year      = {2007},
  publisher = acm,
}
@proceedings{pstoc08,
  booktitle = stoc08,
  year      = {2008},
  publisher = acm,
}
@proceedings{pstoc12,
  booktitle = stoc12,
  year      = {2012},
  publisher = acm,
}

@proceedings{pfocs86,
 booktitle=focs86,
 year={1986},
 publisher=ieee,
}
@proceedings{pfocs91,
 booktitle=focs91,
 year={1991},
 publisher=ieee,
}
@proceedings{pfocs95,
 booktitle=focs95,
 year={1995},
 publisher=ieee,
}
@proceedings{pfocs03,
 booktitle=focs03,
 year={2003},
 publisher=ieee,
}
@proceedings{pfocs04,
 booktitle=focs04,
 year={2004},
 publisher=ieee,
}
@proceedings{pfocs07,
 booktitle=focs07,
 year={2007},
 publisher=ieee,
}
@proceedings{pfocs11,
 booktitle=focs11,
 year={2011},
 publisher=ieee,
}

@proceedings{psoda11,
  booktitle = soda11,
  year = {2011},
  publisher = acm,
}
