Articles in or Submitted to Refereed Journals

1. Relativizations Comparing NP and Exponential Time (with S. Homer), Information and Control, Vol. 58, July 1983, pp. 88-100.
2. Oracles for Deterministic vs. Alternating Classes, SIAM Journal of Computing, Vol. 16, Aug 1987, pp. 613-627.
3. Polynomial Terse Sets (with A. Amir), Information and Computation, Vol. 77, No. 1, 1988, pp. 37-56.
4. Nondeterministic Bounded Query Reducibilities (with R. Beigel, and J. Owings), Annals of Pure and Applied Logic, Vol. 41, 1989, pp. 107-118.
5. Training Sequences (with D. Angluin and C. Smith), Theoretical Computer Science, Vol. 66, 1989, pp. 255-272. TRAINING
6. On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case (with R. Beigel), Annals of Pure and Applied Logic, Vol. 45, 1989, pp. 1-38. RCHROM
7. On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case (with R. Beigel), Annals of Pure and Applied Logic, Vol. 45, 1989, pp. 227-247.
8. Bounded Query Classes and the Difference Hierarchy (with R. Beigel and L. Hay), Archive for Math. Logic, Vol. 29, 1989, pp. 69-84. BDQDIFF
9. The Mapmaker's Dilemma (with R. Beigel), Discrete Applied Math (Special Issue on Theoretical Computer Science), Vol. 34, 1991, pp. 37-48. MAP
10. On Selecting the $k$ Largest with Restricted Quadratic Queries, Information Processing Letters, Vol. 38, 1991, pp. 193-195.
11. Learning via Queries to $[+,<]$ (with M. Pleszkoch and R. Solovay), Journal of Symbolic Logic, Vol. 57, 1992, pp. 53-81. LVQPLUS
12. Learning Programs with an Easy to Calculate Set of Errors (with Rameshkumar Sitarman, C. Smith, and Mahendran Velauthapillai), Fundamentica Informaticae, Vol. 16, No. 3-4, pp. 355-370, 1992. ERRORS
13. Learning via Queries (with C. Smith), Journal of the Association of Computing Machinery, Vol. 39, 1992, pp. 649-675. LVQ
14. Selection Problems using $m$-ary queries (with K. Guimaraes and J. Purtilo), Computational Complexity, Vol. 2, 1992, pp. 256-276. ARITY
15. Terse, Superterse, and Verbose Sets (with R. Beigel, J. Gill, and J. Owings), Information and Computation, Vol. 103, 1993, pp. 68-85, 1993. BDQTERSE
16. On Checking Versus Evaluation of Multiple Queries (with Lane Hemachandra and Albrech Hoene), Information and Computation, Vol. 105, 1993, pp. 72-93. CHECK
17. Extremes in the Degrees of Inferability (with L. Fortnow, S. Jain, E. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman, F. Stephan, R. Solovay), Annals of Pure and Applied Logic, Vol. 66, 1994, pp. 231-276. EXTREMES
18. On Honest Polynomial Reductions and P$=$NP (with R. Downey, and M. Moses), Annals of Pure and Applied Logic, Vol. 70, 1994, pp. 1-27.
19. Learning via Queries with Teams and Anomalies (with E. Kinber, M. Pleszkoch, C. Smith, and T. Zeugmann), Fundamenta Informaticae, Vol. 23, Number 1, May 1995, pp. 67-89. LVQTEAMS
20. Recursion theoretic models of learning: some results and intuitions, (with C. Smith) Annals of Mathematics and Artificial Intelligence, Vol. 15, II, 1995, pp. 155-166. MODELS
21. OptP-Completeness as the Normal Behavior of NP-Complete Problems (with M. Krentel and K. Rappoport), Math Systems Theory, Vol. 28, 1995, 487-514 OPT
22. Frequencey Computation and Bounded Queries (with R. Beigel and E. Kinber) Theoretical Computer Science, Vol. 163, 1996, 177-192. FREQ
23. Bounded Queries and Approximation (with R. Chang and C. Lund), SIAM Journal of Computing, Vol. 26, 1997, 188-209 APPROX
24. Binary search and recursive graph problems (with K. Guimaraes) Theoretical Computer Science Vol 181, 1997, 119-139. (Special issue for LATIN 95 conference). BINARY
25. Asking Questions Versus Verifiability (with M. Velauthapillai), Fundamenta Informaticae Vol. 30, 1-9, 1997 VERIFY
26. Addition in $\log_2{n} + O(1)$ Steps on Average: A Simple Analysis (with R. Beigel, M. Li, L. Zhang), Theoretical Computer Science. Vol 191, 1998, 245-248. ADD
27. Relative Sizes of Learnable Sets (with L. Fortnow, R. Freivalds, M. Kummer, S. Kurtz, C. Smith, and F. Stephan), Theoretical Computer Science Vol 197(1-2):139-156, 1998. SIZE
28. Recursion theory and Reverse Mathematics (with Jeffery Hirst). Mathematical Logic Quarterly. Vol. 44, 1998, 465-473. REVERSE
29. On the Finiteness of the Recursive Chromatic Number (with A. Lee). Annals of Pure and Applied Logic Vol. 93, 73-81, 1998. FINITE
30. Classification via Information (with M. Plezskoch, M. Velauthapillai, and F. Stephan), Annals of Mathematics and Artificial Intelligence. Vol. 23, 147-168, 1998. CLASSIFICATION
31. On the Number of Automorphisms of a Graph (with R. Beals, R. Chang and J. Toran), Chicago Journal of Theory. Feburary 1999. GRAPHAUTO
32. The Complexity of ${\rm ODD}_n^A$ (with R. Beigel, M. Kummer, G. Martin, T. McNichol, and F. Stephan) Journal of Symbolic Logic, Vol. 65, 1-18, 2000. ODD
33. Automata Techniques for Query Inference Machines (with G. Hird), Annals of Pure and Applied Logic Vol. 117, 171-203, 2002. QUERY
34. When can one load a set of dice so that the sum is uniformily distributed? (with C. Kruskal) Mathematics Magazine. Vol. 72, No. 2, 1999, pp 133-138. DICE
35. The Communication Complexity of Enumeration, Elimination, and Selection (with Andris Ambainis, Harry Buhrman, Bala Kalyanasundaram, Leen Torenvliet) Vol 63., pages 148-185, 2001. (Special issue for COMPLEXITY 2000). COMM
36. Some connections between bounded query classes and non-uniform complexity (with A. Amir and R. Beigel), NONUNIFORM