• Tree Root of Graphs:
  A tree root of a graph G is a tree T whose k-th power for some k > 0 is the graph G exactly. Based on the equivalence of the clique tree (respectively, minimal separator tree) of G and the core of tree root when k is even (respectively, odd), we proposed a linear-time algorithm in determining the existence of tree root of a graph, and providing a such tree when does exist.
• Maximal Planar Subgraphs:
  Based on the PC-Tree representation of planar graphs, we have developed a (optimal) linear time algorithm to fi nd a maximal planar subgraph in an arbitrary graph. This algorithm provides an easily understood implementation of PC-Tree that could broaden the scope of application for planar graph algorithms.

An important problem in complexity theory is to understand the power of randomness in computation. We show how to remove randomness when space or parallel time is limited in certain ways. We show that the question of whether or not randomness helps non-deterministic computation is related to the non-determinism versus the determinism problem and the sequential time versus the space problem. We also study the problem of constructing randomness extractors, which can extract almost perfect randomness from slightly random sources, using a short random seed as a catalyst. We provide the first explicit construction of extractors, which are optimal up to constant factors. Extractors have a wide range of applications. We apply them to the construction of encryption schemes with everlasting security in the bounded storage model where any eavesdropper has only a bounded amount of storage. We also explore the limitation of constructing cryptographic protocols in the bounded storage model.

The Voronoi diagram is a very versatile and well-studied geometric construct in geometric computing. Its properties, complexity and how to compute it are among the fundamental problems to study. By introducing different metric, such as timedistance, the diagram will change. In general how the properties of the Voronoi diagram vary with the metric selected and how we make use of the properties of the selected metric, if any, to construct the diagram is what we plan to study. Other problems such as Map Labeling, i.e., how to label given features of a map so that these labels do not overlap, and Defensive Competitive Facility Location, i.e., find the location of a facility so that the gain of prospective competitors is minimized according to certain rules of competition, are also of interest. In biological computing we use some important techniques, e.g. random sampling, parametric search, geometric cutting, expander graph, matrix searching, etc. to tackle certain subsequence problems in a given DNA or arbitrary sequence, e.g., finding a maximum density subsequence or a maximum sum subsequence. We hope to use geometric techniques to solve additional problems in biological computing, and moreover, apply them to problems in pattern recognition, image processing, data mining, etc.

Recently more and more software agents have been designed to solve real-world problems arising from the rapid development of the Internet and e-commerce. Some mental attitudes of agents, such as knowledge, belief, intention, commitment, and trust play very important roles in such systems. We formally analyze different aspects of mental attitudes from a logical viewpoint and obtain the following main results. We propose an epistemic logic with modalities that represents the trusting attitudes and the information transmission action between agents, and discuss how an agent's belief is infl uenced by his trust toward other agents and the information he acquires.

• Applied computation
  Develop a Java-based interactive web application, which supports: communication within different interest groups, remote compiling of application programs, sharing of an expandable database of computational geometry code, and distributed displaying of geometric objects. This web application has been incorporated into our "Open Computational Problem Solving (OpenCPS)" knowledge portal. The integrated web environment facilitates algorithmic researchers in geometric computing to test their ideas, demonstrate their findings, and teach geometric algorithms in the classroom.
  
  
• Data confidentiality and personal privacy protection
  Massive amounts of data have been collected for various purposes. Although sharing the data can be beneficial to the public, it can also be a threat to personal privacy. How to facilitate sharing data while keeping personal privacy intact is the problem we want to address. We discovered a formal framework to discuss privacy leakage, as well as quantitative measures of the severity of privacy leakage. We also developed a prototype privacy-enforcing gateway called CellSecu that can check if sharing a particular dataset or answering a query violates the privacy policy set by the administrator.
  
  
• Applications of graph theory and algorithms
  Graphs are used to model many important applications and are a main tool for solving many theoretical problems. We often start with probing fundamental theoretical problems such as the structure of graphs with certain properties. With these properties, we then design effi cient solutions to them. One example that we work on is the graph augmentation problem, in which we want to add as few edges as possible to a given graph such that the resulting graph satisfies certain prescribed graph properties. This graph augmentation problem has many applications, such as the design of reliable networks, security of statistical tables and drawing of planar graphs. We have obtained several fundamental results for graph connectivity. We are also finding new properties based on real-life applications. For example, in Computer Chinese chess, we use graphtheoretic techniques to efficiently construct large endgame databases. We use graph theory to model Chinese chess tie-breaking rules. The problem of finding a consistent algorithm to check for tiebreaking rules has remained open for decades, if not centuries. Another example that we work on is the power domination and capacitated domination problem. By transforming power network monitoring rules into a domination problem model, and adding extra capacity and demand constraints to the original graph domination problem, we develop new graph-theoretic techniques to tackle power monitoring problems, wireless network problems, and other related problems that arise in real world applications. We make efforts to study variations of domination problem in special graph classes and aim to design efficient approximation algorithms with reasonably good approximation ratio.
  

We have studied various algorithmic problems related to parallel computing such as task scheduling, I/O resource management, I/O scheduling in parallel systems, and collective communication on heterogeneous network-based systems. We are also interested in finding good mapping techniques to implement serial algorithms in parallel machine models.

As the recent advances in commodity highspeed networks and improved microprocessor performance, clusters built up from workstations or PCs are playing a major role in redefi ning the concept of supercomputing. Although clusters of computers can provide enormous computing power at a relatively low cost, programming for these systems is still quite difficult and input/output can have a severe impact on the performance of these systems. The focuses of our research include benchmarking and fi ne-tuning for cache/memory performance, dynamic load distribution and balancing, optimization and compilation for interconnection network communication and parallel I/O. We have constructed a 32-node dual-CPU PC cluster with a parallel Input/Output subsystem and a 12-node dual-CPU workstation cluster. We also study cluster-based algorithms and integrate these optimizations in the development of application programs.

As the data-intensive applications increase continuously in various domains, scientists nowadays need to save, retrieve and analyze rapidly increasing large datasets. A single system has been diffi cult to manage such large-scale scientific data. Built on pervasive Internet standards, grid computing enables organizations to share computing and information resources across department and organizational boundaries in a secure, highly efficient manner. The Grid provides researchers an integrated virtual environment to access a wide variety of distributed resources and to facilitate collaboration among researchers and organizations. The focuses of our research include data grid system architecture, high-performance and reliable data access, data replication strategy, and parallel scientifi c computation on Grids.

Parallel programming languages, compilers, and run-time support systems are the interfaces between parallel algorithms and multiprocessor systems. We are interested in the essential language features that make parallel machines easy to use, and at the same time we study various compiler and run-time support issues that are critical in achieving high performance. We study the parallelization of sequential codes, the optimization of communication and synchronization, processor-level code optimization, parallel data structures and libraries, and performance evaluation of parallelizing compilers and compiler-generated codes. We also found that even in irregular computation, data movement only occurs at processor boundaries. Therefore, we develop domain decomposition and data reordering techniques to signifi cantly reduce the amount of inter-processor data movement.

We design and implement software libraries for scientific computations on parallel machines. We have implemented a tree-code library for the study of astrophysics and multi-fi lament vortex simulations, a library for parallel sparse matrix computations, and novel data structure technology for parallel unstructured mesh computations. In addition, we are also developing parallel simulation methods for numerical wind tunnel simulation and an engine combustion platform for computing reactive fl ows. Key technologies include unstructured mesh generation, sparse matrix computation for Euler and Navier-Stokes PDE solvers, scientifi c visualization, and parallel implementations using the MPI library.