Harry Buhrman

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