# 岩間研究室 発表論文

id=2009-27

パズル・ゲームで楽しむ数学 ,

## [ 論文誌 ]

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

配属人数下限付き研修医配属問題'',

id=2009-04

Cellプロセッサを用いた編集距離計算の高速化 (Cellチャレンジ2009規定課題部門1位)'',

id=2009-11

量子偽コイン問題'',

>> Abstract
id=2009-13

STOC2009参加報告'',

id=2009-17

最大サイズ最大安定度マッチング問題に対する近似下限の改良'',

>> Abstract
id=2009-20
H. Ito, J. Teruyama, Y. Yoshida,
An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins'',

>> Abstract
id=2009-21

3-SAT in RTIME(O(1.3211 to the n))'',

>> Abstract
id=2009-23

片方のみがタイを持つ安定結婚問題に対する25/17-近似アルゴリズム'',

>> Abstract
id=2009-28
K. Seto, S. Tamaki, K. Iwama,
Enumerating Non-3-colorable Planar Graphs by the Hajo's Calculus'',

## [ 解説 ]

id=2009-29

 確率的検査可能証明と近似不可能性 '',

## [ その他 ]

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

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

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.