岩間研究室 発表論文

2012年度

[ 論文誌 ]

id=2012-07
K. Iwama, S. Miyazaki, and H. Yanagisawa,
``Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects'',
vol.vol.13, pp.pp.59--66, May 2012.
 
>> Abstract
id=20012-09
K. Ueno,
``A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints'',
Theoretical Computer Science, vol.vol.434, pp.pp.87--97, May 2012.
 
>> Abstract
id=2012-11
G. Ivanyos, F. Le Gall, and Y. Yoshida,
``On the distance between non-isomorphic groups'',
European Journal of Combinatorics, vol.33, no.4, pp.474--476, May 2012.
 
>> Abstract
id=2012-12
Y. Yoshida, and K. Kobayashi,
``Testing (s,t)-Disconnectivity of Graphs and Digraphs'',
Theoretical Computer Science, vol.434, , pp.98-113, May 2012.

[ 国際会議 ]

id=2012-01
M. Kusumoto, Y. Yoshida, and H. Ito,
``Constant-Time Approximation Algorithms for the Optimum Branching'',
Proc. 5th Asian Association for Algorithms and Computation (AAAC 2012), pp.?, Apr. 2012.
id=2012-02
R. Cleve, K. Iwama, F. Le Gall, H. Nishimura, S. Tani, J. Teruyama, and S. Yamashita,
``Improved Quantum Algorithms for Reconstructing Strings from Substrings'',
Proc. 5th Asian Association for Algorithms and Computation (AAAC 2012), pp.3, Apr. 2012.
id=2012-03
H. Ito, S. Kiyoshima, and Y. Yoshida,
``Constant-Time Approximation Algorithms for the Knapsack Problem'',
Proc. 9th Annual Conference on Theory and Applications of Models of Computation (TAMC 2012), pp.131--142, May 2012.
 
>> Abstract
id=2012-04
Y. Yoshida,
``Testing List H-Homomorphisms'',
Proc. 27th IEEE Conference on Computational Complexity (CCC 2012), pp.85-95, Jun. 2012.
 
>> Abstract
id=2012-05
K. Seto, and S. Tamaki,
``A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis'',
Proc. 27th IEEE Conference on Computational Complexity (CCC 2012), pp.pp107--116, Jun. 2012.
 
>> Abstract
id=2012-06
H. Ito, S. Langerman, and Y. Yoshida,
``Algorithms and Complexity of Generalized River Crossing Problems'',
Proc. 6th International Conference on Fun with Algorithms (FUN 2012), pp.235-244, Jun. 2012.
 
>> Abstract
id=2012-08
S. Tamaki, and Y. Yoshida,
``Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues.'',
Proc. The 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), LNCS 7408, pp.pp.313--324, Aug. 2012.
 
>> Abstract

[ 国内発表 ]

id=2012-10
K. Ueno,
``Candidate Boolean Functions towards Super-Quadratic Formula Size'',
電子情報通信学会 コンピューテーション研究会, 信学技報, vol.vol.112, no.93, COMP2012-18, pp.pp.49--55, 2012年 6月.
 
>> Abstract

Abstract

id=2012-03
id=2012-04
id=2012-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 get strong average-case hardness of affine extractors for linear-sized formulas over the full binary basis.
id=2012-06
id=2012-07
Manlove and O'Malley proposed the Student-Project Allocation Problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of $21/19 (>1.1052)$.
id=2012-08
Given an undirected graph $G=(V,E)$ and positive edge weights $\{w_e\}_{e \in E}$, a \textit{linear arrangement} is a permutation $\pi: V \to [n]$. The value of the arrangement is $\val(G,\pi):= \frac{1}{n}\sum_{e=\{u,v\}}w_e |\pi(u)-\pi(v)|$. In the \textit{minimum linear arrangement problem} (MLA), the goal is to find a linear arrangement $\pi^*$ that achieves $\val(G,\pi^*)=\MLA(G):=\min_{\pi}{\val(G,\pi)}$. In this paper, we show that for any $\epsilon >0$ and positive integer $r$, there is an $O(n^{r/\epsilon})$-time randomized algorithm which, given a graph $G$, returns a permutation $\pi$ such that \[ \val(G,\pi) \leq \left(1+\frac{2+\epsilon}{\lambda_{r+1}(\caL)}\right)\MLA(G) + O\left(\frac{\log n}{\sqrt{n}}\sum_{e \in E}w_e\right) \] with high probability. Here $\caL$ is the normalized Laplacian of $G$ and $\lambda_r(\caL)$ is the $r$-th eigenvalue of $\caL$. Our algorithm gives a constant factor approximation for regular graphs that are weak expanders.
id=20012-09
We introduce a new technique proving formula size lower bounds based on the linear programming bound originally introduced by Karchmer, Kushilevitz and Nisan and the theory of stable set polytopes. We apply it to majority functions and prove their formula size lower bounds improved from the classical result of Khrapchenko. Moreover, we introduce a notion of unbalanced recursive ternary majority functions motivated by a decomposition theory of monotone self-dual functions and give matching upper and lower bounds of their formula size. We also show monotone formula size lower bounds of balanced recursive ternary majority functions improved from the quantum adversary bound of Laplante, Lee and Szegedy.
id=2012-10
In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss candidate recursive Boolean functions which have possibilities to prove super-quadratic formula size lower bounds based on the exact 2-bit Boolean function. We show that its formula complexity is at least $\Omega(n^2)$. Next, we observe the reason of difficulty of resolving formula complexity of the majority function in contrast with the parity function in terms of structure of an optimal protocol partition for the Karchmer-Wigderson communication game.
id=2012-11
A result of Ben-Or, Coppersmith, Luby and Rubinfeld on testing whether a map between two groups is close to a homomorphism implies a tight lower bound on the distance between the multiplication tables of two non-isomorphic groups.