Bibliography of papers by Robert Spalek

Bibliography items for my scientific papers

@UNPUBLISHED{spalek:d-degree,
 AUTHOR    = "R. {\v S}palek",
 TITLE     = "Adversary Lower Bound for the Orthogonal Array Problem",
 YEAR      = 2013,
 NOTE      = "arXiv:1304.0845 [quant-ph]"
}

@INPROCEEDINGS{bs:k-sum,
 AUTHOR    = "A. Belovs and R. {\v S}palek",
 TITLE     = "Adversary Lower Bound for the $k$-sum Problem",
 BOOKTITLE = "Proc. of 4th ACM ITCS",
 PAGES     = "323--328",
 YEAR      = 2013,
 COMMENT   = "arXiv:1206.6528 [quant-ph]"
}

@INPROCEEDINGS{lmrss:state-conversion,
 AUTHOR    = "T. Lee and R. Mittal and B. W. Reichardt and R. {\v S}palek and M. Szegedy",
 TITLE     = "Quantum query complexity of state conversion",
 BOOKTITLE = "Proc. of 52nd IEEE FOCS",
 PAGES     = "344--353",
 YEAR      = 2011,
 COMMENT   = "arXiv:1011.3020 [quant-ph]"
}

@UNPUBLISHED{spalek:dualor,
 AUTHOR    = "R. {\v S}palek",
 TITLE     = "A Dual Polynomial for {OR}",
 YEAR      = 2008,
 NOTE      = "arXiv:0803.4516 [cs.CC]"
}

@INPROCEEDINGS(spalek:multadv,
    author = "R. {\v S}palek",
    title = "The Multiplicative Quantum Adversary",
    booktitle = "Proc. of 23rd IEEE Complexity",
    year = 2008,
    pages = "237--248",
    comment = "quant-ph/0703237"
)

@INPROCEEDINGS(lss:discdpt,
    author = "T. Lee and A. Shraibman and R. {\v S}palek",
    title = "A direct product theorem for discrepancy",
    booktitle = "Proc. of 23rd IEEE Complexity",
    year = 2008,
    pages = "71--80"
)

@INPROCEEDINGS(rs:span-stoc,
    author = "B. Reichardt and R. {\v S}palek",
    title = "Span-program-based quantum algorithm for evaluating formulas",
    booktitle = "Proc. of 40th ACM STOC",
    year = 2008,
    pages = "103--112",
    comment = "arXiv:0710.2630 [quant-ph]"
)

@ARTICLE(rs:span-toc,
    author = "B. Reichardt and R. {\v S}palek",
    title = "Span-program-based quantum algorithm for evaluating formulas",
    journal = "Theory of Computing",
    volume = 8,
    number = 13,
    pages = "291--319",
    year = 2012,
    note = "Earlier version in STOC'08",
    comment = "arXiv:0710.2630 [quant-ph]"
)

@INPROCEEDINGS{acrsz:andor-focs,
 AUTHOR    = "A. Ambainis and A. Childs and B. Reichardt and R. {\v{S}}palek and S. Zhang",
 TITLE     = "Any {AND-OR} formula of size {$N$} can be evaluated in time {$N^{1/2+o(1)}$} on a quantum computer",
 BOOKTITLE = "Proc. of 48th IEEE FOCS",
 PAGES	   = "363--372",
 YEAR      = 2007,
 comment   = "quant-ph/0703015 and quant-ph/0704.3628"
}

@ARTICLE{acrsz:andor-siamjc,
 AUTHOR    = "A. Ambainis and A. Childs and B. Reichardt and R. {\v{S}}palek and S. Zhang",
 TITLE     = "Any {AND-OR} formula of size {$N$} can be evaluated in time {$N^{1/2+o(1)}$} on a quantum computer",
 JOURNAL   = "SIAM Journal on Computing",
 VOLUME    = 39,
 NUMBER    = 6,
 PAGES     = "2513--2530",
 YEAR      = 2010,
 NOTE      = "Special issue of FOCS'07"
}

@INPROCEEDINGS{hls:madv,
    author = "P. H{\o}yer and T. Lee and R. {\v{S}}palek",
    title = "Negative weights make adversaries stronger",
    booktitle = "Proc. of 39th ACM STOC",
    year = 2007,
    pages = "526--535",
    comment = "quant-ph/0611054"
}

@UNPUBLISHED{hls:compose,
 AUTHOR    = "P. H{\o}yer and T. Lee and R. {\v{S}}palek",
 TITLE     = "Tight adversary bounds for composite functions",
 YEAR      = 2005,
 NOTE      = "quant-ph/0509067",
}

@ARTICLE(asw:symmdpt-alg,
    author = "A. Ambainis and R. {\v S}palek and Wolf, R. {de}",
    title = "A new quantum lower bound method, with applications to direct
    product theorems and time-space tradeoffs",
    journal = "Algorithmica",
    volume = 55,
    number = 3,
    pages = "422--461",
    year = 2009,
    note = "Earlier version in STOC'06",
    comment = "quant-ph/0511200",
)

@INPROCEEDINGS(asw:symmdpt-stoc,
    author = "A. Ambainis and R. {\v S}palek and Wolf, R. de",
    title = "A new quantum lower bound method, with applications to direct
    product theorems and time-space tradeoffs",
    booktitle = "Proc. of 38th ACM STOC",
    year = 2006,
    pages = "618--633",
    comment = "quant-ph/0511200"
)

@INPROCEEDINGS{as:flows,
 AUTHOR    = "A. Ambainis and R. {\v{S}}palek",
 TITLE     = "Quantum Algorithms for Matching and Network Flows",
 BOOKTITLE = "Proc. of 23rd STACS",
 YEAR      = 2006,
 PAGES     = "172--183",
 NOTE      = "LNCS 3884",
 comment   = "quant-ph/0508205"
}

@INPROCEEDINGS{bs:matrix,
 AUTHOR    = "H. Buhrman and R. {\v{S}}palek",
 TITLE     = "Quantum Verification of Matrix Products",
 BOOKTITLE = "Proc. of 17th ACM-SIAM SODA",
 YEAR      = 2006,
 PAGES     = "880--889",
 comment   = "quant-ph/0409035",
}

@ARTICLE{hs:survey-lb,
  author = "P. H{\o}yer and R. {\v{S}}palek",
  title = "Lower Bounds on Quantum Query Complexity",
  journal = "EATCS Bulletin",
  volume = 87,
  pages = "78--103",
  year = "October, 2005"
}

@ARTICLE(ss:adversary-toc,
      author = "R. {\v S}palek and M. Szegedy",
      title = "All Quantum Adversary Methods are Equivalent",
      journal = "Theory of Computing",
      volume = 2,
      number = 1,
      pages = "1--18",
      year = 2006,
      note = "Earlier version in ICALP'05",
      comment = "quant-ph/0409116"
)

@INPROCEEDINGS(ss:adversary-icalp,
      author = "R. {\v S}palek and M. Szegedy",
      title = "All Quantum Adversary Methods are Equivalent",
      booktitle = "Proc. of 32nd ICALP",
      year = 2005,
      pages = "1299--1311",
      note = "LNCS 3580",
      comment = "quant-ph/0409116"
)

@INPROCEEDINGS{ksw:dpt-focs,
 AUTHOR    = "H. Klauck and R. {\v{S}}palek and Wolf, R. {de}",
 TITLE     = "Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs",
 BOOKTITLE = "Proc. of 45th IEEE FOCS",
 YEAR      = 2004,
 pages	   = "12--21",
 comment   = "quant-ph/0402123",
}

@ARTICLE(ksw:dpt-siamjc,
 AUTHOR    = "H. Klauck and R. {\v{S}}palek and Wolf, R. {de}",
 TITLE     = "Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs",
 JOURNAL   = "SIAM Journal on Computing",
 VOLUME    = 36,
 NUMBER    = 5,
 PAGES     = "1472--1493",
 YEAR      = 2007,
 NOTE      = "Earlier version in FOCS'04"
)

@ARTICLE(hs:qncwf-toc,
	author = "P. H{\o}yer and R. {\v S}palek",
	title = "Quantum Fan-out is Powerful",
	journal = "Theory of Computing",
	volume = 1,
	number = 5,
	pages = "81--103",
	year = 2005,
	note = "Earlier version in STACS'03",
	comment = "quant-ph/0208043"
)

@INPROCEEDINGS(spalek:qncwf-stacs,
	author = "P. H{\o}yer and R. {\v S}palek",
	title = "Quantum circuits with unbounded fan-out",
	booktitle = "Proc. of 20th STACS",
	year = "2003",
	pages = "234--246",
	note = "LNCS 2607"
)

@PHDTHESIS(spalek:phd,
    author = "R. {\v S}palek",
    title = "Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs",
    school = "CWI and ILLC, Universiteit van Amsterdam",
    address = "Amsterdam",
    year = 2006,
    note = "\url{http://www.ucw.cz/~robert/papers/phd-thesis.pdf}"
)

@MASTERSTHESIS(spalek:thesis-qncwf-uploaded,
	author = "R. {\v S}palek",
	title = "Quantum circuits with unbounded fan-out",
	school = "Faculty of Sciences, Vrije Universiteit",
	address = "Amsterdam",
	year = "2002",
	note = "\url{http://www.ucw.cz/~robert/qncwf/}.  Shorter version and improved results in quant-ph/0208043"
)

@MASTERSTHESIS(spalek:thesis-qbp,
	author = "R. {\v S}palek",
	title = "Space Complexity of Quantum Computation",
	school = "Faculty of Mathematics and Physics, Charles University",
	address = "Prague",
	year = "2002",
	note = "\url{http://www.ucw.cz/~robert/qbp/}"
)