Reports

(I do not list those that are in Conferences or Journals)

1. Relativizations Comparing NP and Exponential Time, Computer Science Department TR-15-83, Harvard Univ., 1983.
2. A Recursion Theoretic View of Van Der Waerden's Theorem, Computer Science Department TR-10-84, Harvard Univ., 1984.
3. Clock versus Vacation Schedules (with Y. Levy), Bell Labs TR, Aug. 1984.
4. Recursion Theoretic Techniques in Complexity Theory and Combinatorics (Ph.D), Computer Science Department TR-17-85, Harvard Univ., 1985.
5. More on the Random Oracle Hypothesis: What is True Almost Always is Not Necessarily So. Computer Science Department TR-1956, The Univ. of Maryland, 1985.
6. Relativized Space with Immunity Computer Science Department TR-1957, The Univ. of Maryland, 1985.
7. A Hierarchy of Functions with Applications to Recursive Graph Theory, Computer Science Department TR-1651, The Univ. of Maryland, 1985.
8. The Complexity of Optimization Functions, Computer Science Department TR-1652, The Univ. of Maryland, 1985.
9. Learning Concepts from Subconcepts (with C. Smith), Computer Science Department TR-1747, The Univ. of Maryland, 1986.
10. Polynomial Terse Sets (with A. Amir), Computer Science Department TR-1782, (also UMIACS TR-87-1), The Univ. of Maryland, 1987.
11. Recursion Theoretic Properties of Minimal Honest Polynomial Degrees. (with Steven Homer), Computer Science Department TR-1803, The Univ. of Maryland, 1987.
12. Applications of Binary Search to Recursive Graph Theory, Computer Science Department TR-1804, The Univ. of Maryland, 1987.
13. Supportive and Parallel-Supportive Sets (with R. Beigel and L. Hay) Computer Science Department TR-1805, The Univ. of Maryland, 1987.
14. Terse, Superterse, and Verbose Sets (with R. Beigel, J. Gill, and J. Owings) Computer Science Department TR-1806, The Univ. of Maryland, 1987.
15. Nondeterministic Bounded Query Reducibilities (with R. Beigel, and J. Owings) Computer Science Department TR-1857, The Univ. of Maryland, 1987.
16. Training Sequences (with Dana Angluin and C. Smith) Computer Science Department TR-1894, The Univ. of Maryland, 1987.
17. Embedding the Three Element Chain Into the Turing Degrees: An Exposition (with David Kamishlian), Computer Science Department TR-2027, The Univ. of Maryland, 1987.
18. The Complexity of Optimization Problems related to Partition (with S. Pearlman) Computer Science Department TR-2028, The Univ. of Maryland, 1988.
19. The Existence of Matchings for Recursive and Highly Recursive Bipartite Graphs (with M. Lockwood) Computer Science Department TR-2029, The Univ. of Maryland, 1988.
20. Complexity Issues in Skeletal Automata (with L. Fass) Computer Science Department TR-2035, The Univ. of Maryland, 1988.
21. On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case (with R. Beigel), Computer Science TR-2036, The Univ. of Maryland, 1988.
22. Cheatable, P-terse, and P-superterse Sets (with R. Beigel and A. Amir) Computer Science Department TR-2090, The Univ. of Maryland, 1988.
23. Learning via Queries (with C. Smith) Computer Science Department TR-2148, (also UMIACS TR-88-89) The Univ. of Maryland, 1988.
24. On Honest Polynomial Reductions, Relativizations, and P=NP (with R. Downey, S. Homer, and M. Moses), Computer Science Department TR-2219, (also UMIACS TR-89-36) The Univ. of Maryland, 1989.
25. The Mapmaker's Dilemma (with R. Beigel) Computer Science Department TR 2262, (also UMIACS TR 89-59) The Univ. of Maryland, 1989
26. On Checking Versus Evaluation of Multiple Queries (with Lane Hemachandra and Albrech Hoene), Department of Computer Science technical report TR-323, Univ. of Rochester, 1990.
27. Learning via Queries in [+,<] (with M. Pleszkoch and R. Solovay), Department of Computer Science TR 2472 (also UMIACS TR 90-70), The Univ. of Maryland, 1990.
28. Selection Problems via k-ary Queries (with K. Guimaraes and Jim Purtilo), Department of Computer Science TR 2535 (also UMIACS TR 90-121), The Univ. of Maryland, 1990.
29. Frequency Computation and Bounded Queries (with R. Beigel and E. Kinber), Department of Computer Science TR 3187 (also UMIACS TR 93-128), The Univ. of Maryland, 1993. (Also on Electronic Colloquium on Computational Complexity. (www.eccc.uni-trier.de/eccc/), TR95-036).
30. Addition in $\log_2 n + O(1)$ steps on average (with R. Beigel, M. Ling, and L. Zhang). Electronic Colloquium on Computational Complexity. (www.eccc.uni-trier.de/eccc/) TR96-051. 1996.
31. Some connections between bounded query classes and Non-uniform complexity (long version). (with A. Amir, R. Beigel). Electronic Colloquium on Computational Complexity. (www.eccc.uni-trier.de/eccc/) TR00-024. 1996.
32. The Communication Complexity of Enumeration, Elimination, and Selection (with Andris Ambainis, Harry Buhrman, Bala Kalyanasundaram, Leen Torenvliet) Electronic Colloquium on Computational Complexity. (www.eccc.uni-trier.de/eccc/) TR01-019. 2001.
33. A Nearly tight bound for private information retrieval. (with R. Beigel and L. Fortnow) Electronic Colloquium on Computational Complexity. (www.eccc.uni-trier.de/eccc/) TR03-087. 2003.
34. Lower bounds on the Deterministic and Quantum Communication Complexity of $HAM_n^a$. (with A. Ambainis, A. Srinivasan, A. Utis) Electronic Colloquium on Computational Complexity. (www.eccc.uni-trier.de/eccc/) TR04-120. 2004.