Lisa Hellerstein

Naifeng Liu

Kevin Schewior

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

A game theoretic approach to a problem in polymatroid maximization.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2023

2022

A General Framework for Approximating Min Sum Ordering Problems.

[BibT_eX]

[DOI]

Felix Happach

INFORMS J. Comput., 2022

The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Algorithms for the Unit-Cost Stochastic Score Classification Problem.

[BibT_eX]

[DOI]

Algorithmica, 2022

Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

Adaptivity gap of the SBFE problem.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics 2022 (ISAIM 2022), 2022

A Local Search Algorithm for the Min-Sum Submodular Cover Problem.

[BibT_eX]

[DOI]

R. Teal Witter

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

A Tight Bound for Stochastic Submodular Cover.

[BibT_eX]

[DOI]

Srinivasan Parthasarathy

J. Artif. Intell. Res., 2021

A Polyhedral Approach to Some Max-min Problems.

[BibT_eX]

[DOI]

CoRR, 2021

2019

Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games.

[BibT_eX]

[DOI]

Daniel Pirutinsky

Oper. Res., 2019

2018

Revisiting the Approximation Bound for Stochastic Submodular Cover.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2018

Submodular goal value of Boolean functions.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Stochastic Evaluation of Symmetric Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2018

Recursive Feature Elimination by Sensitivity Testing.

[BibT_eX]

[DOI]

Nicholas Sean Escanilla

Proceedings of the 17th IEEE International Conference on Machine Learning and Applications, 2018

The Stochastic Score Classification Problem.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

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

[BibT_eX]

[DOI]

CoRR, 2017

Foreword.

[BibT_eX]

[DOI]

Lev Reyzin

György Turán

Ann. Math. Artif. Intell., 2017

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

[BibT_eX]

[DOI]

Özgür Özkan

Linda Sellie

Algorithmica, 2017

Evaluation of Monotone DNF Formulas.

[BibT_eX]

[DOI]

Algorithmica, 2017

2016

Certificate Complexity and Exact Learning.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Scenario Submodular Cover.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

On the Goal Value of a Boolean Function.

[BibT_eX]

[DOI]

Eric Bach

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2016

2015

Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline.

[BibT_eX]

[DOI]

Patrick Lin

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Evaluation of DNF Formulas.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2014

2013

On the gap between ess(f) and cnf_size(f).

[BibT_eX]

[DOI]

Discret. Appl. Math., 2013

2012

Parallel pipelined filter ordering with precedence constraints.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Tight Bounds on Proper Equivalence Query Learning of DNF.

[BibT_eX]

[DOI]

Proceedings of the COLT 2012, 2012

2009

Algorithms for distributional and adversarial pipelined filter ordering problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2009

Special Issue: Learning Theory 2006.

[BibT_eX]

[DOI]

Hans Ulrich Simon

J. Comput. Syst. Sci., 2009

2008

Certificate Complexity and Exact Learning.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Flow Algorithms for Parallel Query Optimization.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Data Engineering, 2008

2007

On PAC learning algorithms for rich Boolean function classes.

[BibT_eX]

[DOI]

Rocco A. Servedio

Theor. Comput. Sci., 2007

2006

Flow algorithms for two pipelined filter ordering problems.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Exact learning of DNF formulas using DNF hypotheses.

[BibT_eX]

[DOI]

Vijay Raghavan

J. Comput. Syst. Sci., 2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Why skewing works: learning difficult Boolean functions with greedy tree learners.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning, 2005

On Compression-Based Text Classification.

[BibT_eX]

[DOI]

Yuval Marton

Ning Wu

Proceedings of the Advances in Information Retrieval, 2005

2004

Naïve Bayes with Higher Order Attributes.

[BibT_eX]

[DOI]

Bernard Rosell

Proceedings of the Advances in Artificial Intelligence, 2004

2001

On generalized constraints and certificates.

[BibT_eX]

[DOI]

Discret. Math., 2001

2000

Equational characterizations of Boolean function classes.

[BibT_eX]

[DOI]

Discret. Math., 2000

1999

On the Generation of 2-Dimensional Index Workloads.

[BibT_eX]

[DOI]

Joseph M. Hellerstein

George Kollios

Proceedings of the Database Theory, 1999

1998

On the Power of Finite Automata with Both Nondeterministic and Probabilistic States.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Attribute-Efficient Learning in Query and Mistake-Bound Models.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Conjunctions of Unate DNF Formulas: Learning and Structure.

[BibT_eX]

[DOI]

Aaron Feigelson

Inf. Comput., 1998

Complexity Theoretic Hardness Results for Query Learning.

[BibT_eX]

[DOI]

Comput. Complex., 1998

1997

The Forbidden Projections of Unate Functions.

[BibT_eX]

[DOI]

Aaron Feigelson

Discret. Appl. Math., 1997

1996

How Many Queries Are Needed to Learn?

[BibT_eX]

[DOI]

Krishnan Pillaipakkamnatt

Vijay Raghavan

Dawn Wilkins

J. ACM, 1996

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

[BibT_eX]

[DOI]

Collette R. Coullard

Comb., 1996

Learning Conjunctions of Two Unate DNF Formulas (Extended Abstract): Computational and Informational Results.

[BibT_eX]

[DOI]

Aaron Feigelson

Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

1995

Learning Arithmetic Read-Once Formulas.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

Learning Boolean Read-Once Formulas over Generalized Bases.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.

[BibT_eX]

[DOI]

Avrim Blum

Nick Littlestone

J. Comput. Syst. Sci., 1995

1994

Guest Editor's Introduction.

[BibT_eX]

[DOI]

Mach. Learn., 1994

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

[BibT_eX]

[DOI]

Comput. Complex., 1994

Coding Techniques for Handling Failures in Large Disk Arrays.

[BibT_eX]

[DOI]

Algorithmica, 1994

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Learning Binary Matroid Ports.

[BibT_eX]

[DOI]

Collette R. Coullard

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

PAC Learning with Irrelevant Attributes

[BibT_eX]

[DOI]

Aditi Dhagat

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Book Review: "Machine Learning: A Theoretical Approach".

[BibT_eX]

[DOI]

Mach. Learn., 1993

Learning Read-Once Formulas with Queries.

[BibT_eX]

[DOI]

Dana Angluin

Marek Karpinski

J. ACM, 1993

Functions that are Read-Once on a Subset of their Inputs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1993

1992

Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries

[BibT_eX]

[DOI]

Howard Aizenstein

Leonard Pitt

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.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991

Learning Read-Once Formulas over Fields and Extended Bases.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 1991

1990

On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs.

[BibT_eX]

[DOI]

Philip N. Klein

Robert Wilber

Inf. Process. Lett., 1990

1989

Learning Read-Once Formulas Using Membership Queries.

[BibT_eX]

[DOI]

Marek Karpinski

Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

Failure Correction Techniques for Large Disk Arrays.

[BibT_eX]

[DOI]

Proceedings of the ASPLOS-III Proceedings, 1989

1987

Notes on the Complexity of Systolic Programs.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1987

1986

Implementing Parallel Algorithms in Concurrent Prolog: The MAXFLOW Experience.

[BibT_eX]

[DOI]