Communication Complexity Lower Bounds by Polynomials Proceedings of the 16th IEEE Annual Conference on Computational Complexity (CCC'01), pp.120-130, 2001
Quantum Algorithms for Element Distinctness Proceedings of the 16th IEEE Annual Conference on Computational Complexity (CCC'01), pp.131-137, 2001.
Time and Space Bounds for Reversible Simulation Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP'01), 1017-1027, 2001
Bounds for Small-Error and Zero-Error Quantum Algorithms Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99) pp. 358-368, 1999
Quantum Bounded Query Complexity Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC99), pp. 149-157, IEEE Computer Society, May 4-6 1999
Quantum Lower Bounds by Polynomials Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS'98) pp. 351--362, 1998
Quantum vs. Classical Communication and Computation Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98), pp. 63-68, ACM Press, May 23-26 1998
Quantum Fingerprinting Physiscal Review Letters, 87(16), October 2001
Quantum Lower Bounds by Polynomials Journal of the ACM, to appear
Time and space bounds for reversible simulation Journal of Physics A: Mathematical and General, 34(2001), 6821--6830, 2001
Quantum Entanglement and Communication Complexity SIAM Journal on Computing (to appear)
A Lower Bound for Quantum Search of an Ordered List Information Processing Letters, Vol 70 (5), pp. 205-209, 1999
Multiparty Quantum Communication Complexity Physical Review A, Vol 60 (4), pp. 2737-2741, 1999
Substituting quantum entanglement for communication Physical Review A, Vol 56 (2) pp. 1201 -- 1204, August 1997
On the importance of having an identity or, is consensus really Universal Distributed Computing Conference (DISC'00), Lecture Notes in Computer Science, Vol. 1914, Springer-Verlag, Berlin, 134--148, 2000
Mutual Search Proceedings 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98), pp. 481--489, 1998
Optimal Routing Tables Proceedings 15th Annual ACM Symposium on Principles of Distributed Computing (PODC96), ACM Press, Philadelphia, PA, pp. 134 -- 142, 1996
Long-Lived Renaming Made Fast Proceedings 14th Annual ACM Symposium on Principles of Distributed Computing (PODC95), ACM Press, Ottawa, Canada, pp. 194 -- 203, 1995
Optimal Resiliency Against Mobile Faults Proceedings 25th International Symposium on Fault-Tolerant Computing (FTCS95), Pasadena, CA, pp.83 -- 88 , 1995
Mutual Search Journal of the ACM, Vol 46 (4), pp. 517-536, 1999
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method SIAM Journal on Computing Vol 28 (4) pp. 1414-1432, 1999
The Communication Complexity of Enumeration, Elimination, and Selection Proceedings of the 15th Annual IEEE Conference on Computational Complexity (CCC'2000), pp44-53, 2000
Are bitvectors optimal? Proceedings of the 32th Annual ACM Symposium on Theory of Computing (STOC'2000) pp. 449-458, 2000
Optimal Proof Systems and Sparse Sets Proceedings 17th Symposium on Theoretical Aspects of Computer Science (STACS'2000) pp. 407-418, 2000
Complicated Complementations Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC99), pp. 227-236, IEEE Computer Society, May 4-6 1999
Randomness is Hard Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC98), pp. 249-260, IEEE Computer Society, June 15-18 1998
Two Queries Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC98), pp. 13-19, IEEE Computer Society, June 15-18 1998
Nonrelativizing Separations Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC98), pp. 8-12, IEEE Computer Society, June 15-18 1998
NP Might Not Be As Easy As Detecting Unique Solutions Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC98), pp. 203-208, ACM Press, May 23-26 1998
The Complexity of Generating and Checking Proofs of Membership Proceedings 13th Symposium on Theoretical Aspects of Computer Science (STACS96), Lecture Notes in Computer Science, Springer, Grenoble, France, pp 75 -- 87, 1996
Using Autoreducibility to Separate Complexity Classes Proceedings 36th Annual Symposium on Foundations of Computer Science (FOCS95), IEEE Computer Society Press, Milwaukee, WI, pp. 520 -- 527, 1995
On the Sparse Set Conjecture for Sets with Low Density Proceedings 12th Symposium on Theoretical Aspects of Computer Science (STACS95), Lecture Notes in Computer Science, Springer-Verlag, München, Germany, pp. 609 -- 618, 1995
On Functions Computable with Nonadaptive Queries to NP Proceedings Structure in Complexity Theory, 9th annual conference (STRUCTURES94), IEEE Computer Society Press, Amsterdam, pp.43--52, 1994
On the Cutting Edge of Relativization: The Resource Bounded Injury Method Proceedings 21st Annual International Colloquium on Automata, Languages and Programming (ICALP94), Lecture Notes in Computer Science, Springer, Jerusalem, Israel, pp. 263 -- 273, 1994
P-selective selfreducible Sets: A new Characterization of P Proceedings Structure in Complexity Theory, 8th annual conference (STRUCTURES93), IEEE Computer Society Press, San Diego, CA pp.52--64, 1993
SPARSE reduces conjunctively to TALLY Proceedings Structure in Complexity Theory, 8th annual conference (STRUCTURES93), IEEE Computer Society Press, San Diego, CA, pp.208--214, 1993 preprint: Report NU-CCS-92-8, College of Computer Science, Northeastern University, Boston, MA
Splittings, robustness and structure of complete sets Proceedings 10th Symposium Theoretical Aspects of Computer Science (STACS93), Lecture Notes in Computer Science, Springer-Verlag, Würzburg, Germany, pp.175--184, 1993
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy Proceedings 12th Conference on the Foundations of Software Technology & Theoretical Computer Science (FSTTCS92), Lecture Notes in Computer Science, Springer-Verlag, New Delhi, India pp.116--127, 1992 preprint: Boston University Tech Report 91-005, 1991
Bounded Reductions Proceedings 8th Symposium Theoretical Aspects of Computer Science (STACS91), Lecture Notes in Computer Science, Springer-Verlag, Hamburg, Germany pp.410--421, 1991 preprint: ITLI-CT-90-04, 1990
Bounding the number of oracle queries for self-reducible sets Proceedings CSN90 Uitgave SION pp.79--93, 1990
A comparison of reductions on nondeterministic space Proceedings CSN89 Uitgave SION pp.191--102, 1989 preprint: Report ITLI-CT-89-04
Two oracles that force a big crunch Computational Complexity, 2001. To appear.
The communication complexity of enumeration, elimination and selection Journal of Computer and System Sciences, special issue of CCC'2000, to appear
Randomness is Hard SIAM Journal on Computing, 30(5): 1485--1501, 2000
Separating complexity classes using autoreducibilty SIAM Journal on Computing, Vol 29(5), pp. 1497-1520, 2000
Two Queries Journal of Computer and System Sciences, Vol 59(2) pp.182-194, 1999 special issue for selected papers from the 13th annual conference on Structural Complexity Theory
On Functions Computable with Nonadaptive Queries to NP Theory of Computing Systems, Vol 31(1), pp. 77-92, 1998
Splittings, Robustness and Structure of Complete Sets SIAM Journal on Computing, Vol 2(3), pp. 637-653, 1998
SPARSE reduces conjunctively to TALLY SIAM Journal on Computing, 24 - 4, 673--681, 1995
P-selective selfreducible Sets are Easy Journal of Computer and System Sciences 53-2, pp 210 -- 217, 1996 special issue for selected papers from the 8th annual conference on Structural Complexity Theory
Twenty Questions to a P-selector Information Processing Letters 48 - 4, 201-204, 1993
The relative power of logspace and polynomial time reductions Journal of Computational Complexity 3, 231-244, 1993
Bounded Reductions Complexity Theory: Current Research, 83--99, Cambridge University press 1993. preprint: ITLI-CT-90-04, 1990
On complete sets for nondeterministic classes Mathematical Systems Theory 24, 179-200, 1991. preprint: Boston University Tech Report 90-013, 1990
New Bounds for the Language Compression Problem Proceedings of the 15th Annual IEEE Conference on Computational Complexity (CCC'2000), to appear
New applications of the incompressibility method Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP99), Lecture Notes in Computer Science Vol 1644, pp 220-230, 1999
Hard Sets are Hard to Find Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC98), pp. 170-181, IEEE Computer Society, June 15-18 1998.
One-sided Versus Two-sided Randomness Proceedings 16th Symposium on Theoretical Aspects of Computer Science (STACS99), Vol 1563, pp. 100-109, 1999
A Generalization of Resource-Bounded Measure, With an Application Proceedings 15th Symposium on Theoretical Aspects of Computer Science (STACS98), pp. 161-171, 1998
Kolmogorov random graphs and the incompressibility method Proceedings of Conference on Compression and Complexity of Sequences (SEQUENCES'97), IEEE Computer Society Press, Positano, Italy, pp. 87-96, 1997
Results on Resource-Bounded Measure Proceedings 24th International Colloquium on Automata, Languages, and Programming (ICALP'97), Lecture Notes in Computer Science, Springer, Bologna, Italy, pp 188 -- 194, 1997
Resource-Bounded Kolmogorov Complexity Revisited Proceedings 14th Symposium on Theoretical Aspects of Computer Science (STACS97), Lecture Notes in Computer Science, Springer, Lübeck, Germany, pp 105 -- 116, 1997
Compressibility and Resource Bounded Measure Proceedings 13th Symposium on Theoretical Aspects of Computer Science (STACS96), Lecture Notes in Computer Science, Springer, Grenoble, France, pp. 13 -- 24 1996.
An excursion to the Kolmogorov Random Strings Proceedings Structure in Complexity Theory, 10th annual conference (STRUCTURES95), IEEE Computer Society Press, Minneapolis, MN, pp. 197 -- 205, 1995
Random Strings Make Hard Instances Proceedings Structure in Complexity Theory, 9th annual conference (STRUCTURES94), IEEE Computer Society Press, Amsterdam, pp.217--223, 1994
Resource-bounded Kolmogorov complexity revisited SIAM Journal on Computing, 2001, To appear
Compressibility and Resource Bounded Measure SIAM Journal on Computing, To appear
A Generalization of Resource-Bounded Measure, With an Application to the BPP vs. EXP Problem SIAM Journal on Computing 30(2): 576-601, 2000
New applications of the incompressibility method: Part II Theoretical Computer Science, 235:1, 59--70, 2000
Kolmogorov Random Graphs and the Incompressibility Method SIAM Journal on Computing, Vol 29(2), pp. 590-599, 1999
Hard Sets are Hard to Find Journal of Computer and System Sciences, Vol 59(2), pp. 327-345, 1999 special issue for selected papers from the 13th annual conference on Structural Complexity Theory
An excursion to the Kolmogorov Random Strings Journal of Computer and System Sciences, Vol 54(2), pp. 393-399, 1997 special issue for selected papers from the 10th annual conference on Structural Complexity Theory
Random Strings Make Hard Instances Journal of Computer and System Science, 53-2, pp. 261 -- 266, 1996 special issue for selected papers from the 9th annual conference on Structural Complexity Theory
Learnability of Kolmogorov-Easy Circuit Expressions Via Queries Proceedings 2nd European Conference on Learning Theory (EUROCOLT95), Lecture Notes in Artificial Intelligence, Springer, Barcelona, Spain, pp. 112 -- 124, 1995
Quantum Computing and Communication Complexity Bulletin of the European Association for Theoretical Computer Science (EATCS), No. 70, pp 131 -- 141, February 2000
On the structure of complete sets Proceedings Structure in Complexity Theory, 9th annual conference (STRUCTURES94), IEEE Computer Society Press, Amsterdam, pp.118--133, 1994
Complete sets and structure in subrecursive classes Proceedings of the 1996 Logic Colloquium (LC96) of the European Chapter of the Association for Symbolic Logic, Lecture Notes in Logic 12, pp45-78, 1998
Six Hypotheses in Search of a Theorem Proceedings Computational Complexity Theory, 12th annual conference, IEEE Computer Science Press, Ulm, 1997 pp. 2 --12, 1997.
Characterizing the Learnability of Kolmogorov Easy Circuit Expressions NeuroCOLT Technical Report NC-TR-96-020, 1996
On Honestly Iteratively Enumerable Sets Technische Universität Berlin, Tech Report 92-34, 1992
On adaptive resource bounded computations preprint: Report ITLI-CT-89-09, 1989
A Short Note on Shor's Factoring Algorithm SIGACT News Vol 27 Nr.1 March 1996 pp 89 -- 90.