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