Conference Papers by Lisa Hellerstein

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