BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Toshiya Itoh

Toshiya Itoh contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityData Structures and AlgorithmsDiscrete MathematicsCryptography and SecurityComputer Science and Game Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2023arXiv

Popularity on the Roommate Diversity Problem

A recently introduced restricted variant of the multidimensional stable roommate 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 coalitions solely depend on the fraction of agents of their own type among their roommates. There are various notions of stability that defines an optimal partitioning of agents. The notion of popularity has received a lot of attention recently. A partitioning of agents is popular if there does not exist another partitioning in which more agents are better off than worse off. Computing a popular partition in a stable roommate game can be done in polynomial time. When we allow ties the stable roommate problem becomes NP-complete. Determining the existence of a popular solution in the multidimensional stable roommate problem also NP-hard. We show that in the roommate diversity problem with the room size fixed to two, 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 coalition size of a roommate diversity game, a popular partitioning may fail to exist and the problem becomes intractable. Our results intractability results are summarized as follows: * Determining the existence of a popular partitioning is co-NP-hard, even if the agents' preferences are trichotomous. * Determining the existence of a strictly popular partitioning is co-NP-hard, even if the agents' preferences are dichotomous. * Computing a mixed popular partitioning of agents in polynomial time is impossible unless P=NP, even if the agents' preferences are dichotomous.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Capacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line

In the online facility assignment problem OFA(k,\ell), there exist k servers with a capacity \ell \geq 1 on a metric space and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for OFA(k,\ell), we consider OFA(k,\ell) on a line, which is denoted by OFAL(k,\ell) and OFAL_{eq}(k,\ell), where the latter is the case of OFAL(k,\ell) with equidistant servers. In this paper, we deal with the competitive analysis for the above problems. As a natural generalization of the greedy algorithm GRDY, we introduce a class of algorithms called MPFS (most preferred free servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any \ell \geq 1, ALG is c-competitive for OFA(k,1) iff ALG is c-competitive for OFA(k,\ell). By applying the capacity-insensitive property of the greedy algorithm GRDY, we derive the matching upper and lower bounds 4k-5 on the competitive ratio of GRDY for OFAL_{eq}(k,\ell). To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm ALG for OFAL_{eq}(k,\ell) is at least $2k-1$. Then we propose a new MPFS algorithm IDAS (Interior Division for Adjacent Servers) for OFAL(k,\ell) and show that the competitive ratio of IDAS for OFAL}_{eq}(k,\ell) is at most 2k-1, i.e., IDAS for OFAL_{eq}(k,\ell) is best possible in all the MPFS algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Physical ZKP for Makaro Using a Standard Deck of Cards

Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation

In this paper, we focus on a multi-queue buffer management in which packets of different values are segregated in different queues. Our model consists of m packets values and m queues. Recently, Al-Bawani and Souza (arXiv:1103.6049v2 [cs.DS] 30 Mar 2011) presented an online multi-queue buffer management algorithm Greedy and showed that it is 2-competitive for the general m-valued case, i.e., m packet values are 0 < v_{1} < v_{2} < ... < v_{m}, and (1+v_{1}/v_{2})-competitive for the two-valued case, i.e., two packet values are 0 < v_{1} < v_{2}. For the general m-valued case, let c_i = (v_{i} + \sum_{j=1}^{i-1} 2^{j-1} v_{i-j})/(v_{i+1} + \sum_{j=1}^{i-1}2^{j-1}v_{i-j}) for 1 \leq i \leq m-1, and let c_{m}^{*} = \max_{i} c_{i}. In this paper, we precisely analyze the competitive ratio of Greedy for the general m-valued case, and show that the algorithm Greedy is (1+c_{m}^{*})-competitive.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Approximation Algorithms for the Highway Problem under the Coupon Model

When a store sells items to customers, the store wishes to determine the prices of the items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy those items, and also assume that each item i \in V has the production cost d_i and each customer e_j \in E has the valuation v_j on the bundle e_j \subseteq V of items. When the store sells an item i \in V at the price r_i, the profit for the item i is p_i=r_i-d_i. The goal of the store is to decide the price of each item to maximize its total profit. In most of the previous works, the item pricing problem was considered under the assumption that p_i \geq 0 for each i \in V, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of loss-leader, and showed that the seller can get more total profit in the case that p_i < 0 is allowed than in the case that p_i < 0 is not allowed. In this paper, we consider the line and the cycle highway problem, and show approximation algorithms for the line and/or cycle highway problem for which the smallest valuation is s and the largest valuation is \ell or all valuations are identical.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

New Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length

A $(k,δ,ε)$-locally decodable code $C: F_{q}^{n} \to F_{q}^{N}$ is an error-correcting code that encodes each message $\vec{x}=(x_{1},x_{2},...,x_{n}) \in F_{q}^{n}$ to $C(\vec{x}) \in F_{q}^{N}$ and has the following property: For any $\vec{y} \in {\bf F}_{q}^{N}$ such that $d(\vec{y},C(\vec{x})) \leq δN$ and each $1 \leq i \leq n$, the symbol $x_{i}$ of $\vec{x}$ can be recovered with probability at least $1-ε$ by a randomized decoding algorithm looking only at $k$ coordinates of $\vec{y}$. The efficiency of a $(k,δ,ε)$-locally decodable code $C: F_{q}^{n} \to F_{q}^{N}$ is measured by the code length $N$ and the number $k$ of queries. For any $k$-query locally decodable code $C: F_{q}^{n} \to F_{q}^{N}$, the code length $N$ is conjectured to be exponential of $n$, however, this was disproved. Yekhanin [In Proc. of STOC, 2007] showed that there exists a 3-query locally decodable code $C: F_{2}^{n} \to F_{2}^{N}$ such that $N=\exp(n^{(1/\log \log n)})$ assuming that the number of Mersenne primes is infinite. For a 3-query locally decodable code $C: F_{q}^{n} \to F_{q}^{N}$, Efremenko [ECCC Report No.69, 2008] reduced the code length further to $N=\exp(n^{O((\log \log n/ \log n)^{1/2})})$, and also showed that for any integer $r>1$, there exists a $k$-query locally decodable code $C: F_{q}^{n} \to F_{q}^{N}$ such that $k \leq 2^{r}$ and $N=\exp(n^{O((\log \log n/ \log n)^{1-1/r})})$. In this paper, we present a query-efficient locally decodable code and show that for any integer $r>1$, there exists a $k$-query locally decodable code $C: F_{q}^{n} \to F_{q}^{N}$ such that $k \leq 3 \cdot 2^{r-2}$ and $N=\exp(n^{O((\log \log n/ \log n)^{1-1/r})})$.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Weighted Random Popular Matchings

For a set A of n applicants and a set I of m items, we consider a problem of computing a matching of applicants to items, i.e., a function M mapping A to I; here we assume that each applicant $x \in A$ provides a preference list on items in I. We say that an applicant $x \in A$ prefers an item p than an item q if p is located at a higher position than q in its preference list, and we say that x prefers a matching M over a matching M&#39; if x prefers M(x) over M&#39;(x). For a given matching problem A, I, and preference lists, we say that M is more popular than M&#39; if the number of applicants preferring M over M&#39; is larger than that of applicants preferring M&#39; over M, and M is called a popular matching if there is no other matching that is more popular than M. Here we consider the situation that A is partitioned into $A_{1},A_{2},...,A_{k}$, and that each $A_{i}$ is assigned a weight $w_{i}>0$ such that w_{1}>w_{2}>...>w_{k}>0$. For such a matching problem, we say that M is more popular than M&#39; if the total weight of applicants preferring M over M&#39; is larger than that of applicants preferring M&#39; over M, and we call M an k-weighted popular matching if there is no other matching that is more popular than M. In this paper, we analyze the 2-weighted matching problem, and we show that (lower bound) if $m/n^{4/3}=o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} \geq 2w_{2}$ has a 2-weighted popular matching with probability o(1); and (upper bound) if $n^{4/3}/m = o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} \geq 2w_{2}$ has a 2-weighted popular matching with probability 1-o(1).

0 citations0 reviewsNo code linkedOpen access