Journal and Book Articles by Lisa Hellerstein

  • Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack ACM Transacations on Algorithms 12:3 (42) (2016) (with Amol Deshpande and Devorah Kletenik)
  • Evaluation of monotone DNF formulas to appear in Algorithmica [available online (2015) doi:10.1007/s00453-015-0092-9] (with Sarah Allen, Devorah Kletenik, and Tonguc Unluyurt)
  • Max-throughput for (conservative) k-of-n testing to appear in Algorithmica [available online (2015) doi:10.1007/s00453-015-0089-4] (with Linda Sellie and Ozgur Ozkan)
  • On the gap between ess(f) and cnf_size(f). Discrete Applied Mathematics 161(1-2): 19-27 (2013) (with Devorah Kletenik). (arXiv version)
  • Parallel pipelined filter ordering with precedence constraints. ACM Transactions on Algorithms 8(4): 41 (2012) (with Amol Deshpande).
  • Exploiting product distributions to identify relevant variables of correlation i mmune functions. Journal of Machine Learning Research, 10:2375-2411, 2009 (with B. Rosell, E. Bach, S. Ray, and D. Page). (pdf)

  • 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. ACM Transactions on Algorithms, 5(2):1--34, 2009 (with A. Condon, A. Deshpande, and N. Wu). Copyright ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Algorithms, Volume 5, Number 2, March 2009. http://doi.acm.org/10.1145/1497290.1497300 (pdf)

  • On PAC learning algorithms for rich Boolean function classes. Theoretical Computer Science, 384(1):66--76, 2007 (with Rocco Servedio). (postscript)

  • Exact learning of DNF formulas using DNF hypotheses. Journal of Computer and System Sciences, 70(4):435--470, 2005 (with Vijay Raghavan). (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)

  • 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)

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

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

  • 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).