William I. Gasarch
According to our database^{1},
William I. Gasarch
authored at least 162 papers
between 1983 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at id.loc.gov
On csauthors.net:
Bibliography
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
Guest Column: The Third P=?NP Poll.
SIGACT News, 2019
Distinct volume subsets via indiscernibles.
Arch. Math. Log., 2019
2018
Open Problems Column.
SIGACT News, 2018
A MuffinTheorem 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
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 HammingDistance Problems.
TOCT, 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 TwentyFirst 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
The Book Review Column.
SIGACT News, 2015
Distinct Volume Subsets.
SIAM J. Discrete Math., 2015
Which Unbounded Protocol for Envy Free Cake Cutting is Better?
CoRR, 2015
Proving Programs Terminate Using WellFounded Orderings, Ramsey's Theorem, and Matrices.
Advances in Computers, 2015
Classifying Problems into Complexity Classes.
Advances in Computers, 2015
2014
Review of The Satisfiability Problem: Algorithms and Analyses by Uwe Schöning and Jacobo Torán.
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ősRado Canonical Ramsey Theorem to ErdősType Problems.
Electron. Notes Discret. Math., 2013
2012
Review of combinatorial games: tictactoe 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 NPComplete Problem in Grid Coloring
CoRR, 2012
2011
Review of those fascinating numbers by JeanMarie 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 DeterministicConstructive.
Electr. 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.
Electronic Colloquium on Computational Complexity (ECCC), 2010
Exposition of the MuchnikPositselsky Construction of a Prefix Free Entropy Function that is not Complete under TruthTable Reductions.
Electronic Colloquium on Computational Complexity (ECCC), 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(A).
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 3free sets I: The small n case.
J. Comput. Syst. Sci., 2008
Memorial issue for Carl Smith.
J. Comput. Syst. Sci., 2008
Invitation to FixedParameter 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, " SpringerVerlag.
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, ShtetlOptimized (www.scottaaronson.com/blog/) by Scott Aaronson, In theory (intheory.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.
Computational Complexity, 2006
The Multiparty Communication Complexity of ExactT: 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 HammingDistance Problems.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006
The Complexity of Learning SUBSEQ (A).
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_{n}^{a}
Electronic Colloquium on Computational Complexity (ECCC), 2004
A Survey on Private Information Retrieval (Column: Computational Complexity).
Bulletin of the 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 ExactN 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
Electronic Colloquium on Computational Complexity (ECCC), 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, Cincinnati, Kentucky, USA, February 27, 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 GinaCarlo Rota (Birkhauser, 1996).
SIGACT News, 2000
The Comlexity of Odd^{A}_{n}.
J. Symb. Log., 2000
Some Connections between Bounded Query Classes and NonUniform Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2000
A Survey of Constant Time Parallel Sorting.
Bulletin of the 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 Handbook of Combinatorics (in two Volumes): edited by R. L. Graham, M. Grötschel, L. Lovász.
SIGACT News, 1999
Review of Alogrithms and Theory of Computation Handbook: edited by Mikhail Atallah.
SIGACT News, 1999
On Finding the Number of Graph Automorphisms.
Chicago J. Theor. Comput. Sci., 1999
1998
On the Relative Sizes of Learnable Sets.
Theor. Comput. Sci., 1998
Addition in log_{2}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. Inform., 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.
Advances in Computers, 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 NPComplete Problems.
Mathematical Systems Theory, 1995
Learning via Queries with Teams and Anomalies.
Fundam. Inform., 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 0817637192. $39.50.).
SIGACT News, 1994
Extremes in the Degrees of Inferability.
Ann. Pure Appl. Log., 1994
The Structure of the Honest Polynomial mDegrees.
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. Inform., 1992
Selection Problems via MAry Queries.
Computational Complexity, 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, 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
Information and Control, 1983