default search action
Lisa Hellerstein
Person information
- affiliation: New York University Tandon School of Engineering, New York City, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c38]Lisa Hellerstein, Naifeng Liu, Kevin Schewior:
Quickly Determining Who Won an Election. ITCS 2024: 61:1-61:14 - [i19]Lisa Hellerstein, Naifeng Liu, Kevin Schewior:
Quickly Determining Who Won an Election. CoRR abs/2401.10476 (2024) - [i18]R. Teal Witter, Lisa Hellerstein:
Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits. CoRR abs/2409.03071 (2024) - 2023
- [j41]Lisa Hellerstein
, Thomas Lidbetter
A game theoretic approach to a problem in polymatroid maximization. Eur. J. Oper. Res. 305(2): 979-988 (2023) - 2022
- [j40]Nathaniel Grammel, Lisa Hellerstein
Algorithms for the Unit-Cost Stochastic Score Classification Problem. Algorithmica 84(10): 3054-3074 (2022) - [j39]Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein
The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions. Discret. Appl. Math. 309: 269-277 (2022) - [j38]Felix Happach
A General Framework for Approximating Min Sum Ordering Problems. INFORMS J. Comput. 34(3): 1437-1452 (2022) - [c37]Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter:
A Local Search Algorithm for the Min-Sum Submodular Cover Problem. ISAAC 2022: 3:1-3:13 - [c36]Felix Happach, Lisa Hellerstein, Thomas Lidbetter:
A general framework for approximating min sum ordering problems. ISAIM 2022 - [c35]Lisa Hellerstein, Devorah Kletenik, Naifeng Liu, R. Teal Witter:
Adaptivity gap of the SBFE problem. ISAIM 2022 - [c34]Lisa Hellerstein, Devorah Kletenik
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem. WAOA 2022: 190-210 - [i17]Lisa Hellerstein, Devorah Kletenik
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem. CoRR abs/2208.03810 (2022) - [i16]Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter:
A Local Search Algorithm for the Min-Sum Submodular Cover Problem. CoRR abs/2209.03054 (2022) - 2021
- [j37]Lisa Hellerstein, Devorah Kletenik
A Tight Bound for Stochastic Submodular Cover. J. Artif. Intell. Res. 71: 347-370 (2021) - [i15]Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy:
A Tight Bound for Stochastic Submodular Cover. CoRR abs/2102.01149 (2021) - [i14]Lisa Hellerstein, Thomas Lidbetter:
A Polyhedral Approach to Some Max-min Problems. CoRR abs/2104.10236 (2021) - [i13]Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik:
The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions. CoRR abs/2111.08793 (2021) - 2020
- [i12]Felix Happach, Lisa Hellerstein, Thomas Lidbetter:
A General Framework for Approximating Min Sum Ordering Problems. CoRR abs/2004.05954 (2020)
2010 – 2019
- 2019
- [j36]Lisa Hellerstein
Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games. Oper. Res. 67(3): 731-743 (2019) - 2018
- [j35]Eric Bach, Jérémie Dusart, Lisa Hellerstein
Submodular goal value of Boolean functions. Discret. Appl. Math. 238: 1-13 (2018) - [j34]Lisa Hellerstein, Devorah Kletenik
Revisiting the Approximation Bound for Stochastic Submodular Cover. J. Artif. Intell. Res. 63: 265-279 (2018) - [c33]Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik
The Stochastic Score Classification Problem. ESA 2018: 36:1-36:14 - [c32]Nicholas Sean Escanilla, Lisa Hellerstein, Ross Kleiman, Zhaobin Kuang, James Shull, David Page:
Recursive Feature Elimination by Sensitivity Testing. ICMLA 2018: 40-47 - [c31]Lisa Hellerstein:
Stochastic Evaluation of Symmetric Boolean Functions. ISAIM 2018 - [i11]Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik:
The Stochastic Score Classification Problem. CoRR abs/1806.10660 (2018) - 2017
- [j33]Lisa Hellerstein, Özgür Özkan, Linda Sellie:
Max-Throughput for (Conservative) k-of-n Testing. Algorithmica 77(2): 595-618 (2017) - [j32]Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik
Evaluation of Monotone DNF Formulas. Algorithmica 77(3): 661-685 (2017) - [j31]Lisa Hellerstein, Lev Reyzin, György Turán:
Foreword. Ann. Math. Artif. Intell. 79(1-3): 1-3 (2017) - [i10]Eric Bach, Jérémie Dusart, Lisa Hellerstein, Devorah Kletenik:
Submodular Goal Value of Boolean Functions. CoRR abs/1702.04067 (2017) - [i9]Lisa Hellerstein, Thomas Lidbetter:
An Algorithmic Approach to Search Games: Finding Solutions Using Best Response Oracles. CoRR abs/1704.02657 (2017) - 2016
- [j30]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): 42:1-42:28 (2016) - [c30]Eric Bach, Lisa Hellerstein, Devorah Kletenik:
On the Goal Value of a Boolean Function. ISAIM 2016 - [c29]Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik
Scenario Submodular Cover. WAOA 2016: 116-128 - [r2]Lisa Hellerstein:
Certificate Complexity and Exact Learning. Encyclopedia of Algorithms 2016: 286-290 - [i8]Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, Patrick Lin:
Scenario Submodular Cover. CoRR abs/1603.03158 (2016) - 2015
- [c28]Lisa Hellerstein, Devorah Kletenik
Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline. CIAC 2015: 235-248 - [i7]Lisa Hellerstein, Devorah Kletenik, Patrick Lin:
Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline. CoRR abs/1504.02146 (2015) - 2014
- [c27]Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt:
Evaluation of DNF Formulas. ISAIM 2014 - [c26]Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover. SODA 2014: 1453-1466 - 2013
- [j29]Lisa Hellerstein, Devorah Kletenik
On the gap between ess(f) and cnf_size(f). Discret. Appl. Math. 161(1-2): 19-27 (2013) - [i6]Amol Deshpande, Lisa Hellerstein, Devorah Kletenik:
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover. CoRR abs/1303.0726 (2013) - [i5]Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt:
Evaluation of DNF Formulas. CoRR abs/1310.3673 (2013) - 2012
- [j28]Amol Deshpande, Lisa Hellerstein:
Parallel pipelined filter ordering with precedence constraints. ACM Trans. Algorithms 8(4): 41:1-41:38 (2012) - [c25]Lisa Hellerstein, Devorah Kletenik:
On the gap between ess(f) and cnf_size(f). ISAIM 2012 - [c24]Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio:
Tight Bounds on Proper Equivalence Query Learning of DNF. COLT 2012: 31.1-31.18 - 2011
- [c23]Lisa Hellerstein, Özgür Özkan, Linda Sellie:
Max-Throughput for (Conservative) k-of-n Testing. ISAAC 2011: 703-713 - [i4]Lisa Hellerstein, Devorah Kletenik:
On the gap between ess(f) and cnf_size(f). CoRR abs/1106.4247 (2011) - [i3]Lisa Hellerstein, Özgür Özkan, Linda Sellie:
Max-Throughput for (Conservative) k-of-n Testing. CoRR abs/1109.3401 (2011) - [i2]Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio:
Tight Bounds on Proper Equivalence Query Learning of DNF. CoRR abs/1111.1124 (2011)
2000 – 2009
- 2009
- [j27]Lisa Hellerstein, Hans Ulrich Simon
Special Issue: Learning Theory 2006. J. Comput. Syst. Sci. 75(1): 1 (2009) - [j26]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: 2374-2411 (2009) - [j25]Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu:
Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Trans. Algorithms 5(2): 24:1-24:34 (2009) - 2008
- [j24]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput. 38(1): 63-84 (2008) - [c22]Amol Deshpande, Lisa Hellerstein:
Flow Algorithms for Parallel Query Optimization. ICDE 2008: 754-763 - [r1]Lisa Hellerstein:
Certificate Complexity and Exact Learning. Encyclopedia of Algorithms 2008 - 2007
- [j23]Lisa Hellerstein, Rocco A. Servedio:
On PAC learning algorithms for rich Boolean function classes. Theor. Comput. Sci. 384(1): 66-76 (2007) - 2006
- [c21]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. CCC 2006: 237-251 - [c20]Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu:
Flow algorithms for two pipelined filter ordering problems. PODS 2006: 193-202 - 2005
- [j22]Lisa Hellerstein, Vijay Raghavan:
Exact learning of DNF formulas using DNF hypotheses. J. Comput. Syst. Sci. 70(4): 435-470 (2005) - [c19]Yuval Marton, Ning Wu, Lisa Hellerstein:
On Compression-Based Text Classification. ECIR 2005: 300-314 - [c18]Bernard Rosell, Lisa Hellerstein, Soumya Ray, David Page:
Why skewing works: learning difficult Boolean functions with greedy tree learners. ICML 2005: 728-735 - [i1]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. TR05 (2005) - 2004
- [c17]Bernard Rosell, Lisa Hellerstein:
Naïve Bayes with Higher Order Attributes. Canadian AI 2004: 105-119 - 2002
- [c16]Lisa Hellerstein, Vijay Raghavan:
Exact learning of DNF formulas using DNF hypotheses. STOC 2002: 465-473 - 2001
- [j21]Lisa Hellerstein:
On generalized constraints and certificates. Discret. Math. 226(1-3): 211-232 (2001) - 2000
- [j20]Oya Ekin, Stephan Foldes, Peter L. Hammer, Lisa Hellerstein:
Equational characterizations of Boolean function classes. Discret. Math. 211: 27-51 (2000)
1990 – 1999
- 1999
- [c15]Joseph M. Hellerstein, Lisa Hellerstein, George Kollios:
On the Generation of 2-Dimensional Index Workloads. ICDT 1999: 113-130 - 1998
- [j19]Howard Aizenstein
Complexity Theoretic Hardness Results for Query Learning. Comput. Complex. 7(1): 19-53 (1998) - [j18]Aaron Feigelson, Lisa Hellerstein:
Conjunctions of Unate DNF Formulas: Learning and Structure. Inf. Comput. 140(2): 203-228 (1998) - [j17]Nader H. Bshouty, Lisa Hellerstein:
Attribute-Efficient Learning in Query and Mistake-Bound Models. J. Comput. Syst. Sci. 56(3): 310-319 (1998) - [j16]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): 739-762 (1998) - 1997
- [j15]Aaron Feigelson, Lisa Hellerstein:
The Forbidden Projections of Unate Functions. Discret. Appl. Math. 77(3): 221-236 (1997) - 1996
- [j14]Collette R. Coullard, Lisa Hellerstein:
Independence and Port Oracles for Matroids, with an Application to Computational Learning Theory. Comb. 16(2): 189-208 (1996) - [j13]Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins:
How Many Queries Are Needed to Learn? J. ACM 43(5): 840-862 (1996) - [c14]Nader H. Bshouty, Lisa Hellerstein:
Attribute-Efficient Learning in Query and Mistake-Bound Models. COLT 1996: 235-243 - [c13]Aaron Feigelson, Lisa Hellerstein:
Learning Conjunctions of Two Unate DNF Formulas (Extended Abstract): Computational and Informational Results. COLT 1996: 255-265 - 1995
- [j12]Avrim Blum, Lisa Hellerstein, Nick Littlestone:
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. J. Comput. Syst. Sci. 50(1): 32-40 (1995) - [j11]Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
Learning Boolean Read-Once Formulas over Generalized Bases. J. Comput. Syst. Sci. 50(3): 521-542 (1995) - [j10]Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
Learning Arithmetic Read-Once Formulas. SIAM J. Comput. 24(4): 706-735 (1995) - [c12]Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins:
How many queries are needed to learn? STOC 1995: 190-199 - 1994
- [j9]Lisa Hellerstein, Garth A. Gibson
Coding Techniques for Handling Failures in Large Disk Arrays. Algorithmica 12(2/3): 182-208 (1994) - [j8]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: 37-61 (1994) - [j7]Lisa Hellerstein:
Guest Editor's Introduction. Mach. Learn. 17(2-3): 111-114 (1994) - [c11]Aditi Dhagat, Lisa Hellerstein:
PAC Learning with Irrelevant Attributes. FOCS 1994: 64-74 - [c10]Lisa Hellerstein, Collette R. Coullard:
Learning Binary Matroid Ports. SODA 1994: 328-335 - [c9]Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson:
On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). STOC 1994: 676-685 - 1993
- [j6]Lisa Hellerstein:
Functions that are Read-Once on a Subset of their Inputs. Discret. Appl. Math. 46(3): 235-251 (1993) - [j5]Dana Angluin, Lisa Hellerstein, Marek Karpinski:
Learning Read-Once Formulas with Queries. J. ACM 40(1): 185-210 (1993) - [j4]Lisa Hellerstein:
Book Review: "Machine Learning: A Theoretical Approach". Mach. Learn. 13: 145-149 (1993) - 1992
- [c8]Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
Learning Boolean Read-Once Formulas with Arbitrary Symmetric and Constant Fan-in Gates. COLT 1992: 1-15 - [c7]Howard Aizenstein, Lisa Hellerstein, Leonard Pitt:
Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries. FOCS 1992: 523-532 - [c6]Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
Learning Arithmetic Read-Once Formulas. STOC 1992: 370-381 - 1991
- [c5]Avrim Blum, Lisa Hellerstein, Nick Littlestone:
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. COLT 1991: 157-166 - [c4]Thomas R. Hancock, Lisa Hellerstein:
Learning Read-Once Formulas over Fields and Extended Bases. COLT 1991: 326-336 - 1990
- [j3]Lisa Hellerstein, Philip N. Klein, Robert Wilber:
On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs. Inf. Process. Lett. 35(5): 261-267 (1990)
1980 – 1989
- 1989
- [c3]Garth A. Gibson, Lisa Hellerstein, Richard M. Karp, Randy H. Katz, David A. Patterson:
Failure Correction Techniques for Large Disk Arrays. ASPLOS 1989: 123-132 - [c2]Lisa Hellerstein, Marek Karpinski:
Learning Read-Once Formulas Using Membership Queries. COLT 1989: 146-161 - 1987
- [j2]Stephen Taylor, Lisa Hellerstein, Shmuel Safra
Notes on the Complexity of Systolic Programs. J. Parallel Distributed Comput. 4(3): 250-265 (1987) - 1986
- [j1]Lisa Hellerstein, Ehud Shapiro:
Implementing Parallel Algorithms in Concurrent Prolog: The MAXFLOW Experience. J. Log. Program. 3(2): 157-184 (1986) - 1984
- [c1]Lisa Hellerstein, Ehud Shapiro:
Implementing Parallel Algorithms in Concurrent Prolog: The MAXFLOW Experience. SLP 1984: 99-115
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-10 21:18 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: