This paper deals with graph colouring games, an example of pseudo-telepathy, in which two players can convince a verifier that a graph G is c-colourable where c is less than the chromatic number of the graph. They win the game if they convince the verifier. It is known that the players cannot win if they share only classical information, but they can win in some cases by sharing entanglement. The smallest known graph where the players win in the quantum setting, but not in the classical setting, was found by Galliard, Tapp and Wolf and has 32,768 vertices. It is a connected component of the Hadamard graph GN with N=c=16. Their protocol applies only to Hadamard graphs where N is a power of 2. We propose a protocol that applies to all Hadamard graphs. Combined with a result of Frankl, this shows that the players can win on any induced subgraph of G12 having 1609 vertices, with c=12. Moreover combined with a result of Godsil and Newman, our result shows that all Hadamard graphs GN (N ≥ 12) and c=N yield pseudo-telepathy games.

Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method [2]. Computational experiments show that our method quickly generates feasible solutions close to optimal.

This paper presents a design method of multi-stage, multi-way microstrip power dividers with the aim of constructing a compact low-loss power divider with numbers of outputs. First, an integration design technique of power dividers composed of multi-step, multi-furcation and mitered bends is described. Since the analytical technique is founded on the planar circuit approach combined with the segmentation method, the optimization of the circuit patterns can be performed in a reasonable short computation time. Next, the present method is applied to the design of broadband Nn-way power dividers such as 32-way power divider consisting of 3-way dividers in two-stage structures, respectively. In addition, a 12-way power divider constructed from a series connection of a 3-way and three 4-way dividers is designed. The dividers equivalently contain a 3-section Chebyshev transformer to realize broadband properties. As a result, the fractional bandwidths of nearly 85% and 66.7% for the power-split imbalance less than 0.2 dB and the return loss better than -20 dB are obtained for the 9- and 12-way power dividers, respectively. The validity of these design results is confirmed by a commercial em-simulator (Ansoft HFSS) and experiments.

In this paper, we study the feedback vertex set problem for trivalent Cayley graphs, and construct a minimum feedback vertex set in trivalent Cayley graphs using the result on cube-connected cycles and the Cayley graph representation of trivalent Cayley graphs.

Magnetoencephalography (MEG) is a method to measure a magnetic field generated by electrical neural activity in a brain, and it plays increasingly important role in clinical diagnoses and neurophysiological studies. However, in MEG analysis, the estimation of the brain activity, of the electric current density distribution in a brain which is represented by current dipoles, is problematic. A spatial filter and subsequent reconstruction of the current density distribution estimated by the spatial filter (spatial filtered reconstruction: SFR) are proposed. The spatial filter is designed to be used without prior or temporal information. The proposed spatial filter ensures that it concentrates the current distribution around the activated sources in the conductor. The current distribution estimated by the spatial filter is reconstructed by multiple linear regression. Redundant current dipoles are eliminated, and the current distribution is optimized in the sense of the Mallows Cp statistic. Numerical studies are demonstrated and show successful estimation by SFR in multiple-dipole cases. In single-dipole cases with SNRs of 101 and more, the location of the true dipole was successfully estimated for about 80% of the simulations. The reconstruction with multiple linear regression corrected the location of the maximum current density estimated by the proposed spatial filtering. The dipole on the correct position contributes to more than 70% of the total dipoles in the estimated current distribution in those cases. These results show that the current distribution is effectively localized by SFR. We also investigate the differences among SFR, the LCMV (linearly constrained minimum variance) beamformer and the SAM (synthetic aperture magnetometry), the representatives of spatial filters in MEG analyses. It is indicated that spatial resolution is improved by avoiding dependence on temporal information.

The performance of the vehicular communication links used for Intelligent Transport Systems is investigated. Intervehicle communication (IVC) and combined vehicular communication implemented by IVC and additional communication media are studied and their performance is explicitly described. Through numerical studies, it is shown that performance varies according to parameter values such as the mean space headway, the speed of the vehicles, and the penetration ratio of the IVC device. To achieve a given level of performance, I propose (i) a design of the information delivery delay of additional communication media and (ii) a method determining the appropriate delay.

A novel blind channel estimation scheme is proposed for OFDM systems employing PSK modulation. This scheme minimizes the number of possible channels by exploiting the constant modulus property, chooses a best fit over the possible channels by exploiting the finite alphabet property of information signals, and achieves competitive performance with low computational complexity. Results comparing the new scheme with the finite-alphabet based channel estimation are presented.

This paper investigates the accepting powers of two-way alternating Turing machines (2ATM's) with only existential (universal) states which have inkdots and sublogarithmic space. It is shown that for sublogarithmic space-bounded computations, (i) multi-inkdot 2ATM's with only existential states and the ones with only universal states are incomparable, (ii) k-inkdot 2ATM's are better than k-inkdot 2ATM's with only existential (universal) states, k ≥ 0, and (iii) the class of sets accepted by multi-inkdot 2ATM's with only existential (universal) states is not closed under complementation.

Group signature schemes with membership revocation have been intensively researched. However, signing and/or verification of some existing schemes have computational costs of O(R), where R is the number of revoked members. Existing schemes using a dynamic accumulator or a similar technique have efficient signing and verifications with O(1) complexity. However, before signing, the signer has to modify his secret key with O(N) or O(R) complexity, where N is the group size. Therefore, for larger groups, signers suffer from enormous costs. On the other hand, an efficient scheme for middle-scale groups with about 1,000 members is previously proposed, where the signer need not modify his secret key. However this scheme also suffers from heavy signing/verification costs for larger groups with more than 10,000 members. In this paper, we adapt the middle-scale scheme to larger groups ranging from 1,000 to 1,000,000 members. At the sacrifice of the group manager's slight cost, our signing/verification is sufficiently efficient.

In this paper, we propose a multicast protocol, called BAM (Branch Aggregation Multicast), for wireless sensor networks. The main contribution of BAM is a reduction in the radio communication load, which is a key determinant of sensor energy consumption. BAM does not use any control packets such as join/leave messages and does not manage multicast groups. BAM is highly compatible with existing wireless sensor protocols, such as routing protocols, MAC protocols, and other kinds of energy efficient protocols. BAM implementation is quite simple and BAM works on various networks even if some sensors are not BAM-capable. BAM is composed of two aggregation techniques. One is single hop aggregation (S-BAM) and the other is multiple paths aggregation (M-BAM). S-BAM aggregates radio transmission within a single hop and enables single transmission to multiple intended receivers. M-BAM aggregates multiple paths into fewer ones and limits the range of radio transmission. S-BAM is designed to reduce redundant communication at every branch while M-BAM is designed to reduce the number of branches. SM-BAM, the combination of S-BAM and M-BAM, can reduce the radio communication load thus enabling energy efficient multicast communication. We evaluate BAM in three ways, qualitative evaluation by theoretical analysis, quantitative evaluation through computer simulations, and experiments using CrossBow's MICA2. Our results show that BAM is a very energy efficient multicast protocol that well supports wireless sensor networks.

The average performance of a single-user MIMO system under spatially correlated fading and with different types of CSI at the transmitter and with perfect CSI at the receiver was studied in recent work. In contrast to analyzing a single performance metric, e.g. the average mutual information or the average bit error rate, we study an arbitrary representative of the class of matrix-monotone functions. Since the average mutual information as well as the average normalized MSE belong to that class, this universal class of performance functions brings together the information theoretic and signal processing performance metric. We use Lowner's representation of operator monotone functions in order to derive the optimum transmission strategies as well as to characterize the impact of correlation on the average performance. Many recent results derived for average mutual information generalize to arbitrary matrix-monotone performance functions, e.g. the optimal transmit strategy without CSI at the transmitter is equal power allocation. The average performance without CSI is a Schur-concave function with respect to transmit and receive correlation. In addition to this, we derive the optimal transmission strategy with long-term statistics knowledge at the transmitter and propose an efficient iterative algorithm. The beamforming-range is the SNR range in which only one data stream spatially multiplexed achieves the maximum average performance. This range is important since it has a simple receiver structure and well known channel coding. We entirely characterize the beamforming-range. Finally, we derive the generalized water-filling transmit strategy for perfect CSI and characterize its properties under channel correlation.

The aim of this research is the efficient cryptanalysis of the Shrinking Generator through its characterization by means of Linear Hybrid Cellular Automata. This paper describes a new known-plaintext attack based on the computation of the characteristic polynomials of sub-automata and on the generation of the Galois field associated to one of the Linear Feedback Shift Registers components of the generator. The proposed algorithm allows predicting with absolute certainty, many unseen bits of the keystream sequence, thanks to the knowledge of both registers lengths, the characteristic polynomial of one of the registers, and the interception of a variable number of keystream bits.

In STS-based mapping, it is necessary to obtain the correct order of probes in a DNA sequence from a given set of fragments or an equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has a consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order uniquely determines the correct order of the probes. Unfortunately this does not hold if the data include errors, and this has been a popular research target in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens because of the lack of some information regarding the data, but almost no further investigation has previously been made. In this paper, we define a measure of such imperfectness of the data as the minimum amount of the additional fragments that are needed to uniquely fix the probe order. Polynomial-time algorithms to compute such additional fragments of the minimum cost are presented. A computer simulation using genes of human chromosome 20 is also noted.

We propose a new analysis technique against a class of countermeasure using randomized binary signed digit (BSD) representations. We also introduce some invariant properties between BSD representations. The proposed analysis technique can directly recover the secret key from power measurements without information for algorithm because of the invariant properties of BSD representation. Thus the proposed attack is applicable to all countermeasures using BSD representations. Finally, we give the simulation results against some countermeasures using BSD representation such as Ha-Moon method, Ebeid-Hasan method, and the method of Agagliate et al. The results show that the proposed attack is practical analysis method.

In this paper, a method is proposed to construct a visual secret sharing (VSS) scheme for multiple secret images in which each share can be rotated with 180 degrees in decryption. The proposed VSS scheme can encrypt more number of secret images compared with the normal VSS schemes. Furthermore, the proposed technique can be applied to the VSS scheme that allows to turn over some shares in decryption. From the theoretical point of view, it is interesting to note that such VSS schemes cannot be obtained from so-called basis matrices straightforwardly.

In this letter, we present timing synchronization method using two consecutive orthogonal frequency division multiplexing (OFDM) symbols which are designed to be cyclic-shifted against each other. Our approach can be viewed as an expansion of Minn's correlation methods. Using the proposed OFDM signal, however, we can estimate the timing offset without any training symbol.

For the measurement of the 3D surface of micro-solderballs in IC (Integrated Circuit) manufacturing inspection, a binary grating project lenses of high MTF (Modulation Transfer Function) with tilted project plane is designed in this paper. Using a combination of lenses and a tilted optical layout both on object and image plane, the wave-front aberrations are reduced and the nonlinear image distortion is corrected with nonlinearity compensation, This optical lens allows us to project the structured light pattern to the inspected objects efficiently for clear deformed coded imaging, it could be used to online measure 3D shape of micro-solderballs with high precision and accuracy.

HfOxNy thin films formed by the electron cyclotron resonance (ECR) Ar/N2 plasma nitridation of HfO2 films were investigated for high-k gate insulator applications. HfOxNy thin films formed by the ECR Ar/N2 plasma nitridation (60 s) of 1.5-nm-thick HfO2 films, which were deposited on chemically oxidized Si(100) substrates, were found to be effective for suppressing interfacial layer growth or crystallization during postdeposition annealing (PDA) in N2 ambient. After 900 PDA of for 5 min in N2 ambient, it was found that HfSiON film with a relatively high dielectric constant was formed on the HfOxNy/Si interface by Si diffusion. An equivalent oxide thickness (EOT) of 2.0 nm and a leakage current density of 1.010-3 A/cm2 (at VFB-1 V) were obtained. The effective mobility of the fabricated p-channel metal-insulator-semiconductor field-effect transistor (MISFET) with the HfOxNy gate insulator was 50 cm2/Vs, and the gate leakage current of the MISFET with the HfOxNy gate insulator was found to be well suppressed compared with the MISFET with the HfO2 gate insulator after 900 PDA because of the nitridation of HfO2.

This paper deals with the diffraction of TM plane wave by a perfectly conductive periodic surface. Applying the Rayleigh hypothesis, a linear equation system determining the diffraction amplitudes is derived. The linear equation is formally solved by Cramer's formula. It is then found that, when the angle of incidence becomes a low grazing limit, the amplitude of the specular reflection becomes -1 and any other diffraction amplitudes vanish for any perfectly conductive periodic surfaces with small roughness and gentle slope.

A design of non-orthogonal 33 space-time block code (STBC) is proposed. The proposed design achieves full rate, full level diversity, and maximum coding gain by symbol rotation (SR) method. In addition, the proposed scheme has lower encoding complexity than the unitary constellation-rotation (CR) STBC, while two methods exhibit the same bit error rate (BER) performance in Rayleigh fading channel.