William I. Gasarch

241 papers A* 11A 2B 8Journal 203Unranked 16
YearRankTypeTitle / Venue / Authors
2019 J jnl
Guest Column: The Third P=?NP Poll.
SIGACT News
William I. Gasarch
2018 J jnl
Open Problems Column.
SIGACT News
William I. Gasarch
2017 J jnl
Open Problems Column.
SIGACT News
William I. Gasarch
2017 J jnl
Open Problems Column.
SIGACT News
William I. Gasarch
2017 J jnl
Open Problems Column.
SIGACT News
William I. Gasarch
2017 J jnl
Open Problems in Computational Topology.
SIGACT News
William I. Gasarch, Brittany Terese Fasy, Bei Wang
2017 J jnl
Review of Ramsey Theory for Discrete Structures by Hans Jürgen Prömel.
SIGACT News
William I. Gasarch
2016 J jnl
On the sizes of DPDAs, PDAs, LBAs.
Theor. Comput. Sci.
Richard Beigel, William I. Gasarch
2016 J jnl
Open Problems About Grid Coloring and The Complexity of Grid Colorings.
SIGACT News
William I. Gasarch
2016 J jnl
Review of Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles by Denis Hirschfeldt.
SIGACT News
William I. Gasarch
2016 J jnl
Review of The Scholar and the State: In Search of Van der Waerden by Alexander Soifer.
SIGACT News
William I. Gasarch
2016 J jnl
Review of What is College For?: The Public Purpose of Higher Education5 by Ellen Condliffe Lagemann and Harry Lewis.
SIGACT News
William I. Gasarch
2016 J jnl
Review of: Asymptopia by Joel Spencer and Laura Florescu.
SIGACT News
William I. Gasarch
2016 J jnl
Review of: Ramsey Theory over the Integers (Second Edition) by Bruce M. Landman and Aaron Robertson.
SIGACT News
William I. Gasarch
2016 J jnl
Review of: The Joy of Factoring by Samuel Wagstaff.
SIGACT News
William I. Gasarch
2016 J jnl
Review of: Turing Computability: Theory and Applications by Robert Soare.
SIGACT News
William I. Gasarch
2015 J jnl
Classifying Problems into Complexity Classes.
Adv. Comput.
William I. Gasarch
2015 J jnl
Distinct Volume Subsets.
SIAM J. Discret. Math.
David Conlon, Jacob Fox, William I. Gasarch, David G. Harris, Douglas Ulrich, Samuel Zbarsky
2015 J jnl
Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems.
ACM Trans. Comput. Theory
Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2015 J jnl
On the Sizes of DPDAs, PDAs, LBAs.
CoRR
Richard Beigel, William I. Gasarch
2015 J jnl
Proving Programs Terminate Using Well-Founded Orderings, Ramsey's Theorem, and Matrices.
Adv. Comput.
William I. Gasarch
2015 J jnl
Review of Mathematics Galore: The First Five Years of the St. Marks' Institute of Mathematics by James Tanton.
SIGACT News
William I. Gasarch
2015 J jnl
Review of: A Walk Through Combinatorics by Miklós Bóna.
SIGACT News
William I. Gasarch
2015 J jnl
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
William I. Gasarch
2015 J jnl
Review of: Infinitesimal How a dangerous mathematical theory shaped the modern world by Amir Alexander.
SIGACT News
William I. Gasarch
2015 J jnl
Review of: Love and Math: The Heart of Hidden Reality by Edward Frenkel.
SIGACT News
William I. Gasarch
2015 J jnl
Review of: Martin Gardner in the Twenty-First Century: Edited by Michael Henle and Brian Hopkins.
SIGACT News
William I. Gasarch
2015 J jnl
Review of: Structure and Randomness: Pages from Year One of a Mathematical Blog by Terence Tao.
SIGACT News
William I. Gasarch
2015 J jnl
Review of: The Cult of Pythagoras: Math and Myths by Alberto A. Martinez.
SIGACT News
William I. Gasarch
2015 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
2015 J jnl
Which Unbounded Protocol for Envy Free Cake Cutting is Better?
CoRR
William I. Gasarch
2014 J jnl
A Sane Proof that COLk ࣘ COL3.
CoRR
William I. Gasarch
2014 J jnl
Distinct volume subsets.
CoRR
David Conlon, Jacob Fox, William I. Gasarch, David G. Harris, Douglas Ulrich, Sam Zbarsky
2014 J jnl
Joint reviews of four articles.
SIGACT News
William I. Gasarch
2014 J jnl
Review of The Satisfiability Problem: Algorithms and Analyses by Uwe Schöning and Jacobo Torán.
SIGACT News
William I. Gasarch
2014 J jnl
Review of companion to the papers of Donald Knuth by Donald E. Knuth.
SIGACT News
William I. Gasarch
2014 J jnl
Review of people, problems, and proofs by Richard Lipton and Ken Regan.
SIGACT News
William I. Gasarch
2014 J jnl
Review of selected papers on fun & games by Donald E. Knuth.
SIGACT News
William I. Gasarch
2014 J jnl
Review of the Erdös distance problem by Julia Garibaldi, Alex Iosevich and Steven Senger.
SIGACT News
William I. Gasarch
2014 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
2014 J jnl
The book review column.
SIGACT News
William I. Gasarch
2014 J jnl
The book review column.
SIGACT News
William I. Gasarch
2013 J jnl
Applications of the Erdős-Rado Canonical Ramsey Theorem to Erdős-Type Problems.
Electron. Notes Discret. Math.
William I. Gasarch, Sam Zbarsky
2013 J jnl
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
William I. Gasarch
2013 J jnl
Limits on the computational power of random strings.
Inf. Comput.
Eric Allender, Luke Friedman, William I. Gasarch
2013 J jnl
Review of algorithmic puzzles by Anany Levitin and Maria Levitin.
SIGACT News
William I. Gasarch
2013 J jnl
Review of boolean function complexity: advances and frontiers by Stasys Jukna.
SIGACT News
William I. Gasarch
2013 J jnl
The book review column.
SIGACT News
William I. Gasarch
2013 J jnl
The book review column.
SIGACT News
William I. Gasarch
2012 J jnl
An NP-Complete Problem in Grid Coloring
CoRR
William I. Gasarch, Kevin Lawler
2012 J jnl
Guest Column: the second P =?NP poll.
SIGACT News
William I. Gasarch
2012 J jnl
Review of an introduction to the history of algebra solving equations from Mesopotamian Times to the Renaissance by Jacques Sesiano.
SIGACT News
William I. Gasarch
2012 J jnl
Review of combinatorial games: tic-tac-toe theory, by Jozsef Beck.
SIGACT News
William I. Gasarch
2012 J jnl
The book review column.
SIGACT News
William I. Gasarch
2012 J jnl
The book review column.
SIGACT News
William I. Gasarch
2012 J jnl
The book review column.
SIGACT News
William I. Gasarch
2012 J jnl
The book review column.
SIGACT News
William I. Gasarch
2011 J jnl
An Application of Ramsey's Theorem to Proving Programs Terminate (An Exposition)
CoRR
William I. Gasarch
2011 J jnl
Joint review of the mathemagician and pied piper: a collection in tribute to Martin Gardner.
SIGACT News
William I. Gasarch
2011 — conf
Limits on the Computational Power of Random Strings.
ICALP (1)
Eric Allender, Luke Friedman, William I. Gasarch
2011 J jnl
Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive.
Electron. J. Comb.
William I. Gasarch, Bernhard Haeupler
2011 J jnl
Review of Dude, can you count?: stories, challenges, and adventures in mathematics by Christian Constanda.
SIGACT News
William I. Gasarch
2011 J jnl
Review of those fascinating numbers by Jean-Marie De Konick.
SIGACT News
William I. Gasarch
2011 J jnl
The book review column.
SIGACT News
William I. Gasarch
2011 J jnl
The book review column.
SIGACT News
William I. Gasarch
2011 J jnl
The book review column.
SIGACT News
William I. Gasarch
2011 J jnl
The book review column.
SIGACT News
William I. Gasarch
2010 J jnl
Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions.
Electron. Colloquium Comput. Complex.
Eric Allender, Luke Friedman, William I. Gasarch
2010 J jnl
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
William I. Gasarch
2010 J jnl
Limits on the Computational Power of Random Strings.
Electron. Colloquium Comput. Complex.
Eric Allender, Luke Friedman, William I. Gasarch
2010 J jnl
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
William I. Gasarch
2010 J jnl
Mathematical treks: from surreal numbers to magic circles by Ivars Peterson published by the maa, 2002 170 pages.
SIGACT News
William I. Gasarch
2010 J jnl
Random curves: journeys of a mathematician by Neal Koblitz published by springer 2008 390 pages.
SIGACT News
William I. Gasarch
2010 J jnl
Review of the P = NP question and Godel's lost letter by Richard J. Lipton Springer, 2010.
SIGACT News
William I. Gasarch
2010 J jnl
Review of the pea and the sun: a mathematical paradox by Leonard Wapner Published by A.K. Peters, 2005.
SIGACT News
William I. Gasarch
2010 J jnl
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
William I. Gasarch
2010 J jnl
The book review column.
SIGACT News
William I. Gasarch
2010 J jnl
The book review column.
SIGACT News
William I. Gasarch
2010 J jnl
The book review column.
SIGACT News
William I. Gasarch
2010 J jnl
The book review column.
SIGACT News
William I. Gasarch
2009 J jnl
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
William I. Gasarch
2009 J jnl
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
William I. Gasarch
2009 J jnl
Review of rock, paper, scissors: game theory for everyday life by Len Fisher (Basic Books, 2008).
SIGACT News
William I. Gasarch
2009 J jnl
Review of the mathematical coloring book: mathematics of coloring and the colorful life of its creators by Alexander Soifer.
SIGACT News
William I. Gasarch
2009 J jnl
The Complexity of Finding SUBSEQ(
Theory Comput. Syst.
Stephen A. Fenner, William I. Gasarch, Brian Postow
2009 J jnl
The book review column.
SIGACT News
William I. Gasarch
2009 J jnl
The book review column.
SIGACT News
William I. Gasarch
2009 J jnl
The book review column.
SIGACT News
William I. Gasarch
2009 J jnl
The book review column.
SIGACT News
William I. Gasarch
2009 J jnl
The complexity of learning SUBSEQ(A).
J. Symb. Log.
Stephen A. Fenner, William I. Gasarch, Brian Postow
2008 J jnl
Finding large 3-free sets I: The small n case.
J. Comput. Syst. Sci.
William I. Gasarch, James Glenn, Clyde P. Kruskal
2008 J jnl
Inferring answers to queries.
J. Comput. Syst. Sci.
William I. Gasarch, Andrew C. Y. Lee
2008 J jnl
Invitation to Fixed-Parameter Algorithms: Parameterized Complexity Theory: Parameterized Algorithmics: Theory, Practice and Prospects.
Comput. J.
William I. Gasarch, Keung Ma Kin
2008 J jnl
Memorial issue for Carl Smith.
J. Comput. Syst. Sci.
William I. Gasarch
2008 J jnl
The book review column.
SIGACT News
William I. Gasarch
2008 J jnl
The book review column.
SIGACT News
William I. Gasarch
2008 J jnl
The book review column.
SIGACT News
William I. Gasarch
2008 J jnl
The complexity of learning SUBSEQ(A).
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, William I. Gasarch, Brian Postow
2007 J jnl
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
William I. Gasarch
2007 J jnl
Review of "A Century of Scientific Publishing: A collection of essays edited by Fredriksson, " IOS press.
SIGACT News
William I. Gasarch
2007 J jnl
Review of "Excellence Without a Soul: How a Great University Forgot Education by Harry Lewis, " Public Affairs, 290 pages.
SIGACT News
William I. Gasarch
2007 J jnl
Review of "Research Problems in Discrete Geometry by Brass, Moser, Pach, " Springer-Verlag.
SIGACT News
William I. Gasarch
2007 J jnl
The book review column.
SIGACT News
William I. Gasarch
2007 J jnl
The book review column.
SIGACT News
William I. Gasarch
2007 J jnl
The book review column.
SIGACT News
William I. Gasarch
2006 J jnl
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
William I. Gasarch
2006 J jnl
A tight lower bound for restricted pir protocols.
Comput. Complex.
Richard Beigel, Lance Fortnow, William I. Gasarch
2006 B conf
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.
ISAAC
Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2006 J jnl
Review of "The Square Root of 2: A Dialogue Concerning a Number and a Sequence by David Flannery", Copernicus Books, 2006.
SIGACT News
William I. Gasarch, Alexander Kruskal, Justin Kruskal, Rebecca Kruskal
2006 B conf
The Complexity of Learning SUBSEQ (
ALT
Stephen A. Fenner, William I. Gasarch
2006 B conf
The Multiparty Communication Complexity of Exact-
MFCS
Richard Beigel, William I. Gasarch, James Glenn
2006 J jnl
The book review column.
SIGACT News
William I. Gasarch
2006 J jnl
The book review column.
SIGACT News
William I. Gasarch
2006 J jnl
The book review column.
SIGACT News
William I. Gasarch
2006 J jnl
The book review column.
SIGACT News
William I. Gasarch
2005 J jnl
Review of "Cryptological Mathematics by Robert Lewand"; MAA, 2000, $33.95, Softcover.
SIGACT News
William I. Gasarch
2005 J jnl
Review of "Proofs that Really Count: The Art of Combinatorial Proof by Arthur T. Benjamin and Jennifer J. Quinn"; MAA, 2003.
SIGACT News
William I. Gasarch
2005 J jnl
The book review column.
SIGACT News
William I. Gasarch
2005 J jnl
The book review column.
SIGACT News
William I. Gasarch
2005 J jnl
The book review column.
SIGACT News
William I. Gasarch
2004 J jnl
A Survey on Private Information Retrieval (Column: Computational Complexity).
Bull. EATCS
William I. Gasarch
2004 — conf
Finding Isolated Cliques by Queries -- An Approach to Fault Diagnosis with Many Faults.
Algebraic Methods in Computational Complexity
William I. Gasarch, Frank Stephan
2004 J jnl
Lower bounds on the Deterministic and Quantum Communication Complexity of HAM
Electron. Colloquium Comput. Complex.
Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2004 J jnl
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
CoRR
Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis
2004 J jnl
Review of "Handbook of Graph Theory edited by Gross and Yellen." CRC, 2004.
SIGACT News
William I. Gasarch
2004 J jnl
The book review column.
SIGACT News
William I. Gasarch
2004 J jnl
The book review column.
SIGACT News
William I. Gasarch
2004 J jnl
The book review column.
SIGACT News
William I. Gasarch
2004 — conf
The communication complexity of the Exact-N Problem revisited.
Algebraic Methods in Computational Complexity
William I. Gasarch, James Glenn, Andrey Utis
2003 J jnl
A Nearly Tight Bound for Private Information Retrieval Protocols
Electron. Colloquium Comput. Complex.
Richard Beigel, Lance Fortnow, William I. Gasarch
2003 J jnl
Constant time parallel sorting: an empirical view.
J. Comput. Syst. Sci.
William I. Gasarch, Evan Golub, Clyde P. Kruskal
2003 J jnl
Some connections between bounded query classes and non-uniform complexity.
Inf. Comput.
Amihood Amir, Richard Beigel, William I. Gasarch
2003 J jnl
The book review column.
SIGACT News
William I. Gasarch
2003 J jnl
The book review column.
SIGACT News
William I. Gasarch
2003 J jnl
The book review column.
SIGACT News
William I. Gasarch
2003 J jnl
The book review column.
SIGACT News
William I. Gasarch
2003 J jnl
When does a random Robin Hood win?
Theor. Comput. Sci.
William I. Gasarch, Evan Golub, Aravind Srinivasan
2002 A conf
Aha! an illuminating perspective.
SIGCSE
David Ginat, Daniel D. Garcia, William I. Gasarch
2002 J jnl
Automata techniques for query inference machines.
Ann. Pure Appl. Log.
William I. Gasarch, Geoffrey R. Hird
2002 J jnl
Max and min limiters.
Arch. Math. Log.
James C. Owings, William I. Gasarch, Georgia Martin
2002 J jnl
Review of Calculated Bets.
SIGACT News
William I. Gasarch
2002 J jnl
The book review column.
SIGACT News
William I. Gasarch
2002 J jnl
The book review column.
SIGACT News
William I. Gasarch
2002 J jnl
The book review column.
SIGACT News
William I. Gasarch
2002 J jnl
The book review column.
SIGACT News
William I. Gasarch
2001 J jnl
Review of "The CodeBreakers: the story of secrete writing" by David Kahn. Scribner.
SIGACT News
William I. Gasarch
2001 J jnl
Review of Proofs and Refutations: author of book: Imre Lakatos.
SIGACT News
William I. Gasarch
2001 J jnl
The Communication Complexity of Enumeration, Elimination, and Selection
Electron. Colloquium Comput. Complex.
Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
2001 J jnl
The Communication Complexity of Enumeration, Elimination, and Selection.
J. Comput. Syst. Sci.
Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
2001 J jnl
The book review column.
SIGACT News
William I. Gasarch
2001 J jnl
The book review column.
SIGACT News
William I. Gasarch
2001 J jnl
The book review column.
SIGACT News
William I. Gasarch
2000 J jnl
A Survey of Constant Time Parallel Sorting.
Bull. EATCS
William I. Gasarch, Evan Golub, Clyde P. Kruskal
2000 J jnl
Book review: Indiscrete Thoughts by Gina-Carlo Rota (Birkhauser, 1996).
SIGACT News
William I. Gasarch
2000 J jnl
Reviews of THREE books on Fair Division of Resources.
SIGACT News
William I. Gasarch
2000 J jnl
Some Connections between Bounded Query Classes and Non-Uniform Complexity
Electron. Colloquium Comput. Complex.
Amihood Amir, Richard Beigel, William I. Gasarch
2000 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
2000 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
2000 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
2000 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
2000 J jnl
The Comlexity of Odd
J. Symb. Log.
Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy H. McNicholl, Frank Stephan
2000 A conf
The Communication Complexity of Enumeration, Elimination, and Selection.
CCC
Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet
1999 J jnl
On Finding the Number of Graph Automorphisms.
Chic. J. Theor. Comput. Sci.
Robert Beals, Richard Chang, William I. Gasarch, Jacobo Torán
1999 J jnl
Review of
SIGACT News
William I. Gasarch
1999 J jnl
Review of
SIGACT News
William I. Gasarch
1999 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1999 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1999 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch, Samir Khuller
1999 J jnl
The book review column.
SIGACT News
William I. Gasarch
1999 — ch.
Theoretical Computer Science.
Handbook of Discrete and Combinatorial Mathematics
William I. Gasarch, Arto Salomaa, Thomas H. Cormen, Lane A. Hemaspaandra, Milena Mihail
1998 J jnl
Addition in log
Theor. Comput. Sci.
Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang
1998 J jnl
Classification Using Information.
Ann. Math. Artif. Intell.
William I. Gasarch, Mark G. Pleszkoch, Frank Stephan, Mahendran Velauthapillai
1998 J jnl
On the Finiteness of the Recursive Chromatic Number.
Ann. Pure Appl. Log.
William I. Gasarch, Andrew C. Y. Lee
1998 J jnl
On the Relative Sizes of Learnable Sets.
Theor. Comput. Sci.
Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan
1998 J jnl
Reverse Mathematics and Recursive Graph Theory.
Math. Log. Q.
William I. Gasarch, Jeffry L. Hirst
1998 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1998 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1998 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1998 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1997 J jnl
Asking Questions Versus Verifiability.
Fundam. Informaticae
William I. Gasarch, Mahendran Velauthapillai
1997 J jnl
Binary Search and Recursive Graph Problems.
Theor. Comput. Sci.
William I. Gasarch, Katia S. Guimarães
1997 J jnl
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
William I. Gasarch
1997 — conf
Implementing WS1S via Finite Automata: Performance Issues.
Workshop on Implementing Automata
James Glenn, William I. Gasarch
1997 A* conf
Inferring Answers to Queries.
COLT
William I. Gasarch, Andrew C. Y. Lee
1997 J jnl
On Bounded Queries and Approximation.
SIAM J. Comput.
Richard Chang, William I. Gasarch, Carsten Lund
1997 B conf
Team Learning as a Game.
ALT
Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, William I. Gasarch, Carl H. Smith
1997 J jnl
The Book Review Column.
SIGACT News
William I. Gasarch
1996 J jnl
Addition in log
Electron. Colloquium Comput. Complex.
Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang
1996 J jnl
Complexity Theory Newsflash.
SIGACT News
Stephen A. Fenner, Lance Fortnow, William I. Gasarch
1996 J jnl
Finding the ith largest of n for small i, n.
SIGACT News
William I. Gasarch, Wayne Kelly, William W. Pugh
1996 J jnl
Frequency Computation and Bounded Queries.
Theor. Comput. Sci.
Richard Beigel, William I. Gasarch, Efim B. Kinber
1996 — conf
Implementing WS1S via Finite Automata.
Workshop on Implementing Automata
James Glenn, William I. Gasarch
1996 B conf
On the Query Complexity of Sets.
MFCS
Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan
1996 J jnl
The Complexity of Problems.
Adv. Comput.
William I. Gasarch
1995 — conf
Classification Using Information.
GOSLER Final Report
William I. Gasarch, Mark G. Pleszkoch, Mahendran Velauthapillai
1995 J jnl
Frequency Computation and Bounded Queries
Electron. Colloquium Comput. Complex.
Richard Beigel, William I. Gasarch, Efim B. Kinber
1995 — conf
Frequency Computation and Bounded Queries.
SCT
Richard Beigel, William I. Gasarch, Efim B. Kinber
1995 J jnl
Learning via Queries with Teams and Anomalies.
Fundam. Informaticae
William I. Gasarch, Efim B. Kinber, Mark G. Pleszkoch, Carl H. Smith, Thomas Zeugmann
1995 A* conf
Measure, Category and Learning Theory.
ICALP
Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan
1995 — conf
On Finding the Number of Graph Automorphisms.
SCT
Richard Chang, William I. Gasarch, Jacobo Torán
1995 J jnl
OptP as the Normal Behavior of NP-Complete Problems.
Math. Syst. Theory
William I. Gasarch, Mark W. Krentel, Kevin J. Rappoport
1995 J jnl
Recursion Theoretic Models of Learning: Some Results and Intuitions.
Ann. Math. Artif. Intell.
Carl H. Smith, William I. Gasarch
1995 A* conf
Reductions for Learning via Queries.
COLT
William I. Gasarch, Geoffrey R. Hird
1995 B conf
Unbounded Search and Recursive Graph Problems.
LATIN
William I. Gasarch, Katia S. Guimarães
1994 J jnl
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
William I. Gasarch
1994 — conf
Classification Using Information.
AII/ALT
William I. Gasarch, Mark G. Pleszkoch, Mahendran Velauthapillai
1994 J jnl
Extremes in the Degrees of Inferability.
Ann. Pure Appl. Log.
Lance Fortnow, William I. Gasarch, Sanjay Jain, Efim B. Kinber, Martin Kummer, Stuart A. Kurtz, Mark Pleszkovich, Theodore A. Slaman, Robert Solovay, Frank Stephan
1994 J jnl
The Structure of the Honest Polynomial m-Degrees.
Ann. Pure Appl. Log.
Rodney G. Downey, William I. Gasarch, Michael F. Moses
1993 A* conf
On Bounded Queries and Approximation
FOCS
Richard Chang, William I. Gasarch
1993 J jnl
On Checking Versus Evaluation of Multiple Queries
Inf. Comput.
William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene
1993 J jnl
Terse, Superterse, and Verbose Sets
Inf. Comput.
Richard Beigel, William I. Gasarch, John Gill, James C. Owings
1992 — conf
Asking Questions Versus Verifiability.
AII
William I. Gasarch, Mahendran Velauthapillai
1992 A* conf
Degrees of Inferability.
COLT
Peter Cholak, Efim B. Kinber, Rodney G. Downey, Martin Kummer, Lance Fortnow, Stuart A. Kurtz, William I. Gasarch, Theodore A. Slaman
1992 J jnl
Learning programs with an easy to calculate set of errors.
Fundam. Informaticae
William I. Gasarch, Ramesh K. Sitaraman, Carl H. Smith, Mahendran Velauthapillai
1992 J jnl
Learning vi Queries in [+, <].
J. Symb. Log.
William I. Gasarch, Mark G. Pleszkoch, Robert Solovay
1992 J jnl
Learning via Queries.
J. ACM
William I. Gasarch, Carl H. Smith
1992 B conf
On the Number Components of a Recursive Graph.
LATIN
William I. Gasarch, Katia S. Guimarães
1992 J jnl
Selection Problems via M-Ary Queries.
Comput. Complex.
Katia S. Guimarães, William I. Gasarch, James M. Purtilo
1991 — conf
Bounded Queries in Recursion Theory: A Survey.
SCT
William I. Gasarch
1991 J jnl
On Selecting the k Largest with Restricted Quadratic Queries.
Inf. Process. Lett.
William I. Gasarch
1991 J jnl
The Mapmaker's dilemma.
Discret. Appl. Math.
Richard Beigel, William I. Gasarch
1990 A* conf
Learning Via Queries With Teams and Anomilies.
COLT
Efim B. Kinber, William I. Gasarch, Thomas Zeugmann, Mark G. Pleszkoch, Carl H. Smith
1990 A* conf
Learning Via Queries in [+, <].
COLT
William I. Gasarch, Mark G. Pleszkoch, Robert Solovay
1990 B conf
On Checking Versus Evaluation of Multiple Queries.
MFCS
William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene
1990 — conf
Some Connections Between Bounded Query Classes and Non-Uniform Complexity.
SCT
Amihood Amir, Richard Beigel, William I. Gasarch
1989 J jnl
Bounded query classes and the difference hierarchy.
Arch. Math. Log.
Richard Beigel, William I. Gasarch, Louise Hay
1989 — conf
Learning Programs With an Easy to Calculate Set of Errors.
AII
William I. Gasarch, Ramesh K. Sitaraman, Carl H. Smith, Mahendran Velauthapillai
1989 A* conf
Learning via Queries to an Oracle.
COLT
William I. Gasarch, Mark G. Pleszkoch
1989 J jnl
Nondeterministic Bounded Query Reducibilities.
Ann. Pure Appl. Log.
Richard Beigel, William I. Gasarch, James C. Owings
1989 — conf
On Honest Polynomial Reductions, Relativizations, and P=NP.
SCT
Rodney G. Downey, Steven Homer, William I. Gasarch, Michael F. Moses
1989 J jnl
On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.
Ann. Pure Appl. Log.
Richard Beigel, William I. Gasarch
1989 J jnl
On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.
Ann. Pure Appl. Log.
Richard Beigel, William I. Gasarch
1989 J jnl
Training Sequences.
Theor. Comput. Sci.
Dana Angluin, William I. Gasarch, Carl H. Smith
1988 A* conf
Learning Programs with an Easy to Calculate Set of Errors.
COLT
William I. Gasarch, Ramesh K. Sitaraman, Carl H. Smith, Mahendran Velauthapillai
1988 A* conf
Learning via Queries
FOCS
William I. Gasarch, Carl H. Smith
1988 A* conf
Learning via Queries.
COLT
William I. Gasarch, Carl H. Smith
1988 J jnl
Polynomial Terse Sets
Inf. Comput.
Amihood Amir, William I. Gasarch
1987 J jnl
Oracles for Deterministic versus Alternating Classes.
SIAM J. Comput.
William I. Gasarch
1987 — conf
Polynomial terse sets.
SCT
Amihood Amir, William I. Gasarch
1986 — conf
On the Inference of Sequences of Functions.
AII
William I. Gasarch, Carl H. Smith
1983 J jnl
Relativizations Comparing NP and Exponential Time
Inf. Control.
William I. Gasarch, Steven Homer