Lisa Hellerstein

107 papers A* 20A 6B 4C 2Misc 6Journal 64Unranked 3
YearRankTypeTitle / Venue / Authors
2026 — conf
An Exact Algorithm for the Unanimous Vote Problem.
SOSA
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha, Christopher Musco, Xinchen Yang
2026 A* conf
Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation.
SODA
Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior
2026 J jnl
Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation.
CoRR
Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior
2026 A conf
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid.
STACS
Haya Diwan, Lisa Hellerstein, Nicole Megow, Jens Schlöter
2025 J jnl
An Exact Algorithm for the Unanimous Vote Problem.
CoRR
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha, Christopher Musco, Xinchen Yang
2025 J jnl
Approximation Algorithms for Stochastic Optimization (Dagstuhl Seminar 25132).
Dagstuhl Reports
Lisa Hellerstein, Viswanath Nagarajan, Kevin Schewior
2025 J jnl
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid.
CoRR
Haya Diwan, Lisa Hellerstein, Nicole Megow, Jens Schlöter
2024 J jnl
Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits.
CoRR
R. Teal Witter, Lisa Hellerstein
2024 A conf
Quickly Determining Who Won an Election.
ITCS
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
2024 J jnl
Quickly Determining Who Won an Election.
CoRR
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
2023 J jnl
A game theoretic approach to a problem in polymatroid maximization.
Eur. J. Oper. Res.
Lisa Hellerstein, Thomas Lidbetter
2022 J jnl
A General Framework for Approximating Min Sum Ordering Problems.
INFORMS J. Comput.
Felix Happach, Lisa Hellerstein, Thomas Lidbetter
2022 B conf
A Local Search Algorithm for the Min-Sum Submodular Cover Problem.
ISAAC
Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter
2022 J jnl
A Local Search Algorithm for the Min-Sum Submodular Cover Problem.
CoRR
Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter
2022 Misc conf
A general framework for approximating min sum ordering problems.
ISAIM
Felix Happach, Lisa Hellerstein, Thomas Lidbetter
2022 B conf
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem.
WAOA
Lisa Hellerstein, Devorah Kletenik, Naifeng Liu, R. Teal Witter
2022 J jnl
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem.
CoRR
Lisa Hellerstein, Devorah Kletenik, Naifeng Liu, R. Teal Witter
2022 Misc conf
Adaptivity gap of the SBFE problem.
ISAIM
Lisa Hellerstein, Devorah Kletenik, Naifeng Liu, R. Teal Witter
2022 J jnl
Algorithms for the Unit-Cost Stochastic Score Classification Problem.
Algorithmica
Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, Naifeng Liu
2022 J jnl
The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions.
Discret. Appl. Math.
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik
2021 J jnl
A Polyhedral Approach to Some Max-min Problems.
CoRR
Lisa Hellerstein, Thomas Lidbetter
2021 J jnl
A Tight Bound for Stochastic Submodular Cover.
CoRR
Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy
2021 J jnl
A Tight Bound for Stochastic Submodular Cover.
J. Artif. Intell. Res.
Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy
2021 J jnl
The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions.
CoRR
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik
2020 J jnl
A General Framework for Approximating Min Sum Ordering Problems.
CoRR
Felix Happach, Lisa Hellerstein, Thomas Lidbetter
2019 J jnl
Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games.
Oper. Res.
Lisa Hellerstein, Thomas Lidbetter, Daniel Pirutinsky
2018 C conf
Recursive Feature Elimination by Sensitivity Testing.
ICMLA
Nicholas Sean Escanilla, Lisa Hellerstein, Ross Kleiman, Zhaobin Kuang, James Shull, David Page
2018 J jnl
Revisiting the Approximation Bound for Stochastic Submodular Cover.
J. Artif. Intell. Res.
Lisa Hellerstein, Devorah Kletenik
2018 Misc conf
Stochastic Evaluation of Symmetric Boolean Functions.
ISAIM
Lisa Hellerstein
2018 J jnl
Submodular goal value of Boolean functions.
Discret. Appl. Math.
Eric Bach, Jérémie Dusart, Lisa Hellerstein, Devorah Kletenik
2018 A conf
The Stochastic Score Classification Problem.
ESA
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik
2018 J jnl
The Stochastic Score Classification Problem.
CoRR
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik
2017 J jnl
An Algorithmic Approach to Search Games: Finding Solutions Using Best Response Oracles.
CoRR
Lisa Hellerstein, Thomas Lidbetter
2017 J jnl
Evaluation of Monotone DNF Formulas.
Algorithmica
Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt
2017 J jnl
Foreword.
Ann. Math. Artif. Intell.
Lisa Hellerstein, Lev Reyzin, György Turán
2017 J jnl
Max-Throughput for (Conservative) k-of-n Testing.
Algorithmica
Lisa Hellerstein, Özgür Özkan, Linda Sellie
2017 J jnl
Submodular Goal Value of Boolean Functions.
CoRR
Eric Bach, Jérémie Dusart, Lisa Hellerstein, Devorah Kletenik
2016 J jnl
Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack.
ACM Trans. Algorithms
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
2016 — ch.
Certificate Complexity and Exact Learning.
Encyclopedia of Algorithms
Lisa Hellerstein
2016 Misc conf
On the Goal Value of a Boolean Function.
ISAIM
Eric Bach, Lisa Hellerstein, Devorah Kletenik
2016 B conf
Scenario Submodular Cover.
WAOA
Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, Patrick Lin
2016 J jnl
Scenario Submodular Cover.
CoRR
Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, Patrick Lin
2015 J jnl
Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline.
CoRR
Lisa Hellerstein, Devorah Kletenik, Patrick Lin
2015 C conf
Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline.
CIAC
Lisa Hellerstein, Devorah Kletenik, Patrick Lin
2014 A* conf
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover.
SODA
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
2014 Misc conf
Evaluation of DNF Formulas.
ISAIM
Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt
2013 J jnl
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover
CoRR
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
2013 J jnl
Evaluation of DNF Formulas.
CoRR
Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt
2013 J jnl
On the gap between ess(f) and cnf_size(f).
Discret. Appl. Math.
Lisa Hellerstein, Devorah Kletenik
2012 Misc conf
On the gap between ess(f) and cnf_size(f).
ISAIM
Lisa Hellerstein, Devorah Kletenik
2012 J jnl
Parallel pipelined filter ordering with precedence constraints.
ACM Trans. Algorithms
Amol Deshpande, Lisa Hellerstein
2012 A* conf
Tight Bounds on Proper Equivalence Query Learning of DNF.
COLT
Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio
2011 J jnl
Max-Throughput for (Conservative) k-of-n Testing
CoRR
Lisa Hellerstein, Özgür Özkan, Linda Sellie
2011 B conf
Max-Throughput for (Conservative) k-of-n Testing.
ISAAC
Lisa Hellerstein, Özgür Özkan, Linda Sellie
2011 J jnl
On the gap between ess(f) and cnf_size(f)
CoRR
Lisa Hellerstein, Devorah Kletenik
2011 J jnl
Tight Bounds on Proper Equivalence Query Learning of DNF
CoRR
Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio
2009 J jnl
Algorithms for distributional and adversarial pipelined filter ordering problems.
ACM Trans. Algorithms
Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu
2009 J jnl
Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions.
J. Mach. Learn. Res.
Lisa Hellerstein, Bernard Rosell, Eric Bach, Soumya Ray, David Page
2009 J jnl
Special Issue: Learning Theory 2006.
J. Comput. Syst. Sci.
Lisa Hellerstein, Hans Ulrich Simon
2008 — ch.
Certificate Complexity and Exact Learning.
Encyclopedia of Algorithms
Lisa Hellerstein
2008 A* conf
Flow Algorithms for Parallel Query Optimization.
ICDE
Amol Deshpande, Lisa Hellerstein
2008 J jnl
Minimizing Disjunctive Normal Form Formulas and AC
SIAM J. Comput.
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2007 J jnl
On PAC learning algorithms for rich Boolean function classes.
Theor. Comput. Sci.
Lisa Hellerstein, Rocco A. Servedio
2006 A* conf
Flow algorithms for two pipelined filter ordering problems.
PODS
Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu
2006 A conf
Minimizing DNF Formulas and AC
CCC
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2005 J jnl
Exact learning of DNF formulas using DNF hypotheses.
J. Comput. Syst. Sci.
Lisa Hellerstein, Vijay Raghavan
2005 J jnl
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electron. Colloquium Comput. Complex.
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2005 A conf
On Compression-Based Text Classification.
ECIR
Yuval Marton, Ning Wu, Lisa Hellerstein
2005 A* conf
Why skewing works: learning difficult Boolean functions with greedy tree learners.
ICML
Bernard Rosell, Lisa Hellerstein, Soumya Ray, David Page
2004 — conf
Naïve Bayes with Higher Order Attributes.
Canadian AI
Bernard Rosell, Lisa Hellerstein
2002 A* conf
Exact learning of DNF formulas using DNF hypotheses.
STOC
Lisa Hellerstein, Vijay Raghavan
2001 J jnl
On generalized constraints and certificates.
Discret. Math.
Lisa Hellerstein
2000 J jnl
Equational characterizations of Boolean function classes.
Discret. Math.
Oya Ekin, Stephan Foldes, Peter L. Hammer, Lisa Hellerstein
1999 A conf
On the Generation of 2-Dimensional Index Workloads.
ICDT
Joseph M. Hellerstein, Lisa Hellerstein, George Kollios
1998 J jnl
Attribute-Efficient Learning in Query and Mistake-Bound Models.
J. Comput. Syst. Sci.
Nader H. Bshouty, Lisa Hellerstein
1998 J jnl
Complexity Theoretic Hardness Results for Query Learning.
Comput. Complex.
Howard Aizenstein, Tibor Hegedüs, Lisa Hellerstein, Leonard Pitt
1998 J jnl
Conjunctions of Unate DNF Formulas: Learning and Structure.
Inf. Comput.
Aaron Feigelson, Lisa Hellerstein
1998 J jnl
On the Power of Finite Automata with Both Nondeterministic and Probabilistic States.
SIAM J. Comput.
Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson
1997 J jnl
The Forbidden Projections of Unate Functions.
Discret. Appl. Math.
Aaron Feigelson, Lisa Hellerstein
1996 A* conf
Attribute-Efficient Learning in Query and Mistake-Bound Models.
COLT
Nader H. Bshouty, Lisa Hellerstein
1996 J jnl
How Many Queries Are Needed to Learn?
J. ACM
Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins
1996 J jnl
Independence and Port Oracles for Matroids, with an Application to Computational Learning Theory.
Comb.
Collette R. Coullard, Lisa Hellerstein
1996 A* conf
Learning Conjunctions of Two Unate DNF Formulas (Extended Abstract): Computational and Informational Results.
COLT
Aaron Feigelson, Lisa Hellerstein
1995 A* conf
How many queries are needed to learn?
STOC
Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins
1995 J jnl
Learning Arithmetic Read-Once Formulas.
SIAM J. Comput.
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein
1995 J jnl
Learning Boolean Read-Once Formulas over Generalized Bases.
J. Comput. Syst. Sci.
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein
1995 J jnl
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
J. Comput. Syst. Sci.
Avrim Blum, Lisa Hellerstein, Nick Littlestone
1994 J jnl
An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models.
Comput. Complex.
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski
1994 J jnl
Coding Techniques for Handling Failures in Large Disk Arrays.
Algorithmica
Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, David A. Patterson
1994 J jnl
Guest Editor's Introduction.
Mach. Learn.
Lisa Hellerstein
1994 A* conf
Learning Binary Matroid Ports.
SODA
Lisa Hellerstein, Collette R. Coullard
1994 A* conf
On the power of finite automata with both nondeterministic and probabilistic states (preliminary version).
STOC
Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson
1994 A* conf
PAC Learning with Irrelevant Attributes
FOCS
Aditi Dhagat, Lisa Hellerstein
1993 J jnl
Book Review: "Machine Learning: A Theoretical Approach".
Mach. Learn.
Lisa Hellerstein
1993 J jnl
Functions that are Read-Once on a Subset of their Inputs.
Discret. Appl. Math.
Lisa Hellerstein
1993 J jnl
Learning Read-Once Formulas with Queries.
J. ACM
Dana Angluin, Lisa Hellerstein, Marek Karpinski
1992 A* conf
Learning Arithmetic Read-Once Formulas
STOC
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein
1992 A* conf
Learning Boolean Read-Once Formulas with Arbitrary Symmetric and Constant Fan-in Gates.
COLT
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein
1992 A* conf
Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries
FOCS
Howard Aizenstein, Lisa Hellerstein, Leonard Pitt
1991 A* conf
Learning Read-Once Formulas over Fields and Extended Bases.
COLT
Thomas R. Hancock, Lisa Hellerstein
1991 A* conf
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
COLT
Avrim Blum, Lisa Hellerstein, Nick Littlestone
1990 J jnl
On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs.
Inf. Process. Lett.
Lisa Hellerstein, Philip N. Klein, Robert Wilber
1989 A* conf
Failure Correction Techniques for Large Disk Arrays.
ASPLOS
Garth A. Gibson, Lisa Hellerstein, Richard M. Karp, Randy H. Katz, David A. Patterson
1989 A* conf
Learning Read-Once Formulas Using Membership Queries.
COLT
Lisa Hellerstein, Marek Karpinski
1987 J jnl
Notes on the Complexity of Systolic Programs.
J. Parallel Distributed Comput.
Stephen Taylor, Lisa Hellerstein, Shmuel Safra, Ehud Shapiro
1986 J jnl
Implementing Parallel Algorithms in Concurrent Prolog: The MAXFLOW Experience.
J. Log. Program.
Lisa Hellerstein, Ehud Shapiro
1984 — conf
Implementing Parallel Algorithms in Concurrent Prolog: The MAXFLOW Experience.
SLP
Lisa Hellerstein, Ehud Shapiro