著者

Demaine Erik D. Demaine Martin L. Uehara Ryuhei Uno Takeaki Uno Yushi

出版者

Springer

雑誌

Lecture Notes in Computer Science (ISSN:03029743)

巻号頁・発行日

vol.6099, pp.133-144, 2010

被引用文献数

3

---

UNO is one of the world-wide well-known and popular card games. We investigate UNO from the viewpoint of combinatorial algorithmic game theory by giving some simple and concise mathematical models for it. They includecooperative and uncooperative versions of UNO, for example. As a result of analyzing their computational complexities, we prove that even a single-player version of UNO is NP-complete, while it becomes in P in some restricted cases. We also show that uncooperative two-player's version is PSPACE-complete.Fun with Algorithms : 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010.

著者

Ohmura Hayato Kitasuka Teruaki Aritsugi Masayoshi オオムラ ハヤト キタスカ テルアキ アリツギ マサヨシ 大村 勇人 北須賀 輝明 有次 正義

出版者

Springer

雑誌

Lecture Notes in Computer Science (ISSN:03029743)

巻号頁・発行日

vol.6884, pp.53-62, 2011

被引用文献数

1

---

In this paper, we introduce a Web browsing behavior recording system for research. Web browsing behavior data can help us to providesophisticated services for human activities, because the data must indicate characteristics ofWeb users.We discuss the necessity of the data with potential benefits, and develop a system for collecting the data as an add-on for Firefox. We also report some results of preliminary experiments to test its usefulness in analyses on human activities in this paper.

著者

Yoshida Mitsuo Arase Yuki

出版者

Springer Berlin Heidelberg

雑誌

Information Retrieval Technology (ISSN:03029743)

巻号頁・発行日

vol.7675, pp.138-149, 2012-12

被引用文献数

1

---

We propose a method for classifying queries whose frequency spikesin a search engine into their topical categories such as celebrities and sports. Unlikeprevious methods using Web search results and query logs that take a certainperiod of time to follow spiking queries, we exploit Twitter to timely classifyspiking queries by focusing on its massive amount of super-fresh content. Theproposed method leverages unique information in Twitter—not only tweets butalso users and hashtags. We integrate such heterogeneous information in a graphand classify queries using a graph-based semi-supervised classification method.We design an experiment to replicate a situation when queries spike. The resultsindicate that the proposed method functions effectively and also demonstrate thataccuracy improves by combining the heterogeneous information in Twitter.

著者

Miyaji Atsuko Rahman Mohammad Shahriar Soshi Masakazu

出版者

Springer

雑誌

Lecture Notes in Computer Science (ISSN:03029743)

巻号頁・発行日

no.6513, pp.160-174, 2011

---

To address the question of secure and efficient management of the access credentials so that a user can store and retrieve them using a 'short and easy-to-remember' password in a connected world、 X. Boyen proposed a user-centric model in ASIACCS'09、 named Hidden Credential Retrieval (HCR). The protocol was shown secure under random-oracle model. However, the construction does not explicitly prevent an HCR server from colluding with the third party service provider (i.e., an online bank), which can result into retrieving the hidden credential without the user's participation. In this paper, we show the HCR construction without the random-oracles with enhanced properties based on Okamoto's blind signature scheme proposed in TCC'06. For the "Insider attack" model, we provide the attacker (server) with more computational ability in trying to recover the plaintext message from the ciphertext that has been stored in the server by the user, being completely offline. Moreover, we include an explicit notion of identity ID that is useful in practice, so that the server knows whose encrypted credential is to be used in the protocol.The 11th International Workshop on Information Security Applications. WISA 2010, Jeju Island, Korea, August 24-26, 2010

著者

Hashimoto Junichi Kishimoto Akihiro Yoshizoe Kazuki Ikeda Kokolo

出版者

Springer

雑誌

Lecture Notes in Computer Science (ISSN:03029743)

巻号頁・発行日

vol.7168, pp.1-12, 2012

被引用文献数

6

---

Monte-Carlo Tree Search (MCTS) is a very successful approach for improving the performance of game-playing programs. This paper presents the Accelerated UCT algorithm, which overcomes a weakness of MCTS caused by deceptive structures which often appear in game tree search. It consists in using a new backup operator that assigns higher weights to recently visited actions, and lower weights to actions that have not been visited for a long time. Results in Othello, Havannah and Go show that Accelerated UCT is not only more effective than previous approaches but also improves the strength of FUEGO, which is one of the best computer Go programs.

著者

HIROSE Shoichi KUWAKADO Hidenori

出版者

Springer-Verlag

雑誌

Lecture Notes in Computer Science (ISSN:03029743)

巻号頁・発行日

pp.262-275, 2009-10

被引用文献数

1

---

This article discusses the provable security of an iteratedhash function using a block cipher. It assumes the construction usingthe Matyas-Meyer-Oseas (MMO) scheme for the compression functionand the Merkle-Damg˚ard with a permutation (MDP) for the domainextension transform. It is shown that this kind of hash function, MDPMMO,is indifferentiable from the variable-input-length random oraclein the ideal cipher model. It is also shown that HMAC using MDPMMOis a pseudorandom function if the underlying block cipher is apseudorandom permutation under the related-key attack with respect tothe permutation used in MDP. Actually, the latter result also assumesthat the following function is a pseudorandom bit generator:(E_<IV>(K ⊕ opad) ⊕ K ⊕ opad)||(E_<IV> (K ⊕ ipad) ⊕ K ⊕ ipad) ,where E is the underlying block cipher, IV is the fixed initial value ofMDP-MMO, and opad and ipad are the binary strings used in HMAC.This assumption still seems reasonable for actual block ciphers, thoughit cannot be implied by the pseudorandomness of E as a block cipher.The results of this article imply that the security of a hash function maybe reduced to the security of the underlying block cipher to more extentwith the MMO compression function than with the Davies-Meyer (DM)compression function, though the DM scheme is implicitly used by thewidely used hash functions such as SHA-1 and MD5.