岩間研究室発表論文

2009年度

[ 著書 ]

id=2009-27: 伊藤大雄 ,; パズル・ゲームで楽しむ数学 ,; 森北出版 , 2010年 2月.

[ 論文誌 ]

id=2009-06: K. Iwama, H. Morizumi, and J. Tarui,; ``Negation-Limited Complexity of Parity and Inverters'',; Algorithmica, vol.54, no.2, pp.256--267, Jun. 2009.; >> Abstract

id=2009-09: S. Miyazaki, and K. Okamoto,; ``Improving the Competitive Ratio of the Online OVSF Code Assignment Problem'',; Algorithms, vol.2, no.2, pp.953-972, Jul. 2009.; >> Abstract

id=2009-12: K. Hamada, K. Iwama, and S. Miyazaki,; ``An Improved Approximation Lower Bound for Finding Almost Stable Maximum Matchings'',; Information Processing Letters, vol.109, no.18, pp.1036--1040, Aug. 2009.; >> Abstract

id=2009-15: H. Morizumi,; ``Limiting Negations in Non-Deterministic Circuits'',; Theoretical Computer Science, vol.410, no.38, pp.3988--3994, Sep. 2009.; >> Abstract

id=2009-16: H. Ito, and K. Iwama,; ``Enumeration of isolated cliques and pseudo-cliques'',; ACM Transactions on Algorithms, vol.5, no.4, Oct. 2009.

id=2009-24: Y. Yoshida, and H. Ito,; ``Query-Number Preserving Reductions and Linear Lower Bounds for Testing'',; IEICE Transactions on Information and Systems, vol.93-D, no.2, pp.233--240, Feb. 2010.; >> Abstract

id=2009-25: H. Morizumi, and G. Suzuki,; ``Negation-Limited Inverters of Linear Size'',; IEICE Transactions on Information and Systems, vol.E93-D, no.2, pp.257--262, Feb. 2010.; >> Abstract

id=2009-26: K. Iwama, K. Seto, and S. Tamaki,; ``The Complexity of the Hajos Calculus for Planar Graphs'',; Theoretical Computer Science, vol.411(7-9), pp.1182--1191, Feb. 2010.; >> Abstract

[ 国際会議 ]

id=2009-01: Y. Yoshida, M. Yamamoto, and H. Ito,; ``Constant-Time Approximations Using Minimum Value Search for Independent Sets and Matchings'',; Proc. 2nd Asian Association for Algorithms and Computation (AAAC 2009), pp.2, Apr. 2009.

id=2009-02: K. Iwama, K. Seto, and S. Tamaki,; ``The Planar Hajos Calculus for Bounded Degree Graphs'',; Proc. 2nd Asian Association for Algorithms and Computation (AAAC 2009), pp.29, Apr. 2009.

id=2009-05: Y. Yoshida, M. Yamamoto, and H. Ito,; ``An Improved Constant-Time Approximation Algorithm for Maximum Matchings'',; Proc. 41st ACM Symposium on Theory of Computing (STOC 2009), pp.225--234, Jun. 2009.; >> Abstract

id=2009-07: R. Freivalds, and K. Iwama,; ``Quantum Queries on Permutations with a Promise'',; Proc. 14th International Conference on Implementation and Application of Automata (CIAA 2009), pp.208--216, Jul. 2009.

id=2009-08: H. Morizumi,; ``Limiting Negations in Formulas'',; Proc. the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), LNCS 5555, pp.701--712, Jul. 2009.; >> Abstract

id=2009-10: K. Iwama, K. Seto, and S. Tamaki,; ``Enumerating Non-3-colorable Planar Graphs by the Hajo's Calculus'',; Proc. 12th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2009), pp.14--21, Jul. 2009.; >> Abstract

id=2009-18: D. Okanohara, and Y. Yoshida,; ``Conjunctive Filter: Breaking the Entropy Barrier'',; Proc. Algorithm Engineering and Experiments (ALENEX10), pp.77--83, Jan. 2010.; >> Abstract

id=2009-19: K. Iwama, H. Nishimura, R. Raymond, and J. Teruyama,; ``Quantum Counterfeit Coin Problems'',; Proc. 13th workshop on Quantum Information Processing(QIP 2010), Jan. 2010.

id=2009-22: K. Iwama, and T. Ichiba,; ``Averaging Techniques for Competitive Actions'',; Proc. Analytic Algorithmic and Combinatorics (ANALCO10), pp.74--81, Jan. 2010.

[ 国内発表 ]

id=2009-03: 濱田浩気, 宮崎修一, 岩間一雄,; ``配属人数下限付き研修医配属問題'',; 京都大学数理解析研究所講究録1649 「理論計算機科学の深化と応用」(冬のLAシンポジウム), pp.73--80, 2009年 5月.

id=2009-04: 桜庭俊, 吉田悠一,; ``Cellプロセッサを用いた編集距離計算の高速化 (Cellチャレンジ2009規定課題部門1位)'',; 先進的計算基盤システムシンポジウム論文集 (SACSIS 2009), pp.97, 2009年 5月.

id=2009-11: 岩間一雄, 西村治道, ルディ・レイモンド, 照山順一,; ``量子偽コイン問題'',; 夏のLAシンポジウム, pp.3.1--3.4, 2009年 7月.; >> Abstract

id=2009-13: 伊藤大雄, 吉田悠一,; ``STOC2009参加報告'',; 情報処理, vol.50, no.8, pp.794--797, 2009年 8月.

id=2009-17: 濱田浩気, 宮崎修一, 岩間一雄,; ``最大サイズ最大安定度マッチング問題に対する近似下限の改良'',; 電子情報通信学会コンピューテーション研究会, 信学技報, vol.109, no.235, COMP2009-37, pp.35--40, 2009年 10月.; >> Abstract

id=2009-20: H. Ito, J. Teruyama, Y. Yoshida,; ``An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins'',; 電子情報通信学会コンピューテーション研究会, 信学技報, vol.109, no.391, COMP2009-45, pp.45--49, 2010年 1月.; >> Abstract

id=2009-21: 高井唯史, 玉置卓, 岩間一雄,; ``3-SAT in RTIME(O(1.3211 to the n))'',; 冬のLAシンポジウム, pp.33.1--33.8, 2010年 1月.; >> Abstract

id=2009-23: 柳澤弘揮, 宮崎修一, 岩間一雄,; ``片方のみがタイを持つ安定結婚問題に対する25/17-近似アルゴリズム'',; 冬のLAシンポジウム, 京都大学数理解析研究所講究録1691, pp.136--141, 2010年 2月.; >> Abstract

id=2009-28: K. Seto, S. Tamaki, K. Iwama,; ``Enumerating Non-3-colorable Planar Graphs by the Hajo's Calculus'',; 電子情報通信学会総合大会 , vol.DS-1-4, pp.(to appear), 2010年 3月.

[ 解説 ]

id=2009-29: 玉置卓 ,; `` 確率的検査可能証明と近似不可能性 '',; 電子情報通信学会知識ベース , vol.6群2編7章2節, to appear., pp., 年 (発表月不明).

[ その他 ]

id=2009-14: A. Ambainis, K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond, S. Tani, and S. Yamashita,; ``Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size'',; CoRR, pp.208--216, Sep. 2009.

Abstract

id=2009-05: This paper studies constant-time approximation algorithms for problems on degree-bounded graphs. Let $n$ and $d$ be the number of vertices and the degree bound, respectively. This paper presents an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity $O(d^2)$. Using this algorithm, it also shows that there are approximation algorithms with additive error $\epsilon n$ for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to $d$ and $\frac{1}{\epsilon}$. Its approximation algorithm for the maximum matching can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. On the contrary, it also shows that every one-sided error tester for the property requires at least $\Omega(n)$ queries.

id=2009-06: In {\em negation-limited\/} complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An {\em inverter\/} is a circuit with inputs $x_1,\ldots,x_n$ and outputs $\neg x_1,\ldots,\neg x_n$. We show that (a) For $n=2^r-1$, circuits computing Parity with $r-1$ NOT gates have size at least $6n-\log_2(n+1)-O(1)$, and (b) For $n=2^r-1$, inverters with $r$ NOT gates have size at least $8n-\log_2(n+1)-O(1)$. We derive our bounds above by considering the minimum size of a circuit with at most $r$ NOT gates that computes Parity for {\em sorted\/} inputs $x_1\geq\cdots\geq x_n$. For an {\em arbitrary\/} $r$, we completely determine the minimum size. It is $2n-r-2$ for odd~$n$ and $2n-r-1$ for even~$n$ for $\lceil \log_2(n+1)\rceil-1\leq r \leq n/2$, and it is $\lfloor 3n/2 \rfloor-1$ for $r \geq n/2$. We also determine the minimum size of an {\em inverter for sorted inputs\/} with at most~$r$ NOT gates. It is $4n-3r$ for $\lceil \log_2(n+1) \rceil \leq r \leq n$. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.

id=2009-08: Negation-limited circuits have been studied as a circuit model between general circuits and monotone circuits. In this paper, we consider limiting negations in formulas. The minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f$. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $\lceil \log_2(n+1) \rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. We determine the inversion complexity of every Boolean function in formulas, i.e., the minimum number of NOT gates (NOT operators) in a Boolean formula computing (representing) a Boolean function, and particularly prove that $\lceil n/2 \rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. Moreover we show that if there is a polynomial-size formula computing a Boolean function $f$, then there is a polynomial-size formula computing $f$ with at most $\lceil n/2 \rceil$ NOT gates. We consider also the inversion complexity in formulas of negation normal form and prove that the inversion complexity is at most polynomials of $n$ for every Boolean function on $n$ variables.

id=2009-09: Online OVSF code assignment has an important application to wireless communications. Recently, this problem was formally modeled as an online problem, and performances of online algorithms have been analyzed by the competitive analysis. The previous best upper and lower bounds on the competitive ratio were 10 and 5/3, respectively. In this paper, we improve them to 7 and 2, respectively. We also show that our analysis for the upper bound is tight by giving an input sequence for which the competitive ratio of our algorithm is $7 - \varepsilon$ for an arbitrary constant $\varepsilon > 0$.

id=2009-10: We propose a generation algorithm for all non-3-colorable planar graphs. It is based on the refinement of the Haj\'{o}s Calculus, which is a non-deterministic procedure for generating all non-3-colorable graphs. Our algorithm never outputs any graphs isomorphic to already generated graphs and generates all non-3-colorable graphs in increasing order with respect to the number of vertices.

id=2009-11: 偽コイン問題とは天秤を用いて与えられた集合からすべての偽コインを見つける問題である。仮定として，天秤からは``釣り合う''または``傾く''の情報しか得られないとし，偽コインの枚数$k$を知っているものとする。天秤はオラクルとして見ることができ，クエリ計算量は天秤の使用回数である。古典計算においてクエリ計算量の下界は$\Omega(k(\log{N/k}))$である。我々は，この問題の量子クエリ計算量を研究している。 $Q(k,N)$を$N$枚のコイン集合から$k$枚の偽コインをすべて見つけるのにかかる量子クエリ計算量とする。本稿では，量子計算において$Q(k,N)=O(k^{1/4})$のアルゴリズムを示す。

id=2009-12: In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Bir\'o et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that this problem is not approximable within some constant $\delta >1$ unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant $\delta$ to $n^{1-\varepsilon}$ for any $\varepsilon >0$, where $n$ is the number of men in an input.

id=2009-15: The minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f$. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $\lceil \log_2(n+1) \rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs.

id=2009-17: 安定結婚問題で不完全希望リストを許すと，同じ例題に対するすべての安定マッチングは同サイズになる．しかし，安定性を無視すると，一般にはそれよりも大きなサイズのマッチングが存在する． Bir\'o らは，最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した．彼らは，(i) この問題がNP困難であり，任意の正定数 $\varepsilon$に対してP$\neq$NPの仮定の下で$n^{1-\epsilon}$-近似アルゴリズムを持たないこと（$n$は例題中の男性の数）， (ii) 希望リストの長さを 3以下に制限してもNP困難であり，ある定数$\delta >1$が存在しP$\neq$NPの仮定の下で$\delta$-近似アルゴリズムを持たないこと， (iii) 片側の性（例えば男性）の希望リストの長さが全て2以下ならば多項式時間で解けること，を示した．本論文では，上記(ii)の近似不可能性を，定数$\delta$から $n^{1-\varepsilon}$（$\varepsilon$は任意の正定数）へと改良した．

id=2009-18: We consider a problem for storing a \textit{map} that associates a key with a set of values. To store $n$ values from the universe of size $m$, it requires $\log_2 \binom{m}{n}$ bits of space, which can be approximated as $(1.44 + n) \log_2 m / n$ bits when $n \ll m$. If we allow $\epsilon$ fraction of errors in outputs, we can store it with roughly $n \log_2\frac{1}{\epsilon}$ bits, which matches the entropy bound. Bloom filter is a well-known example for such data structures. Our objective is to break this entropy bound and construct more space-efficient data structures. In this paper, we propose a novel data structure called a \textit{conjunctive filter}, which supports conjunctive queries on $k$ distinct keys for fixed $k$. Although a conjunctive filter cannot return the set of values itself associated with a queried key, it can perform conjunctive queries with $O(1/\sqrt{m})$ fraction of errors. Also, the consumed space is $\frac{n}{k}\log_2 m$ bits and it is significantly smaller than the entropy bound $\frac{n}{2}\log_2 m$ when $k\geq 3$. We will show that many problems can be solved by using a conjunctive filter such as full-text search and database join queries. Also, we conducted experiments using a real-world data set, and show that a conjunctive filter answers conjunctive queries almost correctly using about $1/2 \sim 1/4$ space as the entropy bound.

id=2009-20: We investigate the following sorting puzzle: We are given $n$ bins with two balls in each bin. Balls in the $i$th bin are numbered $n-i+1$. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this puzzle the best known solution requires almost $\frac{4}{5}n^2$ swaps. In this paper, we show an algorithm which solves this puzzle using less than $\frac{2n^2}{3}$ swaps. Since it is known that the lower bound of the number of swaps is $\lceil \binom{2n}{2}/3 \rceil = \lceil \frac{2n^2}{3}-\frac{n}{3} \rceil$, our result is almost tight. Furthermore, we show that for $n=2^k+1\:(k\geq 0)$ the algorithm is optimal.

id=2009-21: The CNF Satisfiability Problem (SAT) is, given a Boolean formulas in conjunctive normal form (CNF), to determine whether there is an assignment to the variables that satisfies all clauses of the formula. Since many combinatorial problems can be formulated as SAT, it is strongly desired to design faster algorithms than trivial $2^n$ upper bounds of brute force search. In particular, a lot of algorithms are proposed for $3$-SAT case and the current best bound is $O(1.32216^n)$ due to Rolf (J.~SAT, 2006). In this paper, we design a new randomized algorithm which solves $3$-SAT in time $O(1.3211^n)$. Our algorithm exploits the trade-offs between the algorithms of Paturiet al. (FOCS 1998), Sch\"oning (FOCS 1999) and Baumer and Schuler (SAT2003).

id=2009-23: タイと不完全なリストを含む安定結婚問題 (MAX SMTI) において、最大マッチングを求める問題は NP 困難であることが知られている。近似度の下限は $33/29 \ (> 1.1379)$ であり、現時点で最良の近似アルゴリズムの近似度は $1.5$ である。 MAX SMTI はタイを片方のみに制限しても NP 困難であり、近似度の下限は$21/19\(> 1.1052)$である。この制限を加えても、近似度が $1.5$ より良いアルゴリズムは知られていなかった。本稿では、タイを片方に制限した場合の近似度を$25/17 \ (< 1.4706)$に改良する。

id=2009-24: In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property $P$ from the case that it has a large distance to having $P$ with probability at least $\frac{2}{3}$. The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., $3$-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, $3$-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum $3$-dimensional matching.

id=2009-25: An inverter is a circuit which outputs $\neg x_1, \neg x_2, \ldots, \neg x_n$ for any Boolean inputs $x_1, x_2, \ldots, x_n$. We consider constructing an inverter with AND gates and OR gates and a few NOT gates. Beals, Nishino and Tanaka have given a construction of an inverter which has size $O(n\log n)$ and depth $O(\log n)$ and uses $\lceil \log(n+1) \rceil$ NOT gates. In this paper we give a construction of an inverter which has size $O(n)$ and depth $\log^{1+o(1)}n$ and uses $\log^{1+o(1)}n$ NOT gates. This is the first negation-limited inverter of linear size using only $o(n)$ NOT gates. We also discuss implications of our construction for negation-limited circuit complexity.

id=2009-26: The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calculus is polynomially bounded.

岩間研究室 発表論文

2009年度

[ 著書 ]

[ 論文誌 ]

[ 国際会議 ]

[ 国内発表 ]

[ 解説 ]

[ その他 ]

Abstract

岩間研究室発表論文