岩間研究室 発表論文
2013年度
[ 論文誌 ]
- id=2013-01
- F. Le Gall, and Y. Yoshida,
- ``Property Testing for Cyclic Groups and Beyond'',
-
Journal of Combinatorial Optimization, vol.26, no.4, pp.636--654, Nov. 2013.
- id=2013-02
- S. Tamaki, and Y. Yoshida,
- ``A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness'',
-
Random Structures and Algorithms, vol., , pp., (発表月不明) To appear.
-
-
>> Abstract
- id=2013-03
- K. Makino, and S. Tamaki,
- ``Derandomizing HSSW algorithm for 3-SAT'',
-
Algorithmica, vol.67, no.2, pp.112--124, Oct. 2013.
-
-
>> Abstract
- id=2013-04
- K. Seto, and S. Tamaki,
- ``A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis'',
-
Computational Complexity, vol.22, no.2, pp.245--274, May 2013.
- id=2013-13
- Takao Inoshita, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Takashi Nagase,
- ``Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists'',
-
MDPI Algorithms, vol.6, no.2, pp.371--382, May 2013.
-
-
>> Abstract
- id=2013-15
- K. Iwama, S. Miyazaki, and H. Yanagisawa,
- ``A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties'',
-
Algorithmica, vol.68, no.3, pp.758--775, Mar. 2014.
- id=2013-16
- K.Fujii, and T. Morimae,
- ``Blind quantum computation protocol in which Alice only makes measurements'',
-
Physical Review A, vol.87, no.5, pp., May 2013.
-
-
>> Abstract
- id=2013-17
- K. Fujii, and T. Morimae,
- ``Secure entanglement distillation for double-server blind quantum computation'',
-
Physical Review letters, vol.111, no.2, pp., Jul. 2013.
-
-
>> Abstract
- id=2013-18
- K. Fujii,
- ``Quantum Information and Statistical Mechanics: An Introduction to Frontier.'',
-
Interdisciplinary Information Sciences, vol.19, no.1, pp.1--15, Aug. 2013.
-
-
>> Abstract
- id=2013-21
- N. Bansal, X. Han, K. Iwama, M. Sviridenko, and G. Zhang,
- ``A Harmonic Algorithm for the 3D Strip Packing Problem.'',
-
SIAM Journal on Computing, vol.42, no.2, pp.579--592, Nov. 2013.
-
-
>> Abstract
- id=2013-22
- K. Iwama, and H. Nishimura,
- ``Recovering Strings in Oracles: Quantum and Classic.'',
-
International Journal of Foundations of Computer Science, vol.24, no.7, pp.979--994, Nov. 2013.
-
-
>> Abstract
[ 国際会議 ]
- id=2013-05
- T. Sakai, K. Seto, and S. Tamaki,
- ``Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction'',
-
The 17th International Conference on Theory and Applications of Satisfiability Testing (SAT), pp.to appear, Jul. 2014.
-
-
>> Abstract
- id=2013-06
- T. Sakai, K. Seto, and S. Tamaki,
- ``Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction'',
-
The 7th AAAC Annual Meeting Proc. of AAAC 2014, pp.to appear, May 2014.
-
-
>> Abstract
- id=2013-07
- S. Tamaki,
- ``The complexity of robust satisfiability of the constraint satisfaction problem'',
-
Proc. 6th Asian Association for Algorithms and Computation (AAAC), pp., Apr. 2013.
- id=2013-12
- Takao Inoshita, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Takashi Nagase,
- ``Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists'',
-
Proc. 6th Asian Association for Algorithms and Computation (AAAC), pp., Apr. 2013.
- id=2013-14
- Minseon Lee, Shuichi Miyazaki, Kazuo Iwama,
- ``Finding Witnesses for Stability in the Hospitals/Residents Problem'',
- 平成25年度情報処理学会関西支部支部大会 B-02, pp., 2013年 9月.
- id=2013-19
- Jing Chen, He Guo, Xin Han, and Kazuo Iwama,
- ``The Train Delivery Problem Revisited'',
-
Algorithms and Computation (ISAAC 2013), pp.601--611, Dec. 2013.
- id=2013-20
- Jing Chen, Xin Han, and Kazuo Iwama,
- ``Online Bin Packing with (1, 1) and (2, R) Bins'',
-
Combinatorial Optimization and Applications (COCOA 2013), pp.387--401, Dec. 2013.
- id=2013-23
- K. Iwama, and A. Nagao,
- ``Read-Once Branching Programs for Tree Evaluation Problems.'',
-
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp.409--420, Mar. 2014.
-
-
>> Abstract
- id=2013-24
- K. Iwama, and Y. Yoshida,
- ``>Parameterized testability.'',
-
Innovations in Theoretical Computer Science (ITCS 14), pp.507-516, Feb. 2014.
-
-
>> Abstract
- id=2013-25
- A. Nagao, K. Seto, and J. Teruyama,
- ``>Efficient Algorithms for Sorting k-Sets in Bins.'',
-
Algorithms and Computation - 8th International Workshop (WALCOM 2014), pp.225--236, Feb. 2014.
-
-
>> Abstract
[ 国内発表 ]
- id=2013-08
- 玉置 卓,
- ``計算複雑さへの招待 (4): 計算限界証明における障壁'',
- 電子情報通信学会コンピュテーション研究会, pp., 2013年 10月.
- id=2013-09
- 酒井 隆行, 脊戸 和寿, 玉置 卓,
- ``最大充足可能性問題の疎な例題に対する厳密アルゴリズム'',
- 電子情報通信学会 総合大会 DS-1-5, pp., 2014年 3月.
- id=2013-10
- 酒井 隆行, 脊戸 和寿, 玉置 卓,
- ``最大充足可能性問題の疎な例題に対する厳密アルゴリズム'',
- 2013年夏のLAシンポジウム, pp., 2013年 7月.
[ 解説 ]
- id=2013-11
- 玉置 卓,
- ``メタアルゴリズムと計算限界証明の不思議な関係'',
- 電子情報通信学会誌, vol.96, no.9, pp.679-682, 2013年 9月.
Abstract
-
id=2013-02
- Long Code testing is a fundamental problem in the area of property
testing and hardness of approximation.
In this paper,
we study how small the soundness $s$ of the Long Code test with perfect
completeness can be by using non-adaptive $q$ queries.
We show that $s=(2q+3)/2^q$ is possible, where $q$ is of the form
$2^k-1$ for any integer $k>2$.
-
id=2013-03
- We present a (full) derandomization of HSSW algorithm for 3-SAT,
proposed by Hofmeister, Schoning, Schuler, and Watanabe (in STACS 2002,
pp. 192–202, 2002). Thereby, we obtain an $O(1.3303^n)$ time deterministic algorithm
for 3-SAT, which is currently fastest.
-
id=2013-05
- We present a moderately exponential time algorithm for the
satisfiability of Boolean formulas over the full binary basis.
For formulas of size at most $cn$, our algorithm runs in time
$2^{(1-\mu_c)n}$ for some constant $\mu_c>0$.
As a byproduct of the running time analysis of our algorithm,
we obtain strong average-case hardness of affine extractors for
linear-sized formulas over the full binary basis.
-
id=2013-06
- We present a moderately exponential time polynomial space algorithm
for sparse instances of Max SAT.
Our algorithms run in time of the form $O(2^{(1-\mu(c))n})$ for
instances with $n$ variables and $cn$ clauses.
Our deterministic and randomized algorithm achieve $\mu(c) =
\Omega(\frac{1}{c^2\log^2 c})$ and $\mu(c) = \Omega(\frac{1}{c \log^3
c})$ respectively.
Previously, an exponential space deterministic algorithm with $\mu(c)
= \Omega(\frac{1}{c\log c})$ was shown by Dantsin and Wolpert [SAT
2006]
and a polynomial space deterministic algorithm with $\mu(c) =
\Omega(\frac{1}{2^{O(c)}})$ was shown by Kulikov and Kutzkov [CSR
2007].
Our algorithms have three new features.
They can handle instances with (1) weights and (2) hard constraints,
and also (3) they can solve counting versions of Max SAT.
Our deterministic algorithm is based on the combination of two
techniques, width reduction of Schuler and greedy restriction of
Santhanam.
Our randomized algorithm uses random restriction instead of greedy restriction.
-
id=2013-13
- In the stable marriage problem, any instance admits the
so-called {\em man-optimal stable matching}, in which every man is
assigned the best possible partner. However, there are instances for
which all men receive low-ranked partners even in the man-optimal stable
matching. In this paper we consider the problem of improving the
man-optimal stable matching by changing only one man's preference list.
We show that the optimization variant and the decision variant of this
problem can be solved in time $O(n^{3})$ and $O(n^{2})$, respectively,
where $n$ is the number of men (women) in an input. We further extend
the problem so that we are allowed to change $k$ men's preference lists.
We show that the problem is W[1]-hard with respect to the parameter $k$,
and give $O(n^{2k+1})$-time and $O(n^{k+1})$-time exact algorithms for
the optimization and decision variants, respectively. Finally, we show
that the problems become easy when $k=n$; we give $O(n^{2.5}\log
n)$-time and $O(n^{2})$-time algorithms for the optimization and
decision variants, respectively.
-
id=2013-16
- Blind quantum computation is a new secure quantum computing protocol
which enables Alice (who does not have sufficient quantum technology)
to delegate her quantum computation to Bob (who has a full-fledged quantum computer)
in such a way that Bob cannot learn anything about Alice's input, output, and algorithm.
In previous protocols, Alice needs to have a device which generates quantum states,
such as single-photon states. Here we propose another type of blind computing protocol
where Alice does only measurements, such as the polarization measurements with a threshold detector.
In several experimental setups, such as optical systems, the measurement of a state is much easier than
the generation of a single-qubit state. Therefore our protocols ease Alice's burden.
Furthermore, the security of our protocol is based on the no-signaling principle,
which is more fundamental than quantum physics. Finally, our protocols are device independent
in the sense that Alice does not need to trust her measurement device in order to guarantee the security.
-
id=2013-17
- Blind quantum computation is a new secure quantum computing protocol where a client,
who does not have enough quantum technologies at her disposal,
can delegate her quantum computation to a server, who has a fully-fledged quantum computer,
in such a way that the server cannot learn anything about client's input, output, and program.
If the client interacts with only a single server, the client has to have some minimum quantum power,
such as the ability of emitting randomly rotated single-qubit states or the ability of measuring states.
If the client interacts with two servers who share Bell pairs but cannot communicate with each other,
the client can be completely classical. For such a double-server scheme,
two servers have to share clean Bell pairs, and therefore the entanglement distillation is necessary
in a realistic noisy environment. In this paper,
we show that it is possible to perform entanglement distillation in the double-server scheme
without degrading the security of the blind quantum computing.
-
id=2013-18
- This is a short review on an interdisciplinary field of quantum information science and
statistical mechanics. We first give a pedagogical introduction to the stabilizer formalism,
which is an efficient way to describe an important class of quantum states,
the so-called stabilizer states, and quantum operations on them. Furthermore, graph states,
which are a class of stabilizer states associated with graphs, and their applications
for measurement-based quantum computation are also mentioned. Based on the stabilizer formalism,
we review two interdisciplinary topics.
One is the relation between quantum error correction codes and spin glass models,
which allows us to analyze the performances of quantum error correction codes
by using the knowledge about phases in statistical models.
The other is the relation between the stabilizer formalism and partition functions of classical spin models,
which provides new quantum and classical algorithms to evaluate partition functions of classical spin models.
-
id=2013-21
- In the three-dimensional (3D) strip packing problem,
we are given a set of 3D rectangular items and a 3D box $B$.
The goal is to pack all the items in $B$ such that the height of the packing is minimized.
We consider the most basic version of the problem,
where the items must be packed with their edges parallel to the edges of $B$ and cannot be rotated.
Building upon Caprara's work for the two-dimensional (2D) bin packing problem,
we obtain an algorithm that, given any $\epsilon>0$,
achieves an approximation of $T_{\infty}+\epsilon\approx1.69103+\epsilon$,
where $T_{\infty}$ is the well-known number that occurs naturally in the context of bin packing.
Our key idea is to establish a connection between bin packing solutions
for an arbitrary instance $I$ and the strip packing solutions
for the corresponding instance obtained from $I$ by applying the harmonic transformation to certain dimensions.
Based on this connection,
we also give a simple alternate proof of the $T_{\infty}+\epsilon$ approximation for 2D bin packing due to Caprara.
In particular, we show how his result follows from a simple modification of the asymptotic approximation scheme
for 2D strip packing due to Kenyon and Rémila.
-
id=2013-22
-
-
id=2013-23
- Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman and Santhanam
introduced the tree evaluation problem (TEP). For fixed $h$, $k>0$, $FT_h(k)$ is given as a complete,
rooted binary tree of height h, in which each internal node is associated with a function from $[k]^2$ to $[k]$,
and each leaf node with a number in $[k]$. The value of an internal node $v$ is defined naturally, i.e.,
if it has a function $f$ and the values of its two child nodes are $a$ and $b$, then the value of $v$ is $f(a,b)$.
Our task is to compute the value of the root node by sequentially executing this function evaluation
in a bottom-up fashion. The problem is obviously in P and if we could prove that any branching program solving
$FT_h(k)$ needs at least $k^(r(h))$ states for any unbounded function $r$, then this problem is not in L,
thus achieving our goal. The above authors introduced a restriction called thrifty
against the structure of BP’s (i,e., against the algorithm for solving the problem) and proved
that any thrifty BP needs $\Omega(k^h)$ states.
This paper proves a similar lower bound for read-once branching programs,
which allows us to get rid of the restriction on the order of nodes read by the BP
that is the nature of the thrifty restriction.
-
id=2013-24
-
-
id=2013-25
-