Regret-Minimization Heuristics for Identifying Monotone Boolean Functions

Michael Laszlo; Sumitra Mukherjee

doi:10.1007/978-3-031-85902-1_12

Regret-Minimization Heuristics for Identifying Monotone Boolean Functions

Nova Southeastern University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In many applications that involve identification of an unknown monotone Boolean function (MBF), the cost of inferring the value of a vector using monotonicity is negligible compared to the cost of querying its value. Accordingly, heuristics to identify MBFs seek to minimize the number of vectors queried. The order in which queried vectors are selected determines the number of queries needed. This paper presents a method for MBF identification that iteratively selects vectors to be queried based on a regret-minimization criterion. We observe that the best extant heuristic may be considered a special case of our approach and present alternate regret functions that perform no worse than this heuristic.

Original language	English
Title of host publication	Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024
Editors	Douglas D. Hodson, Michael R. Grimaila, Torrey J. Wagner, Hamid R. Arabnia, Leonidas Deligiannidis
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	113-122
Number of pages	10
ISBN (Print)	9783031859014
DOIs	https://doi.org/10.1007/978-3-031-85902-1_12
State	Published - 2025
Event	22nd International Conference on Scientific Computing and Bioinformatics, CSC 2024, and 25th International Conference on Computational Biology, BIOCOMP 2024, held as part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024 - Las Vegas, United States Duration: Jul 22 2024 → Jul 25 2024

Publication series

Name	Communications in Computer and Information Science
Volume	2258 CCIS
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	22nd International Conference on Scientific Computing and Bioinformatics, CSC 2024, and 25th International Conference on Computational Biology, BIOCOMP 2024, held as part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024
Country/Territory	United States
City	Las Vegas
Period	7/22/24 → 7/25/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

ASJC Scopus Subject Areas

General Computer Science
General Mathematics

Keywords

automated inferencing
Boolean lattices
chain decomposition
monotone Boolean functions

Access to Document

10.1007/978-3-031-85902-1_12

Cite this

Laszlo, M., & Mukherjee, S. (2025). Regret-Minimization Heuristics for Identifying Monotone Boolean Functions. In D. D. Hodson, M. R. Grimaila, T. J. Wagner, H. R. Arabnia, & L. Deligiannidis (Eds.), Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024 (pp. 113-122). (Communications in Computer and Information Science; Vol. 2258 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-85902-1_12

Regret-Minimization Heuristics for Identifying Monotone Boolean Functions. / Laszlo, Michael ; Mukherjee, Sumitra.
Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024. ed. / Douglas D. Hodson; Michael R. Grimaila; Torrey J. Wagner; Hamid R. Arabnia; Leonidas Deligiannidis. Springer Science and Business Media Deutschland GmbH, 2025. p. 113-122 (Communications in Computer and Information Science; Vol. 2258 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Laszlo, M & Mukherjee, S 2025, Regret-Minimization Heuristics for Identifying Monotone Boolean Functions. in DD Hodson, MR Grimaila, TJ Wagner, HR Arabnia & L Deligiannidis (eds), Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024. Communications in Computer and Information Science, vol. 2258 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 113-122, 22nd International Conference on Scientific Computing and Bioinformatics, CSC 2024, and 25th International Conference on Computational Biology, BIOCOMP 2024, held as part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024, Las Vegas, United States, 7/22/24. https://doi.org/10.1007/978-3-031-85902-1_12

Laszlo M , Mukherjee S. Regret-Minimization Heuristics for Identifying Monotone Boolean Functions. In Hodson DD, Grimaila MR, Wagner TJ, Arabnia HR, Deligiannidis L, editors, Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024. Springer Science and Business Media Deutschland GmbH. 2025. p. 113-122. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-85902-1_12

Laszlo, Michael ; Mukherjee, Sumitra. / Regret-Minimization Heuristics for Identifying Monotone Boolean Functions. Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024. editor / Douglas D. Hodson ; Michael R. Grimaila ; Torrey J. Wagner ; Hamid R. Arabnia ; Leonidas Deligiannidis. Springer Science and Business Media Deutschland GmbH, 2025. pp. 113-122 (Communications in Computer and Information Science).

@inproceedings{c5899206e09d43d99953ae412932bbe9,

title = "Regret-Minimization Heuristics for Identifying Monotone Boolean Functions",

abstract = "In many applications that involve identification of an unknown monotone Boolean function (MBF), the cost of inferring the value of a vector using monotonicity is negligible compared to the cost of querying its value. Accordingly, heuristics to identify MBFs seek to minimize the number of vectors queried. The order in which queried vectors are selected determines the number of queries needed. This paper presents a method for MBF identification that iteratively selects vectors to be queried based on a regret-minimization criterion. We observe that the best extant heuristic may be considered a special case of our approach and present alternate regret functions that perform no worse than this heuristic.",

keywords = "automated inferencing, Boolean lattices, chain decomposition, monotone Boolean functions",

author = "Michael Laszlo and Sumitra Mukherjee",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 22nd International Conference on Scientific Computing and Bioinformatics, CSC 2024, and 25th International Conference on Computational Biology, BIOCOMP 2024, held as part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024 ; Conference date: 22-07-2024 Through 25-07-2024",

year = "2025",

doi = "10.1007/978-3-031-85902-1\_12",

language = "English",

isbn = "9783031859014",

series = "Communications in Computer and Information Science",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "113--122",

editor = "Hodson, \{Douglas D.\} and Grimaila, \{Michael R.\} and Wagner, \{Torrey J.\} and Arabnia, \{Hamid R.\} and Leonidas Deligiannidis",

booktitle = "Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024",

}

TY - GEN

T1 - Regret-Minimization Heuristics for Identifying Monotone Boolean Functions

AU - Laszlo, Michael

AU - Mukherjee, Sumitra

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - In many applications that involve identification of an unknown monotone Boolean function (MBF), the cost of inferring the value of a vector using monotonicity is negligible compared to the cost of querying its value. Accordingly, heuristics to identify MBFs seek to minimize the number of vectors queried. The order in which queried vectors are selected determines the number of queries needed. This paper presents a method for MBF identification that iteratively selects vectors to be queried based on a regret-minimization criterion. We observe that the best extant heuristic may be considered a special case of our approach and present alternate regret functions that perform no worse than this heuristic.

AB - In many applications that involve identification of an unknown monotone Boolean function (MBF), the cost of inferring the value of a vector using monotonicity is negligible compared to the cost of querying its value. Accordingly, heuristics to identify MBFs seek to minimize the number of vectors queried. The order in which queried vectors are selected determines the number of queries needed. This paper presents a method for MBF identification that iteratively selects vectors to be queried based on a regret-minimization criterion. We observe that the best extant heuristic may be considered a special case of our approach and present alternate regret functions that perform no worse than this heuristic.

KW - automated inferencing

KW - Boolean lattices

KW - chain decomposition

KW - monotone Boolean functions

UR - https://www.scopus.com/pages/publications/105003906362

UR - https://www.scopus.com/pages/publications/105003906362#tab=citedBy

U2 - 10.1007/978-3-031-85902-1_12

DO - 10.1007/978-3-031-85902-1_12

M3 - Conference contribution

AN - SCOPUS:105003906362

SN - 9783031859014

T3 - Communications in Computer and Information Science

SP - 113

EP - 122

BT - Scientific Computing and Bioinformatics and Computational Biology - 22nd International Conference, CSC 2024, and 25th International Conference, BIOCOMP 2024, Held as Part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024

A2 - Hodson, Douglas D.

A2 - Grimaila, Michael R.

A2 - Wagner, Torrey J.

A2 - Arabnia, Hamid R.

A2 - Deligiannidis, Leonidas

PB - Springer Science and Business Media Deutschland GmbH

T2 - 22nd International Conference on Scientific Computing and Bioinformatics, CSC 2024, and 25th International Conference on Computational Biology, BIOCOMP 2024, held as part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024

Y2 - 22 July 2024 through 25 July 2024

ER -

Regret-Minimization Heuristics for Identifying Monotone Boolean Functions

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this