Publications and Other Manuscripts by William Gasarch and co-authors.

Ideal secret sharing sharing-Observations of when and when not. (With Ambasz, Kailad, Rynder, Vanga), 2021. Manuscript

A thorough analysis of quadratic sieve factoring algorihtm and its comparisons to Pollard-Rho factoring algorithm (With Zongxiz Li), 2021. Manuscript

Hilbert's Tenth Problem for Fixed d and n. {sl Bulletin of the European Association for Theoretical Computer Science (EATCS)} Vol 133, February 2021

Low, superlow, and superduperlow sets: An exposition of a known but not well-known result {sl Landscapes in Logic: Contemporary Logic and Computing (Vol 1)} 2020

Small NFA's for cofinite unary languages (with Erik Metz, Zan Zu, Yuang Shen, Sam Zbarsky) {sl Landscapes in Logic: Contemporary Logic and Computing (Vol 1)} 2020

Cracking RSA with Various Factoring Algorithms (with Brian Holt). 2020. Manuscript

Alternative Modes of Computation (with Nathan Hayes). 2020. Manuscript

Sane Bounds on the Polynomial Van Der Warden Numbers (with Clyde Kruskal and Justin Kruskal and Zach Price. 2020. Manuscript

The Third P=?NP Poll. {sl Special Interest Group in Algorithms and Computing Theory (SIGACT)} Vol 50, No 1, 2019

Distinct volume sets via indiscernibles, {sl Archives of Mathematial Logic} Vol 58, 2019.

The Muffin Problem. Guest Column in {it Complexity Column SIGACT News}. Column 101. 2019

A Muffin-Theoerm Generator. (with Guang Cui, Naveen Durvasula, John Dickerson, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, Sunny Yoo) FUN with Algorithms 2018.

Hilbert's proof of his Irreducibility Theorem (with Ken Regan and Mark Villarino) {it American Mathematics Monthly} Vol 125, No. 6, 2018, pages 513–530

The Coefficient-Choosing Game (with Larry Washington and Sam Zbarsky). {it Journal of Combinatorics and Number Theory} Vol 10, No. 1, 2018. Page 1–19.

On the sizes of DPDA's, PDA's, LBA's. (with Richard Beigel) {it Theoretical Computer Science}. Vol 638, No. 25, 2016, pages 63-75.

Three results on making change (An Exposition). (with Naveen Raman). 2016. Manuscript

Lower bounds on the Deterministic and Quantum Communication Complexity of HAM(n,a). (with A. Ambains, A. Srinivasan, A. Utis) ACM Transactions of Computation Theory. Vol 7, No 3, Article 10, July 2015.

Distinct Volume Subsets (with David Conlon, Jacob Fox, David Harris, Doug Ulrich, Sam Zbarsky) SIAM journal of Discrete Math. Vol 29, No. 1, 472–480, 2015.

Proving Programs Terminate using Well Orderings, Ramsey Theory, and Matrices. Book Chapter in Advances in Computers Volume 97. 2015.

An Infinite Number of Proofs of the Reciprocal Theorem. by Vince Cozzo, Carolyn Gasarch, William Gasarch, Dilhan Salgado. Manuscript 2015

Which unbounded protocol for envy free cake cutting is better? 2015. Manuscript

item Classifying Problems Into Complexity Classes. Book Chapter in Advances in Computers Volume 95. Edited by Atif Memon Pages 239–292. 2014. htmladdnormallink{CLASSCOMP}{classcomp.pdf}

item How many ways can you make change: Some easy proofs. 2014. Unpublished. htmladdnormallink{CHANGEEASY}{http:arxiv.orgabs1406.5213}

item The Second P=?NP Poll. (A Guest column in Lane Hemaspaandra's Complexity Column.) htmladdnormallink{POLL2012}{poll2012.pdf}

item The Complexity of Grid Coloring. (with Daniel Apon and Kevin Lawler). 2012. Unpublished. htmladdnormallink{GRIDCOL}{https:arxiv.orgpdf1205.3813.pdf}

item Three proofs of the Hypergraph Ramsey Theorem (with Andy Parrish and Sanai Sandow). 2012. Unpublished. htmladdnormallink{HYPER}{https:arxiv.orgabs1206.4257}

item A Statement in Combinatorics that is Independent of ZFC. (with Stephen Fenner) 2012. Unpublished. htmladdnormallink{ZFCRADO}{https:arxiv.orgabs1201.1207}

item Rectangle Free Colorings of Grids. (with Fenner, Glover, and Purewal). 2012. Unpublished htmladdnormallink{GRIDPAPER.PDF}{https:arxiv.orgabs1005.3750} htmladdnormallink{GRIDTALK.PDF}{gridtalk.pdf}

item Limits on the Computational Power of Random Strings. (with Eric Allender and Luke Friedman)

{it Information and Computation} Special issue for ICALP 2011. Volume 222, 2013, Pages 80–92. htmladdnormallink{RANDOMSTRINGS.PDF}{randomstrings.pdf}

item Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructife (with Bernhard Haeupler) htmladdnormallink{LOWERVDW}{lowervdw.pdf}

{it Electronic Journal of Combinatorics} Vol 18, 2011 htmladdnormallink{LOWERVDW}{https:www.combinatorics.orgojsindex.phpeljcarticleviewv18i1p64}

item The complexity of finding SUBSEQ(A) (with Fenner and Postow)

{it Theory of Computing Systems} Vol 45, No. 3, 2009, 577-612. htmladdnormallink{SUBSEQ.PDF}{subseq.pdf} (Version here has appendices that the journal version did not have.)

item The Complexity of Learning SUBSEQ(A) (with Stephen Fenner and Brian Postow)

{it Journal of Symbolic Logic} Vol. 74, No. 3, 2009, 939–975. htmladdnormallink{learnsubseq.PDF}{learnsubseq.pdf} Earlier Conf Version: htmladdnormallink{learnsubseqCONF.PDF}{learnsubseqCONF.pdf}.

item The Tug of War Game. William Gasarch and Nick Sovich and Paul Zimand. 2009. Unpublished. htmladdnormallink{TUG.PDF}{tug.pdf}

item Inferring answers from data (with A. Lee)

{it Journal of Computing and Systems Sciences}, Volume 74, No 4, 2008, 490-512. (Conference version in {em Conference on Computational Learning theory COLT)} 1997). htmladdnormallink{ANSWERS.PDF}{answers.pdf}

item Finding Large 3-free Sets I: the Small n Case (with James Glenn and Clyde Kruskal),

{it Journal of Computing and Systems Sciences}, Volume 74, No. 4, June 2008. 628–655. htmladdnormallink{3apI.PDF}{3apI.pdf}

item A Nearly Tight Lower Bound for Restricted Private Information Retrieval Protocols (with Richard Beigel and Lance Fortnow),

{it Computational Complexity}. Vol 15, No 1, 2006, 82–91. htmladdnormallink{pirlower.PDF}{pirlower.pdf}

item The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. (with Richard Beigel and James Glenn),

{it 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.) htmladdnormallink{multicomm.PDF}{multicomm.pdf}

item The Egg Game (with Stuart Fletcher 2004. Unpublished. htmladdnormallink{egg}{egg.pdf}

item Constant Time Parallel Sorting: An Empirical View (with E. Golub and C. Kruskal)

{it Journal of Computer and Systems Science} Vol 67, 2003, pages 63-91. htmladdnormallink{emp-p-sort.PDF}{emp-p-sort.pdf},

item Some connections between bounded query classes and non-uniform complexity (with A. Amir and R. Beigel),

{it Information and Computation} Vol 186, 2003, 104-139. Earlier Version in CCC90. Link is to long version that is also at eccc archive. htmladdnormallink{NONUNIFORM.PDF}{nonuniform.pdf}

item A Survey on Private Information Retrieval

{sl Bulletin of the European Association for Theoretical Computer Science} Vol 82, February 2004, pages 72–107. Computational Complexity Column. htmladdnormallink{pirsurvey.PDF}{pirsurvey.pdf}

item When Does a Random Robin Hood Win? (with E. Golub and A. Srinivasan)

{it Theoretical Computer Science} Vol 304, 2003, pages 477–484. htmladdnormallink{robinhood.PDF}{robinhood.pdf}

item Gems in the field of bounded queries.

{sl Computability and Models} Edited by Cooper and Goncharov. 2003. htmladdnormallink{GEMS.PDF}{gems.pdf}

item Automata Techniques for Query Inference Machines (with G. Hird),

{sl Annals of Pure and Applied Logic} Vol. 117, 171–203, 2002. htmladdnormallink{AUT-TECH-QUERY-INF.PDF}{aut-tech-query-inf.pdf} Earlier version in COLT95, with title

{it Reduction in Learning via Queries}

item Max and min limiters (with James Owings and Georgia Martin),

{sl Archives of Mathematical Logic} Vol. 41, 2002, pp 483-495. htmladdnormallink{MAX-MIN-DELIM.PDF}{max-min-delim.pdf}

item AHA: An Illuminating Perspective. (With Dan Garcia and David Ginat)

{sl Thirty third annual SIGCSE Technical Symposium on Computer Science Education}, Feb 2002. (htmladdnormallink{AHA.PDF}{aha.pdf})

item The P=?NP Poll.

{sl SIGACT NEWS} 2002. Complexity Theory Column. htmladdnormallink{POLL.PDF}{poll.pdf}

item 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). htmladdnormallink{COMM.PDF}{comm.pdf}

item A Survey of Constant Time Parallel Sorting, for

{sl 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. htmladdnormallink{SURVEY-CONST-TIME-SORTING.PDF}{survey-const-time-sorting.pdf}

item Squares in a Square: An On-line question (with A.Ambainis). Geocombinatorics, Vol X, No 1, 2000 htmladdnormallink{SQUARES.PDF}{squares.pdf}.

item Computability,

{sl Handbook of Discrete and Combinatorial Mathematics}. Edited by Kenneth Rosen. Published by CRC Press (Boca Raton, Florida). htmladdnormallink{COMPUT.PDF}{comput.pdf}

item The Complexity of ODD(n,A) (with R. Beigel, M. Kummer, G. Martin, T. McNichol, and F. Stephan)

{sl Journal of Symbolic Logic}, Vol. 65, 1–18, 2000. Earlier Version in MFCS96. htmladdnormallink{ODD.PDF}{odd.pdf}

item A techniques-oriented survey of bounded queries. (with Frank Stephan).

{sl 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. htmladdnormallink{BDQ-SURVEY-TECH.PDF}{bdq-survey-tech.pdf}

item On the Number of Automorphisms of a Graph (with R. Beals, R. Chang and J. Toran),

{sl Chicago Journal of Theory}. Feburary 1999. Earlier version in CCC95. htmladdnormallink{NUMAUTO.PDF}{numauto.pdf}

item When can one load a set of dice so that the sum is uniformily distributed? (with C. Kruskal)

{sl Mathematics Magazine}. Vol. 72, No. 2, 1999, pp 133-138. htmladdnormallink{DICE.PDF}{dice.pdf}

item A Survey of Recursive Combinatorics.

{sl Handbook of Recursive Mathematics Volume 2}. Edited by Ershov, Goncharov, Marek, Nerode, and Remmel. 1998. Pages 1041–1176. Published by Elsevier htmladdnormallink{RCOMBSUR.PDF}{rcombsur.pdf}

item Addition in lg(n) + O(1) Steps on Average: A Simple Analysis (with R. Beigel, M. Li, L. Zhang),

{sl Theoretical Computer Science}. Vol 191, 1998, 245–248. htmladdnormallink{ADD.PDF}{add.pdf}

item Recursion theory and Reverse Mathematics (with Jeffery Hirst).

{sl Mathematical Logic Quarterly}. Vol. 44, 1998, 465-473. htmladdnormallink{RR.PDF}{rr.pdf}

item On the Finiteness of the Recursive Chromatic Number (with A. Lee).

{sl Annals of Pure and Applied Logic} Vol. 93, 73-81, 1998. htmladdnormallink{FINITE-REC-CHROM-NUMBER.PDF}{finite-rec-chrom-number.pdf}

item Classification via Information (with M. Plezskoch, M. Velauthapillai, and F. Stephan),

{sl Annals of Mathematics and Artificial Intelligence}. Vol. 23, 147–168, 1998. htmladdnormallink{CLASSIFICATION.PDF}{classification.pdf} Earlier version in ALT94.

item Relative Sizes of Learnable Sets (with L. Fortnow, R. Freivalds, M. Kummer, S. Kurtz, C. Smith, and F. Stephan),

{sl Theoretical Computer Science} Vol 197(1-2):139-156, 1998. Earlier version in ICALP95 with the name

{it Measure, Category, and Learning Theory} htmladdnormallink{MEASURE.PDF}{measure.pdf}

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

item Bounded Queries and Approximation (with R. Chang and C. Lund),

{sl SIAM Journal of Computing}, Vol. 26, 1997, 188-209 htmladdnormallink{BDQAPPROX.PDF}{bdqapprox.pdf} Earlier version in FOCS93 did not have Lund as co-author.

item Implementing WS1S via Finite Finite Automata.

{sl Automata Implementation}. (with James Glenn) In {it Workshop on Implementing Automata-1996} Edited by Raymond, Wood, and Yu. Lecture Notes in Computer Science 1260. 1997 htmladdnormallink{WIA96.PDF}{wia96.pdf}

item Binary search and recursive graph problems (with K. Guimaraes)

{sl Theoretical Computer Science} Vol 181, 1997, 119-139. (Special issue for LATIN 95 conference). htmladdnormallink{BINARY.PDF}{binary.pdf} Subsumeds the conference papers

{it On the number of components of a recursive graph} from LATIN 92. and

{it Unbounded search and recursive graphs} from LATIN 95.

item Asking Questions Versus Verifiability (with M. Velauthapillai),

{sl Fundamenta Informaticae} Vol. 30, 1-9, 1997 htmladdnormallink{VERIFY.PDF}{verify.pdf} Earlier version in AII92.

item A Survey of Inductive Inference with an Emphasis on Learning via Queries (with C. Smith).

{sl Complexity, Logic, and Recursion Theory}. Edited by A. Sorbi. Published by M. Dekker. Volume 187. 1997. htmladdnormallink{LVQSUR.PDF}{lvqsur.pdf}.

item The Complexity of Problems,

{sl Advances in Computers Volume 43}. Edited by Marvin Zelkowitz. Published by Academic Press. 1996. htmladdnormallink{COMPLEXITY.PDF}{complexity.pdf}

item Frequencey Computation and Bounded Queries (with R. Beigel and E. Kinber)

{sl Theoretical Computer Science}, Vol. 163, 1996, 177-192. Earlier version in CCC95. htmladdnormallink{BDQFREQ.PDF}{bdqfreq.pdf}

item Learning via Queries with Teams and Anomalies (with E. Kinber, M. Pleszkoch, C. Smith, and T. Zeugmann),

{sl Fundamenta Informaticae}, Vol. 23, Number 1, May 1995, pp. 67-89. htmladdnormallink{LVQTEAMS.PDF}{lvqteams.pdf} Earlier version in COLT90.

item Recursion theoretic models of learning: some results and intuitions, (with C. Smith)

{sl Annals of Mathematics and Artificial Intelligence}, Vol. 15, II, 1995, pp. 155-166. htmladdnormallink{MODELS.PDF}{models.pdf}

item OptP-Completeness as the Normal Behavior of NP-Complete Problems (with M. Krentel and K. Rappoport),

{sl Math Systems Theory}, Vol. 28, 1995, 487-514 htmladdnormallink{BDQOPT.PDF}{bdqopt.pdf}

item 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),

{sl Annals of Pure and Applied Logic}, Vol. 66, 1994, pp. 231-276. htmladdnormallink{EXTREMES.PDF}{extremes.pdf} Subsumes both

{it Learning via Queries to an Oracle} from COLT89 and

{it Degrees of Inferability} from COLT92.

item On Honest Polynomial Reductions and P=NP (with R. Downey, and M. Moses),

{sl Annals of Pure and Applied Logic}, Vol. 70, 1994, pp. 1-27. Earlier version in CCC89. htmladdnormallink{HONEST.PDF}{honest.pdf} (The version on line is the CCC89 version.)

item Terse, Superterse, and Verbose Sets (with R. Beigel, J. Gill, and J. Owings),

{sl Information and Computation}, Vol. 103, 1993, pp. 68-85, 1993. htmladdnormallink{BDQTERSE.PDF}{bdqterse.pdf}

item On Checking Versus Evaluation of Multiple Queries (with Lane Hemachandra and Albrech Hoene),

{sl Information and Computation}, Vol. 105, 1993, pp. 72–93. htmladdnormallink{CHECK.PDF}{check.pdf} Earlier version in MFCS90.

item Index Sets in Recursive Combinatorics (with G. Martin),

{sl Logical Methods (In honor of Anil Nerodes's Sixtieth Birthday)}. Edited by Crossley, Remmel, Shore, and Sweedler. 1993. Edited by Birkhaeuser, Boston.

item Learning via Queries to +,< (with M. Pleszkoch and R. Solovay),

{sl Journal of Symbolic Logic}, htmladdnormallink{LVQPLUS.PDF}{lvqplus.pdf} Earlier version in COLT90

item Learning Programs with an Easy to Calculate Set of Errors (with Rameshkumar Sitarman, C. Smith, and Mahendran Velauthapillai),

{sl Fundamentica Informaticae}, Vol. 16, No. 3-4, pp. 355–370, 1992. htmladdnormallink{ERRORS.PDF}{errors.pdf} Earlier version appearedin COLT88 and AII89.

item Learning via Queries (with C. Smith),

{sl Journal of the Association of Computing Machinery}, Vol. 39, 1992, pp. 649-675. htmladdnormallink{LVQ.PDF}{lvq.pdf}, Earlier versions appeared at COLT88 and FOCS88.

item Selection Problems using m-ary queries (with K. Guimaraes and J. Purtilo),

{sl Computational Complexity}, Vol. 2, 1992, pp. 256-276. htmladdnormallink{ARITY.PDF}{arity.pdf}

item The Mapmaker's Dilemma (with R. Beigel),

{sl Discrete Applied Math (Special Issue on Theoretical Computer Science)}, Vol. 34, 1991, pp. 37-48. htmladdnormallink{MAP.PDF}{map.pdf}

item On Selecting the k Largest with Restricted Quadratic Queries,

{sl Information Processing Letters}, Vol. 38, 1991, pp. 193-195.

item A Survey of Bounded Queries in Recursion Theory,

{sl Sixth Annual Conferences on Structure in Complexity Theory}, Chicago, June 1991. htmladdnormallink{BDQSUR.PDF}{bdqsur.pdf}

item Training Sequences (with D. Angluin and C. Smith),

{sl Theoretical Computer Science}, Vol. 66, 1989, pp. 255-272. htmladdnormallink{TRAINING.PDF}{training.pdf} Earlier version without Angluin at AII86 was called

{it On the inference of sequences of functions}

item On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case (with R. Beigel),

{sl Annals of Pure and Applied Logic}, Vol. 45, 1989, pp. 1-38. htmladdnormallink{FINDCHROMNUMBER1.PDF}{findchromnumber1.pdf}

item On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case (with R. Beigel),

{sl Annals of Pure and Applied Logic}, Vol. 45, 1989, pp. 227-247. htmladdnormallink{FINDCHROMNUMBER2.PDF}{findchromnumber2.pdf}

item Bounded Query Classes and the Difference Hierarchy (with R. Beigel and L. Hay),

{sl Archive for Math. Logic}, Vol. 29, 1989, pp. 69-84. htmladdnormallink{BDQDIFF.PDF}{bdqdiff.pdf}

item Nondeterministic Bounded Query Reducibilities (with R. Beigel, and J. Owings),

{sl Annals of Pure and Applied Logic}, Vol. 41, 1989, pp. 107-118. htmladdnormallink{BDQ-NONDET.PDF}{bdq-nondet.pdf}

item Polynomial Terse Sets (with A. Amir),

{sl Information and Computation}, Vol. 77, No. 1, 1988, pp. 37–56. Earlier version in CCC87. htmladdnormallink{AMIRGASARCH.PDF}{AmirGasarch.pdf}

item Oracles for Deterministic vs. Alternating Classes,

{sl SIAM Journal of Computing}, Vol. 16, Aug 1987, pp. 613–627. htmladdnormallink{ORACLESEVSSIG.PDF}{oraclesEvsSIG.pdf}

item Oracles: Three New Results.

{sl 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.

item Relativizations Comparing NP and Exponential Time (with S. Homer),

{sl Information and Control}, Vol. 58, July 1983, pp. 88–100. htmladdnormallink{ORACLESEVSNP.PDF}{oraclesEvsNP.pdf} end{enumerate} end{document}