# 岩間研究室 発表論文

## [ 著書 ]

id=2003-34

オートマトン・言語と計算理論 (電子情報通信レクチャーシリーズ B-6),
コロナ社, 2003年 11月.

## [ 論文誌 ]

id=2003-04
K. Iwama, A. Matsuura, and M. Paterson,
A family of NFAs which need $2n-\alpha$ deterministic states'',
Theoretical Computer Science, vol.301, 1-3, pp.451--462, May 2003.

>> Abstract
id=2003-17
K. Amano, K. Iwama, A. Maruoka, K. Matsuo, and A. Matsuura,
Inclusion-Exclusion for k-CNF Formulas'',
Information Processing Letters, vol.87, no.2, pp.111--117, Jul. 2003.

>> Abstract
id=2003-18
K. Iwama, and S. Yamashita,
Transformation Rules for CNOT-based Quantum Circuits and Their Applications'',
New Generation Computing, vol.21, no.4, pp.297--317, Aug. 2003.

>> Abstract
id=2003-19
K. Iwama, and A. Kawachi,
A New Quantum Claw-Finding Algorithm for Three Functions'',
New Generation Computing, vol.21, no.4, pp.319--327, Aug. 2003.

>> Abstract
id=2003-20

安全なギガビットネットワークシステム KUINS-III の構成とセキュリティ対策'',

id=2003-21
H. Ito, K. Makino, K. Arata, S. Honami, Y. Itatsu, and S. Fujishige,
Source location problem with flow requirements in directed networks'',
Optimization Methods and Software, vol.18, pp.427--435, Aug. 2003.

>> Abstract
id=2003-31
M. Halld\'orsson, R. Irving, K. Iwama, D. Manlove, S. Miyazaki, Y. Morita, and S. Scott,
Approximability Results for Stable Marriage Problems with Ties'',
Theoretical Computer Science, vol.306, 1-3, pp.431--447, Sep. 2003.

>> Abstract
id=2003-33
E. Boros, T. Horiyama, T. Ibaraki, K. Makino, and M. Yagiura,
Finding Essential Attributes from Binary Data'',
Annals of Mathematics and Artificial Intelligence, vol.39/3, pp.223--257, Nov. 2003.

>> Abstract
id=2003-35
H. Ito, K. Iwama, Y. Okabe, and T. Yoshihiro,
Avoiding routing loops on the Internet'',
Theory of Computing Systems, vol.36, no.6, pp.597--609, Nov. 2003.

>> Abstract
id=2003-36
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, and K. Watanabe,
Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synsthesis'',
IEICE Trans. Fundamentals, vol.E86-A, no.12, pp.3184--3191, Dec. 2003.

>> Abstract
id=2003-54
H. Fujiwara, K. Iwama, and C. Iwamoto,
Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs'',
Journal of Parallel and Distributed Computing, vol.64, no.3, pp.319--326, Mar. 2004.

## [ 国際会議 ]

id=2003-02
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, and K. Watanabe,
Bit Length Optimization of Fractional Parts on Floating to Fixed Point Conversion for High-Level Synthesis'',
Proc. the 11th Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2003), pp.129--136, Apr. 2003.
id=2003-03
Y. Hanatani, T. Horiyama, and K. Iwama,
Density Condensation of Boolean Formulas'',
Proc. the 6th International Conference on Theory and Application of Satisfiability Testing (SAT 2003), pp.126--133, May 2003.

>> Abstract
id=2003-05
Y. Hanatani, T. Horiyama, and K. Iwama,
Condensation of Boolean Formulas'',
DIMACS Workshop on Complexity and Inference, Jun. 2003.
id=2003-07
H. Ito, K. Iwama, Y. Okabe, and T. Yoshihiro,
Polynomial time computable backup tables for shortest path routing'',
Proc. the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), Proceedings in Informatics, vol.17, pp.163--177, Jun. 2003.

>> Abstract
id=2003-08
K. Iwama, A. Kawachi, and S. Yamashita,
Quantum Sampling for Balanced Allocations'',
Proc. the 9th Annual International Computing and Combinatorics Conference (COCOON 2003), LNCS 2697, pp.304--318, Jul. 2003.

>> Abstract
id=2003-09
M. Halld\'orsson, K. Iwama, S. Miyazaki, and H. Yanagisawa,
Randomized Approximation of the Stable Marriage Problem'',
Proc. the 9th Annual International Computing and Combinatorics Conference (COCOON 2003), LNCS 2697, pp.339--350, Jul. 2003.

>> Abstract
id=2003-10
H. Ito,
Mapping Graphs or Hypergraphs onto Convex Polygons'',
EURO/INFORMS 2003, Jul. 2003.

>> Abstract
id=2003-11
Rudy Raymond H.P., S. Yamashita, and K. Iwama,
Quantum Query Complexity of Biased Oracles'',
Proc. the 8th Quantum Information Technology Symposium (QIT8), Jul. 2003.
id=2003-22
K. Iwama,
On the Power of Quantum Oracles'',
ERATO workshop on Quantum Information Science 2003 (EQIS 03), pp.25, Sep. 2003.

(invited talk)
id=2003-23
Rudy Raymond H.P., S. Yamashita, and K. Iwama,
Quantum Query Complexity of Biased Oracles'',
ERATO workshop on Quantum Information Science 2003 (EQIS 03), pp.33--34, Sep. 2003.
id=2003-24
A. Kawachi, T. Koshiba, H. Nishimura, and T. Yamakami,
A Quantum Trapdoor One-Way Function that Relies on the Hardness of the Graph Automorphism Problem'',
ERATO workshop on Quantum Information Science 2003 (EQIS 03), pp.115--116, Sep. 2003.
id=2003-25
A. Kawachi, T. Koshiba, H. Kobayashi, and Rudy Raymond H.P.,
A Characterization of Quantum One-Way Permutations'',
ERATO workshop on Quantum Information Science 2003 (EQIS 03), pp.153--154, Sep. 2003.
id=2003-30
M. Halld\'orsson, K. Iwama, S. Miyazaki, and H. Yanagisawa,
Improved Approximation of the Stable Marriage Problem'',
Proc. the 11th Annual European Symposium on Algorithms (ESA 2003), LNCS 2832, pp.266--277, Sep. 2003.

>> Abstract
id=2003-32
K. Iwama, and M. Okita,
Compact Routing for Flat Networks'',
Proc. the 17th International Symposium on Distributed Computing (DISC 2003), pp.196--210, Oct. 2003.

>> Abstract
id=2003-38
N. Doi, T. Horiyama, M. Nakanishi, and S. Kimura,
Minimization of Fractional Wordlength on Fixed-Point Conversion for High-Level Synthesis'',
Proc. the 9th Asia and South Pacific Design Automation Conference 2004 (ASP-DAC 2004), 1D-3, pp.80--85, Jan. 2004.
id=2003-39
A. Ambainis, R. Cleve, K. Iwama, A. Kawachi, H. Masuda, Rudy Raymond H.P., and S. Yamashita,
Quantum Oracle Computation with and without Noises'',
Proc. 7th workshop on Quantum Information Processing (QIP 2004), Jan. 2004.
id=2003-40
A. Kawachi, H. Kobayashi, T. Koshiba, and Rudy Raymond H.P.,
Characterizaing the Existence of Quantum One-way Permutations'',
Proc. 7th workshop on Quantum Information Processing (QIP 2004), Jan. 2004.

>> Abstract
id=2003-41
K. Iwama, and S. Tamaki,
Improved Upper Bounds for 3-SAT'',
Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp.321--322, Jan. 2004.
id=2003-47
Y. Asahiro, T. Horiyama, K. Makino, H. Ono, T. Sakuma, and M. Yamashita,
How to Collect Balls Moving in the Euclidean Plane'',
Proc. of Computing: The Australasian Theory Symposium (CATS 2004), Electr. Notes Theor. Comput. Sci., vol.91, pp.229--245, Feb. 2004.
id=2003-51
A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, Rudy Raymond H.P., and S. Yamashita,
Quantum Identification of Boolean Oracles'',
Proc. the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), LNCS 2996, pp.105--116, Mar. 2004.

>> Abstract

## [ 国内発表 ]

id=2003-01

アイテムの入れ替えを許すオンラインナップザック問題について'',

>> Abstract
id=2003-06
Y. Hanatani, T. Horiyama, and K. Iwama,
Density Condensation of Boolean Formulas'',

>> Abstract
id=2003-13

近似を許したオンラインサーバ配置問題について'',

id=2003-14

3SATの計算時間の上限の改良について'',

id=2003-15

畳み込み機構を持つFPGAのマッピング能力について'',

id=2003-16

丸めを考慮した浮動小数点数の固定小数点数への自動変換について'',

id=2003-26
K. Iwama, Rudy Raymond H.P., and S. Yamashita,
Quantum Query Complexity of Biased Oracles'',

id=2003-27

近似を許したオンラインサーバ配置問題について'',

id=2003-28

論理式の解密度の濃縮'',

id=2003-29
A. Kawachi, and K. Iwama,
Randomized Load Balancing with Weak Two-Choice'',

id=2003-37

不正を検出できるネットワーク軍人将棋'',

id=2003-42

H-彩色可能なグラフのクラスの階層構造のCirculant graphs による細分化'',

id=2003-44
T. Imamura, and K. Iwama,
Approximating Vertex Cover on Dense Graphs'',

>> Abstract
id=2003-45
S. Masanishi, T. Horiyama, and K. Iwama,
Automated Competitive Analysis of Online Problems'',

>> Abstract
id=2003-48

安定結婚問題に対する局所探索近似アルゴリズム'',

id=2003-49

量子有限オートマトンの類似性判定アルゴリズム'',

id=2003-50

逆算法に基づく詰将棋の列挙'',

## [ 解説 ]

id=2003-46
K. Iwama,
Worst-case upper bounds for kSAT'',
EATCS Bulletin, no.82, pp.61--71, Feb. 2004.

## [ その他 ]

id=2003-12
K. Iwama, and S. Tamaki,
Improved Upper Bounds for 3-SAT'',
Electronic Colloquium on Computational Complexity, vol.10, no.53, Jul. 2003.

>> Abstract
id=2003-43
A. Kawachi, H. Kobayashi, T. Koshiba, and Rudy Raymond H.P.,
Universal Test for Quantum One-Way Permutations'',
arXiv.org e-Print archive, quant-ph/0401013, Jan. 2004.

>> Abstract
id=2003-52
A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, Rudy Raymond H.P., and S. Yamashita,
Quantum Identification of Boolean Oracles'',
arXiv.org e-Print archive, quant-ph/0403056, Mar. 2004.

>> Abstract
id=2003-53
A. Kawachi, H. Kobayashi, H. Nishimura, and T. Yamakami,
Computational Distinguishability between Quantum States: Random Coset States vs. Maximally Mixed States over the Symmetric Groups'',
arXiv.org e-Print archive, quant-ph/0403069, Mar. 2004.

## Abstract

id=2003-01

id=2003-03
The following problem is considered: Given a Boolean formula $f$, generate another formula $g$ such that: (i) If $f$ is unsatisfiable then $g$ is also unsatisfiable. (ii) If $f$ is satisfiable then $g$ is also satisfiable and furthermore $g$ is easier'' than $f$. For the measure of this easiness, we use the {\it density\/} of a formula $f$ which is defined as (the number of satisfying assignments) / $2^n$, where $n$ is the number of Boolean variables of $f$. In this paper, we mainly consider the case that the input formula $f$ is given as a 3-CNF formula and the output formula $g$ may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: One is to obtain $g$ by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. This is a preliminary report of the on-going research.
id=2003-04
We show that for all integers $n \ge 7$ and $\alpha$, such that $5 \le \alpha \le 2n-2$ and satisfying some coprimality conditions, there exists a minimum $n$-state nondeterministic finite automaton that is equivalent to a minimum deterministic finite automaton with exactly $2^n-\alpha$ states.
id=2003-06
The following problem is considered: Given a Boolean formula $f$, generate another formula $g$ such that: (i) If $f$ is unsatisfiable then $g$ is also unsatisfiable. (ii) If $f$ is satisfiable then $g$ is also satisfiable and furthermore $g$ is easier'' than $f$. For the measure of this easiness, we use the {\it density\/} of a formula $f$ which is defined as (the number of satisfying assignments) / $2^n$, where $n$ is the number of Boolean variables of $f$. In this paper, we mainly consider the case that the input formula $f$ is given as a 3-CNF formula and the output formula $g$ may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: One is to obtain $g$ by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. This is a preliminary report of the on-going research.
id=2003-07
Given a directed graph $G=(V,A)$ with a capacity function $c:A \to {\bf Z}_+$, two demand functions $d^-,d^+:V \to {\bf R}_+$, and a cost function $w:V \to {\bf R}_+$, we consider the problem of computing a minimum-cost set $S\subseteq V$ such that, for each vertex $v\in V-S$, the arc-connectivity from $S$ to $v$ is at least $d^-(v)$ and the arc-connectivity from $v$ to $S$ is at least $d^+(v)$. We present a polynomial time algorithm for the problem where $d^-$ and $d^+$ are uniformly fixed and $w$ is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform.
id=2003-08
It is known that the original Grover Search (GS) can be modified to use a general value for the phase $\theta$ of the diffusion transform. Then, if the number of answers is relatively large, this modified GS can find one of the answers with probability one in a single iteration. However, such a quick and error-free GS can only be possible if we can initially adjust the value of $\theta$ correctly against the number of answers, and this seems very hard in usual occasions. A natural question now arises: Can we enjoy a merit even if GS is used without such an adjustment? In this paper, we give a positive answer using the balls-and-bins game in which the random sampling of bins is replaced by the quantum sampling, i.e., a single round of modified GS. It is shown that by using the quantum sampling: (i) The maximum load can be improved quadratically for the static model of the game and this improvement is optimal. (ii) That is also improved to $O(1)$ for the continuous model if we have a certain knowledge about the total number of balls in the bins after the system becomes stable.
id=2003-09
While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. In this paper, we give a first nontrivial result for the approximation with factor less than two. Our randomized algorithm achieves a factor of $10/7$ for a restricted but still NP-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. Furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much.
id=2003-10
We consider a projection of a vertex-labeled graph or a hypergraph with n vertices onto a vertex-labeled convex polygon with n vertices such that each vertex of the (hyper)graph is projected on a vertex of the polygon with the same label. We compare graphs (resp., hypergraphs) by the sum of the length of the edges (resp., the areas of the hyperedges) on the projection and show some necessary and sufficient conditions, which are based on cuts or (hyper)graph modifications, for that the measure of a (hyper)graph is always less than the measure of another (hyper)graph for any convex polygon.
id=2003-12
This paper presents a new upper bound for the $k$-satisfiability problem. For small $k$'s, especially for $k=3$, there have been a lot of algorithms which run significantly faster than the trivial $2^n$ bound. The following list summarizes those algorithms where a constant $c$ means that the algorithm runs in time $O(c^n)$. Roughly speaking most algorithms are based on Davis-Putnam. [Sch99] is the first local search algorithm which gives a guaranteed performance for general instances and [DGH+02], [HSSW02] and [BS03] follow up this Sch"oning's approach. \begin{verbatim} 3-SAT | 4-SAT | 5-SAT | 6-SAT | type | ref. ------------------------------------------------- 1.782 | 1.835 | 1.867 | 1.888 | det. | [PPZ97] 1.618 | 1.839 | 1.928 | 1.966 | det. | [MS85] 1.588 | 1.682 | 1.742 | 1.782 | prob.| [PPZ97] 1.579 | - | - | - | det. | [Sch92] 1.505 | - | - | - | det. | [Kul99] 1.481 | 1.6 | 1.667 | 1.75 | det. | [DGH+02] 1.362 | 1.476 | 1.569 | 1.637 | prob.| [PPSZ98] 1.334 | 1.5 | 1.6 | 1.667 | prob.| [Sch99] 1.3302 | - | - | - | prob.| [HSSW02] 1.3290 | - | - | - | prob.| [BS03] 1.324 | 1.474 | - | - | prob.| [*] \end{verbatim} Our new bounds are denoted by [*] in the above list, namely we prove that for any satisfiable $n$-variable 3-CNF (4-CNF) formula $F$, there exists a randomized algorithm that finds a satisfying assignment of $F$ in expected running time $O(1.324^n)$ ($O(1.474^n)$). The basic idea is to combine two existing algorithms, the one by Paturi, Pudl'ak, Saks and Zane [PPSZ98] and the other by Sch"oning [Sch99]. It should be noted, however, that simply running the two algorithms independently does not seem to work. Also, our approach can escape one of the most complicated portions in the analysis of [PPSZ98]. In this paper we focus on the 3-SAT case; the 4-SAT case is very similar and may be omitted. The same approach does not improve the bounds for 5-SAT or more.
id=2003-17
We show that the number of satisfying assignments of a $k$-CNF formula is determined uniquely from the numbers of unsatisfying assignments for clause-sets of size up to $\lfloor \log k \rfloor + 2$. This amount of information is also shown to be necessary.
id=2003-18
This paper introduces a simple but nontrivial set of local transformation rules for designing Control-NOT(CNOT)-based combinatorial circuits. We also provide a proof that the rule set is complete, namely, for any two equivalent circuits, $S_1$ and $S_2$, there is a sequence of transformations, each of them in the rule set, which changes $S_1$ to $S_2$. Two applications of the rule set are also presented. One is to simulate Resolution with only polynomial overhead by the rule set. Therefore we can conclude that the rule set is reasonably powerful. The other is to reduce the cost of CNOT-based circuits by using the transformations in the rule set. This implies that the rule set might be used for the practical circuit design.
id=2003-19
For $k$ functions $f_1,...,f_k$, a $k$-tuple $(x_1,...,x_k)$ such that $f_1(x_1)=\cdots=f_k(x_k)$ is called a claw of $f_1,...,f_k$. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the number $M$ of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requires $O(N^{7/8}\log N)$ queries to find a claw, but our algorithm requires $O(N^{3/4}\log N)$ queries if $M\leq \sqrt{N}$ and $O(N^{7/12}M^{1/3}\log N)$ queries otherwise. Thus, our algorithm is more efficient if $M\leq N^{7/8}$.
id=2003-21
Given a directed graph $G=(V,A)$ with a capacity function $c:A \to {\bf Z}_+$, two demand functions $d^-,d^+:V \to {\bf R}_+$, and a cost function $w:V \to {\bf R}_+$, we consider the problem of computing a minimum-cost set $S\subseteq V$ such that, for each vertex $v\in V-S$, the arc-connectivity from $S$ to $v$ is at least $d^-(v)$ and the arc-connectivity from $v$ to $S$ is at least $d^+(v)$. We present a polynomial time algorithm for the problem where $d^-$ and $d^+$ are uniformly fixed and $w$ is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform.
id=2003-30
The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially a factor two approximation. In this paper, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of $2/(1+L^{-2})$ for instances in which only men have ties of length at most $L$. When both men and women are allowed to have ties, we show a ratio of $13/7$ ($< 1.858$) for the case when ties are of length two. We also improve the lower bound on the approximation ratio to $\frac{21}{19}$ ($> 1.1052$).
id=2003-31
We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants $\delta, \delta'$ such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of $\delta, \delta'$ (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.
id=2003-32
Cowen presented a universal compact routing algorithm with a stretch factor of three and a table-size of $O(n^{2/3} \log^{4/3} n)$, based on a simple and practical model. (The table-size is later improved to $O(\sqrt{n \log^3 n})$.) This stretch factor of three matches a general lower bound given and also matches a much tighter lower bound if we restrict the model to the Cowens. Thus it seems quite hard to improve the stretch factor. However, her analysis is of course for the worst case; the situation might differ if we assume some desirable property that average-case networks often possess. As such a property, we consider the notion of flatness in this paper and it is shown that the stretch factor can be significantly improved if the given network is almost flat. Our new algorithm achieves a stretch factor of $s < 3$ and a table size of $O(\sqrt{n\log n})$.
id=2003-33
We consider data sets that consist of $n$-dimensional binary vectors representing positive and negative examples for some (possibly unknown) phenomenon. A subset $S$ of the attributes (or variables) of such a data set is called a support set if the positive and negative examples can be distinguished by using only the attributes in $S$. In this paper we study the problem of finding small support sets, a frequently arising task in various fields, including knowledge discovery, data mining, learning theory, logical analysis of data, etc. We study the distribution of support sets in randomly generated data, and discuss why finding small support sets is important. We propose several measures of separation (real valued set functions over the subsets of attributes), formulate optimization models for finding the smallest subsets maximizing these measures, and devise efficient heuristic algorithms to solve these (typically NP-hard) optimization problems. We prove that several of the proposed heuristics have a guaranteed constant approximation ratio, and we report on computational experience comparing these heuristics with some others from the literature both on randomly generated and on real world data sets.
id=2003-35
Suppose that some particular link in the Internet is currently congested. Then a natural idea is to try to make packets bypass that link. This can be done by increasing the cost of that link intentionally, say from a1 to a2, since the Internet uses the shortest-path routing. Unfortunately, however, this often causes temporary loops for packet traveling, called routing loops. In this paper, we show that routing loops can be avoided by increasing the cost of the link not directly from a1 to a2 but through an intermediate value, a3, i.e., from a1 to a3 and then to a2. We may need several (more than one) intermediate values. We show that in this case, the greedy strategy, namely raising the cost as much as possible in each step, is optimal.
id=2003-36
In the hardware synthesis from a high-level language such as C, the bit length of variables is one of the key issues for the area and speed optimization. Usually, designers are required to optimize the bit-length of each variable manually using the time-consuming simulation on huge-data. In this paper, we propose an optimization method of the fractional bit length in the conversion from floating-point variables to fixed-point variables. The method is based on error propagation and the backward propagation of the accuracy limitation. The method is fully analytical and fast compared to simulation based methods.
id=2003-40
An {\it oracle} is given as a Boolean function of $n$ variables, denoted by $f(x_{0},\ldots,x_{n-1})$, and so there are $2^{2^{n}}$ (or $2^{N}$ for $N = 2^{n}$) different oracles. Note that $f$ is determined by $N$ $0/1$-values, $f(0,\ldots,0)$ through $f(1,\ldots,1)$. An oracle computation is, given an oracle $f$ we do not know in advance (or given $N$ $0/1$-values in the black-box), to determine which oracle $f$ is, through queries to $f$. Sometimes we do not have to completely identify $f$ but have only to decide whether $f$ satisfies some property or not. For example, the OR property means that at least one of the $N$ values of $f$ is 1. Our complexity measure is the so-called the {\it query complexity}, i.e., the number of oracle calls, to get a right answer with bounded error. Obviously we can solve the problem by querying all the $N$ values of $f$, i.e., by querying $f(0,...,0)$ through $f(1,...,1)$. In several occasions, however, we need a much less number of queries. In this paper, we are interested in the following two situations: One is the case that candidate oracles are explicitly given, namely, we determine which oracle $f$ is, under the assumption that it is in a set $S$ of $M$ Boolean oracles. ($M$ is usually much smaller than $2^{N}$.) We call this problem the oracle identification problem (OIP). The other is the case that the oracles does not always return correct answers, i.e., returns correct answers with probability $1/2 + \epsilon$. Such an oracle is said to be $\epsilon$-biased. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. However, little is known about general upper bounds for OIP. We present several bounds for OIP, which are quite general and mostly optimal: (i) The query complexity of OIP is $O(\sqrt{N\log M \log N}\log\log M)$ for {\it any} $S$ such that $M = |S| > N$, which is better than the obvious bound $N$ if $M < 2^{N/\log^{3}N}$. (ii) It is $O(\sqrt{N})$ for {\it any} $S$ if $|S| = N$, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles ($|S| = N$) such as random oracles and balanced oracles, the query complexity is $O(\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$. Query complexity for $\epsilon$-biased oracles are also known for some concrete problems such as Grover Search and Parity by H\o yer et al. and Buhrman et al., respectively. In this paper, we again give a rather general result. Namely, we slightly extend the quantum adversary argument (QAA) by Ambainis for $\epsilon$-biased oracles. In more detail, suppose that we can use the (conventional) QAA to prove an $\Omega(T)$ lower bound for an oracle computation problem $P$. Then we can use our new QAA for $\epsilon$-biased oracles to prove an $\Omega(T/\epsilon)$ bound for the same problem $P$.
id=2003-43
The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we relax their sufficient condition and give a new condition that is necessary and sufficient for quantum one-way permutations. Our condition can be regarded as a universal test for quantum one-way permutations, since our condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.
id=2003-44
Although many problems in MAX-SNP admit a PTAS for dense graphs, that is not the case for Vertex Cover, which is MAX-SNP hard even for dense graphs. This paper presents a randomized approximation algorithm for Vertex Cover on dense graphs which is probably optimal: Let $\ve=\avd/\Delta$ where $\avd$ and $\Delta$ are the average and maximum degrees of a given graph $G$. $G$ is said to be dense if its $\avd$ is $\Omega(n)$. (i)~Our algorithm achieves an approximation factor of $2 - \frac{\ve}{1+\ve/2}$ for dense graphs, which improves the best-known bound by Karpinski and Zelikovsky. (ii)~It achieves the same factor for a wider range of graphs, i.e., for the graphs whose $\Delta$ is $\Omega(n\frac{\log\log n}{\log n})$.
id=2003-45
An online knapsack problem is an online problem where an online player receives a sequence of items one by one and on every arrival of an item he must decide whether he takes it or not. In an exchangeable online knapsack problem (EOK), the player has two (or more) knapsacks of size 1, and he is allowed to exchange (and also discard) items in his knapsacks. It is known that the competitive ratio of this problem has an upper bound $1.3333$ and a lower bound $1.2808$ when the number of knapsack $k$ is $2$. Unfortunately, the tight bound is not known. The difficulty for obtaining those bounds is mainly caused by a large number of possible cases to be considered in their proofs. In this paper, we propose a computer aided analysis on the competitive ratios of online problems, and show proofs of the upper bounds $1.3660$ and $1.333$ for $2$-bin EOK. These results do not only give an another proof of the known bound, but also give a basis for the tight bound.
id=2003-51
The oracle identification problem (OIP) is, given a set $S$ of $M$ Boolean oracles out of $2^{N}$ ones, to determine which oracle in $S$ is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to $S$. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is $O(\sqrt{N\log M \log N}\log\log M)$ for {\it any} $S$ such that $M = |S| > N$, which is better than the obvious bound $N$ if $M < 2^{N/\log^{3}N}$. (ii) It is $O(\sqrt{N})$ for {\it any} $S$ if $|S| = N$, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles ($|S| = N$) such as random oracles and balanced oracles, the query complexity is $O(\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$.
id=2003-52
The oracle identification problem (OIP) is, given a set $S$ of $M$ Boolean oracles out of $2^{N}$ ones, to determine which oracle in $S$ is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to $S$. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is $O(\sqrt{N\log M \log N}\log\log M)$ for {\it any} $S$ such that $M = |S| > N$, which is better than the obvious bound $N$ if $M < 2^{N/\log^{3}N}$. (ii) It is $O(\sqrt{N})$ for {\it any} $S$ if $|S| = N$, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles ($|S| = N$) such as random oracles and balanced oracles, the query complexity is $O(\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$.