## Conference Papers by Lisa Hellerstein

**Scenario Submodular Cover. **Workshop on Approximation and Online Algorithms (WAOA), 2016: 116-128 (with Nathaniel Grammel, Devorah Kletenik, and Patrick Lin).

**Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline. ** Algorithms and Complexity-9th International Conference (CIAC), 2015: 235-248 (with Devorah Kletenik and Patrick Lin).
** Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover.** ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014 (with Amol Deshpande and Devorah Kletenik). (arXiv version)** Tight Bounds on Proper Equivalence Query Learning of DNF.**
Proceedings of the 25th Conference on Learning Theory (COLT), 2012 (with Devorah Kletenik, Linda Sellie and Rocco A. Servedio). (arXiv version)**
Max-Throughput for (Conservative) k-of-n Testing.
**
Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), 2011
(with Ozgur Ozkan and Linda Sellie).
(arXiv version)

**
Flow algorithms for parallel query optimization.
**
Proceedings of the 24th International Conference on
Data Engineering (ICDE), 2008 (with Amol Deshpande).

**
Minimizing DNF formulas and AC0_d circuits given a truth table.
**
Proceedings of the 21st IEEE Computational Complexity Conference (CCC), 2006
(with Eric Allender, Paul McCabe, Toniann Pitassi, and Michael Saks).

**
Flow algorithms for two pipelined filter ordering problems.
**
Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS), 2006 (with
Anne Condon, Amol Deshpande, and Ning Wu).

**
Why Skewing Works: Learning Difficult Boolean Functions with Greedy Tree Learners.
**
Proceedings of the 22nd International Conference on Machine Learning (ICML), 2005
(with Bernard Rosell, Soumya Ray, and David Page).
(postscript file)

**
On Compression-Based Text Classification.
**
Proceedings of the 27th European Conference on Information Retrieval (ECIR), 2005
(with Yuval Marton and Ning Wu).
(pdf file)
(Errata)

**
Naive Bayes with higher order attributes.
**
Proceedings of the Seventeenth Canadian Conference on
Artificial Intelligence, 2004 (with Bernard Rosell).

**
Exact learning of DNF formulas using DNF hypotheses.
**
Proceedings of the Thirty Fourth ACM Symposium on the Theory of Computing
(STOC '02), 2002, 465--473
(with Vijay Raghavan).
(postscript file)

**
On the generation of 2-dimensional index workloads.**
Proceedings of the International Conference on Database Theory (ICDT),
Lecture Notes in Computer Science, Vol. 1540,
1999,
(with J. M. Hellerstein and G. Kollios).
(postscript file)
(c) Springer-Verlag

**
Attribute efficient learning with queries. **
Proceedings of the Ninth Annual ACM Conference on
Computational Learning Theory (COLT), 1996 (with Nader Bshouty).

**
Learning conjunctions of two unate DNF formulas: Computational and
informational results. **
Proceedings of the Ninth Annual ACM Conference on
Computational Learning Theory (COLT), 1996 (with
Aaron Feigelson).

**
How many queries are needed to learn? **
Proceedings of the 1995 ACM Symposium on
the Theory of Computing (STOC),
(with Krishnan Pillaipakkamnatt, Vijay Raghavan, and
Dawn Wilkins).

**
PAC learning with irrelevant attributes. **
Proceedings of the
35th IEEE Conference on the Foundations of Computer Science (FOCS), 1994
(with Aditi Dhagat).

**
On the power of finite automata with both
nondeterministic and probablistic states. **
Proceedings of the 1994 ACM Symposium on the Theory of Computing (STOC),
(with Anne Condon, Samuel Pottle, and Avi Wigderson).

**
Learning binary matroid ports. **
Proceedings
of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
1994 (with Collette Coullard).

**
Read-thrice DNF is hard to learn with membership and
equivalence queries. **
Proceedings of the
33rd IEEE Conference on the Foundations of Computer Science (FOCS), 1992
(with Howard Aizenstein and Leonard Pitt).

**
Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates. **
Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory (COLT), 1992 (with Nader Bshouty and Thomas Hancock).

**
Learning arithmetic read-once formulas. **
Proceedings of the 24th ACM Symposium on the Theory of Computing (STOC), 1992
(with Nader Bshouty and Thomas Hancock).

**
Learning read-once formulas over fields and extended bases. **
Proceedings of the Fourth Annual ACM Workshop on Computational
Learning Theory (COLT), 1991 (with Thomas Hancock).

**
Learning in the presence of finitely or infinitely many
irrelevant attributes. **
Proceedings of the Fourth ACM Annual Workshop on Computational
Learning Theory (COLT), 1991
(with
Avrim Blum and Nick Littlestone).

**
Learning read-once formulas using membership queries. **
Proceedings of the Second Annual Workshop on Computational Learning Theory (COLT), 1989 (with Marek Karpinski).

**
Coding techniques for handling failures in large disk arrays.
**
Proceedings of the Third International Conference on
Architectural Support for Programming Languages and Operating Systems (ASPLOS III), 1989
(with
G. Gibson, R.M. Karp, R.H. Katz, and D.A. Patterson).

**
Implementing parallel algorithms in Concurrent
Prolog: The MAXFLOW experience. **
Proceedings of the International Symposium on Logic Programming, 1984
(with Ehud Shapiro).