Lisa Hellerstein

Publication Activity (10 Years)

Years Active: 1984-2024
Publications (10 Years): 33

Top Topics

Approximation Algorithms

Top Venues

J. Artif. Intell. Res.

Publications

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