Novel Ω-protocols for NP

Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concur- rent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle prob- lem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et al. and we believe that the method for our construction may be of independent interest.     

Existence of 3-round zero-knowledge proof systems for NP

This paper considers the existence of 3-round zero-knowledge proof systems for NP. Whether there exist 3-round non-black-box zero-knowledge proof systems for NP language is an open problem. By introducing a new interactive proof model, we construct a 3-round zero-knowledge proof system for graph 3-coloring under standard assumptions. Our protocol is a non-black-box zero-knowledge proof because we adopt a special strategy to prove the zero-knowledge property. Consequently, our construction shows the existence of 3-round non-black-box zero-knowledge proof for all languages in NP under the DDH assumption.     

Biologically inspired collective construction with visual landmarks

We describe our research in using environmental visual landmarks as the basis for completing simple robot construction tasks.Inspired by honeybee visual navigation behavior,a visual template mechanism is proposed in which a natural landmark serves as a visual reference or template for distance determination as well as for navigation during collective construction.To validate our proposed mechanism,a wall construction problem is investigated and a minimalist solution is given.Experimental results show that,using the mechanism of a visual template,a collective robotic system can successfully build the desired structure in a decentralized fashion using only local sensing and no direct communication.In addition,a particular variable,which defines tolerance for alignment of the structure,is found to impact the system performance.By decreasing the value of the variable,system performance is improved at the expense of a longer construction time.The visual template mechanism is appealing in that it can use a reference point or salient object in a natural environment that is new or unexplored and it could be adapted to facilitate more complicated building tasks.     

A Generic Framework for Anonymous Authentication in Mobile Networks

Designing an anonymous user authentication scheme in global mobility networks is a non-trivial task because wireless networks are susceptible to attacks and mobile devices powered by batteries have limited communication, processing and storage capabilities. In this paper, we present a generic construction that converts any existing secure password authen- tication scheme based on a smart card into an anonymous authentication scheme for roaming services. The security proof of our construction can be derived from the underlying password authentication scheme employing the same assumptions. Compared with the original password authentication scheme, the transformed scheme does not sacrifice the authentication effciency, and additionally, an agreed session key can be securely established between an anonymous mobile user and the foreign agent in charge of the network being visited. Furthermore, we present an instantiation of the proposed generic construction. The performance analysis shows that compared with other related anonymous authentication schemes, our instantiation is more effcient.     

A Form-Correcting System of Chinese Characters Using a Model of Correcting Procedures of Calligraphists

A support system for form-correction of Chinese Characters is developed based upon a generation model SAM,and its feasibility is evaluated.SAM is excellent as a model for generating Chinese characters,but it is difficult to determine appropriate parameters because the use of calligraphic knowledge is needed.by noticing that calligraphic knowledge of calligraphists is included in their corrective actions, we adopt a strategy to acquire calligraphic knowledge by monitoring,recording and analyzing corrective actions of calligraphists,and try to realize an environment under which calligraphists can easily make corrections to character forms and which can record corrective actions of calligraphists without interfering with them.In this paper,we first construct a model of correcting procedures of calligraphists,which is composed of typical correcting procedures that are acquired by extensively observing their corrective actions and interviewing them,and develop a form-correcting system for brush-written Chinese characters by using the model.Secondly,through actual correcting experiments,we demonstrate that parameters within SAM can be easily corrected at the level of character patterns by our system,and show that it is effective and easy for calligraphists to be used by evaluating effectiveness of the correcting model,sufficiency of its functions and execution speed.     

Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP

Barak and Lindell showed that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors.This leaves the open problem of whether it is possible to obtain an analogous result regarding constant-round zero-knowledge proofs of knowledge for NP.This paper focuses on this problem and gives a positive answer by presenting a construction of constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP.     

A temporal context model for boosting video annotation

In this paper, we propose a new method to model the temporal context for boosting video annotation accuracy. The motivation of our idea mainly comes from the fact that temporally continuous shots in video are generally with relevant content, so that the performance of video annotation could be comparably boosted by mining the temporal dependency between shots in video. Based on this consideration, we propose a temporal context model to mine the redundant information between shots. By connecting our model with conditional random field and borrowing the learning and inference approaches from it, we could obtain the refined probability of a concept occurring in the shot, which is the leverage of temporal context information and initial output of video annotation. Comparing with existing methods for temporal context mining of video annotation, our model could capture different kinds of shot dependency more accurately to improve the video annotation performance. Furthermore, our model is relatively simple and efficient, which is important for the applications which have large scale data to process. Extensive experimental results on the widely used TRECVID datasets exhibit the effectiveness of our method for improving video annotation accuracy.     

Effectively Discriminating Fighting Shots in Action Movies

Fighting shots are the highlights of action movies and an effective approach to discriminating fighting shots is very useful for many applications,such as movie trailer construction,movie content filtering,and movie content retrieval. In this paper,we present a novel method for this task.Our approach first extracts the reliable motion information of local invariant features through a robust keypoint tracking computation;then foreground keypoints are distinguished from background keypoints by a sophisticated voting process;further,the parameters of the camera motion model is computed based on the motion information of background keypoints,and this model is then used as a reference to compute the actual motion of foreground keypoints;finally,the corresponding feature vectors are extracted to characterizing the motions of foreground keypoints,and a support vector machine(SVM) classifier is trained based on the extracted feature vectors to discriminate fighting shots.Experimental results on representative action movies show our approach is very effective.     

Improving Fault Detection in Modified Code ——- A Study from the Telecommunication Industry

Many software systems are developed in a number of consecutive releases. In each release not only new code is added but also existing code is often modified. In this study we show that the modified code can be an important source of faults. Faults are widely recognized as one of the major cost drivers in software projects. Therefore, we look for methods that improve the fault detection in the modified code. We propose and evaluate a number of prediction models that increase the efficiency of fault detection. To build and evaluate our models we use data collected from two large telecommunication systems produced by Ericsson. We evaluate the performance of our models by applying them both to a different release of the system than the one they are built on and to a different system. The performance of our models is compared to the performance of the theoretical best model, a simple model based on size, as well as to analyzing the code in a random order （not using any model）. We find that the use of our models provides a significant improvement over not using any model at all and over using a simple model based on the class size. The gain offered by our models corresponds to 38-57% of the theoretical maximum gain.     

Explicit-form complex orthogonal design for space-time block codes

In this paper,we present a construction of complex orthogonal design for space-time block codes in any number of antennas.Our construction achieves both the maximal rate and minimal delay.So far as we know,our construction is the first explicit-form construction,which has asymptotically optimal time complexity and space complexity.And new representation of complex orthogonal design might bring advantages in analyzing some properties.In addition,when the number of antennas n ≡ 1,2,3(mod 4),our construction satisfies transceiver signal linearization property,which allows for design of low complexity channel equalizers and interference suppressing filters.     

Graph-based image segmentation using directional nearest neighbor graph

Graph-based image segmentation techniques generally represent the problem in terms of a graph. In this work, we present a novel graph, called the directional nearest neighbor graph. The construction principle of this graph is that each node corresponding to a pixel in the image is connected to a fixed number of nearest neighbors measured by color value and the connected neighbors are distributed in four directions. Compared with the classical grid graph and the nearest neighbor graph, our method can capture low-level texture information using a less-connected edge topology. To test the performance of the proposed method, a comparison with other graph-based methods is carried out on synthetic and real-world images. Results show an improved segmentation for texture objects as well as a lower computational load.     

Predicting RNA Secondary Structure Using Profile Stochastic Context-Free Grammars and Phylogenic Analysis

Stochastic context-free grammars （SCFGs） have been applied to predicting RNA secondary structure. The prediction of RNA secondary structure can be facilitated by incorporating with comparative sequence analysis. However, most of existing SCFG-based methods lack explicit phylogenic analysis of homologous RNA sequences, which is probably the reason why these methods are not ideal in practical application. Hence, we present a new SCFG-based method by integrating phylogenic analysis with the newly defined profile SCFG. The method can be summarized as： 1） we define a new profile SCFG, M, to depict consensus secondary structure of multiple RNA sequence alignment; 2） we introduce two distinct hidden Markov models, λ and λ＇, to perform phylogenic analysis of homologous RNA sequences. Here, λ＇ is for non-structural regions of the sequence and λ＇ is for structural regions of the sequence; 3） we merge λ and λ＇ into M to devise a combined model for prediction of RNA secondary structure. We tested our method on data sets constructed from the Rfam database. The sensitivity and specificity of our method are more accurate than those of the predictions by Pfold.     

Algorithms for Quantum Branching Programs Based on Fingerprinting

In the paper, we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on ˉngerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as MODm, EQn, Palindromen, and PERMn (testing whether given Boolean matrix is the Permutation Matrix). We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.     

Round-optimal zero-knowledge proofs of knowledge for NP

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse.     

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.     

Control of Non-Deterministic Systems With μ-Calculus Specifications Using Quotienting

The supervisory control problem for discrete event system(DES) under control involves identifying the supervisor, if one exists, which, when synchronously composed with the DES,results in a system that conforms to the control specification. In this context, we consider a non-deterministic DES under complete observation and control specification expressed in action-based propositional μ-calculus. The key to our solution is the process of quotienting the control specification against the plan resulting in a new μ-calculus formula such that a model for the formula is the supervisor. Thus the task of control synthesis is reduced a problem of μ-calculus satisfiability. In contrast to the existing μ-calculus quotienting-based techniques that are developed in deterministic setting, our quotienting rules can handle nondeterminism in the plant models. Another distinguishing feature of our technique is that while existing techniques use a separate μ-calculus formula to describe the controllability constraint(that uncontrollable events of plants are never disabled by a supervisor), we absorb this constraint as part of quotienting which allows us to directly capture more general state-dependent controllability constraints. Finally, we develop a tableau-based technique for verifying satisfiability of quotiented formula and model generation. The runtime for the technique is exponential in terms of the size of the plan and the control specification. A better complexity result that is polynomial to plant size and exponential to specification size is obtained when the controllability property is state-independent. A prototype implementation in a tabled logic programming language as well as some experimental results are presented.     

A Class of Key Predistribution Schemes Based on Orthogonal Arrays

Pairwise key establishment is a fundamental security service in sensor networks; it enables sensor nodes to communicate securely with each other using cryptographic techniques. In order to ensure this security, many approaches have been proposed recently. One of them is to use key predistribution schemes (KPSs) by means of combinatorial designs. In this paper, we use the Bush’s construction of orthogonal arrays to present a class of key predistribution schemes for distributed sensor networks. The secure connectivity and resilience of the resulting sensor network are analyzed. This KPS constructed in our paper has some better properties than those of the existing schemes.     

Towards functional verifying a family of SystemC TLMs

It is often the case that in the development of a system-on-a-chip(SoC)design,a family of SystemC transaction level models(TLM)is created.TLMs in the same family often share common functionalities but differ in their timing,implementation,configuration and performance in various SoC developing phases.In most cases,all the TLMs in a family must be verified for the follow-up design activities.In our previous work,we proposed to call such family TLM product line(TPL),and proposed feature-oriented(FO)design methodology for efficient TPL development.However,developers can only verify TLM in a family one by one,which causes large portion of duplicated verification overhead.Therefore,in our proposed methodology,functional verification of TPL has become a bottleneck.In this paper,we proposed a novel TPL verification method for FO designs.In our method,for the given property,we can exponentially reduce the number of TLMs to be verified by identifying mutefeature-modules(MFM),which will avoid duplicated veri-fication.The proposed method is presented in informal and formal way,and the correctness of it is proved.The theoretical analysis and experimental results on a real design show the correctness and efficiency of the proposed method.     

Encoding of primary structures of biological macromolecules within a data mining perspective

An encoding method has a direct effect on the quality and the representation of the discovered knowledge in data mining systems. Biological macromolecules are encoded by strings of characters, called primary structures. Knowing that data mining systems usually use relational tables to encode data, we have then to reencode these strings and transform them into relational tables. In this paper, we do a comparative study of the existing static encoding methods, that are based on the Biologist know-how, and our new dynamic encoding one, that is based on the construction of Discriminant and Minimal Substrings (DMS). Different classification methods are used to do this study. The experimental results show that our dynamic encoding method is more efficient than the static ones, to encode biological macromolecules within a data mining perspective.     

CORE: Common Region Extension Based Multiple Protein Structure Alignment for Producing Multiple Solution

Over the past several decades, biologists have conducted numerous studies examining both general and specific functions of proteins. Generally, if similarities in either the structure or sequence of amino acids exist for two proteins, then a common biological function is expected. Protein function is determined primarily based on the structure rather than the sequence of amino acids. The algorithm for protein structure alignment is an essential tool for the research. The quality of the algorithm depends on the quality of the similarity measure that is used, and the similarity measure is an objective function used to determine the best alignment. However, none of existing similarity measures became golden standard because of their individual strength and weakness. They require excessive filtering to find a single alignment. In this paper, we introduce a new strategy that finds not a single alignment, but multiple alignments with di?erent lengths. This method has obvious benefits of high quality alignment. However, this novel method leads to a new problem that the running time for this method is considerably longer than that for methods that find only a single alignment. To address this problem, we propose algorithms that can locate a common region (CORE) of multiple alignment candidates, and can then extend the CORE into multiple alignments. Because the CORE can be defined from a final alignment, we introduce CORE* that is similar to CORE and propose an algorithm to identify the CORE*. By adopting CORE* and dynamic programming, our proposed method produces multiple alignments of various lengths with higher accuracy than previous methods. In the experiments, the alignments identified by our algorithm are longer than those obtained by TM-align by 17% and 15.48%, on average, when the comparison is conducted at the level of super-family and fold, respectively.