EDBT 2026 Demo / reviewers in the wild / expert
Kazuhiko Kawakami
dblp:63/5168
· DBLP profile ↗
1ranked-venue papers
0as first author
0since 2021 · last 1997
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Computational complexity · 91% Algorithms and data structures · 9% |
Topics — the 3 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › boolean function analysis
monotone boolean function |
0.0 | 1 | 1997 | Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle · SIAM J. Comput. 1997 |
Computational complexity › query complexity
oracle query |
0.0 | 1 | 1997 | Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle · SIAM J. Comput. 1997 |
Algorithms and data structures
polynomial-time algorithms |
0.0 | 1 | 1997 | Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle · SIAM J. Comput. 1997 |
| Year | Publication | Venue | Position |
|---|---|---|---|
| 1997 | Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an OracleabstractWe consider the problem of identifying an unknown Boolean function f by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that f is a positive (or monotone) function of n variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in n and m, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of f. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function f of n variables, decide whether or not f is 2-monotonic and, if f is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries. Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Kazuhiko Kawakami |
SIAM J. Comput. | 4 |