Journal and Book Articles by Lisa Hellerstein
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
Journal of Machine Learning Research, 10:2375-2411, 2009
(with B. Rosell, E. Bach, S. Ray, and D. Page).
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).
Exact learning of DNF formulas using DNF hypotheses.
Journal of Computer and System Sciences, 70(4):435--470, 2005
(with Vijay Raghavan).
On generalized constraints and certificates.
Discrete Mathematics, 226:211-232, 2001.
Preliminary version issued as RUTCOR Technical Report 26-98, September 1998
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).
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).
The forbidden projections of unate functions.
Discrete Applied Mathematics 77(3):221-236, 1997
(with Aaron Feigelson)
How many queries are needed to learn?
JACM 43(5):840-862, 1996 (with K. Pillaipakkamnatt, D. Wilkins, and V. Raghavan).
Independence and port oracles for matroids, with
an application to computational learning theory.
Combinatorica 16(2): 1-20, 1996 (with Collette Coullard).
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).
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
Journal of Computer and System Sciences
(with Nader Bshouty and Thomas Hancock).
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).
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
Journal of Computer and System Sciences 50:1, 1995
Avrim Blum and Nick Littlestone).
Learning read-once formulas with queries.
Journal of the Association for Computing Machinery 40:1, 1993
(with Dana Angluin and Marek Karpinski).
Functions that are read-once on a subset of their inputs.
Discrete Applied Mathematics 46:235-251, 1993.
Coding techniques for handling failures in large disk arrays.
Algorithmica, 12:182-208, 1994
G. Gibson, R.M. Karp, R.H. Katz, and D.A. Patterson).
On the time-space complexity of reachability queries for
Information Processing Letters 35:261-267, 1990
(with Philip Klein and Robert Wilber).
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).