Projects and Programs

Computer science is integral to almost every modern research effort in science and engineering; however, computer science does not limit itself to applications, in fact it gives us new and exciting ways of thinking about our complex world. According to Bernard Chazelle of Princeton University "…mathematics can't come near to describing the complexity of human endeavors in the way that computer science can…computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot."

Computer science research seeks to help us understand our world through the analysis of computational processes and computational problems. The analysis is made possible by capturing the most significant features to define a model, and removing irrelevant or less-important details that can obscure our understanding. Models are successful when they illuminate the possibilities or the limitations inherent in complex problems. Models are also successful when they are used to discover fundamental associations between seemingly disparate areas of computing.

The faculty of the Department of Computer Science is currently active in several research thrust areas, most notably in the areas of Computer and Network Security, Wireless and Sensor Networks, Intelligent Information Processing, and Theory and Algorithms.

Computer and Network Security

    John Franco and John Schlipf are building Satisfiability tools that are useful in the formal verification of hardware, software, and network protocols.   The Satisfiability solvers they have developed, under the name SBSAT, are patented jointly by UC and the NSA.

     Dharma Agrawal and Qing-An Zeng, as part of their research in computer networks, are investigating traceback schemes.  Traceback schemes are of interest due to the need to pinpoint the source of network attacks. They are also currently working on high throughput authentication protocols for bandwidth-restricted wireless networking.

     George Purdy has developed a family of one-way functions that has many applications in computer security, including password encryption for Unix.  He has recently developed a secure hash function that can compute a message digest of a file, which can used to verify message integrity.

     Dieter Schmidt and Jintai Ding of the Department of Mathematical Sciences have been collaborating for several years on analyzing Multivariate Public Key Cryptographic (MPKC) systems.  Traditional RSA is not suitable for devices with limited computing power such as smart cards and RFIDs.  The work of Schmidt and Ding shows promise for generating digital signatures for such systems.

     Raj Bhatnagar has developed algorithms for querying distributed databases while preserving security and privacy.  He computes global inferences based on an exchange of local summaries and local computation results among the participating databases. The global computation is completed by accumulating local summaries. Privacy is protected because a potential intruder does not know the semantics underlying the summaries.

Wireless and Sensor Networks

     Dharma Agrawal, Kenneth Berman, and Qing-An Zeng are working on topology control and management in WSNs.  They are investigating the determination of the transmission power of each node in a sensor network so as to maintain network connectivity while consuming the minimum possible power.

     Chia-Yung Han is building automation control applications, where the sensors are placed in strategic points of the environment and building systems.  He has been involved in intelligent building research project at UC for the last twelve years.

Intelligent Information Processing

     Raj Bhatnagar is working on distributed intelligent information processing algorithms.  This work addresses various issues, brought about by the problem of adapting known information processing algorithms (e.g.,clustering of data) to the case of distributed databases, depending on the actual partition of the database (vertical versus horizontal partition).

     Yizong Cheng's recent research involves mean shift clustering and biclustering.  This work is considered pioneering and influential in the data mining community.  He has been collaborating with biologists at organizations including Children's Hospital and Procter & Gamble. He has developed new methods and software for simulating and analyzing gene networks and membrane protein dynamics.

     Chia-Yung Han's is working on "smart buildings" and human computer interaction. This is currently complemented by his interest in the area of multimodal sensory input and interaction of multi-agents based on multimedia information processing.

     Anca Ralescu works in working in the area of machine learning and management of uncertainty in intelligent systems.  Her work includes image understanding systems, modeling high level concepts (e.g., spatial organization within an image, facial expressions), pattern recognition and machine learning. Her work on modeling with word of the image content, modeling spatial relations in an image and fuzzy classifiers for imbalanced data has pioneered use of fuzzy sets in these problems. More recently, she has started new directions, in quantum computing and statistical learning theory and applications.

Theory and Algorithms

    Jerry Paul is working on Ramsey-type problems in combinatorics and various extremal problems in graph theory. His current research projects include implementing various heuristic search strategies on multiple Beowulf clusters, including the development of a general framework for backtracking on single and multiple clusters. Recently, work with his Ph.D. student, Michal Kouril, has established that the van der Waerden number W(2,6) is 1132 (i.e., the smallest integer n such that  every 2-coloring of {1,2, ..., n} contains a monochromatic arithmetic progression of length 6 is exactly 1132).   The more recent previous result (W(2,5) = 78) was discoverd 30 years ago.   The computation was carried out using a special SAT-solver and clever techniques to bound the search.  It was run on Beowulf clusters, and, in the last phase, FPGAs to help speedup the search.

    Ken Berman is working on algorithmic problems in networks and applied graph theory, and parallel and distributed computing. He recently developed new methods of high-bandwidth file transfers. This result is part of an effort to build a system called Galaxy, built on top of PlanetLab, which is designed to solve problems associated with high bandwidth filesharing over the Internet

    Ken Berman and Jerry Paul have published a textbook "Algorithms: Sequential, Parallel, and Distributed" which offers in-depth coverage of traditional and current topics in sequential algorithms, as well as a solid introduction to the theory of parallel and distributed algorithms. Berman and Paul's text teaches graduate and undergraduate students how to create new algorithms or modify existing algorithms, thereby enhancing students' ability to think independently.

    Ken Berman and Fred Annexstein are collaborating on network algorithm research, including routing schemes in scalable networks and new algorithmic approaches to network optimization.  These algorithms address such things as information dissemination on the Internet and the national information infrastructure. They are currently exploring new models for effective network routing, including dynamic routing, fault-tolerant routing, hybrid routing models, adversarial routing, and geographic/geometric models.

    Fred Annexstein works on algorithmic issues related to social network models, including, recommendation systems and peer-to-peer networks. In recent work he developed new coding methods for tagging web documents and developed new algorithms for multicast content distribution trees.

    John Schlipf works in applications of formal logic in computer science, more specifically, logic programming, as a basis for intelligent computation.  His work in formal logic is recognized at an international level, e.g., one of his papers is listed by Citeseer as the eighth most cited paper in computer science published in 1991.  He is currently working on the development of a new logic programming solver (under stable semantics or a relative) that would combine ideas from two projects previously developed at UC.