5 papers
The Complexity of Kings
Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe
A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely orient…
Boolean Operations, Joins, and the Extended Low Hierarchy
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe +1
We prove that the join of two sets may actually fall into a lower level of the extended low hierarchy than either of the sets. In particular, there exist sets that are not in the s…
Polynomial-Time Multi-Selectivity
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe +1
We introduce a generalization of Selman's P-selectivity that yields a more flexible notion of selectivity, called (polynomial-time) multi-selectivity, in which the selector is allo…
Practical algorithms for on-line sampling
Carlos Domingo, Ricard Gavalda, Osamu Watanabe
One of the core applications of machine learning to knowledge discovery consists on building a function (a hypothesis) from a given amount of data (for instance a decision tree or…
Hard instance generation for SAT
Satoshi Horie, Osamu Watanabe
We propose an algorithm of generating hard instances for the Satisfying Assignment Search Problem (in short, SAT). The algorithm transforms instances of the integer factorization p…