The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

William I. Gasarch: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  81. Max and min limiters. [Citation Graph (, )][DBLP]


  82. Invitation to Fixed-Parameter Algorithms: Parameterized Complexity Theory: Parameterized Algorithmics: Theory, Practice and Prospects. [Citation Graph (, )][DBLP]


  83. The Mapmaker's dilemma. [Citation Graph (, )][DBLP]


  84. The complexity of learning SUBSEQ(A). [Citation Graph (, )][DBLP]


Search in 0.006secs, Finished in 0.011secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002