Books and papers by William Gasarch and co-authors. All sections in rev alpha order
Books
Computational Intractability: A Guide to Algorithmic Lower Bounds (with Erik Demaine and Mohammad Hajiaghayi). To appear in 2024. MIT Press.
Mathematical Muffin Morsels: Nobody wants a small piece (with Erik Metz, Jacob Prinz, Daniel Smolyak) 2019. World Scientific.
Problems with a Point: Exploring Mathematics and Computer Science (with Clyde Kruskal). 2018. World Scientific.
Bounded Queries in Recursion Theory (With Georgia Martin). Birkhauser. 1998
Articles and Conference that were published somewhere officially
Fermat's Last Theorem, Schur's Theorem (in Ramsey Theory), and the infinitude of the primes, Discrete Math, 2023 (to appear)
Christian Elsholtz paper that ind obtained the same result
Arxiv version of Elsholtz paper. NOT behind a paywall!
The Complexity of Grid Coloring (with Apon and Lawler), Theory of Computing Sytems, 2023, (to appear)
Hilbert's Tenth Problem for Fixed d and n.
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
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)
Landscapes in Logic: Contemporary Logic and Computing (Vol 1)
2020
The Third P=?NP Poll.
Special Interest Group in Algorithms and Computing Theory (SIGACT)
Vol 50, No 1, 2019
Distinct volume sets via indiscernibles,
Archives of Mathematical Logic
Vol 58, 2019.
The Muffin Problem. Guest Column in
Complexity Column SIGACT News
. Column 101. 2019
A Muffin-Theorem 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)
American Mathematics Monthly
Vol 125, No. 6, 2018, pages 513–530
The Coefficient-Choosing Game (with Larry Washington and Sam Zbarsky).
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)
Theoretical Computer Science
. Vol 638, No. 25, 2016, pages 63-75.
Lower bounds on the Deterministic and Quantum Communication Complexity of HAM(n,a). (with A. Ambainis, A. Srinivasan, A. Utis)
ACM Transactions of Computation Theory
. Vol 7, No 3, Article 10, July 2015.
Distinct Vol 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
Vol 97. 2015.
Classifying Problems Into Complexity Classes. Book
Chapter in Advances
in Computers Vol 95. 2014.
The Second P=?NP Poll.
Complexity Column in SIGACT News
. 2012
Limits on the Computational Power of Random Strings. (with Eric Allender and Luke Friedman)
Information and Computation
Vol 222, 2013, Pages 80–92
Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive (with Bernhard Haeupler)
Electronic Journal of Combinatorics
Vol 18, 2011
The complexity of finding SUBSEQ(A) (with Fenner and Postow)
Theory of Computing Systems
Vol 45, No. 3, 2009, 577-612
The Complexity of Learning SUBSEQ(A) (with Stephen Fenner and Brian Postow)
Journal of Symbolic Logic
Vol. 74, No. 3, 2009, 939–975
Inferring answers from data (with A. Lee)
Journal of Computing and Systems Sciences
, Vol 74, No 4, 2008, 490-512
Finding Large 3-free Sets I: the Small n Case (with James Glenn and Clyde Kruskal),
Journal of Computing and Systems Sciences
, Vol 74, No. 4, June 2008. 628–655
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
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. (with Richard Beigel and James Glenn), ·athematical Foundations of Computer Science 2006
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
Some connections between bounded query classes and non-uniform complexity (with A. Amir and R. Beigel),
Information and Computation
Vol 186, 2003, 104-139
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
When Does a Random Robin Hood Win? (with E. Golub and A. Srinivasan)
Theoretical Computer Science
Vol 304, 2003, pages 477–484
Gems in the field of bounded queries.
Computability and Models
Edited by Cooper and Goncharov. 2003
Automata Techniques for Query Inference Machines (with G. Hird),
Annals of Pure and Applied Logic
Vol. 117, 171–203, 2002
Max and min limiters (with James Owings and Georgia Martin),
Archives of Mathematical Logic
Vol. 41, 2002, pp 483-495
AHA: An Illuminating Perspective. (With Dan Garcia and David Ginat)
Thirty third annual SIGCSE Technical Symposium on Computer Science Education
, Feb 2002
The P=?NP Poll.
SIGACT NEWS
2002. Complexity Theory Column
The Communication Complexity of Enumeration, Elimination, and Selection (with Andris Ambainis, Harry Buhrman, Bala Kalyanasundaram, Leen Torenvliet) Vol 63., pages 148-185, 2001.
Journal of Computer and System Sciences
(Special issue for COMPLEXITY 2000)
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
Squares in a Square: An On-line question (with A.Ambainis).
Geocombinatorics
, Vol X, No 1, 2000
Computability,
Handbook of Discrete and Combinatorial Mathematics
, Edited by Kenneth Rosen. Published by CRC Press (Boca Raton, Florida)
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
A techniques-oriented survey of bounded queries (with Frank Stephan).
Models and Computability (invited papers from Logic Colloquium ’97)
(Lecture Note Series 259), Edited by Cooper and Truss. London Mathematical Society 117-156, 1999. Forschungsberichte Mathematische Logik 32 / 1998, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 1998
On the Number of Automorphisms of a Graph (with R. Beals, R. Chang and J. Toran),
Chicago Journal of Theory
February 1999
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
A Survey of Recursive Combinatorics.
Handbook of Recursive Mathematics Vol 2
, Edited by Ershov, Goncharov, Marek, Nerode, and Remmel. 1998. Pages 1041–1176. Published by Elsevier
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
Recursion theory and Reverse Mathematics (with Jeffery Hirst).
Mathematical Logic Quarterly
, Vol. 44, 1998, 465-473
On the Finiteness of the Recursive Chromatic Number (with A. Lee).
Annals of Pure and Applied Logic
, Vol. 93, 73-81, 1998
Classification via Information (with M. Plezskoch, M. Velauthapillai, and F. Stephan),
Annals of Mathematics and Artificial Intelligence
, Vol. 23, 147–168, 1998
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
Bounded Queries and Approximation (with R. Chang and C. Lund),
SIAM Journal of Computing
, Vol. 26, 1997, 188-209
Implementing WS1S via Finite Automata (with James Glenn)
Workshop on Implementing Automata-1996
Edited by Raymond, Wood, and Yu. Lecture Notes in Computer Science 1260. 1997
Binary search and recursive graph problems (with K. Guimaraes)
Theoretical Computer Science
Vol 181, 1997, 119-139. (Special issue for LATIN 95 conference)
Asking Questions Versus Verifiability (with M. Velauthapillai),
Fundamenta Informaticae
Vol. 30, 1-9, 1997
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 Vol 187. 1997
The Complexity of Problems,
Advances in Computers Vol 43
Edited by Marvin Zelkowitz. Published by Academic Press. 1996
Frequency Computation and Bounded Queries (with R. Beigel and E. Kinber)
Theoretical Computer Science
, Vol. 163, 1996, 177-192
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.
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.
OptP-Completeness as the Normal Behavior of NP-Complete Problems (with M. Krentel and K. Rappoport),
Math Systems Theory
, Vol. 28, 1995, 487-514
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.
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
Terse, Superterse, and Verbose Sets (with R. Beigel, J. Gill, and J. Owings),
Information and Computation
, Vol. 103, 1993, pp. 68-85, 1993.
On Checking Versus Evaluation of Multiple Queries (with Lane Hemachandra and Albrech Hoene),
Information and Computation
, Vol. 105, 1993, pp. 72–93.
Sets in Recursive Combinatorics SORRY NO LINK. (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
Learning via Queries to
(with M. Pleszkoch and R. Solovay), /Journal of Symbolic Logic
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
Learning via Queries (with C. Smith),
Journal of the Association of Computing Machinery
Vol. 39, 1992, pp. 649-675
Selection Problems using m-ary queries (with K. Guimaraes and J. Purtilo),
Computational Complexity
, Vol. 2, 1992, pp. 256-276.
The Mapmaker's Dilemma (with R. Beigel),
Discrete Applied Math (Special Issue on Theoretical Computer Science)
Vol. 34, 1991, pp. 37-48.
On Selecting the k Largest with Restricted Quadratic Queries,
Information Processing Letters
, Vol. 38, 1991, pp. 193-195
A Survey of Bounded Queries in Recursion Theory,
Sixth Annual Conferences on Structure in Complexity Theory
, Chicago, June 1991
Training Sequences (with D. Angluin and C. Smith),
Theoretical Computer Science
, Vol. 66, 1989, pp. 255-272.
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.
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.
Bounded Query Classes and the Difference Hierarchy (with R. Beigel and L. Hay),
Archive for Math. Logic
, Vol. 29, 1989, pp. 69-84.
Nondeterministic Bounded Query Reducibilities (with R. Beigel, and J. Owings),
Annals of Pure and Applied Logic
, Vol. 41, 1989, pp. 107-118.
Polynomial Terse Sets (with A. Amir),
Information and Computation
, Vol. 77, No. 1, 1988, pp. 37–56
Oracles for Deterministic vs. Alternating Classes,
SIAM Journal of Computing
, Vol. 16, Aug 1987, pp. 613–627.
Three New Results. SORRY NO LINK.
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.
Relativizations Comparing NP and Exponential Time (with S. Homer),
Information and Control
, Vol. 58, July 1983, pp. 88–100.
The Egg Game (with Stuart Fletcher 2004.
Manuscript
Manuscripts that are not yet pulished anywhere. One day…
Ideal secret sharing sharing-Observations of when and when not. (With Ambasz, Kailad, Rynder, Vanga), 2021.
Manuscript
The Tug of War Game. William Gasarch and Nick Sovich and Paul Zimand. 2009.
Manuscript
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
A thorough analysis of quadratic sieve factoring algorithm and its comparisons to Pollard-Rho factoring algorithm (With Zongxiz Li), 2021.
Manuscript
Cracking RSA with Various Factoring Algorithms (with Brian Holt). 2020.
Manuscript
Alternative Modes of Computation (with Nathan Hayes). 2020.
Manuscript
High School Proofs for Better Bounds on the Quadratic Van der Waerden Numbers (with Clyde Kruskal and Justin Kruskal and Zach Price. 2020.
Manuscript
Three results on making change (An Exposition). (with Naveen Raman). 2016.
Manuscript
Which unbounded protocol for envy free cake cutting is better? 2015.
Manuscript
How many ways can you make change: Some easy proofs. 2014.
Manuscript
The Second P=?NP Poll.
Complexity Column in SIGACT News
. 2012
Three proofs of the Hypergraph Ramsey Theorem (with Andy Parrish and Sanai Sandow). 2012.
Manuscript
A Statement in Combinatorics that is Independent of ZFC. (with Stephen Fenner) 2012.
Manuscript
Rectangle Free Colorings of Grids. (with Fenner, Glover, and Purewal). 2012.
Manuscript