next up previous
Next: About this document ...

PUBLICATIONS and IN PROGRESS

  1. The Second P=?NP Poll. (A Guest column in Lane Hemaspaandra's Complexity Column.) POLL2012

  2. The Complexity of Grid Coloring. (with Daniel Apon and Kevin Lawler). GRIDCOL

  3. Three proofs of the Hypergraph Ramsey Theorem (with Andy Parrish and Sanai Sandow). HYPER

  4. A Statement in Combinatorics that is Independent of ZFC. (with Stephen Fenner) In Progress. ZFCRADO.PDF

  5. The Tug of War Game. William Gasarch and Nick Sovich and Paul Zimand. TUG.PDF

  6. Rectangle Free Colorings of Grids. (with Fenner, Glover, and Purewal). GRIDPAPER.PDF GRIDTALK.PDF In progress.

  7. Limits on the Computational Power of Random Strings. (with Eric Allender and Luke Friedman) RANDOMSTRINGS.PDF To appear in Information and Computation Special issue devotedto ICALP 2011.

  8. Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructife (with Bernhard Haeupler) LOWERVDW Electronic Journal of Combinatorics Vol 18, 2011

  9. The complexity of finding SUBSEQ(A) (with Fenner and Postow) Theory of Computing Systems Vol 45, No. 3, 2009, 577-612. SUBSEQ.PDF (Version here has appendices that the journal version did not have.)

  10. The Complexity of Learning SUBSEQ(A) (with Stephen Fenner and Brian Postow) Journal of Symbolic Logic Vol. 74, No. 3, 2009, 939-975. learnsubseq.PDF Earlier Conf Version: learnsubseqCONF.PDF.

  11. Inferring answers from data (with A. Lee) Journal of Computing and Systems Sciences, (To appear) Conference Version in COLT97. ANSWERS.PDF
  12. Finding Large 3-free Sets I: the Small n Case (with James Glenn and Clyde Kruskal), Journal of Computing and Systems Sciences, Volume 74, No. 4, June 2008. 628-655. 3apI.PDF

  13. 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. pirlower.PDF

  14. The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. (with Richard Beigel and James Glenn), Mathematical Foundations of Computer Science 2006. (I post the long version, which is not the same as the conference version. It has more in it.) multicomm.PDF

  15. Lower bounds on the Deterministic and Quantum Communication Complexity of HAM(n,a). (with A. Ambains, A. Srinivasan, A. Utis) Proceedings of the 17th International Symposisum on Algorithms (ISAAC), 2006. HAM.PDF

  16. 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. emp-p-sort.PDF,

  17. Some connections between bounded query classes and non-uniform complexity (with A. Amir and R. Beigel), Information and Computation Vol 186, 2003, 104-139. Earlier Version in CCC90. Link is to long version that is also at eccc archive. NONUNIFORM.PDF

  18. A Survey on Private Information Retrieval Bulletin of the European Association for Theoretical Computer Science Vol 82, February 2004, pages 72-107. Computational Complexity Column. pirsurvey.PDF

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

  20. Gems in the field of bounded queries. Computability and Models Edited by Cooper and Goncharov. 2003. GEMS.PDF

  21. Automata Techniques for Query Inference Machines (with G. Hird), Annals of Pure and Applied Logic Vol. 117, 171-203, 2002. AUT-TECH-QUERY-INF.PDF Earlier version in COLT95, with title Reduction in Learning via Queries

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

  23. AHA: An Illuminating Perspective. (With Dan Garcia and David Ginat) Thirty third annual SIGCSE Technical Symposium on Computer Science Education, Feb 2002. (AHA.PDF)

  24. The P=?NP Poll. SIGACT NEWS 2002. Complexity Theory Column. POLL.PDF

  25. 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.PDF

  26. A Survey of Constant Time Parallel Sorting, for Bulletin of the European Association for Theoretical Computer Science (with Evan Golub and Clyde Kruskal), Vol 72, pages 84-102, October 2000, Computational Complexity Column. SURVEY-CONST-TIME-SORTING.PDF

  27. Squares in a Square: An On-line question (with A.Ambainis). Geocombinatorics, Vol X, No 1, 2000 SQUARES.PDF.

  28. Computability, Handbook of Discrete and Combinatorial Mathematics. Edited by Kenneth Rosen. Published by CRC Press (Boca Raton, Florida). COMPUT.PDF

  29. The Complexity of ODD(n,A) (with R. Beigel, M. Kummer, G. Martin, T. McNichol, and F. Stephan) Journal of Symbolic Logic, Vol. 65, 1-18, 2000. Earlier Version in MFCS96. ODD.PDF

  30. A techniques-oriented survey of bounded queries. (with Frank Stephan). Models and Computability (invited papers from Logic Colloquium '97) (Lecture Note Series 259), Editted by Cooper and Truss. London Mathematical Society 117-156, 1999. Forschungsberichte Mathematische Logik 32 / 1998, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 1998. BDQ-SURVEY-TECH.PDF

  31. On the Number of Automorphisms of a Graph (with R. Beals, R. Chang and J. Toran), Chicago Journal of Theory. Feburary 1999. Earlier version in CCC95. NUMAUTO.PDF

  32. 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.PDF

  33. A Survey of Recursive Combinatorics. Handbook of Recursive Mathematics Volume 2. Edited by Ershov, Goncharov, Marek, Nerode, and Remmel. 1998. Pages 1041-1176. Published by Elsevier RCOMBSUR.PDF

  34. Addition in lg(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.PDF

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

  36. On the Finiteness of the Recursive Chromatic Number (with A. Lee). Annals of Pure and Applied Logic Vol. 93, 73-81, 1998. FINITE-REC-CHROM-NUMBER.PDF

  37. Classification via Information (with M. Plezskoch, M. Velauthapillai, and F. Stephan), Annals of Mathematics and Artificial Intelligence. Vol. 23, 147-168, 1998. CLASSIFICATION.PDF Earlier version in ALT94.

  38. 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. Earlier version in ICALP95 with the name Measure, Category, and Learning Theory MEASURE.PDF

  39. Bounded Queries in Recursion Theory (With Georgia Martin). Birkhauser. 1998.

  40. Bounded Queries and Approximation (with R. Chang and C. Lund), SIAM Journal of Computing, Vol. 26, 1997, 188-209 BDQAPPROX.PDF Earlier version in FOCS93 did not have Lund as co-author.

  41. Implementing WS1S via Finite Finite Automata. Automata Implementation. (with James Glenn) In Workshop on Implementing Automata-1996 Edited by Raymond, Wood, and Yu. Lecture Notes in Computer Science 1260. 1997 WIA96.PDF

  42. Binary search and recursive graph problems (with K. Guimaraes) Theoretical Computer Science Vol 181, 1997, 119-139. (Special issue for LATIN 95 conference). BINARY.PDF Subsumeds the conference papers On the number of components of a recursive graph from LATIN 92. and Unbounded search and recursive graphs from LATIN 95.

  43. Asking Questions Versus Verifiability (with M. Velauthapillai), Fundamenta Informaticae Vol. 30, 1-9, 1997 VERIFY.PDF Earlier version in AII92.

  44. A Survey of Inductive Inference with an Emphasis on Learning via Queries (with C. Smith). Complexity, Logic, and Recursion Theory. Edited by A. Sorbi. Published by M. Dekker. Volume 187. 1997. LVQSUR.PDF.

  45. The Complexity of Problems, Advances in Computers Volume 43. Edited by Marvin Zelkowitz. Published by Academic Press. 1996. COMPLEXITY.PDF

  46. Frequencey Computation and Bounded Queries (with R. Beigel and E. Kinber) Theoretical Computer Science, Vol. 163, 1996, 177-192. Earlier version in CCC95. BDQFREQ.PDF

  47. 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.PDF Earlier version in COLT90.

  48. 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.PDF

  49. OptP-Completeness as the Normal Behavior of NP-Complete Problems (with M. Krentel and K. Rappoport), Math Systems Theory, Vol. 28, 1995, 487-514 BDQOPT.PDF

  50. 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.PDF Subsumes both Learning via Queries to an Oracle from COLT89 and Degrees of Inferability from COLT92.

  51. 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. Earlier version in CCC89. HONEST.PDF (The version on line is the CCC89 version.)

  52. Terse, Superterse, and Verbose Sets (with R. Beigel, J. Gill, and J. Owings), Information and Computation, Vol. 103, 1993, pp. 68-85, 1993. BDQTERSE.PDF

  53. On Checking Versus Evaluation of Multiple Queries (with Lane Hemachandra and Albrech Hoene), Information and Computation, Vol. 105, 1993, pp. 72-93. CHECK.PDF Earlier version in MFCS90.

  54. Index Sets in Recursive Combinatorics (with G. Martin), Logical Methods (In honor of Anil Nerodes's Sixtieth Birthday). Edited by Crossley, Remmel, Shore, and Sweedler. 1993. Edited by Birkhaeuser, Boston.

  55. Learning via Queries to [+,<] (with M. Pleszkoch and R. Solovay), Journal of Symbolic Logic, LVQPLUS.PDF Earlier version in COLT90

  56. 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.PDF Earlier version appearedin COLT88 and AII89.

  57. Learning via Queries (with C. Smith), Journal of the Association of Computing Machinery, Vol. 39, 1992, pp. 649-675. LVQ.PDF, Earlier versions appeared at COLT88 and FOCS88.

  58. Selection Problems using m-ary queries (with K. Guimaraes and J. Purtilo), Computational Complexity, Vol. 2, 1992, pp. 256-276. ARITY.PDF

  59. The Mapmaker's Dilemma (with R. Beigel), Discrete Applied Math (Special Issue on Theoretical Computer Science), Vol. 34, 1991, pp. 37-48. MAP.PDF

  60. On Selecting the k Largest with Restricted Quadratic Queries, Information Processing Letters, Vol. 38, 1991, pp. 193-195.

  61. A Survey of Bounded Queries in Recursion Theory, Sixth Annual Conferences on Structure in Complexity Theory, Chicago, June 1991. BDQSUR.PDF

  62. Training Sequences (with D. Angluin and C. Smith), Theoretical Computer Science, Vol. 66, 1989, pp. 255-272. TRAINING.PDF Earlier version without Angluin at AII86 was called On the inference of sequences of functions

  63. 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. FINDCHROMNUMBER1.PDF

  64. 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. FINDCHROMNUMBER2.PDF

  65. Bounded Query Classes and the Difference Hierarchy (with R. Beigel and L. Hay), Archive for Math. Logic, Vol. 29, 1989, pp. 69-84. BDQDIFF.PDF

  66. Nondeterministic Bounded Query Reducibilities (with R. Beigel, and J. Owings), Annals of Pure and Applied Logic, Vol. 41, 1989, pp. 107-118. BDQ-NONDET.PDF

  67. Polynomial Terse Sets (with A. Amir), Information and Computation, Vol. 77, No. 1, 1988, pp. 37-56. Earlier version in CCC87. AMIRGASARCH.PDF

  68. Oracles for Deterministic vs. Alternating Classes, SIAM Journal of Computing, Vol. 16, Aug 1987, pp. 613-627. ORACLESEVSSIG.PDF

  69. Oracles: Three New Results. Marcel Dekker Lecture Notes in Pure and Applied Mathematics Vol. 106, Edited by D.W. Kueker, E.G.K. Lopez-Escobar, and C.H. Smith, 1987, pp. 219-252.

  70. Relativizations Comparing NP and Exponential Time (with S. Homer), Information and Control, Vol. 58, July 1983, pp. 88-100. ORACLESEVSNP.PDF



next up previous
Next: About this document ...
William Gasarch 2013-07-31