| 2008 |
|---|
| 112 | EE | William I. Gasarch,
Keung Ma Kin:
Invitation to Fixed-Parameter Algorithms: Parameterized Complexity Theory: Parameterized Algorithmics: Theory, Practice and Prospects.
Comput. J. 51(1): 137-140 (2008) |
| 111 | EE | Stephen A. Fenner,
William I. Gasarch,
Brian Postow:
The complexity of learning SUBSEQ(A).
Electronic Colloquium on Computational Complexity (ECCC) 15(053): (2008) |
| 110 | EE | William I. Gasarch:
Memorial issue for Carl Smith.
J. Comput. Syst. Sci. 74(4): 408 (2008) |
| 109 | EE | William I. Gasarch,
Andrew C. Y. Lee:
Inferring answers to queries.
J. Comput. Syst. Sci. 74(4): 490-512 (2008) |
| 108 | EE | William I. Gasarch,
James Glenn,
Clyde P. Kruskal:
Finding large 3-free sets I: The small n case.
J. Comput. Syst. Sci. 74(4): 628-655 (2008) |
| 107 | EE | William I. Gasarch:
The book review column.
SIGACT News 39(1): 9-12 (2008) |
| 106 | EE | William I. Gasarch:
The book review column.
SIGACT News 39(2): 29-31 (2008) |
| 2007 |
|---|
| 105 | EE | William I. Gasarch:
Review of "Excellence Without a Soul: How a Great University Forgot Education by Harry Lewis, " Public Affairs, 290 pages.
SIGACT News 38(1): 9-13 (2007) |
| 104 | EE | William I. Gasarch:
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 38(2): 23-25 (2007) |
| 103 | EE | William I. Gasarch:
The book review column.
SIGACT News 38(2): 8-10 (2007) |
| 102 | EE | William I. Gasarch:
The book review column.
SIGACT News 38(3): 14-16 (2007) |
| 101 | EE | William I. Gasarch:
The book review column.
SIGACT News 38(4): 16-18 (2007) |
| 100 | EE | William I. Gasarch:
Review of "A Century of Scientific Publishing: A collection of essays edited by Fredriksson, " IOS press.
SIGACT News 38(4): 23-24 (2007) |
| 99 | EE | William I. Gasarch:
Review of "Research Problems in Discrete Geometry by Brass, Moser, Pach, " Springer-Verlag.
SIGACT News 38(4): 31-34 (2007) |
| 2006 |
|---|
| 98 | EE | Stephen A. Fenner,
William I. Gasarch:
The Complexity of Learning SUBSEQ (A).
ALT 2006: 109-123 |
| 97 | EE | Andris Ambainis,
William I. Gasarch,
Aravind Srinivasan,
Andrey Utis:
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.
ISAAC 2006: 628-637 |
| 96 | EE | Richard Beigel,
William I. Gasarch,
James Glenn:
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems.
MFCS 2006: 146-156 |
| 95 | EE | Richard Beigel,
Lance Fortnow,
William I. Gasarch:
A tight lower bound for restricted pir protocols.
Computational Complexity 15(1): 82-91 (2006) |
| 94 | EE | William I. Gasarch:
The book review column.
SIGACT News 37(1): 9-11 (2006) |
| 93 | EE | William I. Gasarch:
The book review column.
SIGACT News 37(2): 10-12 (2006) |
| 92 | EE | William I. Gasarch:
The book review column.
SIGACT News 37(3): 14-17 (2006) |
| 91 | EE | William I. Gasarch:
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 37(3): 17-19 (2006) |
| 90 | EE | William I. Gasarch,
Alexander Kruskal,
Justin Kruskal,
Rebecca Kruskal:
Review of "The Square Root of 2: A Dialogue Concerning a Number and a Sequence by David Flannery", Copernicus Books, 2006.
SIGACT News 37(3): 27-32 (2006) |
| 89 | EE | William I. Gasarch:
The book review column.
SIGACT News 37(4): 27-29 (2006) |
| 2005 |
|---|
| 88 | EE | William I. Gasarch:
Review of "Proofs that Really Count: The Art of Combinatorial Proof by Arthur T. Benjamin and Jennifer J. Quinn"; MAA, 2003.
SIGACT News 36(1): 12-14 (2005) |
| 87 | EE | William I. Gasarch:
The book review column.
SIGACT News 36(2): 3-4 (2005) |
| 86 | EE | William I. Gasarch:
Review of "Cryptological Mathematics by Robert Lewand"; MAA, 2000, $33.95, Softcover.
SIGACT News 36(2): 4-7 (2005) |
| 85 | EE | William I. Gasarch:
The book review column.
SIGACT News 36(3): 4-5 (2005) |
| 84 | EE | William I. Gasarch:
The book review column.
SIGACT News 36(4): 4-5 (2005) |
| 2004 |
|---|
| 83 | EE | William I. Gasarch,
Frank Stephan:
Finding Isolated Cliques by Queries -- An Approach to Fault Diagnosis with Many Faults.
Algebraic Methods in Computational Complexity 2004 |
| 82 | EE | William I. Gasarch,
James Glenn,
Andrey Utis:
The communication complexity of the Exact-N Problem revisited.
Algebraic Methods in Computational Complexity 2004 |
| 81 | EE | William I. Gasarch:
A Survey on Private Information Retrieval (Column: Computational Complexity).
Bulletin of the EATCS 82: 72-107 (2004) |
| 80 | EE | Andris Ambainis,
William I. Gasarch,
Aravind Srinivasan,
Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
CoRR cs.CC/0411076: (2004) |
| 79 | EE | Andris Ambainis,
William I. Gasarch,
Aravind Srinivasan,
Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna
Electronic Colloquium on Computational Complexity (ECCC)(120): (2004) |
| 78 | EE | William I. Gasarch:
The book review column.
SIGACT News 35(1): 3-4 (2004) |
| 77 | EE | William I. Gasarch:
The book review column.
SIGACT News 35(2): 3-4 (2004) |
| 76 | EE | William I. Gasarch:
Review of "Handbook of Graph Theory edited by Gross and Yellen." CRC, 2004.
SIGACT News 35(3): 5-8 (2004) |
| 75 | EE | William I. Gasarch:
The book review column.
SIGACT News 35(4): 4-5 (2004) |
| 2003 |
|---|
| 74 | EE | Richard Beigel,
Lance Fortnow,
William I. Gasarch:
A Nearly Tight Bound for Private Information Retrieval Protocols
Electronic Colloquium on Computational Complexity (ECCC)(087): (2003) |
| 73 | EE | Amihood Amir,
Richard Beigel,
William I. Gasarch:
Some connections between bounded query classes and non-uniform complexity.
Inf. Comput. 186(1): 104-139 (2003) |
| 72 | EE | William I. Gasarch,
Evan Golub,
Clyde P. Kruskal:
Constant time parallel sorting: an empirical view.
J. Comput. Syst. Sci. 67(1): 63-91 (2003) |
| 71 | EE | William I. Gasarch,
Evan Golub,
Aravind Srinivasan:
When does a random Robin Hood win?
Theor. Comput. Sci. 1-3(304): 477-484 (2003) |
| 2002 |
|---|
| 70 | EE | David Ginat,
Daniel D. Garcia,
William I. Gasarch:
Aha! an illuminating perspective.
SIGCSE 2002: 1-2 |
| 69 | | William I. Gasarch,
Geoffrey R. Hird:
Automata techniques for query inference machines.
Ann. Pure Appl. Logic 117(1-3): 169-201 (2002) |
| 68 | EE | James C. Owings,
William I. Gasarch,
Georgia Martin:
Max and min limiters.
Arch. Math. Log. 41(5): 483-495 (2002) |
| 2001 |
|---|
| 67 | EE | Andris Ambainis,
Harry Buhrman,
William I. Gasarch,
Bala Kalyanasundaram,
Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection
Electronic Colloquium on Computational Complexity (ECCC) 8(19): (2001) |
| 66 | | Andris Ambainis,
Harry Buhrman,
William I. Gasarch,
Bala Kalyanasundaram,
Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection.
J. Comput. Syst. Sci. 63(2): 148-185 (2001) |
| 2000 |
|---|
| 65 | EE | Andris Ambainis,
Harry Buhrman,
William I. Gasarch,
Bala Kalyanasundaram,
Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection.
IEEE Conference on Computational Complexity 2000: 44-53 |
| 64 | | William I. Gasarch,
Evan Golub,
Clyde P. Kruskal:
A Survey of Constant Time Parallel Sorting.
Bulletin of the EATCS 72: 84-102 (2000) |
| 63 | EE | Amihood Amir,
Richard Beigel,
William I. Gasarch:
Some Connections between Bounded Query Classes and Non-Uniform Complexity
Electronic Colloquium on Computational Complexity (ECCC) 7(24): (2000) |
| 62 | | Richard Beigel,
William I. Gasarch,
Martin Kummer,
Georgia Martin,
Timothy McNicholl,
Frank Stephan:
The Comlexity of OddAn.
J. Symb. Log. 65(1): 1-18 (2000) |
| 1999 |
|---|
| 61 | EE | Robert Beals,
Richard Chang,
William I. Gasarch,
Jacobo Torán:
On Finding the Number of Graph Automorphisms.
Chicago J. Theor. Comput. Sci. 1999: (1999) |
| 1998 |
|---|
| 60 | | William I. Gasarch,
Mark G. Pleszkoch,
Frank Stephan,
Mahendran Velauthapillai:
Classification Using Information.
Ann. Math. Artif. Intell. 23(1-2): 147-168 (1998) |
| 59 | | William I. Gasarch,
Andrew C. Y. Lee:
On the Finiteness of the Recursive Chromatic Number.
Ann. Pure Appl. Logic 93(1-3): 73-81 (1998) |
| 58 | | William I. Gasarch,
Jeffry L. Hirst:
Reverse Mathematics and Recursive Graph Theory.
Math. Log. Q. 44: 465-473 (1998) |
| 57 | EE | Richard Beigel,
William I. Gasarch,
Ming Li,
Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis.
Theor. Comput. Sci. 191(1-2): 245-248 (1998) |
| 56 | EE | Lance Fortnow,
Rusins Freivalds,
William I. Gasarch,
Martin Kummer,
Stuart A. Kurtz,
Carl H. Smith,
Frank Stephan:
On the Relative Sizes of Learnable Sets.
Theor. Comput. Sci. 197(1-2): 139-156 (1998) |
| 1997 |
|---|
| 55 | | Andris Ambainis,
Kalvis Apsitis,
Rusins Freivalds,
William I. Gasarch,
Carl H. Smith:
Team Learning as a Game.
ALT 1997: 2-17 |
| 54 | EE | William I. Gasarch,
Andrew C. Y. Lee:
Inferring Answers to Queries.
COLT 1997: 275-284 |
| 53 | | James Glenn,
William I. Gasarch:
Implementing WS1S via Finite Automata: Performance Issues.
Workshop on Implementing Automata 1997: 75-86 |
| 52 | | William I. Gasarch,
Mahendran Velauthapillai:
Asking Questions Versus Verifiability.
Fundam. Inform. 30(1): 1-9 (1997) |
| 51 | | Richard Chang,
William I. Gasarch,
Carsten Lund:
On Bounded Queries and Approximation.
SIAM J. Comput. 26(1): 188-209 (1997) |
| 50 | EE | William I. Gasarch,
Katia S. Guimarães:
Binary Search and Recursive Graph Problems.
Theor. Comput. Sci. 181(1): 119-139 (1997) |
| 1996 |
|---|
| 49 | | Richard Beigel,
William I. Gasarch,
Martin Kummer,
Timothy McNicholl,
Frank Stephan:
On the Query Complexity of Sets.
MFCS 1996: 206-217 |
| 48 | | James Glenn,
William I. Gasarch:
Implementing WS1S via Finite Automata.
Workshop on Implementing Automata 1996: 50-63 |
| 47 | | William I. Gasarch:
The Complexity of Problems.
Advances in Computers 43: 215-241 (1996) |
| 46 | EE | Richard Beigel,
William I. Gasarch,
Ming Li,
Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis
Electronic Colloquium on Computational Complexity (ECCC) 3(51): (1996) |
| 45 | EE | Richard Beigel,
William I. Gasarch,
Efim B. Kinber:
Frequency Computation and Bounded Queries.
Theor. Comput. Sci. 163(1&2): 177-192 (1996) |
| 1995 |
|---|
| 44 | EE | William I. Gasarch,
Geoffrey R. Hird:
Reductions for Learning via Queries.
COLT 1995: 152-161 |
| 43 | | William I. Gasarch,
Mark G. Pleszkoch,
Mahendran Velauthapillai:
Classification Using Information.
GOSLER Final Report 1995: 162-173 |
| 42 | | Lance Fortnow,
Rusins Freivalds,
William I. Gasarch,
Martin Kummer,
Stuart A. Kurtz,
Carl H. Smith,
Frank Stephan:
Measure, Category and Learning Theory.
ICALP 1995: 558-569 |
| 41 | | William I. Gasarch,
Katia S. Guimarães:
Unbounded Search and Recursive Graph Problems.
LATIN 1995: 323-331 |
| 40 | | Richard Beigel,
William I. Gasarch,
Efim B. Kinber:
Frequency Computation and Bounded Queries.
Structure in Complexity Theory Conference 1995: 125-132 |
| 39 | | Richard Chang,
William I. Gasarch,
Jacobo Torán:
On Finding the Number of Graph Automorphisms.
Structure in Complexity Theory Conference 1995: 288-298 |
| 38 | | Carl H. Smith,
William I. Gasarch:
Recursion Theoretic Models of Learning: Some Results and Intuitions.
Ann. Math. Artif. Intell. 15(2): 151-166 (1995) |
| 37 | EE | Richard Beigel,
William I. Gasarch,
Efim B. Kinber:
Frequency Computation and Bounded Queries
Electronic Colloquium on Computational Complexity (ECCC) 2(36): (1995) |
| 36 | | William I. Gasarch,
Efim B. Kinber,
Mark G. Pleszkoch,
Carl H. Smith,
Thomas Zeugmann:
Learning via Queries with Teams and Anomalies.
Fundam. Inform. 23(1): 67-89 (1995) |
| 35 | | William I. Gasarch,
Mark W. Krentel,
Kevin J. Rappoport:
OptP as the Normal Behavior of NP-Complete Problems.
Mathematical Systems Theory 28(6): 487-514 (1995) |
| 1994 |
|---|
| 34 | | William I. Gasarch,
Mark G. Pleszkoch,
Mahendran Velauthapillai:
Classification Using Information.
AII/ALT 1994: 290-300 |
| 33 | | Lance Fortnow,
William I. Gasarch,
Sanjay Jain,
Efim B. Kinber,
Martin Kummer,
Stuart A. Kurtz,
Mark Pleszkovich,
Theodore A. Slaman,
Robert Solovay,
Frank Stephan:
Extremes in the Degrees of Inferability.
Ann. Pure Appl. Logic 66(3): 231-276 (1994) |
| 32 | | Rodney G. Downey,
William I. Gasarch,
Michael Moses:
The Structure of the Honest Polynomial m-Degrees.
Ann. Pure Appl. Logic 70(2): 113-139 (1994) |
| 1993 |
|---|
| 31 | | Richard Chang,
William I. Gasarch:
On Bounded Queries and Approximation
FOCS 1993: 547-556 |
| 30 | | Richard Beigel,
William I. Gasarch,
John Gill,
James C. Owings:
Terse, Superterse, and Verbose Sets
Inf. Comput. 103(1): 68-85 (1993) |
| 29 | | William I. Gasarch,
Lane A. Hemachandra,
Albrecht Hoene:
On Checking Versus Evaluation of Multiple Queries
Inf. Comput. 105(1): 72-93 (1993) |
| 1992 |
|---|
| 28 | | William I. Gasarch,
Mahendran Velauthapillai:
Asking Questions Versus Verifiability.
AII 1992: 197-213 |
| 27 | EE | Peter Cholak,
Efim B. Kinber,
Rodney G. Downey,
Martin Kummer,
Lance Fortnow,
Stuart A. Kurtz,
William I. Gasarch,
Theodore A. Slaman:
Degrees of Inferability.
COLT 1992: 180-192 |
| 26 | | William I. Gasarch,
Katia S. Guimarães:
On the Number Components of a Recursive Graph.
LATIN 1992: 177-190 |
| 25 | | Katia S. Guimarães,
William I. Gasarch,
James M. Purtilo:
Selection Problems via M-Ary Queries.
Computational Complexity 2: 256-276 (1992) |
| 24 | | William I. Gasarch,
Ramesh K. Sitaraman,
Carl H. Smith,
Mahendran Velauthapillai:
Learning programs with an easy to calculate set of errors.
Fundam. Inform. 16(3-4): 355-370 (1992) |
| 23 | EE | William I. Gasarch,
Carl H. Smith:
Learning via Queries.
J. ACM 39(3): 649-674 (1992) |
| 22 | | William I. Gasarch,
Mark G. Pleszkoch,
Robert Solovay:
Learning vi Queries in [+, <].
J. Symb. Log. 57(1): 53-81 (1992) |
| 1991 |
|---|
| 21 | | William I. Gasarch:
Bounded Queries in Recursion Theory: A Survey.
Structure in Complexity Theory Conference 1991: 62-78 |
| 20 | EE | Richard Beigel,
William I. Gasarch:
The Mapmaker's dilemma.
Discrete Applied Mathematics 34(1-3): 37-48 (1991) |
| 19 | | William I. Gasarch:
On Selecting the k Largest with Restricted Quadratic Queries.
Inf. Process. Lett. 38(4): 193-195 (1991) |
| 1990 |
|---|
| 18 | EE | Efim B. Kinber,
William I. Gasarch,
Thomas Zeugmann,
Mark G. Pleszkoch,
Carl H. Smith:
Learning Via Queries With Teams and Anomilies.
COLT 1990: 327-337 |
| 17 | EE | William I. Gasarch,
Mark G. Pleszkoch,
Robert Solovay:
Learning Via Queries in [+, <].
COLT 1990: 338-351 |
| 16 | | William I. Gasarch,
Lane A. Hemachandra,
Albrecht Hoene:
On Checking Versus Evaluation of Multiple Queries.
MFCS 1990: 261-268 |
| 15 | | Amihood Amir,
Richard Beigel,
William I. Gasarch:
Some Connections Between Bounded Query Classes and Non-Uniform Complexity.
Structure in Complexity Theory Conference 1990: 232-243 |
| 1989 |
|---|
| 14 | | William I. Gasarch,
Ramesh K. Sitaraman,
Carl H. Smith,
Mahendran Velauthapillai:
Learning Programs With an Easy to Calculate Set of Errors.
AII 1989: 124-137 |
| 13 | EE | William I. Gasarch,
Mark G. Pleszkoch:
Learning via Queries to an Oracle.
COLT 1989: 214-229 |
| 12 | | Rodney G. Downey,
Steven Homer,
William I. Gasarch,
Michael Moses:
On Honest Polynomial Reductions, Relativizations, and P=NP.
Structure in Complexity Theory Conference 1989: 196-207 |
| 11 | | Richard Beigel,
William I. Gasarch,
James C. Owings:
Nondeterministic Bounded Query Reducibilities.
Ann. Pure Appl. Logic 41(2): 107-118 (1989) |
| 10 | | Richard Beigel,
William I. Gasarch:
On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.
Ann. Pure Appl. Logic 45(1): 1-38 (1989) |
| 9 | | Richard Beigel,
William I. Gasarch:
On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.
Ann. Pure Appl. Logic 45(3): 227-246 (1989) |
| 8 | | Dana Angluin,
William I. Gasarch,
Carl H. Smith:
Training Sequences.
Theor. Comput. Sci. 66(3): 255-272 (1989) |
| 1988 |
|---|
| 7 | EE | William I. Gasarch,
Carl H. Smith:
Learning via Queries.
COLT 1988: 227-241 |
| 6 | EE | William I. Gasarch,
Ramesh K. Sitaraman,
Carl H. Smith,
Mahendran Velauthapillai:
Learning Programs with an Easy to Calculate Set of Errors.
COLT 1988: 242-250 |
| 5 | | William I. Gasarch,
Carl H. Smith:
Learning via Queries
FOCS 1988: 130-137 |
| 4 | | Amihood Amir,
William I. Gasarch:
Polynomial Terse Sets
Inf. Comput. 77(1): 37-56 (1988) |
| 1987 |
|---|
| 3 | | William I. Gasarch:
Oracles for Deterministic versus Alternating Classes.
SIAM J. Comput. 16(4): 613-627 (1987) |
| 1986 |
|---|
| 2 | | William I. Gasarch,
Carl H. Smith:
On the Inference of Sequences of Functions.
AII 1986: 23-41 |
| 1983 |
|---|
| 1 | | William I. Gasarch,
Steven Homer:
Relativizations Comparing NP and Exponential Time
Information and Control 58(1-3): 88-100 (1983) |
