Lisa Hellerstein

According to our database1, Lisa Hellerstein authored at least 66 papers between 1986 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 





A General Framework for Approximating Min Sum Ordering Problems.
CoRR, 2020

Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games.
Oper. Res., 2019

Revisiting the Approximation Bound for Stochastic Submodular Cover.
J. Artif. Intell. Res., 2018

Submodular goal value of Boolean functions.
Discret. Appl. Math., 2018

Stochastic Evaluation of Symmetric Boolean Functions.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2018

Recursive Feature Elimination by Sensitivity Testing.
Proceedings of the 17th IEEE International Conference on Machine Learning and Applications, 2018

The Stochastic Score Classification Problem.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

An Algorithmic Approach to Search Games: Finding Solutions Using Best Response Oracles.
CoRR, 2017

Ann. Math. Artif. Intell., 2017

Max-Throughput for (Conservative) k-of-n Testing.
Algorithmica, 2017

Evaluation of Monotone DNF Formulas.
Algorithmica, 2017

Certificate Complexity and Exact Learning.
Encyclopedia of Algorithms, 2016

Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack.
ACM Trans. Algorithms, 2016

Scenario Submodular Cover.
Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

On the Goal Value of a Boolean Function.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2016

Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Evaluation of DNF Formulas.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2014

On the gap between ess(f) and cnf_size(f).
Discret. Appl. Math., 2013

Parallel pipelined filter ordering with precedence constraints.
ACM Trans. Algorithms, 2012

Tight Bounds on Proper Equivalence Query Learning of DNF.
Proceedings of the COLT 2012, 2012

Algorithms for distributional and adversarial pipelined filter ordering problems.
ACM Trans. Algorithms, 2009

Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions.
J. Mach. Learn. Res., 2009

Special Issue: Learning Theory 2006.
J. Comput. Syst. Sci., 2009

Certificate Complexity and Exact Learning.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.
SIAM J. Comput., 2008

Flow Algorithms for Parallel Query Optimization.
Proceedings of the 24th International Conference on Data Engineering, 2008

On PAC learning algorithms for rich Boolean function classes.
Theor. Comput. Sci., 2007

Flow algorithms for two pipelined filter ordering problems.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Exact learning of DNF formulas using DNF hypotheses.
J. Comput. Syst. Sci., 2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electronic Colloquium on Computational Complexity (ECCC), 2005

Why skewing works: learning difficult Boolean functions with greedy tree learners.
Proceedings of the Machine Learning, 2005

On Compression-Based Text Classification.
Proceedings of the Advances in Information Retrieval, 2005

Naïve Bayes with Higher Order Attributes.
Proceedings of the Advances in Artificial Intelligence, 2004

On generalized constraints and certificates.
Discret. Math., 2001

Equational characterizations of Boolean function classes.
Discret. Math., 2000

On the Generation of 2-Dimensional Index Workloads.
Proceedings of the Database Theory, 1999

On the Power of Finite Automata with Both Nondeterministic and Probabilistic States.
SIAM J. Comput., 1998

Attribute-Efficient Learning in Query and Mistake-Bound Models.
J. Comput. Syst. Sci., 1998

Conjunctions of Unate DNF Formulas: Learning and Structure.
Inf. Comput., 1998

Complexity Theoretic Hardness Results for Query Learning.
Comput. Complex., 1998

The Forbidden Projections of Unate Functions.
Discret. Appl. Math., 1997

How Many Queries Are Needed to Learn?
J. ACM, 1996

Independence and Port Oracles for Matroids, with an Application to Computational Learning Theory.
Combinatorica, 1996

Learning Conjunctions of Two Unate DNF Formulas (Extended Abstract): Computational and Informational Results.
Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

Learning Arithmetic Read-Once Formulas.
SIAM J. Comput., 1995

Learning Boolean Read-Once Formulas over Generalized Bases.
J. Comput. Syst. Sci., 1995

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
J. Comput. Syst. Sci., 1995

Guest Editor's Introduction.
Mach. Learn., 1994

An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models.
Comput. Complex., 1994

Coding Techniques for Handling Failures in Large Disk Arrays.
Algorithmica, 1994

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Learning Binary Matroid Ports.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

PAC Learning with Irrelevant Attributes
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Book Review: "Machine Learning: A Theoretical Approach".
Mach. Learn., 1993

Learning Read-Once Formulas with Queries.
J. ACM, 1993

Functions that are Read-Once on a Subset of their Inputs.
Discret. Appl. Math., 1993

Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Learning Boolean Read-Once Formulas with Arbitrary Symmetric and Constant Fan-in Gates.
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

Learning Read-Once Formulas over Fields and Extended Bases.
Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 1991

On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs.
Inf. Process. Lett., 1990

Learning Read-Once Formulas Using Membership Queries.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

Failure Correction Techniques for Large Disk Arrays.
Proceedings of the ASPLOS-III Proceedings, 1989

Notes on the Complexity of Systolic Programs.
J. Parallel Distributed Comput., 1987

Implementing Parallel Algorithms in Concurrent Prolog: The MAXFLOW Experience.
J. Log. Program., 1986