Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Kazuhiko Kawakami

dblp:63/5168 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Computational complexity › boolean function analysis
monotone boolean function
0.011997
Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle · SIAM J. Comput. 1997
Computational complexity › query complexity
oracle query
0.011997
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.011997
Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle · SIAM J. Comput. 1997
YearPublicationVenuePosition
1997 Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
abstract
We 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