Toshiya Itoh

TCS Journal 2025 Journal Article

Popularity on the roommate diversity problem

• Steven Ge
• Toshiya Itoh

A recently introduced restricted variant of the multidimensional stable roommates problem is the roommate diversity problem: each agent belongs to one of two types (e. g. , red and blue), and the agents' preferences over the rooms solely depend on the fraction of agents of their own type among their roommates. We study this variant with the notion of popularity. We show that in the roommate diversity problem with the room size fixed to 2, the problem becomes tractable. Particularly, a popular partitioning of agents is guaranteed to exist and can be computed in polynomial time. Additionally, a mixed popular partitioning of agents is always guaranteed to exist in any roommate diversity game. By contrast, when there are no restrictions on the room size of a roommate diversity game, a popular partitioning may fail to exist and the problem becomes intractable.

TCS Journal 2021 Journal Article

Physical zero-knowledge proof for Ripple Effect

• Suthee Ruangwises
• Toshiya Itoh

Ripple Effect is a logic puzzle where the player has to fill numbers into empty cells in a rectangular grid. The grid is divided into rooms, and each room must contain consecutive integers starting from 1 to its size. Also, if two cells in the same row or column contain the same number x, there must be a space of at least x cells separating the two cells. In this paper, we develop a physical zero-knowledge proof for the Ripple Effect puzzle using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, given a secret number x and a list of numbers, our protocol can physically verify that x does not appear among the first x numbers in the list without revealing x or any number in the list.

TCS Journal 2021 Journal Article

Securely computing the n-variable equality function with 2n cards

• Suthee Ruangwises
• Toshiya Itoh

Research in the area of secure multi-party computation using a deck of playing cards, often called card-based cryptography, started from the introduction of the five-card trick protocol to compute the logical AND function by den Boer in 1989. Since then, many card-based protocols to compute various functions have been developed. In this paper, we propose two new protocols that securely compute the n-variable equality function (determining whether all inputs are equal) E: { 0, 1 } n → { 0, 1 } using 2n cards. The first protocol can be generalized to compute any doubly symmetric function f: { 0, 1 } n → Z using 2n cards, and any symmetric function f: { 0, 1 } n → Z using 2 n + 2 cards. The second protocol can be generalized to compute the k-candidate n-variable equality function E: ( Z / k Z ) n → { 0, 1 } using 2 ⌈ lg ⁡ k ⌉ n cards.

TCS Journal 2018 Journal Article

Optimal online algorithms for the multi-objective time series search problem

• Shun Hasegawa
• Toshiya Itoh

Tiedemann et al. (2015) [8] formulated multi-objective online problems and several measures of the competitive analysis, and showed best possible online algorithms for the multi-objective time series search problem with respect to those measures of the competitive analysis. In this paper, we present modified definitions of the competitive analysis for multi-objective online problems and propose a simple online algorithm Balanced Price Policy ( bpp k ) for the multi-objective (k-objective) time series search problem. Under the modified framework, we show that the algorithm bpp k is best possible with respect to any measure of the competitive analysis and we also derive best possible values of the competitive ratio for the multi-objective time series search problem with respect to several natural measures of the competitive analysis.

TCS Journal 2015 Journal Article

Buffer management of multi-queue QoS switches with class segregation

• Toshiya Itoh
• Seiji Yoshimoto

In this paper, we focus on buffer management of multi-queue QoS switches in which packets of different values are segregated in different queues. Our model consists of m queues and m packet values 0 < v 1 < v 2 < ⋯ < v m. Recently, Al-Bawani and Souza (2013) [2] presented an online algorithm greedy for buffer management of multi-queue QoS switches with class segregation and showed that if m queues have the same size, then greedy is ( 1 + r ) -competitive, where r = max 1 ≤ i ≤ m − 1 ⁡ v i v i + 1. In this paper, we show that greedy is ( 1 + r ) -competitive for the case that m queues do not necessarily have the same size.

STOC Conference 2003 Conference Paper

On the sample size of k-restricted min-wise independent permutations and other k-wise distributions

• Toshiya Itoh
• Yoshinori Takei
• Jun Tarui

An explicit study of min-wise independent permutation families, together with their variants --- k-restricted, approximate, etc. --- was initiated by Broder, et al[4]. In this paper, we give a lower bound for the size of k-restricted min-wise independent permutation family. A family F of permutations on [0,n-1]=(0,1,...,n-1) is said to be k-restricted min-wise independent if for any subset X ⊆ [0,n-1] with |X| ≤ k and any x ∈ X, Pr[min(π(X))=π(x)] = 1/|X|, when π is randomly chosen from F according to a probability distribution D on the family F. For the minimum size of a family of k-restricted min-wise independent permutations, upper bounds of O(n k ) for any fixed k have been shown for uniform and biased probability distributions on F. We show that if a family F of permutations on [0,n-1] is k-restricted min-wise independent, then |F| ≥ m(n-1,k-1), where m(n,d) = ∑ i=0 d/2 ( n i ) if d is even; m(n,d)= ∑ i=0 (d-1)/2 ( n i ) + ( n-1 (d-1)/2 ) otherwise. The lower bound for the size of F still holds when we allow an arbitrary probability distribution on F. Our proof technique is based on linear algebra methods, and can be regarded as a generalization of the result by Alon, Babai, and Itai[1], i.e., if random variables X 1 ,X 2 ,...,X n : Ω → (0,1) are k-wise independent and Pr[X i =1] = p i is neither 0 nor 1, then |Ω| ≥ m(n,k). By applying our proof technique, we also derive lower bounds for the sample size of the related notions, e.g., k-wise symmetrically independent distributions, k-rankwise independent permutation families, etc.

SODA Conference 2000 Conference Paper

On permutations with limited independence

• Toshiya Itoh
• Yoshinori Takei
• Jun Tarui

I&C Journal 1996 Journal Article

Simulating Fair Dice with Biased Coins

• Toshiya Itoh

This paper is concerned with simulating a fair die with a bounded number of coin flips and a bounded number of (possibly biased) coins. As the main results, this paper shows that for anyn⩾2, a set ofH(n) coins is sufficient to simulate a fairn-sided die withind=⌈lg n⌉ coin flips, whereH(n) is the number of 1's of the binary representation of an integern, and that for anyn=2 d −1 (d⩾3), a set ofd=H(n) coins is necessary and sufficient to simulate a fairn-sided die withind=⌈lg n⌉ coin flips.

I&C Journal 1989 Journal Article

Structure of parallel multipliers for a class of fields GF(2m)

• Toshiya Itoh
• Shigeo Tsujii

This paper presents a configuration of parallel multipliers for GF(2 m ) based on canonical bases. The possible parallel multipliers by the proposed configuration are limited to a class of fields GF(2 m ). However they can be constructed by O(m2) AND-gates and O(m2) EOR-gates with the structural modularity (this is a desirable feature for the hardware implementation), and their operation time is about (log m) T, where m is the dimension of GF(2 m ) and T is the delay time of an EOR-gate. In order to construct such parallel multipliers, we define two types of polynomials of special form over GF(2), one is called all one polynomial (denoted by AOP) and the other is called equally spaced polynomial (denoted by ESP). Furthermore, we show a necessary and sufficient condition for ESPs to be irreducible over GF(2) and the uniqueness of the irreducible ESPs over GF(2). Finally, we propose the configuration of parallel multipliers for a class of fields GF(2 m ) based on irreducible AOPs and ESPs over GF(2).

I&C Journal 1988 Journal Article

A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases

• Toshiya Itoh
• Shigeo Tsujii

This paper proposes a fast algorithm for computing multiplicative inverses in GF(2 m ) using normal bases. Normal bases have the following useful property: In the case that an element x in GF(2 m ) is represented by normal bases, 2 k power operation of an element x in GF(2 m ) can be carried out by k times cyclic shift of its vector representation. C. C. Wang et al. proposed an algorithm for computing multiplicative inverses using normal bases, which requires (m − 2) multiplications in GF(2 m ) and (m − 1) cyclic shifts. The fast algorithm proposed in this paper also uses normal bases, and computes multiplicative inverses iterating multiplications in GF(2 m ). It requires at most 2[log2(m − 1)] multiplications in GF(2 m ) and (m − 1) cyclic shifts, which are much less than those required in the Wang's method. The same idea of the proposed fast algorithm is applicable to the general power operation in GF(2 m ) and the computation of multiplicative inverses in GF(q m ) (q = 2 n ).