Journal and Book Articles by Lisa Hellerstein

  • Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM Journal on Computing, 38(1):63--84, 2008 (with E. Allender, P. McCabe, T. Pitassi, M. E. Saks).

  • Algorithms for distributional and adversarial pipelined filter ordering problems. To appear in ACM Transactions on Algorithms (with A. Condon, A. Desphande, and N. Wu).

  • On PAC learning algorithms for rich Boolean function classes. To appear in Theoretical Computer Science (with Rocco Servedio).

  • Exact learning of DNF formulas using DNF hypotheses. Journal of Computer and System Sciences, 70(4):435--470, 2005 (with Vijay Raghavan). preprint (postcript)

  • Exact learning of DNF formulas using DNF hypotheses. Journal of Computer and System Sciences, 70(4):435--470, 2005 (with Vijay Raghavan). preprint (postcript)

  • On generalized constraints and certificates. Discrete Mathematics, 226:211-232, 2001. Preliminary version issued as RUTCOR Technical Report 26-98, September 1998 (postcript)

  • Equational theories of Boolean functions. Discrete Mathematics, 211:27--51, 2000. Preliminary version issued as DIMACS Technical Report 97-79, December 1997 (with O. Ekin, S. Foldes, and P. Hammer). (compressed postscript file)

  • Conjunctions of unate DNF formulas: Learning and structure. Information and Computation, 140(2):203-228, 1998 (with Aaron Feigelson). (postscript file)

  • Attribute efficient learning in query and mistake-bound models. Attribute efficient learning in query and mistake-bound models Journal of Computing and System Sciences 56:310--319, 1998 (with Nader Bshouty). (postscript file)

  • The forbidden projections of unate functions. Discrete Applied Mathematics 77(3):221-236, 1997 (with Aaron Feigelson) (postscript file)

  • How many queries are needed to learn? JACM 43(5):840-862, 1996 (with K. Pillaipakkamnatt, D. Wilkins, and V. Raghavan). (postscript file)

  • Independence and port oracles for matroids, with an application to computational learning theory. Combinatorica 16(2): 1-20, 1996 (with Collette Coullard). (postscript file)

  • On the power of finite automata with both nondeterministic and probabilistic states. SIAM Journal on Computing 27(3): 739--762, 1998. (with Anne Condon, Samuel Pottle, and Avi Wigderson). (postscript file)

  • Complexity theoretic hardness results for query learning. Computational Complexity 7: 19--53, 1998. (with Howard Aizenstein, Tibor Hegedus, and Leonard Pitt).

  • Learning boolean read-once formulas over generalized bases. Journal of Computer and System Sciences 50(3):521--542, 1995 (with Nader Bshouty and Thomas Hancock). (postscript file)

  • An algorithm to learn read-once threshold formulas, and transformations between l earning models. Computational Complexity 4: 37-61, 1994 (with Nader Bshouty, Thomas Hancock, and Marek Karpinski). (postscript file)

  • Learning arithmetic read-once formulas. SIAM Journal on Computing, 24:4, 1995 (with Nader Bshouty and Thomas Hancock).

  • Learning in the presence of finitely or infinitely many irrelevant attributes. Journal of Computer and System Sciences 50:1, 1995 (with Avrim Blum and Nick Littlestone). (postscript file)

  • Learning read-once formulas with queries. Journal of the Association for Computing Machinery 40:1, 1993 (with Dana Angluin and Marek Karpinski). (postscript file)

  • Functions that are read-once on a subset of their inputs. Discrete Applied Mathematics 46:235-251, 1993. (postscript file)

  • Coding techniques for handling failures in large disk arrays. Algorithmica, 12:182-208, 1994 (with G. Gibson, R.M. Karp, R.H. Katz, and D.A. Patterson). (postscript file)

  • On the time-space complexity of reachability queries for preprocessed graphs. Information Processing Letters 35:261-267, 1990 (with Philip Klein and Robert Wilber).

  • Notes on the complexity of systolic programs. J. Parallel and Distributed Computing, 4:250-265, 1987 (with Stephen Taylor, Shmuel Safra,and Ehud Shapiro).

  • A Concurrent Prolog based region finding algorithm, in E. Shapiro (ed.), Concurrent Prolog: Collected Papers, MIT Press, 1987, Vol. I, pp. 291-317.

  • Implementing parallel algorithms in Concurrent Prolog: The MAXFLOW experience. The Journal of Logic Programming, 3:157-184, 1985 (with Ehud Shapiro).