Harry Buhrman - RankMe

214 papers A* 19A 46B 3C 1Misc 1Journal 115Unranked 25

Year	Rank	Type	Title / Venue / Authors
2026	—	`conf`	A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. SOSA Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2025	J	`jnl`	A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. CoRR Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2025	J	`jnl`	Formal Framework for Quantum Advantage. CoRR Harry Buhrman, Niklas Galke, Konstantinos Meichanetzidis
2025	—	`conf`	Quantum Catalytic Space. TQC Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, Quinten Tupker
2025	J	`jnl`	Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians. Quantum Harry Buhrman, Jonas Helsen, Jordi Weggemans
2024	A	`conf`	A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS Scott Aaronson, Harry Buhrman, William Kretschmer
2024	J	`jnl`	Beating Grover search for low-energy estimation and state preparation. CoRR Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2024	J	`jnl`	Classical versus quantum queries in quantum PCPs with classical proofs. CoRR Harry Buhrman, François Le Gall, Jordi Weggemans
2024	A	`conf`	Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). ITCS Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann
2024	J	`jnl`	Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians. CoRR Harry Buhrman, Jonas Helsen, Jordi Weggemans
2024	J	`jnl`	Relating non-local quantum computation to information theoretic cryptography. Quantum Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, Philip Verduyn Lunel
2024	J	`jnl`	State preparation by shallow circuits using feed forward. Quantum Harry Buhrman, Marten Folkertsma, Bruno Loff, Niels M. P. Neumann
2023	J	`jnl`	A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR Scott Aaronson, Harry Buhrman, William Kretschmer
2023	J	`jnl`	A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. Scott Aaronson, Harry Buhrman, William Kretschmer
2023	J	`jnl`	Noisy decoding by shallow circuits with parities: classical and quantum. CoRR Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann
2023	A	`conf`	Quantum Majority Vote. ITCS Harry Buhrman, Noah Linden, Laura Mancinska, Ashley Montanaro, Maris Ozols
2022	A	`conf`	Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. ITCS Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2022	J	`jnl`	Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. CoRR Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman
2022	—	`conf`	Memory Compression with Quantum Random-Access Gates. TQC Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2022	J	`jnl`	Memory Compression with Quantum Random-Access Gates. CoRR Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2021	A	`conf`	A Framework of Quantum Strong Exponential-Time Hypotheses. STACS Harry Buhrman, Subhasree Patro, Florian Speelman
2021	J	`jnl`	High Entropy Random Selection Protocols. Algorithmica Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
2021	J	`jnl`	Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks. CoRR Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2019	A	`conf`	Bounding Quantum-Classical Separations for Classes of Nonlocal Games. STACS Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee
2019	J	`jnl`	Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
2019	J	`jnl`	The Quantum Strong Exponential-Time Hypothesis. CoRR Harry Buhrman, Subhasree Patro, Florian Speelman
2018	J	`jnl`	Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
2018	J	`jnl`	Round elimination in exact communication complexity. CoRR Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman
2018	J	`jnl`	The Case for Quantum Software. ERCIM News Harry Buhrman, Floor van de Pavert
2017	A	`conf`	Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. ITCS Harry Buhrman, Matthias Christandl, Jeroen Zuiddam
2016	A	`conf`	Catalytic Space: Non-determinism and Hierarchy. STACS Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
2016	J	`jnl`	Distinguishing Two Probability Ensembles with One Sample from each Ensemble. Theory Comput. Syst. Luis Filipe Coelho Antunes, Harry Buhrman, Armando Matos, André Souto, Andreia Teixeira
2016	J	`jnl`	Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. CoRR Harry Buhrman, Matthias Christandl, Jeroen Zuiddam
2016	J	`jnl`	Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
2015	J	`jnl`	Entanglement-Assisted Zero-Error Source-Channel Coding. IEEE Trans. Inf. Theory Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan, Giannicola Scarpa
2015	J	`jnl`	Hardness of Approximation for Knapsack Problems. Theory Comput. Syst. Harry Buhrman, Bruno Loff, Leen Torenvliet
2015	—	`conf`	Round Elimination in Exact Communication Complexity. TQC Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman
2014	J	`jnl`	Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
2014	A*	`conf`	Computing with a full memory: catalytic space. STOC Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
2014	—	`conf`	On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. TQC Harry Buhrman, Serge Fehr, Christian Schaffner
2014	J	`jnl`	Position-Based Quantum Cryptography: Impossibility and Constructions. SIAM J. Comput. Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
2014	J	`jnl`	Reductions to the set of random strings: The resource-bounded case. Log. Methods Comput. Sci. Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2014	—	`ch.`	Turing in Quantumland. Turing's Legacy Harry Buhrman
2013	B	`conf`	Learning Reductions to Sparse Sets. MFCS Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
2013	J	`jnl`	Multipartite entanglement in XOR games. Quantum Inf. Comput. Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick
2013	A	`conf`	The garden-hose model. ITCS Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman
2013	J	`jnl`	The non-adaptive query complexity of testing k-parities. Chic. J. Theor. Comput. Sci. Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf
2013	A	`conf`	Towards a Reverse Newman's Theorem in Interactive Information Complexity. CCC Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
2012	J	`jnl`	Complete Insecurity of Quantum Protocols for Classical Two-Party Computation CoRR Harry Buhrman, Matthias Christandl, Christian Schaffner
2012	J	`jnl`	Near-Optimal and Explicit Bell Inequality Violations. Theory Comput. Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
2012	B	`conf`	Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2012	J	`jnl`	Reductions to the set of random strings: the resource-bounded case. Electron. Colloquium Comput. Complex. Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2012	J	`jnl`	The non-adaptive query complexity of testing k-parities CoRR Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf
2012	J	`jnl`	Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electron. Colloquium Comput. Complex. Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
2012	J	`jnl`	Violating the Shannon capacity of metric graphs with entanglement CoRR Jop Briët, Harry Buhrman, Dion Gijswijt
2011	A	`conf`	Near-Optimal and Explicit Bell Inequality Violations. CCC Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
2011	J	`jnl`	Position-Based Quantum Cryptography. ERCIM News Harry Buhrman, Serge Fehr, Christian Schaffner
2011	A*	`conf`	Position-Based Quantum Cryptography: Impossibility and Constructions. CRYPTO Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
2011	J	`jnl`	Some Mathematical Refinements Concerning Error Minimization in the Genetic Code. IEEE ACM Trans. Comput. Biol. Bioinform. Harry Buhrman, Peter T. S. van der Gulik, Steven Kelk, Wouter M. Koolen, Leen Stougie
2011	J	`jnl`	The Garden-Hose Game: A New Model of Computation, and Application to Position-Based Quantum Cryptography CoRR Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman
2010	J	`jnl`	A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electron. Colloquium Comput. Complex. Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek
2010	A	`conf`	Derandomizing from Random Strings. CCC Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
2010	J	`jnl`	Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2010	J	`jnl`	Learning parities in the mistake-bound model. Inf. Process. Lett. Harry Buhrman, David García-Soriano, Arie Matsliah
2010	J	`jnl`	Non-Uniform Reductions. Theory Comput. Syst. Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet
2010	J	`jnl`	Position-Based Quantum Cryptography: Impossibility and Constructions CoRR Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
2010	J	`jnl`	Position-Based Quantum Cryptography: Impossibility and Constructions. IACR Cryptol. ePrint Arch. Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
2010	J	`jnl`	Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
2009	J	`jnl`	Derandomizing from Random Strings CoRR Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
2009	—	`conf`	Learning Parities in the Mistake-Bound model. Algebraic Methods in Computational Complexity Harry Buhrman, David García-Soriano, Arie Matsliah
2009	J	`jnl`	Learning parities in the mistake-bound model. Electron. Colloquium Comput. Complex. Harry Buhrman, David García-Soriano, Arie Matsliah
2009	—	`conf`	Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009	—	`conf`	Unconditional Lower Bounds against Advice. ICALP (1) Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009	J	`jnl`	Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Rahul Santhanam
2008	—	`ed.`	Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2008	J	`jnl`	Foreword. J. Comput. Syst. Sci. Harry Buhrman
2008	A	`conf`	NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. CCC Harry Buhrman, John M. Hitchcock
2008	J	`jnl`	NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electron. Colloquium Comput. Complex. Harry Buhrman, John M. Hitchcock
2008	J	`jnl`	Quantum Property Testing. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
2008	A	`conf`	Randomised Individual Communication Complexity. CCC Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin
2007	—	`conf`	07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2007	—	`conf`	07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2007	—	`conf`	High Entropy Random Selection Protocols. APPROX-RANDOM Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
2007	—	`conf`	High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity Nikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir
2007	J	`jnl`	Individual communication complexity. J. Comput. Syst. Sci. Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2007	Misc	`conf`	Inverting Onto Functions and Polynomial Hierarchy. CSR Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2007	A	`conf`	On Computation and Communication with Small Bias. CCC Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf
2007	—	`conf`	On Computation and Communication with Small Bias. SAGA Harry Buhrman
2007	J	`jnl`	Quantum Information Processing. ERCIM News Bram Vermeer, Harry Buhrman
2007	J	`jnl`	Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
2006	J	`jnl`	Enumerations of the Kolmogorov function. J. Symb. Log. Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet
2006	J	`jnl`	Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2006	A*	`conf`	New Limits on Fault-Tolerant Quantum Computation. FOCS Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger
2006	J	`jnl`	On the importance of having an identity or, is consensus really universal?. Distributed Comput. Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi
2006	J	`jnl`	Power from Random Strings. SIAM J. Comput. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
2006	A*	`conf`	Quantum verification of matrix products. SODA Harry Buhrman, Robert Spalek
2006	A	`conf`	Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. STACS Harry Buhrman, Leen Torenvliet, Falk Unger
2006	J	`jnl`	What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Log. Eric Allender, Harry Buhrman, Michal Koucký
2005	J	`jnl`	A Post's Program for Complexity Theory. Bull. EATCS Harry Buhrman, Leen Torenvliet
2005	—	`ed.`	Algebraic Methods in Computational Complexity, 10.-15. October 2004 Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Thomas Thierauf
2005	A	`conf`	Increasing Kolmogorov Complexity. STACS Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2005	J	`jnl`	Language compression and pseudorandom generators. Comput. Complex. Harry Buhrman, Troy Lee, Dieter van Melkebeek
2005	J	`jnl`	Quantum Algorithms for Element Distinctness. SIAM J. Comput. Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf
2005	C	`conf`	Quantum Computing. CiE Harry Buhrman
2005	A	`conf`	Robust Polynomials and Quantum Algorithms. STACS Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
2005	J	`jnl`	Some Results on Derandomization. Theory Comput. Syst. Harry Buhrman, Lance Fortnow, Aduri Pavan
2004	—	`conf`	04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Thomas Thierauf
2004	J	`jnl`	Enumerations of the Kolmogorov Function Electron. Colloquium Comput. Complex. Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet
2004	J	`jnl`	Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2004	A	`conf`	Individual Communication Complexity: Extended Abstract. STACS Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2004	J	`jnl`	Language Compression and Pseudorandom Generators Electron. Colloquium Comput. Complex. Troy Lee, Dieter van Melkebeek, Harry Buhrman
2004	A	`conf`	Language Compression and Pseudorandom Generators. CCC Harry Buhrman, Troy Lee, Dieter van Melkebeek
2004	A	`conf`	Multiparty Quantum Coin Flipping. CCC Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig
2004	A	`conf`	Separating Complexity Classes Using Structural Properties. CCC Harry Buhrman, Leen Torenvliet
2004	A	`conf`	What Can be Efficiently Reduced to the K-Random Strings? STACS Eric Allender, Harry Buhrman, Michal Koucký
2004	J	`jnl`	What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electron. Colloquium Comput. Complex. Eric Allender, Harry Buhrman, Michal Koucký
2003	B	`conf`	Distributed Quantum Computing. MFCS Harry Buhrman, Hein Röhrig
2003	J	`jnl`	Individual Communication Complexity CoRR Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2003	J	`jnl`	Multiparty Quantum Coin Flipping CoRR Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig
2003	A	`conf`	One Bit of Advice. STACS Harry Buhrman, Richard Chang, Lance Fortnow
2003	A*	`conf`	Quantum property testing. SODA Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
2003	J	`jnl`	Quantum zero-error algorithms cannot be composed. Inf. Process. Lett. Harry Buhrman, Ronald de Wolf
2003	J	`jnl`	Robust Quantum Algorithms and Polynomials CoRR Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
2003	A	`conf`	Some Results on Derandomization. STACS Harry Buhrman, Lance Fortnow, Aduri Pavan
2002	J	`jnl`	Are Bitvectors Optimal? SIAM J. Comput. Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2002	J	`jnl`	Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. Harry Buhrman, Ronald de Wolf
2002	J	`jnl`	On the Importance of Having an Identity or, is Consensus really Universal? CoRR Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi
2002	J	`jnl`	Power from Random Strings Electron. Colloquium Comput. Complex. Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek
2002	A*	`conf`	Power from Random Strings. FOCS Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
2002	J	`jnl`	Quantum Zero-Error Algorithms Cannot be Composed CoRR Harry Buhrman, Ronald de Wolf
2001	A	`conf`	Communication Complexity Lower Bounds by Polynomials. CCC Harry Buhrman, Ronald de Wolf
2001	J	`jnl`	Compressibility and Resource Bounded Measure. SIAM J. Comput. Harry Buhrman, Luc Longpré
2001	A	`conf`	Quantum Algorithms for Element Distinctness. CCC Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf
2001	—	`ch.`	Quantum Computing and Communication Complexity. Current Trends in Theoretical Computer Science Harry Buhrman
2001	J	`jnl`	Quantum lower bounds by polynomials. J. ACM Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf
2001	J	`jnl`	Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Sophie Laplante
2001	J	`jnl`	The Communication Complexity of Enumeration, Elimination, and Selection Electron. Colloquium Comput. Complex. Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
2001	J	`jnl`	The Communication Complexity of Enumeration, Elimination, and Selection. J. Comput. Syst. Sci. Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
2001	J	`jnl`	Time and Space Bounds for Reversible Simulation CoRR Harry Buhrman, John Tromp, Paul M. B. Vitányi
2001	A*	`conf`	Time and Space Bounds for Reversible Simulation. ICALP Harry Buhrman, John Tromp, Paul M. B. Vitányi
2001	J	`jnl`	Two oracles that force a big crunch. Comput. Complex. Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet
2000	J	`jnl`	A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. SIAM J. Comput. Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
2000	A*	`conf`	Are bitvectors optimal? STOC Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2000	A	`conf`	New Bounds for the Language Compression Problem. CCC Harry Buhrman, Sophie Laplante, Peter Bro Miltersen
2000	J	`jnl`	New applications of the incompressibility method: Part II. Theor. Comput. Sci. Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi
2000	A	`conf`	On the Importance of Having an Identity or is Consensus Really Universal? DISC Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi
2000	A	`conf`	Optimal Proof Systems and Sparse Sets. STACS Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek
2000	J	`jnl`	Quantum Computing and Communication Complexity. Bull. EATCS Harry Buhrman
2000	J	`jnl`	Quantum Entanglement and Communication Complexity. SIAM J. Comput. Harry Buhrman, Richard Cleve, Wim van Dam
2000	J	`jnl`	Randomness is Hard. SIAM J. Comput. Harry Buhrman, Leen Torenvliet
2000	J	`jnl`	Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet
2000	A	`conf`	The Communication Complexity of Enumeration, Elimination, and Selection. CCC Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
1999	J	`jnl`	A Lower Bound for Quantum Search of an Ordered List. Inf. Process. Lett. Harry Buhrman, Ronald de Wolf
1999	J	`jnl`	Bounds for Small-Error and Zero-Error Quantum Algorithms CoRR Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka
1999	A*	`conf`	Bounds for Small-Error and Zero-Error Quantum Algorithms. FOCS Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka
1999	J	`jnl`	Communication Complexity Lower Bounds by Polynomials CoRR Harry Buhrman, Ronald de Wolf
1999	A	`conf`	Complicated Complementations. CCC Harry Buhrman, Leen Torenvliet
1999	J	`jnl`	Hard Sets Are Hard to Find. J. Comput. Syst. Sci. Harry Buhrman, Dieter van Melkebeek
1999	J	`jnl`	Kolmogorov Random Graphs and the Incompressibility Method. SIAM J. Comput. Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi
1999	J	`jnl`	Mutual Search CoRR Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi
1999	J	`jnl`	Mutual Search. J. ACM Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi
1999	A*	`conf`	New Applications of the Incompressibility Method. ICALP Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi
1999	A	`conf`	One-sided Versus Two-sided Error in Probabilistic Computation. STACS Harry Buhrman, Lance Fortnow
1999	J	`jnl`	Quantum Bounded Query Complexity CoRR Harry Buhrman, Wim van Dam
1999	A	`conf`	Quantum Bounded Query Complexity. CCC Harry Buhrman, Wim van Dam
1999	J	`jnl`	Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method CoRR Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi
1999	J	`jnl`	Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method. SIAM J. Comput. Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi
1999	J	`jnl`	Two Queries. J. Comput. Syst. Sci. Harry Buhrman, Lance Fortnow
1998	J	`jnl`	A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem Electron. Colloquium Comput. Complex. Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar
1998	A	`conf`	A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). STACS Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
1998	J	`jnl`	Functions Computable with Nonadaptive Queries to NP. Theory Comput. Syst. Harry Buhrman, Jim Kadin, Thomas Thierauf
1998	A	`conf`	Hard Sets are Hard to Find. CCC Harry Buhrman, Dieter van Melkebeek
1998	J	`jnl`	Lower Bounds for Quantum Search and Derandomization CoRR Harry Buhrman, Ronald de Wolf
1998	A*	`conf`	Mutual Search (Extended Abstract). SODA Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi
1998	A*	`conf`	NP Might Not Be As Easy As Detecting Unique Solutions. STOC Richard Beigel, Harry Buhrman, Lance Fortnow
1998	J	`jnl`	New Applications of the Incompressibility Method: Part II CoRR Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi
1998	A	`conf`	Nonrelativizing Separations. CCC Harry Buhrman, Lance Fortnow, Thomas Thierauf
1998	J	`jnl`	Quantum Lower Bounds by Polynomials CoRR Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf
1998	A*	`conf`	Quantum Lower Bounds by Polynomials. FOCS Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf
1998	A*	`conf`	Quantum vs. Classical Communication and Computation. STOC Harry Buhrman, Richard Cleve, Avi Wigderson
1998	A	`conf`	Randomness is Hard. CCC Harry Buhrman, Leen Torenvliet
1998	J	`jnl`	Splittings, Robustness, and Structure of Complete Sets. SIAM J. Comput. Harry Buhrman, Albrecht Hoene, Leen Torenvliet
1998	A	`conf`	Two Queries. CCC Harry Buhrman, Lance Fortnow
1997	J	`jnl`	An Excursion to the Kolmogorov Random Strings. J. Comput. Syst. Sci. Harry Buhrman, Elvira Mayordomo
1997	—	`conf`	Kolmogorov random graphs. SEQUENCES Harry Buhrman, Ming Li, Paul M. B. Vitányi
1997	A	`conf`	Resource-Bounded Kolmogorov Complexity Revisited. STACS Harry Buhrman, Lance Fortnow
1997	A*	`conf`	Results on Resource-Bounded Measure. ICALP Harry Buhrman, Stephen A. Fenner, Lance Fortnow
1997	A	`conf`	Six Hypotheses in Search of a Theorem. CCC Harry Buhrman, Lance Fortnow, Leen Torenvliet
1996	J	`jnl`	A short note on Shor's factoring algorithm. SIGACT News Harry Buhrman
1996	A	`conf`	Compressibility and Resource Bounded Measure. STACS Harry Buhrman, Luc Longpré
1996	A*	`conf`	Optimal Routing Tables. PODC Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi
1996	J	`jnl`	P-Selektive Self-Reducible Sets: A New Characterization of P. J. Comput. Syst. Sci. Harry Buhrman, Leen Torenvliet
1996	J	`jnl`	Random Strings Make Hard Instances. J. Comput. Syst. Sci. Harry Buhrman, Pekka Orponen
1996	A	`conf`	The Complexity of Generating and Checking Proffs of Membership. STACS Harry Buhrman, Thomas Thierauf
1995	—	`conf`	An Excursion to the Kolmogorov Random Strings. SCT Harry Buhrman, Elvira Mayordomo
1995	—	`conf`	Learnability of Kolmogorov-easy circuit expressions via queries. EuroCOLT José L. Balcázar, Harry Buhrman, Montserrat Hermo
1995	A*	`conf`	Long-Lived Renaming Made Fast. PODC Harry Buhrman, Juan A. Garay, Jaap-Henk Hoepman, Mark Moir
1995	A	`conf`	On the Sparse Set Conjecture for Sets with Low Denisty. STACS Harry Buhrman, Montserrat Hermo
1995	—	`conf`	Optimal Resiliency against Mobile Faults. FTCS Harry Buhrman, Juan A. Garay, Jaap-Henk Hoepman
1995	J	`jnl`	SPARSE Reduces Conjunctively to TALLY. SIAM J. Comput. Harry Buhrman, Edith Hemaspaandra, Luc Longpré
1995	A*	`conf`	Using Autoreducibility to Separate Complexity Classes. FOCS Harry Buhrman, Lance Fortnow, Leen Torenvliet
1994	—	`conf`	On Functions Computable with Nonadaptive Queries to NP. SCT Harry Buhrman, Jim Kadin, Thomas Thierauf
1994	A*	`conf`	On the Cutting Edge of Relativization: The Resource Bounded Injury Method. ICALP Harry Buhrman, Leen Torenvliet
1994	—	`conf`	On the Structure of Complete Sets. SCT Harry Buhrman, Leen Torenvliet
1994	—	`conf`	Random Strings Make Hard Instances. SCT Harry Buhrman, Pekka Orponen
1993	—	`conf`	P-Selective Self-reducibles Sets: A New Characterization of SCT Harry Buhrman, Peter van Helden, Leen Torenvliet
1993	—	`conf`	SPARSE reduces conjunctively to TALLY. SCT Harry Buhrman, Luc Longpré, Edith Spaan
1993	A	`conf`	Splittings, Robustness and Structure of Complete Sets. STACS Harry Buhrman, Albrecht Hoene, Leen Torenvliet
1993	J	`jnl`	The Relative Power of Logspace and Polynomial Time Reductions. Comput. Complex. Harry Buhrman, Edith Spaan, Leen Torenvliet
1993	J	`jnl`	Twenty Questions to a P-Selector. Inf. Process. Lett. Harry Buhrman, Leen Torenvliet, Peter van Emde Boas
1992	—	`conf`	Bounded Reductions. Complexity Theory: Current Research Harry Buhrman, Edith Spaan, Leen Torenvliet
1992	—	`conf`	Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. FSTTCS Harry Buhrman, Steven Homer
1991	A	`conf`	Bounded Reductions. STACS Harry Buhrman, Edith Spaan, Leen Torenvliet
1991	J	`jnl`	Completeness for Nondeterministic Complexity Classes. Math. Syst. Theory Harry Buhrman, Steven Homer, Leen Torenvliet