Journal and Book Articles by Lisa Hellerstein

  • A game theoretic approach to a problem in polymatroid maximization European Journal of Operational Research (in press, available online 2022) (with Thomas Lidbetter).

  • Algorithms for the unit-cost stochastic score classifcation problem Algorithmica, 1--21 (in press, available online 2022) (with Nathaniel Grammel, Devorah Kletenik, and Naifeng Liu).

  • A general framework for approximating min-sum ordering problems INFORMS Journal on Computing 34(3), 1437--1452,2022 (with Felix Happach and Thomas Lidbetter).

  • The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions. Discrete Applied Mathematics 309:269--277, 2022 (with Dimitrios Gkenosis, Nathaniel Grammel, and Devorah Kletenik).

  • Solving zero-sum games using best-response oracles with applications to search games. Operations Research 67(3):731-743, 2019 (with Thomas Lidbetter and Daniel Pirutinsky)

  • Revisiting the approximation bound for stochastic submodular cover. Journal of Artificial Intelligence Research 63:265-279, 2018 (with Devorah Kletenik)

  • Submodular goal value of Boolean functions. Discrete Applied Mathematics 238:1--13, 2018 (with Eric Bach, Jérémie Dusart, and Devorah Kletenik)

  • Evaluation of monotone DNF formulas. Algorithmica 77(3):661--685, 2017 (with Sarah Allen, Devorah Kletenik, and Tonguc Unluyurt)

  • Max-throughput for (conservative) k-of-n testing Algorithmica 77(2):595--618, 2017 (with Linda Sellie and Ozgur Ozkan)

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

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

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