Harry Buhrman
![](cwi_logo.gif)
Department INS4
Address CWI
Kruislaan 413
P.O. Box 94079
1090 GB Amsterdam
The Netherlands
Office M265
Telephone 020-5924076 (+31 20 5924076)
Telefax 020-5924199 (+31 20 5924199)
E-mail Harry.Buhrman@cwi.nl
Research Interests
Computational Complexity Theory
- Buhrman H.,
L. Fortnow and L. Torenvliet,"Using Autoreducibility to Separate Complexity
Classes" (FOCS'95)
- Buhrman H., E.
Hemaspaandra and L. Longpre,"SPARSE reduces conjunctively to TALLY"
(STRUCTURES'93 to appear in SIAM J. on Comp.)
- Buhrman H. and
S. Homer,"Superpolynomial Circuits, Almost Sparse Oracles and the Exponential
Hierarchy" (FST&TCS'92)
- Buhrman H. and M.
Hermo,"On the Sparse Set Conjecture for Sets with Low Density" (STACS'95)
- Buhrman H.,
A. Hoene and L. Torenvliet,"Splittings, Robustness and Structure of Complete
Sets" (STACS'93)
- Buhrman H., J.
Kadin and T. Thierauf,"On Functions Computable with Nonadaptive Queries to
NP" (STRUCTURES'94)
- Buhrman H., E.
Mayordomo,"An Excursion To The Kolmogorov Random Strings" (STRUCTURES'95)
- Buhrman H. and
P. Orponen,"Random Strings Make Hard Instances" (STRUCTURES'94, to
appear in JCSS)
- Buhrman H., E.
Spaan and L. Torenvliet, "Bounded Reductions" (STACS'91, in Complexity
Theory, 1993 Cambridge University Press pp83--99)
- Buhrman H., E.
Spaan and L. Torenvliet,"The relative power of logspace and polynomial time
reductions" (Comp. Compl. 1993, Vol 3 Nr 3 pp231--244)
- Buhrman H. and
L. Torenvliet,"On the Cutting Edge of Relativization: The Resource Bounded
Injury Method" (ICALP'94)
- Buhrman
H. and L. Torenvliet,"P-selective Self-reducible sets: A New Characterization
of P" (STRUCTURES'93, to appear in JCSS)
- Buhrman H.
and L. Torenvliet,"On the structure of complete sets" (STRUCTURES'94)
- Buhrman
H., L. Torenvliet and P. van Emde Boas,"Twenty Questions to a P-selector" (IPL
1993, Vol 4 Nr 4 pp201--204)
Distributed Computing
- Buhrman H.,
J.A. Garay and J.-H. Hoepman, "Optimal Resiliency agains Mobile
Faults" (FTCS-25, 1995)
- Buhrman H., J.A. Garay,J.-H. Hoepman, and M. Moir, "Long-Lived Renaming Made Fast" (PODC95)
Learning Theory
- Balcazar J., H.
Buhrman and M. Hermo,"Learnability of Kolmogorov-Easy Circuit Expressions Via
Queries" (Eurocolt'95)
My Thesis
obtain a copy
buhrman@cwi.nl
Last Updated 21/07/95
CWI DISCLAIMER