Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.4230/LIPIcs.FUN

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

DOI： 10.1016/j.tcs.2021.09.034

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：World Scientific Pub Co Pte Ltd  

In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM([Formula: see text]). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM([Formula: see text]). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM([Formula: see text]) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL([Formula: see text]), where [Formula: see text] is the number of servers. We first observe that the upper and lower bounds for OMM([Formula: see text]) also hold for OFAL([Formula: see text]), so the competitive ratio for OFAL([Formula: see text]) is exactly 3. We then show lower bounds on the competitive ratio [Formula: see text] [Formula: see text], [Formula: see text] [Formula: see text] and [Formula: see text] [Formula: see text] for OFAL([Formula: see text]), OFAL([Formula: see text]) and OFAL([Formula: see text]), respectively.

DOI： 10.1142/s1793830921501561

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer International Publishing  

DOI： 10.1007/978-3-030-87993-8_10

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

DOI： 10.1016/j.tcs.2021.07.007

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

DOI： 10.1007/s00224-020-09978-5

researchmap

Other Link： https://link.springer.com/article/10.1007/s00224-020-09978-5/fulltext.html

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-64843-5_33

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/cocoa/cocoa2020.html#ItohMS20

Language：English  

DOI： 10.4230/LIPIcs.FUN.2021.22

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Science and Business Media Deutschland GmbH  

DOI： 10.1007/978-3-030-59267-7_3

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.7155/jgaa.00513

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transfun.E102.A.1150

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-030-19955-5_30

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-030-25005-8_33

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-030-19955-5_29

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transfun.E101.A.1404

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

DOI： 10.1016/j.tcs.2017.01.008

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/978-3-319-75172-6_10

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/978-3-319-30139-6_24

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2015.04.010

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1002/rsa.20316

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.E93.D.263

Web of Science

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

When a store sells items to customers, the store wishes to decide the prices of 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 the items, and also assume that each item i ∈ V has the production cost d_i and each customer e_j ∈ E has the valuation v_j on the bundle e_j ⊆ V of items. When the store sells an item i ∈ 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. We refer to this maximization problem as the item pricing problem. In most of the previous works, the item pricing problem was considered under the assumption that p_i ≥ 0 for each i ∈ 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 highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is s and the largest valuation is l (this is called an [s, l]-valuation setting) or all valuations are identical (this is called a single valuation setting).

DOI： 10.1587/transfun.E92.A.1779

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.E92.D.149

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1093/ietisy/e91-d.2.187

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1002/rsa.20184

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1093/ietfec/e89-a.5.1186

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1145/780542.780645

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/978-3-540-45198-3_33

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Tohoku University  

In a factory, we need to make capital investments in machines for manufacturing a product. In this paper, we deal with the convex case capital investment such that more expensive machines have cheaper production costs. What we with to achieve is to design a good online algorithm that minimizes the sum of the production and capital costs when the production request and investment opportunities in the future are unknown. Azar, et al. proposed an (online) algorithm Convex for the convex case capital investment and showed that it is (4+2√2)-competitive. In this paper, we investigate the competitive ratio of the convex case capital investment more precisely and show that (1) for the convex case capital investment, the competitive ratio of the algorithm Convex is at least 4+2√2-ε for any ε>0 (Theorem 3.3). In the practical point of view, we introduce a notion of "γ-restricted" to the convex case capital investment and show that (2) for the γ-restricted convex case capital investment, the competitive ratio of the algorithm Convex is at most 5+4/(γ−4) for any γ≥6 (Theorem 4.3); (3) for the γ-restricted convex case capital investment, the competitive ratio of the algorithm Convex is at least 5−ε for any ε>0 (Theorem 4.4). Finally, we also show that the competitive ratio of the γ-restricted convex case capital investment is at least 2−ε for any ε>0 (Theorem 5.4).

DOI： 10.4036/iis.2002.77

CiNii Books

researchmap

Other Link： https://jlc.jst.go.jp/DN/JALC/00162126877?from=CiNii

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Tohoku University  

The metric travelling salesman problem Δ-Tsp is the traveling salesman problem in which the distances among cities satisfy the triangle inequality. In this paper, we consider the matric traveling salesman problem Δ(1,2)-Tsp with distances one and two and Δ(1,2,3)-Tsp with distances one, two, and three as the special cases of Δ-Tsp. Since Δ(1,2)-Tsp is NP-complete, it is NP-hard to find an optimal solution for Δ(1,2)-Tsp. So in polynomial time, we with to find an approximate solution for Δ(1,2)-Tsp. However Δ(1,2)-Tsp is APX-complete, there is a nontrivial approximation lower bound for Δ(1,2)-Tsp. For any ε>0, Engebretsen showed that it is NP-hard to approximate the symmetric Δ(1,2)-Tsp within 5381/5380-ε; the asymmetric Δ(1,2)-Tsp within 2805/2804-ε, and Böchenhauer, et al. showed that it is NP-hard to approximate the symmetric Δ(1,2,3)-Tsp within 3813/3812-ε. In this paper, we improve those lower bounds and show that for any ε>0, it is NP-hard to approximate the symmetric Δ(1,2)-Tsp within 1027/1026-ε (Corollary 4.5); the asymmetric Δ(1,2)-Tsp within 535/534-ε (Corollary 4.7); the symmetric Δ(1,2,3)-Tsp within 817/816-ε (Theorem 5.2); the asymmetric Δ(1,2,3)-Tsp within 364/363-ε (Theorem 5.3). We also show that for any ε>0, it is NP-hard to approximate Shortest-Superstring within 1279/1278-ε (Corollary 6.3).

DOI： 10.4036/iis.2002.63

CiNii Books

researchmap

Other Link： https://jlc.jst.go.jp/DN/JALC/00162126860?from=CiNii

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Scopus

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1145/338219.338245

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Institute of Electronics, Information and Communication, Engineers, IEICE  

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer New York LLC  

DOI： 10.1007/s001459900053

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer New York  

DOI： 10.1007/s001459900018

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1006/inco.1996.0036

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/3-540-61996-8_39

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/BF00190804

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/3-540-48071-4_17

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/3-540-48329-2_6

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/3-540-48658-5_20

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/3-540-57332-1_28

researchmap

DOI： 10.1007/3-540-57332-1_33

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/3-540-57220-1_81

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/3-540-57220-1_65

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/3-540-46877-3_3

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/3-540-46416-6_29

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

DOI： 10.1007/BFb0030368

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/0890-5401(89)90045-X

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1049/el:19890449

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/0020-0190(89)90127-0

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/0890-5401(88)90024-7

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1049/el:19880226

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1002/scj.4690190202

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1049/el:19870615

Scopus

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Let A be the set of n applicants and I be the set of m items. We assume that the set A is partitioned into A_1,A_2,...,A_k and each A_i is assigned a weight W_i such that w_1&gt; w_2 &gt; ・ ・ ・ &gt; w_k &gt; 0. Let us consider the problem of matching applicants to items, where each applicant x ∈ A provides a preference list defined on items. We say that an applicant x prefers an item p than an item q if p is located at higher position than q in the preference list. For any matchings M and M&#039;, we say that an applicant x prefers M. over M&#039; if x prefers M(x) over M&#039;(x). We say that M is more, popular than M&#039; if the total weight of applicants preferring M over M&#039; is larger than that of applicants preferring M&#039; over M, and define M to be a k-weighted popular matching if there are no other matchings that are more popular than M. For the case where k = 1, Mahdian showed that if m &gt; 1.42n, then a random instance of the matching problem has a popular matching with high probability, but nothing is known for the k-weighted matching problems. In this paper, we analyze the k-weighted matching problems, and show that for any β such that m=βn, (lower bound) if β/n^&lt;1/3&gt;=o(1), then a random instanc

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, hte customers buys more (resp. less) items, which provides less profit to the store. So it whould be hard for the store to decide the prices of items. Assume that a storeshas a set V of n items and there is a set C of m coutomers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problem according to how many items the store can sell and how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as an unlimited supply model (resp. a limited supply model). The item pricing problem is said to be single-minded if each customer j ∈ C wishes to buy a set ej ⊆ V of items and assigns its valiation w(ej) >___ 0. Balcan and Blum regarde the single-minded item pricing problems (in unlimited supply model) as weighted k-hypertraphs and described several approximation algorithms. Tn this paper, we consider the maximum (pseudo)degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded unlimited supply item pricing problems, we show improved approximation algorithms w.r.t. the maximum (pseudo)degree and the valuation ratio.

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

Recently, information access control must be implemented on IT system in universities. For instance, IT systems dealing with confidential information such as students' and salary records must perform access control using authentication technologies such as PKI. If we implement authentication on a system-by-system basis, it will degrade information confidentiality, user convenience and system's maintenance ability. Therefore, a common authentication system is very much important in universities' IT system. In order to design the common authentication system, we must care about existing business procedures and existing IT systems in universities. In this paper, we introduce Campus-wide authentication and authorization system in Tokyo Institute of Technology. Particularly, we focus on the cooperation with existing business procedures and existing IT systems. We also provide issues and solutions that come up after starting our system operation.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A family F of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, let S_n be the family of all permutations on [numerical formula]. For any integer k such that 1&le;k&le;n and any real ε>0, we say that a family F⊆S_n of permutations is ε-approximate k-restricted min-wise independent if for any (nonempty) subset X⊆[1, n] such that ∥X∥&le;k and any element x∈X,[numerical formula], when π is chosen from F uniformly at random (where ∥A∥denotes the cardinality of a finite set A). For the size of families F⊆S_n of ε-approximate k-restricted min-wise independent permutations, the following results are known: For any integer k such that 1&le;k&le;n and any real ε>0, (constructive upper bound) [numerical formula]; (nonconstructive upper bound) [numerical formula]; (lower bound) [numerical formula] and [numerical formula], [numerical formula]. In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with m&le;2 colors of a complete graph K_l of l vertices, and by the linear algebra method, we then derive a slightly improved lower bound, i.e., we show that for any family F⊆S_n of ε-approximate k-restricted min-wise independent permutations, [numerical formula].

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

The new IEEE standards of wireless LAN security and network technologies used in the standards are shown in this paper. The problem of WEP encryption discussed in the recent years are summarized, and TKIP technology and AES encryption for the next standard IEEE 802.11i are shown. For authentication, authorization, and accounting of wireless LAN client, IEEE 802.1X port-based network access control will be adopted in IEEE 802.11i. We explain EAP, RADIUS technologies, which gives the foundation for IEEE 802.1X. Finally, we show an example of management and operation of a wireless LAN environment using these technologies and point out some problems and prospects.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A notion of k-wise random permutations has several applications. From the practical point of view, it often suffices to consider ε-approximate k-wise random permutation families rather than k-wise random permutation families, however, we know little about how to construct families of ε-approximate k-wise random permutations of small size. For any integer n > 0, we use S_n to denote the set of all permutations on {0,1,...,n-1}. In this paper, we iteratively apply the Feistel Transform to construct a family of ε-approximate k-wise random permutations and we show that for any n = p^<2h> with p prime and any k = O(logn), there exists a family F⊆S_n of ε-approximate k-wise random permutations such that |F|=(n^<k^<k>>/ε^k)^<3+o>(1).. This is the first nontrivial construction for families of ε-approximate k-wise random permutations. To capture efficient evaluation of permutation families in the practical point of view, we introduce a notion of "s(n)-space pointwise samplability," and show that the family F⊆S_n of permutations constructed in this paper is O(logn)-space pointwise samplable.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A video-on-demand (VoD) is a system in which each client requests to receive a hot video and the video server immediately responds its request. In VoD system, bandwidth requirement is one of the most important measures, e.g., the maximum bandwidth and the total bandwidth, and it is known that online stream merging can reduce the bandwidth requirement. Recently, Chan et al. proposed the modified greedy algorithm MGRD_λ with catch-up parameter λ[>!_]1 and showed that for any integer λ[>!_]1, it is (2+ε)-competitive w.r.t. the maximum bandwidth and is 2.5-competitive w.r.t. the total bandwidth. In this paper, we precisely analyze the competitive ratio of the modified greedy algorithm MGRD_λ, and show that w.r.t. the maximum bandwidth, (1) the competitive ratio of the algorithm MGRD_λ is at most 2 for any integer λ[>!_]1; (2) the competitive ratio of the algorithm MGRD_λ is at least 2 for any integer λ[>!_]1; and that w.r.t. the total bandwidth, (3) the competitive ratio of the algorithm MGRD_λ is at most 2 for any integer λ[>!_]2; (4) the competitive ratio of the algorithm MGRD_λ is at least (5λ+4)/(3λ+3) for any integer λ[>!_]1.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

The recent growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of the communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required to each packet. In this paper, we derive lower bounds for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of priorities 1 and α[>!_]1, and show that for any α[>!_]1, 1+/α ln((α-1) if α[>!_]α^*; 1/(1-e^<-γ0>) if 1[>!_]α<α^*, where α^* [〜!〜] 1.657 and γ_0 is a root of the equality that e^<-γ>(1/α+γ)=1-e^γ. As an immediate result, this shows a lower bound 1.466 for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of single priority, which slightly improves the best known lower bound 1.366.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

The notion of "a family of min-wise independent permutations" was introduced by Broder, et al. It is a basic tool to estimate resemblance between documents and has applications of detecting almost identical documents on the Web and of reducing the amount of randomness used by algorithms. In this paper, we focus on min-wise independent permutations and the related notions, e. g., ε-approximate min-wise independent permutations, k-restricted min-wise independent permutatios, etc., and overview the recen tresults on (1) how to estimate resemblance between documents by min-wise independent permutations ; (2) upper and lower bounds for the size of min-wise independent permutations ; (3) upper and lower bounds for the size of ε-approximate min-wise independent permutations ; (4) upper and loer obunds for the size of k-restricted min-wise independent permutations.

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Itoh, Takei, and Tarui [7] showed that if a family 〓⊆S_n of permutations is k-restricted min-wise (resp.k-rankwise) independent, then|〓|=Ω(n^<[(k-1)/2]>)(resp.|〓|=Ω(n^<[(k-1)/2]>)). In this paper, we construct permutation families 〓⊆S_n of which size are close to those lower bounds for k=3,4. We construct a family 〓⊆S_n of 3-restricted (resp. 4-restricted) min-wise independent permutations such that |〓|= O(nlg^2n) (resp.|〓|=O(nlg^3n) by the affine plane AG(2, q) and a family 〓⊆S_n of 4-rankwise independent permutations such that |〓|= O(n^3lg^6n) by the projecive plane PG(2,q). We notice that if a family 〓⊆S_n of permutations is 4-rankwise independent, then |〓|=Ω(n^2). Since a family 〓⊆S_n of 4-rankwise independent permutations is 4-restricted min-wise independent, our family 〓⊆S_n of 4-restricted min-wise independent permutations is exactly the witness that properly separates the notion of 4-rankwise independence and that of 4-restricted min-wise independence.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper, we investigate the family size of ε-approximate k-wise independent permutations and show the following results : (1) For any ε&ge;0, if a family F⊆S_n of permutations is ε-approximate k-wise independent, then|F|&ge;n(n-1)…(n-k+1) if ε<1 ; |F|&ge;{n(n-1)…(n-k+1)}/(1+ε) otherwise ; (2) For any 0<ε&ge;1, there exists a family F⊆S_n of ε-approximete k-wise independent permutations such that |F|=O(n(n-1)/ε) ; (4) For any ε>0 and any n=p^m with p prime, it is possible to construct a polynomial time samplable family F⊆S_n of ε-approximate 3-wise independent permutations such that |F|=O(n(n-1)(n-2)/ε).

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A family F of permutations of {0, 1,..., n - 1} is k-restricted min-wise independent if for any set X ⊆ {0, 1, ..., n - 1} with |X| &le;〓k and any x ∈ X, Pr[π(x) = min{π(X)}] = 1/|X| when a permutation π is randomly drawn from F. We show that if a permutation family F of an n-set is k-restricted min-wise independent, then |F| &ge;〓m(n - 1, k - 1), where m(n, d) =Σ^<d/2>_i=0 ( ^n_i) if d is even, and m(n, d) = Σ^<(d-i)/2>_i=0 ( ^n_i) + ( ^<n-1>_(d-1)/2) if d is odd. The lower bound for the size of F still holds when we allow an aribitrary probability distribution on F. It is well known that if random variables X_1, X_2,... , X_n : Ω→ {0, 1} are d-wise independent and Pr[X_i, = 1] =p_i is neither 0 nor 1, then |Ω|&ge; m(n, d). We give the following generalization and derive the result above: if random variables X_1, , X_n, : |Ω| → {0, 1} have an identical d-wise distribution with some random variables Y_1,..., Y_n and the n-tuple (Y_1,..., Y_n,) visits all the 2^n values with positive probabilities, then |Ω|&ge; m(n, d). The existence of such Y_i's is immediate when one starts with fully-distributed truly random variables and considers random variables with an identical d-wise distribution.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Private information retrieval for k 〓 1 databases (denoted by (k, l)-PIR for short) is a protocol that (1) a user sends an l tuple query to each of k noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the l tuple query; (3) the user privately retrieve any single bit out of the n bits of data stored in k databases. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he wishes to get. In general, the efficiency of (k, l)-PIR is measured by the total amount of bits exchanged between the user and the k databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (k, l)=PIR into a linear type, a multilinear type, and an affine type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (k, l)-PIR is Ω([chemical formula])(Theorem 3.1);(2) the lower bound for the communication complexity of any linear type (k, l)-PIR is Ω(√<n>)(Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (k, l)-PIR is Ω([chemical formula])(Theorem 4.2).

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A family F of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family F of permutations on{0, 1, ..., n-1}is min-wise independent if for any X⊆{0, 1, ..., n-1}and any x∈X, Pr[min{π(X)}=π(x)]=∥X∥^<-1>when π is chosen uniformly at random from F, where∥A∥is the cardinality of a finite set A. We also say that a family F of permutations on{0, 1, ..., n-1}is d-wise independent if for any distinct x_1, x_2, ..., x_d∈{0, 1, ..., n-1}and any distinct y_1, y_2, ..., y_d∈{0, 1, ..., n-1}, Pr[Λ^d_<i=1>π(x_i)=π(y_i)]=1/{n(n-1)・・・(n-d+1)}when π is chosen uniformly at random from F(note that nontrivial constructions of d-wise independent family F of permutations on{0, 1, ..., n-1}are known only for d=2, 3). Recently, Broder, et al.showed that any family F of pairwise(2-wise)indenpendent permutations behaves close to a family of min-wise independent permutations, i.e., for any X⊆{0, 1, ..., n-1}such that 3&le;∥X∥=k&le;n-2 and any x∈X, (lower bound Pr_<π∈F>[min{π(X)}=π(x)&ge;1/{2(k-1)};(upper bound)Pr_<π∈F>[min{π(X)}=π(x)]&le;2/√<k>-3/(2k).In this paper, we extend this to 3-wise independence and show that any family F of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any X⊆{0, 1, ..., n-1}such that 4&le;∥X∥=k&le;n-3 and any x∈X, (lower bound)Pr_<π∈F>[min{π(X)}=π(x)]&ge;1/{2(k-2)}-1/{6(k-2)^2};(upper bound) Pr_<π∈F>[min{π(X)}=π(x)]&ge;2/√<k>-2/k+1/(3k√<k>).

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Private information retrieval for κ&ge;1 databases(denoted by (κ, l)-PIR)is a protocol that (1)a user sends an l tuple query to each of κ noncommunicating replicated databases;(2)each database responds the user with an answer corresponding to the l tuple query;(3)the user privately retrieve any single bit out of the n bits of data stored in κ databases. In this model, "privacy"implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he wishes to get. In general, the efficiency of (κ, l)-PIR is measured by the total amount of bits exchanged between the user and the κ databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (κ, l)-PIR into a linear type, a multilinear type, and an affine type with respect to the relationship between queries to each database(made by the user)and answers to the user(made by each database), and show that(1)the lower bound for the communication complexity of any multilinear type(κ, l)-PIR is Ω(^l+1√<n>)(Theorem3.1);(2)the lower bound for the communication complexity of any linear type(κ, l)-PIR is Ω(√<n>)(Corollary3.2);(3)the lower bound for the communication complexity of any affine type(κ, l)-PIR is Ω(^l+1√<n>)(Theorem4.2).

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c &isinsv;C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT&notion;PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHTto make the approximation upper and lower bounds more precise, adn show that (1) MAX-WEIGHTis APX-complete; (2) MAX-WEIGHTis approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHTis not approximabler within relative error 1/10 to the optimum unless P=NP.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

The metric traveling salesman problem △-TSP is the traveling salesman problem in which the distances among cities satisfy the triangle inequality. In this paper, we consider the metric traveling salesman problem (1, 2)-TSP with distances one and two as the special case of △-TSP. Since (1, 2)-TSP is NP-complete, it is HP-hard to compute an optimal solution for (1, 2)-TSP, i. e., a minimum weight tour that visits every city exactly once. Let MIN-(1, 2)-TSP be the minimization problem for (1, 2)-TSP and we wish to compute an approximate solution for MIN-(1, 2)-TSP, i. e., a tour with weight close to the minimum weight. However MIN-(1, 2)-TSP is APX-complete, there exists a nontrivial approximation lower bound for MIN-(1, 2)-TSP. Recently, Engebretsen showed that for any ε>0, it is NP-hard to approximate the symmetric MIN-(1, 2)-TSP within 5381 / 5380-ε; it is NP-hard to approximate the asymmetric MIN-(1, 2)-TSP within 2805-2804-ε. In this paper, we improve those lower bounds above and we show that for any ε>0, it is NP-hard to approximate the symmetric MIN-(1, 2)-TSP within 1027 / 1026-ε (Corollary 4.4); it is NP-hard to approximate the asymmetric MIN-(1, 2)-TSP within 535 / 534-ε (Corollary 4.6). In addition to the above, we also show that for any ε>0, it is NP-hard to approximate SHORTEST-SUPERSTRING within 2983 / 2982-ε (Corollary 5.3).

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In a factory, we need to make capital investments in machines for manufacturing a product. In this paper, we deal with the convex case capital investment such that more expensive machines have cheaper production costs. What we wish to achieve is to design a good online algorithm that minimizes the sum of the production and capital costs when the production request and investment opportunities in the future are unknown. Azar, et. al proposed an online algorithm CONVEX for the convex case capi-tal investment and showed that it is 7-competitive. In this paper, we investigate the competitive ratio of the convex case capital investment precisely and show that (1) the competitive ratio of the algorithm CONVEX is at most 4+2√<2> (Theorem 3.2); (2)for any ε>0, the competitive ratio of the algorithm CONVEX is at least 4+2√<2>-ε (Theorem 3.4); (3) for any ε>0, the competitive ratio of the convex case capital investment is at least 2-ε (Theorem 4.1). Finally, we introduce a notion of "γ-restricted" and show that (4) the competitive ratio of the algorithm CONVEX for the γ-restricted convex case cap-ital investment is at most 5+4 / (γ-4) (Theorem 5.3); (5) for any ε>0, the competitive ratio of the algorithm CONVEX for the γ-restricted case capital investment is at least 5-ε (Theorem 5.4).(

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A family of min-wise independent permutations C is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, a family of permutations C on{1, 2, ..., n}is said to be min-wise independent if for any(nonempty)X⊆{1, 2, ..., n}and any x∈X, Pr(min{π(X)}=π(x))=∥X∥^<-1>when π is chosen uniformly at random from C, where ∥A∥is the cardinality of a finite set A. For any integer n>0, it has been known that∥c∥>1cm(n, n-1, ..., 2, 1)=e^<n-o(n)>for any family of min-wise independent permutations C on{1, 2, ..., n}and that there exists a family of min-wise independent permutations C on{1, 2, ..., n}such that∥C∥<4^n. However, it has been unclear whether there exists a family of min-wise independent family C such that∥C∥=1cm(n, n-1, ..., 2, 1)for each integer n>0 and how to construct such a family of min-wise independent permutations C for each integer n>0 if it exists. In this paper, we shall construct a family of permutations F_n for each integer n>0 and show that F_n is min-wise independent and ∥F_n∥=1cm(n, n-1, ..., 2, 1). Thus our construction of F_n is optimal in the sense of family size.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical and theoretical importance. These problems are known to be NP-hard and are NP-hard to approximate within any constant factor to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generating matrix of a linear code C, find a codeword c∈C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT notin PTAS unless P = NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and then show that (1) MAX-WEIGHT is APX-compete; (2) MAX-WEIGHT is 2-approximable; and (3) MAX-WEIGHT is not (10/9)-approximable unless P = NP.

CiNii Books

researchmap

Language：English   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Informally, private information retrieval for k≧1 databases (k-PIR) is an interactive scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et.al. proposed 2-PIR with communication complexity 12n^<1/3>+2 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k≧2, there exists k-PIR with communication complexity at most c_k・n^<1/(2k-1)> some constant c_k>0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12n^<1/3>. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k≧4, there exists k-PIR witla communication complexity at most c'_k・n^<1/(2k-1)> for some constant c'_k≪c_k.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Identity-based noninteractive key-sharing schemes (ID-NIKS) are practical crypto-graphic tools to make key management tasks easier in large-scale networks. Several ID-NIKS's have been proposed so far, but most of them are proved to be insecure when sufficiently many entities conspire. Recently, Murakami, Fujikawa, and Kasahara presented a new ID-NIKS based on the RSA cryptosystem and mentioned that it is secure even when sufficiently many entities conspire. The ID-NIKS looks secure, but its security analysis only deals with several potential attacks and would be logically insufficient. In this paper, we analyze the security of the scheme and show that (1) any single entity can factor the public modulus ; (2) if three entities conspire, they can impersonate a specific entity ; (3) if n entities conspire, they can impersonate any other entity ; and (4) if n entities conspire, they can derive the trusted center's secret-key that might be different from but is equivalent to the original secret-key of the trusted center.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Private information retrieval for k&ges;1 databases (k-PIR) is a scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy"implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et. al. proposed 2-PIR with communication complexity 12n^<1/3>+2 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k&ges;2, there exists k-PIR with communication complexity at most c_k・n^<1/(2k-1)> some constant c_k&ges;0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12n^<1/3>. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k&ges;4, there exists k-PIR with communication complexity at most c^l_k・n^<1/(2k-1)> for some constant c^l_k≪c_k.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

For a code C over GF(2), the radius and covering radius of C are useful metric properties of C and play important roles in the analysis of C.In general, the decision problem for the radius and covering radius of C is computationally hard.Indeed, the decision problem for the covering radius of linear codes over GF(2)is Il^p_<2->complete and the decision problems for the radius and covering radius of nonlinear general (not necessarily linear)codes over GF(2)is NP-complete. In this paper, we first formalize those decision problems for the radius and covering radius of codes over GF(2)as minimization problems, i.e., MINIMUM RADIUS and MINIMUM COVERING RADIUS of codes over GF(2), respectively.Then we show that MINIMUM RADIUS and MINIMUM COVERING RADIUS of codes over GF(2)are hard to approximate within any constant ratio unless P=NP.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect to oracle entropy and average case oracle measures. As main results, we show the following: (1) for any k(n) ≧1/poly(n), if a language L has perfect KC k(n) + n^<-ω(1)> with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) ≧1/poly(n), if a language L has perfect KC k(n) + n^<-ω(1)> with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ∈ o(1) with respect to oracle entropy measure, then for any ε> 0, L has statistical KC k(n) + 1 +ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ∈ o(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

A checker, a self-tester, and a self-corrector for a function f are known as powerful tools in designing programs that compute f, however, the relationships among them have not been known well. In this paper, we show first that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that transform a faulty program into a less faulty program, and show that (2) if a function f has self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has a self-improver that transforms a faulty program into an almost correct program.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper, we investigate statistical and perfect Knowledge Complexity(KC) with respect to oracle entropy and average case oracle measures. As main results, we show the following : (1)for any k(n)&ge;1/poly(n), if a language L has perfect KC k(n)+n^<-w(1)> with respect to oracle entropy measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.1) ; (2)for any k(n)&ge;1/poly(n), if a language L has perfect KC k(n)+n^<-w(1)> with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2) ; (3)if a language L has statistical KC k(n)∈o(1) with respect to oracle entropy measure, then for any ∈>0, L has statistical KC k(n)+1+∈ with respect to average case oracle measure (Theorem 4.1) ; and (4) if a language L has perfect KC k(n)∈o(1) with respect to oracle entropy measure, then for any c>0, L has perfect KC k(n)+2+∈ with respect to average case oracle measure (Theorem 4.2).

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Damgard defined the notion of a collision intractable hash functions and showed that there exists a collection of collision intractable hash functions if there exists a collection of claw-free permutation pairs. For a long time, the necessary and sufficient condition for the existence of a collection of collision intractable hash functions has not been known, however, very recently Russell finally showed that there exists a collection of collision intractable hash functions iff there exists a collection of claw-free pseudo-permutation pairs. In this paper, we show an alternative necessary and sufficient condition for the existence of a collection of collision intractable hash functions, i.e., there exists a collection of collision intractable hash functions iff there exists a collection of distinction intractable pseudo-permutations.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper,we define two classes of languages,one induces opaque, transparent bit commitments and the other induces transparent/opaque bit commitments.As an application of the opaque/ transparent and the transparent/opaque properties,we first show that if a language L indnces an opaque/transparent bit commitment, then there exists a prover-practical perfect zero-knowledge proof for L,and we then show that if a language L induces a transparent/ opaque bit commitment,then there exists a bounded round perfect zero-knowledge proof for L.

CiNii Books

researchmap

Language：English   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

This paper presents a zero-knowledge interactive protocol that demonstrates two factors a and b of a composite number n (=ab) are really known by the prover, without revealing the factors themselves. Here the factors a and b need not be primes. The security of the protocol is based on the difficulty of computing discrete logarithms modulo a large prime.

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper we investigate the AM languages that seem to be located outside NP &xcup; co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in &xutri;^2&xcap; AM &xcap; co-AM but is unlikely to be in NP &xcup; co-NP, and that GH is in &xutri;^2&xcap; AM but is unlikely to be in NP &xcup; co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those

CiNii Books

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

This article reponts the papers presented in Crypto′93.

CiNii Books

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Books

researchmap

Language：Japanese   Publisher：Information Processing Society of Japan (IPSJ)  

CiNii Books

researchmap

Other Link： http://id.nii.ac.jp/1001/00004334/

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in ZPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and L^^-without any unproven assumption.

CiNii Books

researchmap

Language：Japanese   Publisher：Information Processing Society of Japan (IPSJ)  

CiNii Books

researchmap

Other Link： http://id.nii.ac.jp/1001/00004661/

Language：Japanese  

CiNii Books

researchmap

Language：English  

Web of Science

researchmap

Language：Japanese   Publisher：電子情報通信学会基礎・境界ソサイエティ  

CiNii Books

researchmap