Articles in 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.
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.
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.
9. The Mapmaker's Dilemma (with R. Beigel), Discrete Applied Math (Special Issue on Theoretical Computer Science), Vol. 34, 1991, pp. 37-48.
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.
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.
13. Learning via Queries (with C. Smith), Journal of the Association of Computing Machinery, Vol. 39, 1992, pp. 649-675.
14. Selection Problems using m-ary queries (with K. Guimaraes and J. Purtilo), Computational Complexity, Vol. 2, 1992, pp. 256-276.
15. Terse, Superterse, and Verbose Sets (with R. Beigel, J. Gill, and J. Owings), Information and Computation, Vol. 103, 1993, pp. 68-85, 1993.
16. On Checking Versus Evaluation of Multiple Queries (with Lane Hemachandra and Albrech Hoene), Information and Computation, Vol. 105, 1993, pp. 72-93.
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.
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.
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.

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

22. Frequency Computation and Bounded Queries (with R. Beigel and E. Kinber) Theoretical Computer Science, Vol. 163, 1996, 177-192.

23. Bounded Queries and Approximation (with R. Chang and C. Lund), SIAM Journal of Computing, Vol. 26, 1997, 188-209

24. Binary search and recursive graph problems (with K. Guimaraes) Theoretical Computer Science Vol 181, 1997, 119-139. (Special issue for LATIN 95 conference).

25. Asking Questions Versus Verifiability (with M. Velauthapillai), Fundamenta Informaticae Vol. 30, 1-9, 1997

26. Addition in log n + O(1) Steps on Average: A Simple Analysis (with R. Beigel, M. Li, L. Zhang), Theoretical Computer Science. Vol 191, 1998, 245-248.

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.

28. Recursion theory and Reverse Mathematics (with Jeffery Hirst). Mathematical Logic Quarterly. Vol. 44, 1998, 465-473.

29. On the Finiteness of the Recursive Chromatic Number (with A. Lee). Annals of Pure and Applied Logic Vol. 93, 73-81, 1998.

30. Classification via Information (with M. Plezskoch, M. Velauthapillai, and F. Stephan), Annals of Mathematics and Artificial Intelligence. Vol. 23, 147-168, 1998.

31. On the Number of Automorphisms of a Graph (with R. Beals, R. Chang and J. Toran), Chicago Journal of Theory. February 1999.

32. When can one load a set of dice so that the sum is uniformly distributed? (with C. Kruskal) Mathematics Magazine. Vol. 72, No. 2, 1999, pp 133-138.

33. 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.

34. The Communication Complexity of Enumeration, Elimination, and Selection (with Andris Ambainis, Harry Buhrman, Bala Kalyanasundaram, Leen Torenvliet) Journal of Computer and Systems Science (Special issue for COMPLEXITY 2000). Vol 63, pages 148-185, 2001.

35. Automata Techniques for Query Inference Machines (with G. Hird), Annals of Pure and Applied Logic Vol. 117, 2002, pp 171-202.

36. Max and min limiters (with James Owings and Georgia Martin), Archives of Mathematical Logic Vol. 41, 2002, pp 483-495.

37. Constant Time Parallel Sorting: An Empirical View (with E. Golub and C. Kruskal) Journal of Computer and Systems Science Vol 67, 2003, pages 63-91.

38. When Does a Random Robin Hood Win? (with E. Golub and A. Srinivasan) Theoretical Computer Science Vol 304, 2003, pages 477-484.

39. Some connections between bounded query classes and non-uniform complexity (with A. Amir and R. Beigel), Information and Computation Vol 186, 2003, 104-139.

40. A Nearly Tight Lower Bound for Restricted Private Information Retrieval Protocols (with Richard Beigel and Lance Fortnow), Computational Complexity. Vol 15, No 1, 2006, 82-91.

41. Inferring Answers from Questions (with Andre Lee) Journal of Computer and Systems Sciences. To Appear.

42. Large 3-free sets: An Empirical Study. (with James Glenn and Clyde Kruskal), Journal of Computer and Systems Science To Appear.