William I. Gasarch

Orcid: 0000-0003-3698-5991

Affiliations:
  • University of Maryland, College Park, USA


According to our database1, William I. Gasarch authored at least 185 papers between 1983 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Fermat's Last Theorem, Schur's Theorem (in Ramsey Theory), and the infinitude of the primes.
Discret. Math., November, 2023

The Complexity of Grid Coloring.
Theory Comput. Syst., June, 2023

Joint Review of The Mathematics of Various Entertaining Subjects: Research in Recreational Math and The Mathematics of Various Entertaining Subjects: Vol. 2. Research in Games, Graphs, Counting, and Complexity and The Mathematics of Various Entertaining Subjects Vol. 3. The Magic of Mathematics.
SIGACT News, March, 2023

2022
The Complexity of Chromatic Number When Restricted to graphs with Bounded Genus or Bounded Crossing Number.
SIGACT News, 2022

Review of "The Engines of Cognition: Essays by the Less Wrong Community by Less Wrong Less Wrong Press 720 pages, Year: 2019 $30.00".
SIGACT News, 2022

Review of A Map that Reflects the Territory: Essays by the LessWrong Community Author: LessWrong.
SIGACT News, 2022

Review of Tales of Impossibility: The 2000-Year Quest to Solve the Mathematical Problems of Antiquity Author: David Richeson.
SIGACT News, 2022

$(\mathbb {Z}, \text {succ}, U), (\mathbb {Z}, E, U)$, and Their CSP's.
Proceedings of the Theory and Applications of Models of Computation, 2022

2021
Open Problems Column.
SIGACT News, 2021

Hilbert's Tenth Problem: Refinements and Variants.
SIGACT News, 2021

Review of Blown to Bits: Your Life, Liberty, and Happiness after the Digital Explosion by Hal Abelson, Ken Ledeen, Harry Lewis, and Wendy Seltzer.
SIGACT News, 2021

Review of Ideas that Created the Future: Classic Papers of Computer Science Edited by Harry Lewis.
SIGACT News, 2021

Hilbert's Tenth Problem for Fixed d and n.
Bull. EATCS, 2021

Alternative Paradigms of Computation.
CoRR, 2021

An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm.
CoRR, 2021

2020
Open Problems Column.
SIGACT News, 2020

Open Problems Column Edited by William Gasarch This Issue's Column!
SIGACT News, 2020

Review of Theorems of the 21st Century: Volume I.
SIGACT News, 2020

Review of Essential Discrete Mathematics for Computer Science By Harry Lewis and Rachel Zax.
SIGACT News, 2020

Review of What Can Be Computed: A Practical Guide to the Theory of Computation by John MacCormick.
SIGACT News, 2020

2019
Guest Column: The Muffin Problem.
SIGACT News, 2019

Review of Factor Man by Matt Ginsberg.
SIGACT News, 2019

Review of An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics by Matthew Katz and Jan Reimann.
SIGACT News, 2019

Review of Q is for Quantum by Terry Rudolph.
SIGACT News, 2019

Guest Column: The Third P=?NP Poll.
SIGACT News, 2019

Distinct volume subsets via indiscernibles.
Arch. Math. Log., 2019

Problems with a Point - Exploring Math and Computer Science
WorldScientific, ISBN: 9789813279742, 2019

2018
Hilbert's Proof of His Irreducibility Theorem.
Am. Math. Mon., 2018

A Muffin-Theorem Generator.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

2017
Open Problems in Computational Topology.
SIGACT News, 2017

Review of Ramsey Theory for Discrete Structures by Hans Jürgen Prömel.
SIGACT News, 2017

Open Problems Column.
SIGACT News, 2017

2016
On the sizes of DPDAs, PDAs, LBAs.
Theor. Comput. Sci., 2016

Review of: Turing Computability: Theory and Applications by Robert Soare.
SIGACT News, 2016

Open Problems About Grid Coloring and The Complexity of Grid Colorings.
SIGACT News, 2016

Review of: Ramsey Theory over the Integers (Second Edition) by Bruce M. Landman and Aaron Robertson.
SIGACT News, 2016

Review of: Asymptopia by Joel Spencer and Laura Florescu.
SIGACT News, 2016

Review of: The Joy of Factoring by Samuel Wagstaff.
SIGACT News, 2016

Review of The Scholar and the State: In Search of Van der Waerden by Alexander Soifer.
SIGACT News, 2016

Review of Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles by Denis Hirschfeldt.
SIGACT News, 2016

Review of What is College For?: The Public Purpose of Higher Education5 by Ellen Condliffe Lagemann and Harry Lewis.
SIGACT News, 2016

2015
Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems.
ACM Trans. Comput. Theory, 2015

Review of Mathematics Galore: The First Five Years of the St. Marks' Institute of Mathematics by James Tanton.
SIGACT News, 2015

Review of: Structure and Randomness: Pages from Year One of a Mathematical Blog by Terence Tao.
SIGACT News, 2015

Review of: Love and Math: The Heart of Hidden Reality by Edward Frenkel.
SIGACT News, 2015

Review of: Algorithmic Barriers Falling: P=NP? by Donald E. Knuth and Edgar G. Daylight and The Essential Knuth by Donald E. Knuth and Edgar G. Daylight.
SIGACT News, 2015

Review of: Martin Gardner in the Twenty-First Century: Edited by Michael Henle and Brian Hopkins.
SIGACT News, 2015

Review of: Infinitesimal How a dangerous mathematical theory shaped the modern world by Amir Alexander.
SIGACT News, 2015

Review of: The Cult of Pythagoras: Math and Myths by Alberto A. Martinez.
SIGACT News, 2015

Review of: A Walk Through Combinatorics by Miklós Bóna.
SIGACT News, 2015

Distinct Volume Subsets.
SIAM J. Discret. Math., 2015

Which Unbounded Protocol for Envy Free Cake Cutting is Better?
CoRR, 2015

Proving Programs Terminate Using Well-Founded Orderings, Ramsey's Theorem, and Matrices.
Adv. Comput., 2015

Classifying Problems into Complexity Classes.
Adv. Comput., 2015

2014
Review of The Satisfiability Problem: Algorithms and Analyses by Uwe Schöning and Jacobo Torán.
SIGACT News, 2014

The Book Review Column.
SIGACT News, 2014

Review of the Erdös distance problem by Julia Garibaldi, Alex Iosevich and Steven Senger.
SIGACT News, 2014

Review of people, problems, and proofs by Richard Lipton and Ken Regan.
SIGACT News, 2014

Joint reviews of four articles.
SIGACT News, 2014

Review of companion to the papers of Donald Knuth by Donald E. Knuth.
SIGACT News, 2014

Review of selected papers on fun & games by Donald E. Knuth.
SIGACT News, 2014

A Sane Proof that COLk ࣘ COL3.
CoRR, 2014

2013
Review of algorithmic puzzles by Anany Levitin and Maria Levitin.
SIGACT News, 2013

Joint review of the honor class: Hilbert's problems and their solver by Ben Yandell and: Mathematical developments arising from Hilbert's problems edited by Felix Browder.
SIGACT News, 2013

Review of boolean function complexity: advances and frontiers by Stasys Jukna.
SIGACT News, 2013

Applications of the Erdős-Rado Canonical Ramsey Theorem to Erdős-Type Problems.
Electron. Notes Discret. Math., 2013

2012
Review of combinatorial games: tic-tac-toe theory, by Jozsef Beck.
SIGACT News, 2012

Guest Column: the second P =?NP poll.
SIGACT News, 2012

Review of an introduction to the history of algebra solving equations from Mesopotamian Times to the Renaissance by Jacques Sesiano.
SIGACT News, 2012

An NP-Complete Problem in Grid Coloring
CoRR, 2012

2011
Review of those fascinating numbers by Jean-Marie De Konick.
SIGACT News, 2011

Review of Dude, can you count?: stories, challenges, and adventures in mathematics by Christian Constanda.
SIGACT News, 2011

Joint review of the mathemagician and pied piper: a collection in tribute to Martin Gardner.
SIGACT News, 2011

An Application of Ramsey's Theorem to Proving Programs Terminate (An Exposition)
CoRR, 2011

Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive.
Electron. J. Comb., 2011

2010
Review of the pea and the sun: a mathematical paradox by Leonard Wapner Published by A.K. Peters, 2005.
SIGACT News, 2010

Review of the P = NP question and Godel's lost letter by Richard J. Lipton Springer, 2010.
SIGACT News, 2010

Mathematical treks: from surreal numbers to magic circles by Ivars Peterson published by the maa, 2002 170 pages.
SIGACT News, 2010

Games of no chance (1998, edited by Richard Nowakowski) and more games of no chance (2002, edited by Richard Nowakowski) and games of no chance iii (2009, edited by Michael Albert and Richard Nowakowski published by cambridge press).
SIGACT News, 2010

Random curves: journeys of a mathematician by Neal Koblitz published by springer 2008 390 pages.
SIGACT News, 2010

Riot at the calc exam and other mathematically bent stories by Colin Adams, published by the AMS, 2009 271 pages, softcover and The great debate which is the best number? by Colin Adams VS Thomas Garrity, moderated by Edward Burger, published by the MAA, 2006 and The United States of mathematics presidential debate by Colin Adams VS Thomas Garrity, moderated by Edward Burger, published by the MAA, 2009.
SIGACT News, 2010

Logicomix text by Apostolos Doxiadis and Christos Papadimitriou Art by Alecos Papadatos and Annie di Donna, published by Bloomsbury, 2009 314 pages, softcover. comic book!
SIGACT News, 2010

Limits on the Computational Power of Random Strings.
Electron. Colloquium Comput. Complex., 2010

Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions.
Electron. Colloquium Comput. Complex., 2010

2009
Joint review of Professor Stewart's cabinet of mathematical curiosities by Ian Stewart and Five minute mathematics by Ehrhard Behrends and Aha gotcha!-aha insight! by Martin Gardner and Origami, eleusis, and the soma cube by Martin Gardner and Hexaexagons, probability paradoxes, and the tower of Hanoi by Martin Gardner and Group theory in the bedroom and other mathematical diversions by Brian Hayes.
SIGACT News, 2009

Review of the mathematical coloring book: mathematics of coloring and the colorful life of its creators by Alexander Soifer.
SIGACT News, 2009

Review of rock, paper, scissors: game theory for everyday life by Len Fisher (Basic Books, 2008).
SIGACT News, 2009

Review of blown to bits: your life, liberty, and happiness after the digital explosion by Hal Abelson, Ken Ledeen, and Harry Lewis (Addison Wesley, 2008).
SIGACT News, 2009

The Complexity of Finding SUBSEQ(<i>A</i>).
Theory Comput. Syst., 2009

The complexity of learning SUBSEQ(A).
J. Symb. Log., 2009

2008
Inferring answers to queries.
J. Comput. Syst. Sci., 2008

Finding large 3-free sets I: The small n case.
J. Comput. Syst. Sci., 2008

Memorial issue for Carl Smith.
J. Comput. Syst. Sci., 2008

Invitation to Fixed-Parameter Algorithms: Parameterized Complexity Theory: Parameterized Algorithmics: Theory, Practice and Prospects.
Comput. J., 2008

2007
Review of "Research Problems in Discrete Geometry by Brass, Moser, Pach, " Springer-Verlag.
SIGACT News, 2007

Review of "A Century of Scientific Publishing: A collection of essays edited by Fredriksson, " IOS press.
SIGACT News, 2007

Joint review of "Three Blogs by theorists: Computational Complexity (weblog.fortnow.com) by Lance Fortnow, Shtetl-Optimized (www.scottaaronson.com/blog/) by Scott Aaronson, In theory (in-theory.blogspot.com) by Luca Trevisan, ".
SIGACT News, 2007

Review of "Excellence Without a Soul: How a Great University Forgot Education by Harry Lewis, " Public Affairs, 290 pages.
SIGACT News, 2007

2006
Review of "The Square Root of 2: A Dialogue Concerning a Number and a Sequence by David Flannery", Copernicus Books, 2006.
SIGACT News, 2006

A joint review of "Reality Conditions: Short Mathematical Fiction, by Alex Kasman", MAA 2005;"Numb3rs, TV show. CBS", Free. Currently running Fridays at 10: 00PM; "Mathematical Apocryphia: Stories and Annecdotes of Mathematicians and the Mathematical by Steven Kranz", MAA, 2002; "Mathematical Apocryphia Redux: More Stories and Annecdotes of Mathematicians and the Mathematical by Steven Kranz", MAA, 1999.
SIGACT News, 2006

A tight lower bound for restricted pir protocols.
Comput. Complex., 2006

The Multiparty Communication Complexity of Exact-<i>T</i>: Improved Bounds and New Problems.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

The Complexity of Learning SUBSEQ (<i>A</i>).
Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005
Review of "Cryptological Mathematics by Robert Lewand"; MAA, 2000, $33.95, Softcover.
SIGACT News, 2005

Review of "Proofs that Really Count: The Art of Combinatorial Proof by Arthur T. Benjamin and Jennifer J. Quinn"; MAA, 2003.
SIGACT News, 2005

2004
Review of "Handbook of Graph Theory edited by Gross and Yellen." CRC, 2004.
SIGACT News, 2004

Lower bounds on the Deterministic and Quantum Communication Complexity of HAM<sub>n</sub><sup>a</sup>
Electron. Colloquium Comput. Complex., 2004

A Survey on Private Information Retrieval (Column: Computational Complexity).
Bull. EATCS, 2004

Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
CoRR, 2004

Finding Isolated Cliques by Queries -- An Approach to Fault Diagnosis with Many Faults.
Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

The communication complexity of the Exact-N Problem revisited.
Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

2003
When does a random Robin Hood win?
Theor. Comput. Sci., 2003

Constant time parallel sorting: an empirical view.
J. Comput. Syst. Sci., 2003

A Nearly Tight Bound for Private Information Retrieval Protocols
Electron. Colloquium Comput. Complex., 2003

2002
Review of Calculated Bets.
SIGACT News, 2002

Automata techniques for query inference machines.
Ann. Pure Appl. Log., 2002

Max and min limiters.
Arch. Math. Log., 2002

Aha! an illuminating perspective.
Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education, 2002

2001
Review of Proofs and Refutations: author of book: Imre Lakatos.
SIGACT News, 2001

Review of "The CodeBreakers: the story of secrete writing" by David Kahn. Scribner.
SIGACT News, 2001

The Communication Complexity of Enumeration, Elimination, and Selection.
J. Comput. Syst. Sci., 2001

2000
Reviews of THREE books on Fair Division of Resources.
SIGACT News, 2000

Book review: Indiscrete Thoughts by Gina-Carlo Rota (Birkhauser, 1996).
SIGACT News, 2000

The Comlexity of Odd<sup>A</sup><sub>n</sub>.
J. Symb. Log., 2000

Some Connections between Bounded Query Classes and Non-Uniform Complexity
Electron. Colloquium Comput. Complex., 2000

A Survey of Constant Time Parallel Sorting.
Bull. EATCS, 2000

1999
Theoretical Computer Science.
Proceedings of the Handbook of Discrete and Combinatorial Mathematics., 1999

The Book Review Column.
SIGACT News, 1999

Review of <i>Handbook of Combinatorics (in two Volumes)</i>: edited by R. L. Graham, M. Grötschel, L. Lovász.
SIGACT News, 1999

Review of <i>Alogrithms and Theory of Computation Handbook</i>: edited by <i> Mikhail Atallah</i>.
SIGACT News, 1999

On Finding the Number of Graph Automorphisms.
Chic. J. Theor. Comput. Sci., 1999

1998
On the Relative Sizes of Learnable Sets.
Theor. Comput. Sci., 1998

Addition in log<sub>2</sub>n + O(1) Steps on Average: A Simple Analysis.
Theor. Comput. Sci., 1998

Reverse Mathematics and Recursive Graph Theory.
Math. Log. Q., 1998

On the Finiteness of the Recursive Chromatic Number.
Ann. Pure Appl. Log., 1998

Classification Using Information.
Ann. Math. Artif. Intell., 1998

1997
Binary Search and Recursive Graph Problems.
Theor. Comput. Sci., 1997

Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series)).
SIGACT News, 1997

On Bounded Queries and Approximation.
SIAM J. Comput., 1997

Asking Questions Versus Verifiability.
Fundam. Informaticae, 1997

Implementing WS1S via Finite Automata: Performance Issues.
Proceedings of the Automata Implementation, 1997

Team Learning as a Game.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996
Frequency Computation and Bounded Queries.
Theor. Comput. Sci., 1996

Finding the ith largest of n for small i, n.
SIGACT News, 1996

Complexity Theory Newsflash.
SIGACT News, 1996

The Complexity of Problems.
Adv. Comput., 1996

Implementing WS1S via Finite Automata.
Proceedings of the Automata Implementation, 1996

On the Query Complexity of Sets.
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

1995
OptP as the Normal Behavior of NP-Complete Problems.
Math. Syst. Theory, 1995

Learning via Queries with Teams and Anomalies.
Fundam. Informaticae, 1995

Recursion Theoretic Models of Learning: Some Results and Intuitions.
Ann. Math. Artif. Intell., 1995

Unbounded Search and Recursive Graph Problems.
Proceedings of the LATIN '95: Theoretical Informatics, 1995

Measure, Category and Learning Theory.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Reductions for Learning via Queries.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

On Finding the Number of Graph Automorphisms.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
Book Review: Finite Automata, Formal Logic, and Circuit Complexity. By Howard Straubing. (Birkhauser. 1994. xii+226pp. ISBN 0-8176-3719-2. $39.50.).
SIGACT News, 1994

Extremes in the Degrees of Inferability.
Ann. Pure Appl. Log., 1994

The Structure of the Honest Polynomial m-Degrees.
Ann. Pure Appl. Log., 1994

Classification Using Information.
Proceedings of the Algorithmic Learning Theory, 1994

1993
On Checking Versus Evaluation of Multiple Queries
Inf. Comput., July, 1993

Terse, Superterse, and Verbose Sets
Inf. Comput., March, 1993

On Bounded Queries and Approximation
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Learning vi Queries in [+, <].
J. Symb. Log., 1992

Learning via Queries.
J. ACM, 1992

Learning programs with an easy to calculate set of errors.
Fundam. Informaticae, 1992

Selection Problems via M-Ary Queries.
Comput. Complex., 1992

On the Number Components of a Recursive Graph.
Proceedings of the LATIN '92, 1992

Degrees of Inferability.
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991
On Selecting the k Largest with Restricted Quadratic Queries.
Inf. Process. Lett., 1991

The Mapmaker's dilemma.
Discret. Appl. Math., 1991

Bounded Queries in Recursion Theory: A Survey.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990
Learning Via Queries With Teams and Anomilies.
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

Learning Via Queries in [+, <].
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989
Training Sequences.
Theor. Comput. Sci., 1989

Nondeterministic Bounded Query Reducibilities.
Ann. Pure Appl. Log., 1989

On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.
Ann. Pure Appl. Log., 1989

On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.
Ann. Pure Appl. Log., 1989

Bounded query classes and the difference hierarchy.
Arch. Math. Log., 1989

Learning via Queries to an Oracle.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

On Honest Polynomial Reductions, Relativizations, and P=NP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Polynomial Terse Sets
Inf. Comput., April, 1988

1987
Oracles for Deterministic versus Alternating Classes.
SIAM J. Comput., 1987

1986
On the Inference of Sequences of Functions.
Proceedings of the Analogical and Inductive Inference, 1986

1983
Relativizations Comparing NP and Exponential Time
Inf. Control., 1983


  Loading...