Harry Buhrman Home Page Coauthor index DBLP Vis pubzone.org

List of publications from the DBLP Bibliography Server - FAQ
Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

DBLP keys2010
140Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46(1): 143-156 (2010)
2009
139Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209
138Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings CoRR abs/0912.3162: (2009)
2008
137no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLManindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008
136Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, John M. Hitchcock: NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. IEEE Conference on Computational Complexity 2008: 1-7
135Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Michal Koucký, Nikolai K. Vereshchagin: Randomised Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331
134Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, John M. Hitchcock: NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electronic Colloquium on Computational Complexity (ECCC) 15(022): (2008)
133Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman: Foreword. J. Comput. Syst. Sci. 74(3): 297 (2008)
132Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)
2007
131Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin: High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379
130Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLManindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
129Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLManindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
128Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir: High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity 2007
127Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
126Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf: On Computation and Communication with Small Bias. IEEE Conference on Computational Complexity 2007: 24-32
125Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman: On Computation and Communication with Small Bias. SAGA 2007: 1
124Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007)
123Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379-395 (2007)
2006
122Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger: New Limits on Fault-Tolerant Quantum Computation. FOCS 2006: 411-419
121Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Robert Spalek: Quantum verification of matrix products. SODA 2006: 880-889
120Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet, Falk Unger: Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. STACS 2006: 455-468
119Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEric Allender, Harry Buhrman, Michal Koucký: What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Logic 138(1-3): 2-19 (2006)
118Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi: On the importance of having an identity or, is consensus really universal?. Distributed Computing 18(3): 167-176 (2006)
117Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting onto functions might not be hard. Electronic Colloquium on Computational Complexity (ECCC) 13(024): (2006)
116Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006)
2005
115no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Thomas Thierauf: Algebraic Methods in Computational Complexity, 10.-15. October 2004 IBFI, Schloss Dagstuhl, Germany 2005
114Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman: Quantum Computing. CiE 2005: 68-68
113Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
112Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. STACS 2005: 593-604
111no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: A Post's Program for Complexity Theory. Bulletin of the EATCS 85: 41-51 (2005)
110Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Troy Lee, Dieter van Melkebeek: Language compression and pseudorandom generators. Computational Complexity 14(3): 228-255 (2005)
109Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf: Quantum Algorithms for Element Distinctness. SIAM J. Comput. 34(6): 1324-1330 (2005)
108Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Aduri Pavan: Some Results on Derandomization. Theory Comput. Syst. 38(2): 211-227 (2005)
2004
107Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Thomas Thierauf: 04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004
106Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: Separating Complexity Classes Using Structural Properties. IEEE Conference on Computational Complexity 2004: 130-138
105Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Troy Lee, Dieter van Melkebeek: Language Compression and Pseudorandom Generators. IEEE Conference on Computational Complexity 2004: 15-28
104Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping. IEEE Conference on Computational Complexity 2004: 250-259
103Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30
102Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEric Allender, Harry Buhrman, Michal Koucký: What Can be Efficiently Reduced to the K-Random Strings? STACS 2004: 584-595
101Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLTroy Lee, Dieter van Melkebeek, Harry Buhrman: Language Compression and Pseudorandom Generators Electronic Colloquium on Computational Complexity (ECCC)(002): (2004)
100Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRichard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet: Enumerations of the Kolmogorov Function Electronic Colloquium on Computational Complexity (ECCC)(015): (2004)
99Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEric Allender, Harry Buhrman, Michal Koucký: What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electronic Colloquium on Computational Complexity (ECCC)(044): (2004)
98Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC)(081): (2004)
2003
97Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Hein Röhrig: Distributed Quantum Computing. MFCS 2003: 1-20
96Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum property testing. SODA 2003: 480-488
95Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Aduri Pavan: Some Results on Derandomization. STACS 2003: 212-222
94Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Richard Chang, Lance Fortnow: One Bit of Advice. STACS 2003: 547-558
93Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity CoRR cs.CC/0304012: (2003)
92Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping CoRR quant-ph/0304112: (2003)
91Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Quantum Algorithms and Polynomials CoRR quant-ph/0309220: (2003)
90Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: Quantum zero-error algorithms cannot be composed. Inf. Process. Lett. 87(2): 79-84 (2003)
2002
89Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. FOCS 2002: 669-678
88Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi: On the Importance of Having an Identity or, is Consensus really Universal? CoRR cs.DC/0201006: (2002)
87Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: Quantum Zero-Error Algorithms Cannot be Composed CoRR quant-ph/0211029: (2002)
86Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek: Power from Random Strings Electronic Colloquium on Computational Complexity (ECCC)(028): (2002)
85Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are Bitvectors Optimal? SIAM J. Comput. 31(6): 1723-1744 (2002)
84no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1): 21-43 (2002)
2001
83Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation. ICALP 2001: 1017-1027
82Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: Communication Complexity Lower Bounds by Polynomials. IEEE Conference on Computational Complexity 2001: 120-130
81Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf: Quantum Algorithms for Element Distinctness. IEEE Conference on Computational Complexity 2001: 131-137
80no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman: Quantum Computing and Communication Complexity. Current Trends in Theoretical Computer Science 2001: 664-679
79Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation CoRR quant-ph/0101133: (2001)
78Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet: Two oracles that force a big crunch. Computational Complexity 10(2): 93-116 (2001)
77Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet: The Communication Complexity of Enumeration, Elimination, and Selection Electronic Colloquium on Computational Complexity (ECCC) 8(19): (2001)
76Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRobert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM 48(4): 778-797 (2001)
75no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet: The Communication Complexity of Enumeration, Elimination, and Selection. J. Comput. Syst. Sci. 63(2): 148-185 (2001)
74Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Luc Longpré: Compressibility and Resource Bounded Measure. SIAM J. Comput. 31(3): 876-886 (2001)
73Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Sophie Laplante: Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. 31(3): 887-905 (2001)
2000
72Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi: On the Importance of Having an Identity or is Consensus Really Universal? DISC 2000: 134-148
71Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Sophie Laplante, Peter Bro Miltersen: New Bounds for the Language Compression Problem. IEEE Conference on Computational Complexity 2000: 126-130
70Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet: The Communication Complexity of Enumeration, Elimination, and Selection. IEEE Conference on Computational Complexity 2000: 44-53
69Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek: Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418
68Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are bitvectors optimal? STOC 2000: 449-458
67no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman: Quantum Computing and Communication Complexity. Bulletin of the EATCS 70: 131-141 (2000)
66no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet: Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (2000)
65no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss: A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. SIAM J. Comput. 30(2): 576-601 (2000)
64Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: Randomness is Hard. SIAM J. Comput. 30(5): 1485-1501 (2000)
63Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Richard Cleve, Wim van Dam: Quantum Entanglement and Communication Complexity. SIAM J. Comput. 30(6): 1829-1841 (2000)
62Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi: New applications of the incompressibility method: Part II. Theor. Comput. Sci. 235(1): 59-70 (2000)
1999
61Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka: Bounds for Small-Error and Zero-Error Quantum Algorithms. FOCS 1999: 358-368
60Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi: New Applications of the Incompressibility Method. ICALP 1999: 220-229
59Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Wim van Dam: Quantum Bounded Query Complexity. IEEE Conference on Computational Complexity 1999: 149-
58Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: Complicated Complementations. IEEE Conference on Computational Complexity 1999: 227-236
57Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow: One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109
56Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka: Bounds for Small-Error and Zero-Error Quantum Algorithms CoRR cs.CC/9904019: (1999)
55Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: Communication Complexity Lower Bounds by Polynomials CoRR cs.CC/9910010: (1999)
54Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi: Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method CoRR cs.DC/9903009: (1999)
53Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi: Mutual Search CoRR cs.DS/9902005: (1999)
52Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Wim van Dam: Quantum Bounded Query Complexity CoRR quant-ph/9903035: (1999)
51Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: A Lower Bound for Quantum Search of an Ordered List. Inf. Process. Lett. 70(5): 205-209 (1999)
50Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi: Mutual Search. J. ACM 46(4): 517-536 (1999)
49no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow: Two Queries. J. Comput. Syst. Sci. 59(2): 182-194 (1999)
48no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Dieter van Melkebeek: Hard Sets Are Hard to Find. J. Comput. Syst. Sci. 59(2): 327-345 (1999)
47no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi: Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method. SIAM J. Comput. 28(4): 1414-1432 (1999)
46no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi: Kolmogorov Random Graphs and the Incompressibility Method. SIAM J. Comput. 29(2): 590-599 (1999)
1998
45Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRobert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum Lower Bounds by Polynomials. FOCS 1998: 352-361
44Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow: Two Queries. IEEE Conference on Computational Complexity 1998: 13-
43Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Dieter van Melkebeek: Hard Sets are Hard to Find. IEEE Conference on Computational Complexity 1998: 170-181
42Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: Randomness is Hard. IEEE Conference on Computational Complexity 1998: 249-260
41Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Thomas Thierauf: Nonrelativizing Separations. IEEE Conference on Computational Complexity 1998: 8-12
40Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi: Mutual Search (Extended Abstract). SODA 1998: 481-489
39Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss: A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). STACS 1998: 161-171
38Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRichard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208
37Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Richard Cleve, Avi Wigderson: Quantum vs. Classical Communication and Computation. STOC 1998: 63-68
36Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi: New Applications of the Incompressibility Method: Part II CoRR cs.CC/9809060: (1998)
35Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRobert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum Lower Bounds by Polynomials CoRR quant-ph/9802049: (1998)
34Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Ronald de Wolf: Lower Bounds for Quantum Search and Derandomization CoRR quant-ph/9811046: (1998)
33Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar: A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem Electronic Colloquium on Computational Complexity (ECCC) 5(58): (1998)
32no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Albrecht Hoene, Leen Torenvliet: Splittings, Robustness, and Structure of Complete Sets. SIAM J. Comput. 27(3): 637-653 (1998)
31no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Jim Kadin, Thomas Thierauf: Functions Computable with Nonadaptive Queries to NP. Theory Comput. Syst. 31(1): 77-92 (1998)
1997
30Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Stephen A. Fenner, Lance Fortnow: Results on Resource-Bounded Measure. ICALP 1997: 188-194
29Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Leen Torenvliet: Six Hypotheses in Search of a Theorem. IEEE Conference on Computational Complexity 1997: 2-12
28Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow: Resource-Bounded Kolmogorov Complexity Revisited. STACS 1997: 105-116
27no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. J. Comput. Syst. Sci. 54(3): 393-399 (1997)
1996
26no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi: Optimal Routing Tables. PODC 1996: 134-142
25Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Luc Longpré: Compressibility and Resource Bounded Measure. STACS 1996: 13-24
24Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Thomas Thierauf: The Complexity of Generating and Checking Proffs of Membership. STACS 1996: 75-86
23no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: P-Selektive Self-Reducible Sets: A New Characterization of P. J. Comput. Syst. Sci. 53(2): 210-217 (1996)
22no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Pekka Orponen: Random Strings Make Hard Instances. J. Comput. Syst. Sci. 53(2): 261-266 (1996)
21Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman: A short note on Shor's factoring algorithm. SIGACT News 27(1): 89-90 (1996)
1995
20no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJosé L. Balcázar, Harry Buhrman, Montserrat Hermo: Learnability of Kolmogorov-easy circuit expressions via queries. EuroCOLT 1995: 112-124
19no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Lance Fortnow, Leen Torenvliet: Using Autoreducibility to Separate Complexity Classes. FOCS 1995: 520-527
18no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Juan A. Garay, Jaap-Henk Hoepman: Optimal Resiliency against Mobile Faults. FTCS 1995: 83-88
17no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Juan A. Garay, Jaap-Henk Hoepman, Mark Moir: Long-Lived Renaming Made Fast. PODC 1995: 194-203
16Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Montserrat Hermo: On the Sparse Set Conjecture for Sets with Low Denisty. STACS 1995: 609-618
15no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. Structure in Complexity Theory Conference 1995: 197-203
14no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Edith Hemaspaandra, Luc Longpré: SPARSE Reduces Conjunctively to TALLY. SIAM J. Comput. 24(4): 673-681 (1995)
1994
13Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: On the Cutting Edge of Relativization: The Resource Bounded Injury Method. ICALP 1994: 263-273
12no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet: On the Structure of Complete Sets. Structure in Complexity Theory Conference 1994: 118-133
11no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Pekka Orponen: Random Strings Make Hard Instances. Structure in Complexity Theory Conference 1994: 217-222
10no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Jim Kadin, Thomas Thierauf: On Functions Computable with Nonadaptive Queries to NP. Structure in Complexity Theory Conference 1994: 43-52
1993
9Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Albrecht Hoene, Leen Torenvliet: Splittings, Robustness and Structure of Complete Sets. STACS 1993: 175-184
8no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Luc Longpré, Edith Spaan: SPARSE reduces conjunctively to TALLY. Structure in Complexity Theory Conference 1993: 208-214
7no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Peter van Helden, Leen Torenvliet: P-Selective Self-reducibles Sets: A New Characterization of P. Structure in Complexity Theory Conference 1993: 44-51
6no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Edith Spaan, Leen Torenvliet: The Relative Power of Logspace and Polynomial Time Reductions. Computational Complexity 3: 231-244 (1993)
5no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Leen Torenvliet, Peter van Emde Boas: Twenty Questions to a P-Selector. Inf. Process. Lett. 48(4): 201-204 (1993)
1992
4no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Edith Spaan, Leen Torenvliet: Bounded Reductions. Complexity Theory: Current Research 1992: 83-99
3Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Steven Homer: Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. FSTTCS 1992: 116-127
1991
2Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Edith Spaan, Leen Torenvliet: Bounded Reductions. STACS 1991: 410-421
1no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHarry Buhrman, Steven Homer, Leen Torenvliet: Completeness for Nondeterministic Complexity Classes. Mathematical Systems Theory 24(3): 179-200 (1991)

Coauthor Index

1Manindra Agrawal [129] [130] [137]
2Eric Allender [86] [89] [99] [102] [116] [119]
3Andris Ambainis [70] [75] [77] [92] [104]
4José L. Balcázar [20]
5Robert Beals [35] [45] [76]
6Richard Beigel [38] [100]
7Peter van Emde Boas [5]
8Richard Chang [94]
9Matthias Christandl [128] [131]
10Richard Cleve [35] [37] [45] [56] [61] [63] [76] [122]
11Wim van Dam [52] [59] [63]
12Yevgeniy Dodis [92] [104]
13Christoph Dürr [81] [109]
14Peter A. Fejer [100]
15Stephen A. Fenner [30] [69] [78]
16Lance Fortnow [19] [28] [29] [30] [38] [41] [44] [49] [57] [66] [69] [73] [78] [94] [95] [96] [98] [100] [107] [108] [113] [115] [117] [127] [129] [130] [132] [137] [138] [139] [140]
17Matthew K. Franklin [40] [50] [53]
18Juan A. Garay [17] [18] [40] [50] [53]
19William I. Gasarch [70] [75] [77]
20Piotr Grabowski [100]
21Mark Heiligman [81] [109]
22Peter van Helden [7]
23Edith Hemaspaandra (Edith Spaan) [2] [4] [6] [8] [14]
24Montserrat Hermo [16] [20]
25John M. Hitchcock [134] [136]
26Albrecht Hoene [9] [32]
27Jaap-Henk Hoepman [17] [18] [26] [40] [47] [50] [53] [54]
28Steven Homer [1] [3]
29Peter Høyer [81] [109]
30Tao Jiang [36] [60] [62]
31Jim Kadin [10] [31]
32Bala Kalyanasundaram [70] [75] [77]
33Hartmut Klauck [93] [103] [124]
34Michal Koucký [86] [89] [99] [102] [116] [117] [119] [127] [128] [131] [135] [138] [140]
35Sophie Laplante [71] [73]
36Monique Laurent [122]
37Troy Lee [101] [105] [110]
38Ming Li [36] [46] [60] [62]
39Noah Linden [122]
40Bruno Loff [138]
41Luc Longpré [8] [14] [25] [74] [100]
42Zvi Lotker [128] [131]
43Frédéric Magniez [81] [109]
44Elvira Mayordomo [15] [27]
45Dieter van Melkebeek [33] [39] [43] [48] [65] [66] [69] [86] [89] [101] [105] [110] [116]
46Peter Bro Miltersen [68] [71] [85]
47Mark Moir [17]
48Michele Mosca [35] [45] [76]
49Andrej Muchnik (Andrei A. Muchnik) [100]
50Ilan Newman [91] [96] [98] [112] [113] [123] [132]
51Pekka Orponen [11] [22]
52Alessandro Panconesi [72] [88] [118]
53Boaz Patt-Shamir [128] [131]
54Aduri Pavan [95] [108]
55Jaikumar Radhakrishnan [68] [85]
56Kenneth W. Regan [33] [39] [65]
57John D. Rogers [117] [127] [140]
58Hein Röhrig [91] [92] [96] [97] [104] [112] [123] [132]
59Detlef Ronneburger [86] [89] [116]
60Miklos Santha [81] [109]
61Rahul Santhanam [139]
62Alexander Schrijver [122]
63Riccardo Silvestri [72] [88] [118]
64D. Sivakumar [33] [39] [65]
65Robert Spalek [121]
66Frank Stephan [100]
67Martin Strauss (Martin J. Strauss) [33] [39] [65]
68Thomas Thierauf [10] [24] [31] [41] [107] [115] [129] [130] [137]
69Leen Torenvliet [1] [2] [4] [5] [6] [7] [9] [12] [13] [19] [23] [29] [32] [42] [58] [64] [66] [70] [75] [77] [78] [100] [106] [111] [120]
70John Tromp [40] [46] [50] [53] [79] [83]
71Falk Unger [120] [122]
72Srinivasan Venkatesh [68] [85]
73Nikolai K. Vereshchagin [93] [98] [103] [113] [117] [124] [126] [127] [128] [131] [135] [140]
74Paul M. B. Vitányi [26] [36] [40] [46] [47] [50] [53] [54] [60] [62] [72] [79] [83] [88] [93] [103] [118] [124]
75Avi Wigderson [37]
76Ronald de Wolf [34] [35] [45] [51] [55] [56] [61] [76] [81] [82] [84] [87] [90] [91] [109] [112] [123] [126]
77Christof Zalka [56] [61]

Colors in the list of coauthors

Copyright © Sun Mar 14 22:39:24 2010 by Michael Ley (ley@uni-trier.de)