岩間研究室 発表論文
2003年度
[ 著書 ]
- 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 の構成とセキュリティ対策'',
- 電子情報通信学会論文誌, vol.J86-B, no.8, pp.1494--1501, 2003年 8月.
- 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
- 正西申悟, 岩間一雄,
- ``アイテムの入れ替えを許すオンラインナップザック問題について'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.103, no.31, COMP2003-1, pp.1--8, 2003年 4月.
-
-
>> Abstract
- id=2003-06
- Y. Hanatani, T. Horiyama, and K. Iwama,
- ``Density Condensation of Boolean Formulas'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, COMP2003-20, pp.29--34, Jun. 2003.
-
-
>> Abstract
- id=2003-13
- 藤原洋志, 米澤弘毅, 岩間一雄,
- ``近似を許したオンラインサーバ配置問題について'',
- 夏のLAシンポジウム, pp.19.1--19.6, 2003年 7月.
- id=2003-14
- 玉置卓, 岩間一雄,
- ``3SATの計算時間の上限の改良について'',
- 夏のLAシンポジウム, pp.29-1--29-3, 2003年 7月.
- id=2003-15
- 清水友樹, 木村晋二, 堀山貴史, 中西正樹, 柳澤政生,
- ``畳み込み機構を持つFPGAのマッピング能力について'',
- 情報処理学会 DA シンポジウム 2003 論文集, pp.31--36, 2003年 7月.
- id=2003-16
- 土井伸洋, 中西正樹, 堀山貴史, 木村晋二,
- ``丸めを考慮した浮動小数点数の固定小数点数への自動変換について'',
- 情報処理学会 DA シンポジウム 2003 論文集, 2003年 7月.
- id=2003-26
- K. Iwama, Rudy Raymond H.P., and S. Yamashita,
- ``Quantum Query Complexity of Biased Oracles'',
- 情報技術レターズ (情報科学技術フォーラム; FIT), LA-007, pp.17--18, Sep. 2003.
- id=2003-27
- 村井隆仁, 藤原洋志, 米澤弘毅, 岩間一雄,
- ``近似を許したオンラインサーバ配置問題について'',
- 情報技術レターズ (情報科学技術フォーラム; FIT), LA-010, pp.23--24, 2003年 9月.
- id=2003-28
- 花谷陽一, 堀山貴史, 岩間一雄,
- ``論理式の解密度の濃縮'',
- 情報科学技術フォーラム; FIT, A-061, pp.135--136, 2003年 9月.
- id=2003-29
- A. Kawachi, and K. Iwama,
- ``Randomized Load Balancing with Weak Two-Choice'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.103, no.326, COMP2003-40, pp.21--28, Sep. 2003.
- id=2003-37
- 加藤俊策, 宮崎修一, 岡部寿男,
- ``不正を検出できるネットワーク軍人将棋'',
- 電子情報通信学会 情報セキュリティ研究会, 信学技報, vol.103, no.499, ISEC2003-84, pp.1--6, 2003年 12月.
- id=2003-42
- 上嶋章宏, 伊藤大雄,
- ``H-彩色可能なグラフのクラスの階層構造のCirculant graphs による細分化'',
- 情報処理学会 アルゴリズム研究会, 情処研報, 2004-AL-93, pp.1--8, 2004年 1月.
- id=2003-44
- T. Imamura, and K. Iwama,
- ``Approximating Vertex Cover on Dense Graphs'',
- 冬のLAシンポジウム, pp.8.1--8.12, Feb. 2004.
-
-
>> Abstract
- id=2003-45
- S. Masanishi, T. Horiyama, and K. Iwama,
- ``Automated Competitive Analysis of Online Problems'',
- 冬のLAシンポジウム, pp.10.1--10.10, Feb. 2004.
-
-
>> Abstract
- id=2003-48
- 岡本和也, 宮崎修一, 岩間一雄,
- ``安定結婚問題に対する局所探索近似アルゴリズム'',
- 電子情報通信学会総合大会講演論文集, D-1-2, 2004年 3月.
- id=2003-49
- 小林浩二, 河内亮周, 小柴健史, 岩間一雄,
- ``量子有限オートマトンの類似性判定アルゴリズム'',
- 電子情報通信学会総合大会講演論文集, , pp., 2004年 3月.
- id=2003-50
- 中塚裕之, 堀山貴史, 岩間一雄,
- ``逆算法に基づく詰将棋の列挙'',
- 電子情報通信学会総合大会講演論文集, , pp., 2004年 3月.
[ 解説 ]
- 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
- 本稿では、岩間・武富によって導入された除去可能
オンラインナップザック問題の
$k$複数解モデルの制限を緩和した入れ替え可能$k$複数解モデルを考案する。
除去可能$k$複数解モデルは、通常では認められていない1度ナップザックに
入れたアイテムを捨てる事を許可している。さらに$k$個のナップザックを持ち
その中で最もコストが大きいナップザックを出力とする問題である。
$k \geq 2$の場合には、競合比の上下限が$1.3815$である事が示されている。
このモデルでは、1度ナップザックに入れたアイテムは他のナップザックに移す事が
認められていなかった。そこで本稿ではこれを認めたモデルを
入れ換え可能$k$複数解モデルとして定義し考察した。
主要結果として$k=2$の場合の競合比の上限が$1.3333$、下限が$1.2808$
である事を示す。
また、入れ替えが許されないモデルでは、$k \geq 2$の場合に競合比が
変化しないが、入れ替えを許すと、$k$と共に競合比は
いくらでも改善出来ることを示す。
-
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$.