A queue layout of a graph G consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G1 = (V1,E1) and G2 = (V2,E2), denoted by G1 × G2, is the graph with {:v1 ∈ V1 and v2 ∈ V2} as its vertex set and an edge (,) belongs to G1×G2 if and only if either (u1,v1) ∈ E1 and u2 = v2 or (u2,v2) ∈ E2 and u1 = v1. Let Tk1,k2,...,kn denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., Tk1,k2,...,kn = Ck1 × Ck2 × … × Ckn, where Cki is a cycle of length ki ≥ 3. If k1 = k2 = … = kn = k, the graph is also called the k-ary n-cube and is denoted by Qnk. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(Tk1,k2,...,kn) ≤ 2n-2 if n ≥ 2 and ki ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k1,k2 ≥ 3, we acquire qn(Tk1,k2) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Qnk) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Qnk) when n ≥2 and k ≥9.

Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.

Face recognition plays an important role in security applications, but in real-world conditions face images are typically subject to issues that compromise recognition performance, such as geometric transformations, occlusions and changes in illumination. Most face detection and recognition works to date deal with single face images using global features and supervised learning. Differently from that context, here we propose a multiple face recognition approach based on local features which does not rely on supervised learning. In order to deal with multiple face images under varying conditions, the extraction of invariant and discriminative local features is achieved by using the SURF (Speeded-Up Robust Features) approach, and the search for regions from which optimal features can be extracted is done by an improved ABC (Artificial Bee Colony) algorithm. Thresholds and parameters for SURF and improved ABC algorithms are determined experimentally. The approach was extensively assessed on 99 different still images - more than 400 trials were conducted using 20 target face images and still images under different acquisition conditions. Results show that our approach is promising for real-world face recognition applications concerning different acquisition conditions and transformations.

Multi-task learning is an important area of machine learning that tries to learn multiple tasks simultaneously to improve the accuracy of each individual task. We propose a new tree-based ensemble multi-task learning method for classification and regression (MT-ExtraTrees), based on Extremely Randomized Trees. MT-ExtraTrees is able to share data between tasks minimizing negative transfer while keeping the ability to learn non-linear solutions and to scale well to large datasets.

The label estimation technique provides a new way to design semi-supervised learning algorithms. If the labels of the unlabeled data can be estimated correctly, the semi-supervised methods can be replaced by the corresponding supervised versions. In this paper, we propose a novel semi-supervised learning algorithm, called Geodesic Weighted Sparse Representation (GWSR), to estimate the labels of the unlabeled data. First, the geodesic distance and geodesic weight are calculated. The geodesic weight is utilized to reconstruct the labeled samples. The Euclidean distance between the reconstructed labeled sample and the unlabeled sample equals the geodesic distance between the original labeled sample and the unlabeled sample. Then, the unlabeled samples are sparsely reconstructed and the sparse reconstruction weight is obtained by minimizing the L1-norm. Finally, the sparse reconstruction weight is utilized to estimate the labels of the unlabeled samples. Experiments on synthetic data and USPS hand-written digit database demonstrate the effectiveness of our method.

This paper introduces an unsupervised method for motion pattern learning and abnormality detection from video surveillance. In the preprocessing steps, trajectories are segmented based on their locations, and the sub-trajectories are represented as codebooks. Under our framework, Hidden Markov Models (HMMs) are used to characterize the motion pattern feature of the trajectory groups. The state of trajectory is represented by a HMM and has a probability distribution over the possible output sub-trajectories. Bayesian Information Criterion (BIC) is introduced to measure the similarity between groups. Based on the pairwise similarity scores, an affinity matrix is constructed which indicates the distance between different trajectory groups. An Adaptable Dynamic Hierarchical Clustering (ADHC) tree is proposed to gradually merge the most similar groups and form the trajectory motion patterns, which implements a simpler and more tractable dynamical clustering procedure in updating the clustering results with lower time complexity and avoids the traditional overfitting problem. By using the HMM models generated for the obtained trajectory motion patterns, we may recognize motion patterns and detect anomalies by computing the likelihood of the given trajectory, where a maximum likelihood for HMM indicates a pattern, and a small one below a threshold suggests an anomaly. Experiments are performed on EIFPD trajectory datasets from a structureless scene, where pedestrians choose their walking paths randomly. The experimental results show that our method can accurately learn motion patterns and detect anomalies with better performance.

We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.

In the paper [4], the authors generalized the Cipolla-Lehmer method [2][5] for computing square roots in finite fields to the case of r-th roots with r prime, and compared it with the Adleman-Manders-Miller method [1] from the experimental point of view. In this paper, we compare these two methods from the theoretical point of view.

This paper describes the design and evaluation of a method for developing a chat-oriented dialog system by utilizing real human-to-human conversation examples from movie scripts and Twitter conversations. The aim of the proposed method is to build a conversational agent that can interact with users in as natural a fashion as possible, while reducing the time requirement for database design and collection. A number of the challenging design issues we faced are described, including (1) constructing an appropriate dialog corpora from raw movie scripts and Twitter data, and (2) developing an multi domain chat-oriented dialog management system which can retrieve a proper system response based on the current user query. To build a dialog corpus, we propose a unit of conversation called a tri-turn (a trigram conversation turn), as well as extraction and semantic similarity analysis techniques to help ensure that the content extracted from raw movie/drama script files forms appropriate dialog-pair (query-response) examples. The constructed dialog corpora are then utilized in a data-driven dialog management system. Here, various approaches are investigated including example-based (EBDM) and response generation using phrase-based statistical machine translation (SMT). In particular, we use two EBDM: syntactic-semantic similarity retrieval and TF-IDF based cosine similarity retrieval. Experiments are conducted to compare and contrast EBDM and SMT approaches in building a chat-oriented dialog system, and we investigate a combined method that addresses the advantages and disadvantages of both approaches. System performance was evaluated based on objective metrics (semantic similarity and cosine similarity) and human subjective evaluation from a small user study. Experimental results show that the proposed filtering approach effectively improve the performance. Furthermore, the results also show that by combing both EBDM and SMT approaches, we could overcome the shortcomings of each.

This paper proposes a novel approach for integrating spectral feature extraction and acoustic modeling in hidden Markov model (HMM) based speech synthesis. The statistical modeling process of speech waveforms is typically divided into two component modules: the frame-by-frame feature extraction module and the acoustic modeling module. In the feature extraction module, the statistical mel-cepstral analysis technique has been used and the objective function is the likelihood of mel-cepstral coefficients for given speech waveforms. In the acoustic modeling module, the objective function is the likelihood of model parameters for given mel-cepstral coefficients. It is important to improve the performance of each component module for achieving higher quality synthesized speech. However, the final objective of speech synthesis systems is to generate natural speech waveforms from given texts, and the improvement of each component module does not always lead to the improvement of the quality of synthesized speech. Therefore, ideally all objective functions should be optimized based on an integrated criterion which well represents subjective speech quality of human perception. In this paper, we propose an approach to model speech waveforms directly and optimize the final objective function. Experimental results show that the proposed method outperformed the conventional methods in objective and subjective measures.

Lossy identification schemes are used to construct tightly secure signature schemes via the Fiat-Shamir heuristic in the random oracle model. Several lossy identification schemes are instantiated by using the short discrete logarithm assumption, the ring-LWE assumption and the subset sum assumption, respectively. For assumptions concerning the integer factoring, Abdalla, Ben Hamouda and Pointcheval [3] recently presented lossy identification schemes based on the φ-hiding assumption, the QR assumption and the DCR assumption, respectively. In this paper, we propose new instantiations of lossy identification schemes. We first construct a variant of the Schnorr's identification scheme, and show its lossiness under the subgroup decision assumption. We also construct a lossy identification scheme which is based on the DCR assumption. Our DCR-based scheme has an advantage relative to the ABP's DCR-based scheme since our scheme needs no modular exponentiation in the response phase. Therefore our scheme is suitable when it is transformed to an online/offline signature.

This paper proposes a generic construction of hierarchical identity-based identification (HIBI) protocols secure against impersonation under active and concurrent attacks in the standard model. The proposed construction converts a digital signature scheme existentially unforgeable against chosen message attacks, where the scheme has a protocol for showing possession of a signing key, not a signature. Our construction is based on the so-called certificate-based construction of hierarchical identity-based cryptosystems, and utilizes a variant of the well-known OR-proof technique to ensure the security against impersonation under active and concurrent attacks. We also present several concrete examples of our construction employing the Waters signature (EUROCRYPT 2005), and other signatures. As results, its concurrent security of each instantiation is proved under the computational Diffie-Hellman (CDH) assumption, the RSA assumption, or their variants in the standard model. Chin, Heng, and Goi proposed an HIBI protocol passively and concurrently secure under the CDH and one-more CDH assumption, respectively (FGIT-SecTech 2009). However, its security is proved in the random oracle model.

In this paper, we consider decouple-and-forward (DCF) relaying, where the relay encodes and amplifies decoupled data using orthogonal space-time block codes (OSTBCs), to achieve the maximum diversity gain of multiple-input multiple-output (MIMO) amplify-and-forward (AF) relaying. Since the channel status of all antennas is generally unknown and time-varying for cooperation in multi-antenna multiple-relay systems, we investigate an opportunistic relaying scheme for DCF relaying to harness distributed antennas and minimize the cooperation overheads by not using the global channel state information (CSI). In addition, for realistic wireless channels which have spatial fading correlation due to closely-spaced antenna configurations and poor scattering environments, we analyze the exact and lower bound on the symbol error probability (SEP) of the opportunistic DCF relaying over spatially correlated MIMO Rayleigh fading channels. Numerical results show that, even in the presence of spatial fading correlation, the proposed opportunistic relaying scheme is efficient and achieves additional performance gain with low overhead.

This study analyzes the performance of a downlink beamformer with partitioned vector quantization under optimized feedback budget allocation. A multiuser multiple-input single-output downlink precoding system with perfect channel state information at mobile stations is considered. The number of feedback bits allocated to the channel quality indicator (CQI) and the channel direction indicator (CDI) corresponding to each partition are optimized by exploiting the quantization mean square error. In addition, the effects of equal and unequal partitioning on codebook memory and system capacity are studied and elucidated through simulations. The results show that with optimized CQI-CDI allocation, the feedback budget distributions of equal or unequal partitions are proportional to the size ratios of the partitioned subvectors. Furthermore, it is observed that for large-sized partitions, the ratio of optimal CDI to CQI is much higher than that for small-sized partitions.

This paper studies Tripartite Key Exchange (3KE) which is a special case of Group Key Exchange. Though general one-round GKE satisfying advanced security properties such as forward secrecy and maximal-exposure-resilience (MEX-resilience) is not known, it can be efficiently constructed with the help of pairings in the 3KE case. In this paper, we introduce the first one-round 3KE which is MEX-resilient in the standard model, though existing one-round 3KE schemes are proved in the random oracle model (ROM), or not MEX-resilient. Each party broadcasts 4 group elements, and executes 14 pairing operations. Complexity is only three or four times larger in computation and communication than the existing most efficient MEX-resilient 3KE scheme in the ROM; thus, our protocol is adequately practical.

A fully on-chip CMOS relaxation oscillator (ROSC) with a PVT variation compensation circuit is proposed in this paper. The circuit is based on a conventional ROSC and has a distinctive feature in the compensation circuit that compensates for comparator's non-idealities caused by not only offset voltage, but also delay time. Measurement results demonstrated that the circuit can generate a stable clock frequency of 6.66kHz. The current dissipation was 320nA at 1.0-V power supply. The measured line regulation and temperature coefficient were 0.98%/V and 56ppm/°C, respectively.

This letter proposes a pipelined architecture with prediction mode scheduling for high efficiency video coding (HEVC). An increased number of intra prediction modes in HEVC have introduced a new technique, named rough mode decision (RMD). This development, however, means that pipeline architectures for H.264 cannot be used in HEVC. The proposed scheme executes the RMD and the rate-distortion optimization (RDO) process simultaneously by grouping the intra prediction modes and changing the candidate selection method of the RMD algorithm. The proposed scheme reduces execution cycle by up to 26% with negligible coding loss.

Establishing trust measurements among peer-to-peer (P2P) networks is fast becoming a de-facto standard, and a fair amount of work has been done in the area of trust aggregation and calculation algorithms. However, the area of developing secure underlying protocols to distribute and access the trust ratings in the overlay network has been relatively unexplored. We propose an elliptic curve-based trust management protocol for P2P systems, which is designed to provide authentication and signature functions to protect the processes of trust value query and rating report. Additionally, instead of using single identities, the protocol generates two verifiable pseudonyms, one is used for transaction, the other is applied when the peer acts as a trust holding peer. A security analysis shows that the proposed protocol is extremely secure in the face of a variety of possible attacks.

At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.

We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.