PAVAN ADURI, Assistant Professor of Computer Science

 

Ph.D. 2001, Computer Science, University at Buffalo, Buffalo

M. Tech. 1995, Computer Science, Indian Institute of Technology, Kanpur

B. Tech, 1993, Computer Science, JNT University, Hyderabad

 

Major Interests:

Computational Complexity: Average-case complexity, Connections between average-case complexity and worst-case complexity, Structural complexity of function classes.

 

Current Research:

Part of my work is motivated by the following questions:

1. What is a hard problem? What are the properties of hard problems?

2. What are the relationships among various notions of hardness?

3. For problems in NP, what is the relationship between search and decision ?

There are several ways to define a satisfactory notion of hardness such as worst-case hardness, average-case hardness, and almost-everywhere hardness. Part of the work concerns with a variation of average-case hardness known as distributional hardness. This involves understanding various properties of distributionally-hard languages and investigate the question of whether such languages exist in NP.

Some problems such as Permanent have the fascinating property that if they are easy on average, then they are easy in worst-case. Thus, the worst-case hardness of the problem is the same as the average-case hardness of the problem. Can we find such problems in NP? A slightly related question is given a problem in NP that is mildly hard can we construct a much harder problem in NP?

The last question deals with the complexity of function classes. Is computing a witness for a NP problem more difficult than decision? Can we compute some non trivial partial information about NP-complete problems? These questions lead to a study of concepts such as selectivity and membership comparable.

 

Representative Publications:

"Separation of NP-completeness notions", A. Pavan and A. Selman. 16^th Annual IEEE Conference on Computational Complexity, 1999, pp 78-89.

 

"Complete distributional problems, hard languages, and resource-bounded measure", A. Pavan and A. Selman. Theoretical Computer Science. 234:273-286 (2000).

 

"On the hardness of permanent", J. Cai, A. Pavan and D. Sivakumar. Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science LNCS 1563: 90-99, 1999.

 

 

SAMIK BASU, Assistant Professor of Computer Science

 

Ph.D. 2003, Computer Science, State University of New York at Stony Brook

M.S. 2000, Computer Science, State University of New York at Stony Brook

B.E. 1998, Computer Science & Engineering, Jadavpur University, Calcutta

 

Major Interests:

Model Checking, Software Safety & Security Analysis

 

Current Research:

The main thrust of my research is to develop techniques for verification of infinite-state systems and use them to ensure the reliability and security of software systems. Two major activities of my research include (a) developing efficient techniques to detect system flaws and (b) enhancing debugging capabilities by building effective justification of the cause of these flaws.

 

Representative Publications:

Model-Carrying Code: A Practical Approach for Secure Execution of Untrusted Applications. R. Sekar, V.N. Venkatakrishnan, Samik Basu, Sandeep Bhatkar and Daniel C. DuVarney. Nineteenth ACM Symposium on Operating Systems Principles (SOSP-2003)

 

Generation of All Counter-Examples for Push-Down Systems. Samik Basu, Diptikalyan Saha, Yow-Jian Lin and Scott A. Smolka. Application of Formal Description Techniques in Internet and Communication Domains (FORTE-2003)

 

Compositional Analysis for Verification of Parameterized Systems. Samik Basu and C.R. Ramakrishnan. Ninth International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS-2003).

 

Resource Constrained Model Checking for Push-down Systems. Samik Basu, K. Narayan Kumar, Robert L. Pokorny and C.R. Ramakrishan. Eighth International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS-2002).

 

Local and Symbolic Bisimulation using Tabled Constraint Logic Programming. Samik Basu, C.R. Ramakrishan, I.V. Ramakrishnan, M. Mukund and R.M. Verma. International Conference on Logic Programming (ICLP-2001).

 

Model Checking the Java Meta-locking Algorithm. Samik Basu, Scott A. Smolka and Orson R. Ward. Seventh IEEE Conference and Workshops on Engineering of Computer-Based Systems (ECBS-2000).

 

 

CARL K. CHANG, Professor and Chair of Computer Science

 

B.S. 1974, Mathematics, National Central University, Taiwan

M.S. 1978, Computer Science, Northern Illinois University

Ph.D. 1982, Computer Science, Northwestern University

 

Major Interests:

Software engineering, net-centric computing.

 

Current Research:

Professor Chang’s research in software engineering includes two major activities: software architecture based requirements engineering (SABRE) and project management with genetic algorithms (PROMGA). His research in net-centric computing currently focuses on rule-mitigated collaboration technology to support formal electronic meetings. He also studies distributed requirements engineering using mobile agents.

 

Representative Publications (1994-)

Refereed Journal Papers:

Carl K. Chang, Jane Cleland-Huang, Shiyan Hua and Annie Combelles, “On Function-Class Decomposition”, IEEE Computer, Dec. 2001, pp. 87-93.

 

Carl K. Chang, Tao Zhang and Mark Christensen, “Genetic Algorithms for Project Management”, Annals of Software Engineering, Kluwer Academic Publishers, 11:107-139, Nov. 2001.

 

Carl K. Chang, Yong Liu, Thribhuvana Murthy, James Kenevan and Pattanasak Mongkolwat, “Simulation of UICCELL II'', SIMULATION, The Society for Computer Simulation International, 75(3):128-140, Sept. 2000.

 

Carl K. Chang and Chiao-Chuan Shih, “A Circular Skip-Cluster Scheme to Support Video-on-Demand Services'', ACM Multimedia Systems, Springer-Verlag, 7(2):107-118, 1999.

 

Carl K. Chang, Gerald Engel, Willis King, Eric Roberts, Russ Shackelford, Robert H. Sloan, and Pradip K. Srimani, “Curricula 2001: Bringing the Future to the Classroom”, IEEE Computer, 32(9):85-88, September 1999.

 

Carl K. Chang and Mark Christensen, “Net Practice in Software Project Management”, IEEE Software, 16(6):80-88, Nov/Dec 1999.

 

Luqi, Carl K. Chang and Hong Zhu, “Specifications in Software Prototyping'', The Journal of Systems and Software, 42:125-140, 1998.

 

Yahya Al-Salqan and Carl K. Chang, “MediaWare: A Distributed Multimedia Environment with Interoperability.'' Computers in Industry, 29(1-2):71-78, July 1996, Elsevier Science B.V., Netherlands, 1995.

 

Yahya Al-Salqan and Carl K. Chang, “MediaWare : On Distributed Multimedia Temporal Relations and Synchronization Agents.'' IEEE Multimedia, June 1996, pp. 30-39.

 

Carl K. Chang and Chiao-Chuan Shih, “Challenges and Trends of Multimedia Services'', 1994-1995 Annual Review of Communications, National Engineering Consortium, 1995, pp. 683-686.

 

C. K. Chang and Yahya Al-Salqan, “Performance Study of CSMA/CD with Connected Direct Data Link--Simulation Study'', Int'l Journal in Computer Simulation, 4(3):343-371, 1994.

 

Refereed Conference Papers:

Carl K. Chang, Jia Zhang, and Tsang Ming Jiang, “Formalization of Computer Supported Cooperative Work Applications”, Prof. of 2001 IEEE Workshop on Future Trends of Distributed Computing Systems, Bologna, Italy, October 31-November 2, 2001, pp. 185-191.

 

 

Chia-Song Ma*, Carl K. Chang, Jane Cleland-Huang, “Measuring the Intensity of Object Coupling in C++ Programs”, to be published in Proc. of IEEE COMPSAC 2001, Lisle, Illinois, October 8-12, 2001.

 

Jane Cleland-Huang, Carl K. Chang, Hosung Kim and Arun Balakrishnan, “Requirements-Based Dynamic Metrics on Object-Oriented Systems”, to be published in Proc. ff IEEE International Symposium on Requirements Engineering, Toronto, Canada, August, 2001.

 

Carl K. Chang and Lie Cai, “Agent Based Requirements Evolution Over the Internet,” Proc. of IEEE Workshop on Software Engineering on the Internet, The IEEE-CS/IPSJ 2001 Symposium on Applications and the Internet (SAINT 2001), Jan. 8-12, 2001, pp. 83-88.

 

Jane L. Huang and Carl K. Chang, “Supporting the Partitioning of Distributed Systems with Function Class Decomposition”, Proc. of IEEE COMPSAC 2000, Taipei, Taiwan, Oct. 25-27, 2000, pp. 351-356

 

Carl K. Chang, Alexei Vorontsov, Jia Zhang and Francis Quek, “Rule-Mitigated Collaboration Technology”, Proc. of 1999 IEEE Workshop on Future Trends of Distributed Computing Systems, Dec. 20-22, Cape Town, South Africa, pp. 137-142.

 

Carl K. Chang and Seongwoon Kim, “I^3:A Petri-net based Specification Method for Architectural Component”, Proc. of IEEE COMPSAC’99, Oct. 27-29, Phoenix, Arizona, pp. 396-402.

 

Carl K. Chang, Lie Cai and Francis Quek, “On Formal Meetings for Net-centric Web-based Computing”, Proc. of The International Symposium on Internet Technology, Taipei, April 29-May 1, 1998, pp. 35-40.

 

Carl K. Chang, Francis Quek, Lie Cai, Seongwoon Kim and Annie Kunzmann-Combelles, "A Research on Collaboration Net", Proc. of 1997 IEEE Workshop on Future Trends of Distributed Computing Systems, Tunis, Tunisia, October 1997, pp. 228-233.

 

Carl K. Chang, Yi-Te Tseng, and Ugo Buy, "Compiling Process Algebraic Specifications Into Timed Automata", Proc. of IEEE COMPSAC'97, Washington, DC, August 1997, pp. 338-343.

 

Carl K. Chang, Chiao-Chuan Shih, Thinh T. Nguyen and Pattanasak Mongkolwat, “A Popularity-based Data Allocation Scheme for a Cluster-based VOD Server'', Proc. of IEEE COMPSAC'96, Seoul, Korea, August 1996, pp. 62-67.

 

Carl K. Chang and Chiao-Chuan Shih, "Reducing the System Response Time of a Large-scale VOD Server by Disk Grouping", Proc. of IEEE ICCASS '96 (International Conference on Circuits and Systems Symposium), Shanghai, China, June 1996.

 

Yahya Al-Salqan and Carl K. Chang, “MediaWare: On Distributed Multimedi a Synchronization'', Proc. of The second IEEE International Conference on Multimedia Computing and Systems, Washington, DC, May 1995, pp. 150-158.

 

Yahya Al-Salqan and Carl K. Chang, “MediaWare: A Distributed Multimedia Environment with Interoperability'', Proc. of The Fourth IEEE International Workshop on Enabling Technology: Infrastructure for Collaborative Environment, Berkely Springs, WV, April 1995, pp. 128-137.

 

Carl K. Chang, Jamsheed Bugwadia and Pattanasak Mongkolwat, “An Message-Oriented Discrete Event Simulation Model of the Cellular Telephone System", Proc. of 1995 Summer Computer Simulation Conference, Ottawa, Ontario, Canada, 1995, pp. 858-862.

 

Carl K. Chang, Pattanasak Mongkolwat and Bashir Haswarey, “Creating a Distributed Environment Using Object-Oriented Technology'', Proc. of IEEE COMPSAC' 95, Pheonix, Arizona, August 1995, pp. 262-267.

 

Carl K. Chang, Yong Liu and Thribhuvana Murthy, “Study of Performance Engineering with Emphasis on Simulation of UICCELL II", Proc. of IASTED International Conference: MODELLING AND SIMULATION, Pittsburgh, Pennsylvania. April 27-29, 1995, pp. 403-406.

 

 

SOMA CHAUDHURI, Associate Professor of Computer Science

 

B.S. 1984, Mathematics, Massachusetts Institute of Technology, Cambridge

B.S. 1984, Computer Science & Engineering, Massachusetts Institute of Technology, Cambridge

M.S. 1987, Computer Science & Engineering, University of Washington, Seattle

Ph.D. 1990, Computer Science & Engineering, University of Washington, Seattle

 

Major Interests:

Theory of Distributed Computing, Parallel Algorithms and Parallel Complexity.

 

Current Research:

Dr. Chaudhuri's research in distributed computing has focused on understanding the power of asynchronous distributed systems subject to various kinds of failures. A persistent question has been to determine the problems that are solvable in the presence of uncertainty due to processor asynchrony and failures. She used combinatorial techniques to prove that certain problems are impossible to solve in these systems. The current focus of her research has shifted to the study of systems that are semi-synchronous, i.e., that have partial but inexact information about timing. These systems are much more realistic and deserve further study.  Dr. Chaudhuri is using similar combinatorial techniques with the goal of obtaining time and space complexity characterizations for problems in semi-synchronous systems analogous to the fault-resiliency character-ization obtained for problems in asynchronous systems.  The ultimate objective would be to understand in a formal sense the advantage that can be gained by considering timing-based models for distributed computing over asynchronous models, and the disadvantage they represent in relation to fully synchronous models.

Dr. Chaudhuri has also been recently interested in the area of distributed ad hoc networks. In particular, it would be useful to develop algorithms that are specifically suited to solving problems in these networks. These networks are unpredictable due to frequent link failures when nodes drift apart and link formations when nodes drift closer to each other. Existing distributed algorithms that rely on static communication links cannot run in such networks. Instead, efficient algorithms would have to be designed that adjusts to the mobility of the network.

 

Representative Publications:

"Tight Bounds for "k"-Set Agreement." Chaudhuri, S., Herlihy, M., Lynch, N., & Tuttle, M. (2000). To appear in Journal of the ACM.

 

"One-Write Algorithms for Multi-Valued Regular and Atomic Registers," Chaudhuri, S., Kosa, M., & Welch, J.L. Acta Informatica, 37:161-192, 2000.

 

"Wait-Free Implementations in Message Passing Systems."  Chaudhuri, S., Herlihy, M., & Tuttle, M. Theoretical Computer Science  (2000).  Theoretical Computer Science, 220(1):211-245, June 1999.

 

"Shared Memory Consistency Conditions for Non-Sequential Execution: Definitions and Programming Strategies," Chaudhuri, S., Attiya, H., Friedman, R., & Welch, J.L.  SIAM Journal on Computing, 27(1):65-89, February 1998.

 

"Understanding the Set Consensus Partial order Using the Borowsky-Gafni Simulation," Chaudhuri, S., & Reiners, P.  Proceedings of the Tenth International Workshop on Distributed Algorithms, 1996.  Lecture notes in Computer Science 1151, Springer-Verlag, pp. 362-379.

 

"Using Adaptive Timeouts to Achieve At-Most-Once Message Delivery," Chaudhuri, S., Coan, B., & Welch, J. Distributed Computing, 9(3):109-117, September 1995.

 

"Bounds on the Costs of Multi-Valued Register Implementations," Chaudhuri, S., & Welch, J. SIAM Journal on Computing, 23(2):335-354, April 1994.

 

"Designing Algorithms for Distributed Systems with Partially Synchronized Clocks," Chaudhuri, S., Gawlick, R., & Lynch, N. Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, August 1993.

 

"More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems," Chaudhuri, S. Information and Computation, 105(1):132-158, July 1993.

 

 

HUI-HSIEN CHOU, Assistant Professor of Computer Science & Zoology and Genetics

 

B.S, 1984, Chemical Engineering, Ming-Chih Institute of Technology, Taipei, Taiwan

B.S, 1989, Computer Science, National Taiwan University, Taipei, Taiwan

Ph.D., 1996, Computer Science, University of Maryland at College Park

 

203 Science II, Iowa State University, Ames, IA 50011;

Email: hhchou@iastate.edu

 

Major Interests:

Bioinformatics, computational biology, cellular automata, programming language design and compiling.

 

Current Research:

Dr. Chou's research centers around two complementary scientific front-ends: computational biology and artificial life. In computational biology, he studies how to best analyze the vast amount of biological data generated because of recent advances in high-throughput molecular biology research, such as genomics, transcriptomics and proteomics.  These advances allow us to gather explosively more biological data about species, but then only computers can efficiently analyze these huge quantity of data. Dr. Chou has designed an automatic DNA sequence quality assurance program (Lucy) that is in use by many research centers to turn raw DNA sequences into high quality data for subsequent genomic data processing. Dr. Chou is currently working on an integrated approach of biological data analysis that handles sequence, structure, microarray and pathway data altogether based on specialized coding methods developed by him.

One can view computational biology as an analytical approach to understanding life. An alternative, the synthetic approach taken in the artificial life research, aims at simulating life phenomena within computers. It is an attempt to grasp the principles of life in an information processing context without touching the difficult details of implementation such as DNA or proteins. Dr. Chou has been working on the cellular automata modeling of self-replication processes. Cellular automata are massively parallel computer-theoretical models which closely resemble the information restrictions in living cells. As in cells, where no single molecule is the commander-in-chief, in cellular automata, there is no centralized control. All global behaviors must be the collaborative results of each automaton making up the models. Yet, complex and very interesting behaviors such as information self-replication can be observed with such models, promoting one to computationally study the principles of life.

On more practical aspects, Dr. Chou is also involved in programming language design and compiling. He has developed the Trend cellular automata programming language to facilitate the cellular automata studies mentioned above. He is currently working on a visual programming tool that can automatically generate working Perl programs for biologists who may not know how to program in Perl directly.

 

Representative Publications:

Hui-Hsien Chou, Wei Huang and James A. Reggia. "The Trend Cellular Automata Programming Environment." To by published by SIMULATION: Transactions of The Society for Modeling and Simulation International.

 

Hui-Hsien Chou and Michael H. Holmes.  "DNA Sequences Quality Trimming and Vector Removal."  Bioinformatics, 17(12):1093-1104, Dec. 2001.

 

Eugene W. Myers, et al. "A Whole-Genome Assembly of Drosophila." Science, 287:2196-2204, March 24, 2000.

 

Hui-Hsien Chou and James A. Reggia. "Problem Solving During Artificial Selection of Self-Replicating Loops." Physica, D 115:293-312, 1998.

 

Hui-Hsien Chou and James A. Reggia. "Emergent of Self-Replicating Structures in a Cellular Automata Space."  Physica, D 100:252-276, 1997.

 

Hui-Hsien Chou, James A. Reggia, Rafael Navarro-Gonzalez, and Jayoung Wu. "An Extended Cellular Space Method for Simulating Autocatalytic Oligonucleotides." Computers and Chemistry, 18(1):33-43, 1994.

 

James A. Reggia, Steven L. Armentrout, Hui-Hsien Chou, and Yun Peng. "Simple Systems that Exhibit Self-Directed Replication." Science, 259:1282-1288, Feb. 26, 1993.

 

 

OLIVER EULENSTEIN, Assistant Professor of Computer Science

 

Dr.rer.nat. 1998, Computer Science, University of Bonn

Diplom-Informatiker 1991, Computer Science, University of Paderborn (the US-equivalent for Dr.rer.nat. is Ph.D. and for Diplom-Informatiker is M.S )

 

Web Page:  http://www.cs.iastate.edu/~oeulenst

 

Major Research Interests:

Computational Biology, Combinatorial Optimization in Science and Engineering, and Design and Analysis of Discrete Algorithms.

 

Current Research:

Introducing Computational Biology: In July 1995 the first organism, {\Haemo\-philius influenzae} was entirely sequenced and its 1 830 137 DNA base pairs were published. Soon after this other organisms were completely sequenced and, most likely, the human genome will be completely sequenced by the end of this decade.

Given an organism's sequence information, the biologists task is now to reveal  function and interference of these sequences. As a metaphor, the biologist wants  to understand the function of a complex spacecraft engine only by looking at its  parts.

Computational Biology offers algorithms to support biologists in their effort to retrieve information out of an organism's enormous set of sequence information. Design and analysis of these algorithms is based on models that reflect the biologists needs as best as possible. A model must also allow the design of an algorithm that actually solves the problem in practice in a reasonable time. Thus, a basic problem in Computational Biology is to develop good models. Most of the time biologists and computer scientists collaborate to set up an initial model and then refine it stepwise according to practical results. Thus, Computational Biology is an interdisciplinary science where Biology and Computer Science are intertwined.

Current Research in Computational Biology: Reconstructing the ancestral relations of biological sequences can give insights into the function of biological sequences, and thus helps to reveal unknown functions of genes. The ancestral relations of a set of biological sequences can be represented by a rooted tree, where any two sequences are related through their least common ancestor.

Most of my current research is in constructing phylogenetic trees, which is a sub-area of Computational Biology. For convenience I will describe one of my research topics, “phylogenetic super-trees” in more detail.

Computational Biology offers a huge set of different methods for phylogenetic tree construction that are available through program packages like PAUP, McClade and Component, which are widely used by systematic biologists. Already reconstructed phylogenetic trees can be found in phylogenetic tree databases like TreeBase. Some of these databases have grown enormously and now contain sets of trees that overlap in some of their sequences. My goal is to construct a “super-tree” from such a set of overlapping phylogenetic trees. A super-tree would give a much broader picture of how sequences evolve. Unfortunately, combining trees into a super-tree is not an easy task. For example one of the arising problems is that phylogenetic trees have for their shared sequences often different ancient relationships.\medskip

Together with the biologist Mike Sanderson from the University of California Davis, I developed a model to construct super-trees. In collaboration with David Fernandez-Baca and the help of the student Duhong Chen we are designing algorithms based on this model. In our new computational biology lab (CBL), we are implementing own ideas and analyze algorithms. We are also refining the underlying model. Recently Mike Sanderson, the biologist Olaf Biminda-Edmondson, and I received an NSF grand that will support our research on super-trees for the coming three years.

Other topics of my current research in Computational Biology are the prediction of gene-duplications and reconstructing phylogenetic trees from incomplete information. The above should not led to the impression that my interests are exclusively in phylogenetic tree construction. In fact I am interested in many algorithmic problems of biology and actively look for potential interdisciplinary collaborations.

 

Grants:
$  398,170,  funding period 2000-2003,  "Algorithms and Software for Phylogenetic Supertrees"  (NSF-1053164),
O. Eulenstein (co-PI), D. Gusfield (co-PI), M.J. Sanderson (PI).

 

Representative Publications:

D. Chen, L. Diao, O. Eulenstein, D. Fernández-Baca, M. J. Sanderson, Flipping: A Supertree Construction Method to appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, AMS (2003).

 

D. Chen, O. Eulenstein, D. Fernández-Baca, and M.J. Sanderson; Supertrees by Flipping; Computing & Combinatorics Conference (COCOON) 2002.

D. Chen, L. Diao, O. Eulenstein, D. Fernández-Baca, and M.J. Sanderson; Flipping: A Supertree Construction Method; Ed. F.B.M. Morris et al., DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, AMS (2002).

J.  Schonfeld, O. Eulenstein, K. VanderVelden, and G.J.P. Naylor; Investigating Evolutionary Lines of Least Resistance Using the Inverse Protein-Folding Problem; Pacific Symposium on Biocomputing (PSB) 2002.

 

Oliver Eulenstein and Martin Vingron, "On the equivalence of two tree mapping measures", Discrete Applied Mathematics, 88:103-128, 1998.

 

Oliver Eulenstein, Boris Mirkin and Martin Vingron. "Duplication-Based Measures of Difference Between Gene- and Species Trees", Journal of Computational Biology, 5:135-148, 1998.

 

Yan P. Yuan, Oliver Eulenstein, Martin Vingron and Per Bork,  "Towards detection of orthologues in sequence databases", Bioinformatics, 14(3):285-289, 1998.

 

Oliver Eulenstein, Boris Mirkin and Martin Vingron, "Comparison of Annotation Duplication, Tree Mapping, and Copying as Methods to Compare Gene Trees with Species Trees,” DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences AMS, 1997.

 

 

DAVID FERNANDEZ-BACA, Professor of Computer Science

 

        B.S. 1980, Electrical & Computer Engineering, National University of Mexico, Mexico City

      M.S. 1983, Electrical & Computer Engineering, University of California, Davis

      Ph.D. 1986, Computer Science, University of California, Davis

 

Major Interests:

Design and analysis of algorithms, combinatorial optimization, graph algorithms, computational biology.

 

Current Research:

Dr. Fernandez-Baca's research is in the design and analysis of combinatorial algorithms.  His main area is parametric optimization, where his goal is to design efficient algorithms to analyze the sensitivity of the optimum solution to changes in the input data. Dr. Fernandez-Baca also studies combinatorial problems arising in sequence comparison and construction of evolutionary trees for sets of species.

 

Representative Publications:

D. Chen, L. Diao, O. Eulenstein, D. Fernández-Baca, and M. Sanderson. Flipping: A supertree construction method. To appear in the Bioconsensus volume of the DIMACS Series in Discrete Mathematics and Theoretical Computer Science, F. McMorris et al. (eds), American Mathematical Society, 2002.

 

D. Fernández-Baca, T. Seppäläinen, and G. Slutzki. Bounds for parametric sequence comparison. Discrete Applied Mathematics, 118:181-198, 2002.

 

D. Chen, O. Eulenstein, D. Fernández-Baca, and M. Sanderson. Supertrees by flipping. To appear in Proceedings of COCOON 2002, Springer-Verlag LNCS.

 

F. Sun, D. Fernández-Baca, and W. Yu. Inverse parametric sequence alignment. To appear in Proceedings of COCOON 2002, Springer-Verlag LNCS.

 

D. Fernández-Baca. Multiparameter matroidal knapsack problems. To appear in Theoretical Computer Science, 2002.

 

D. Fernández-Baca. The perfect phylogeny problem. In Steiner Trees in Industry, X. Cheng and D.-Z. Du (eds.), pp. 203-234, Kluwer, 2001.

 

D. Fernández-Baca. On nonlinear parametric search. Algorithmica, 30:1-11, 2001.

 

D. Fernández-Baca, T. Seppäläinen, and G. Slutzki. Parametric multiple sequence alignment and phylogeny construction. Proc. Combinatorial Pattern Matching 2000, Springer-Verlag LNCS, Vol. 1848, pp. 69--83.

D. Fernández-Baca and J. Lagergren. On the approximability of the Steiner tree problem in phylogeny. Discrete Applied Mathematics 88:129-145, 1998.

 

D. Fernández-Baca and G. Slutzki. Linear-time algorithms for parametric minimum spanning tree problems on planar graphs. Theoretical Computer Science, 181:57-74, 1997 .

 

D. Fernández-Baca and G. Slutzki. Optimal parametric search on graphs of bounded tree-width. Journal of Algorithms 22:212-240, 1997.

 

D. Fernández-Baca and J. Lagergren. A polynomial-time algorithm for near-perfect phylogeny. In proceedings of 23rd International Conference on Automata, Languages, and Programming, pp. 670-680, Springer Verlag Lecture Notes in Computer Science, 1996.

 

 

SHASHI K. GADIA, Associate Professor of Computer Science

 

        B.S. (Hons), 1969, Mathematics, Birla Inst. of Tech. & Science

        M.Sc. 1970, Mathematics, Birla Inst. of Tech. & Science

        Ph.D. 1977, Mathematics, University of Illinois

        M.S. 1980, Computer Science, Ohio State University

 

Major Interests:

Temporal, spatial, belief, security, statistical and incomplete data; database models, type hierarchy, languages, user interfaces, optimization, implementation and access methods; pattern matching in spatio-temporal data.

 

Current Research:

Models, query languages, incomplete information, implementation, index structures, and query optimization for dimensional (temporal, spatial, and belief), genetic, and other forms of data, in relational, object-oriented, and semistructured (XML) database paradigms. The goal of the research in dimensional data is to unify different forms of dimensional data seamlessly in a scalable, efficient, easy to use, and coherent framework. An object-oriented model and query language for dimensional data that is consistent with the ODMG (Object Data Management Group) standard is of interest. Database models for semistructured data are rapidly advancing under the banner of XML (Extensible Markup Language). The February 16, 2001 announcements of the XML’s Query Group of the W3 (World Wide Web) Consortium represent a major milestone that extends the established classic database style wisdom of powerful and declarative algebraic querying to XML by treating XML documents as databases. This will advance the frontiers of databases in revolutionary ways to applications such as e-business, software engineering, and genetic data where representation and/or exchange of heterogeneous and evolutionary information is required. 

 

Representative Publications:

 “A linguistic framework for multidimensional data,” Elisa Bertino, Tsz S. Cheng, Shashi K Gadia, and Giovanna Guerrini. Submitted for publication, February, 2001. 

 

“Querying multiple temporal granularity data.” Isabella Merlo, Elisa Bertino, Elena Ferrari, Shashi K Gadia, and Giovanna Guerrini.  Proceedings Seventh International Workshop on Temporal Representation and Reasoning of TIME-2000, Nova Scotia, Canada, July 7-9, 2000

 

“Algebraic identities and query optimization in the parametric model for relational temporal databases,” IEEE Transactions on Knowledge and Data Engineering. Vol 10(5), pp 793-807, 1998.

 

“Applicability of Temporal Data Models to Query Multilevel Security Databases: A Case Study, Shashi K. Gadia. Research and Practice; Etzion, Jajodia, and Sripada, eds.; Lecture Notes in Computer Science, 1399: 238-256, Springer Verlag, Berlin, 1998.

 

“Relational Database Systems With Zero Information-Loss,” Gadia, S., & Bhargava, G. (1993).  IEEE Transactions on Knowledge and Data Engineering, 5:76-87.

 

"Incomplete Information in Relational Temporal Databases,” Gadia, S., Nair, S., & Poon, Y. (1992).  Proceedings of the 18th International Conference on Very Large Databases, pp. 395-406.

 

"A Generalized Model for a Relational Temporal Database,” Gadia, S., & Yeung, C.  (1988).  ACM SIGMOD Conference on Management of Data, pp. 251-259.

 

“A Homogeneous Relational Model and Query Languages for Temporal Databases,” Gadia, S.  (1988). ACM Transactions on Database Systems, 14:418-448.

 

“A Query Language for a Homogeneous Temporal Database,” Gadia, S., & Vaishnav, J.  (1985). Proc. Fourth Annual ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp 51-56.

 

“The concept of an error in a database: an application of temporal databases,” Gautam Bhargava and Shashi K. Gadia. Appeared in Proceedings of INSDOC COMAD90 International Conference on Management of Data, December 1990.

 

VASANT HONAVAR, Professor of Computer Science

 

B.E. 1982, Electronics Engineering, Bangalore University, India

M.S. 1984, Electrical and Computer Engineering, Drexel University

M.S. 1989, Computer Science, University of Wisconsin at Madison

Ph.D. 1990, Computer Science and Cognitive Science, University of Wisconsin at Madison

 

www:  http://www.cs.iastate.edu/~honavar/

 

Current Affiliations:

Professor, Department of Computer Science

Director, Artificial Intelligence Research Laboratory

Editor-in-Chief, Cognitive Systems Research

Project Director, Bioinformatics, Computational Molecular Biology Training Group

Associate Chair, Bioinformatics and Computational Biology Graduate Program

Faculty Member, Bioinformatics and Computational Biology Graduate Program

Faculty Member, Laurence H. Baker Center for Bioinformatics and Biological Statistics

Faculty Member, Virtual Reality Applications Center

Faculty Member, Information Security Graduate Program

Faculty Member, Neuroscience Graduate Program

 

Research and Teaching Interests:

Artificial Intelligence (Autonomous Agents; Automata Induction; Computational Learning Theory; Computational Organizational Theory; Data Mining, Knowledge Discovery and Visualization; Distributed Knowledge Networks; Cumulative Distributed Learning; Incremental Learning; Intelligent Agents and Multi-Agent Systems; Multi-Agent Coordination, Communication, and Negotiation; Knowledge Representation and Inference; Probabilistic Models and Bayesian Inference; Machine Learning; Neural Networks); Bioinformatics (Distributed Information Networks for for Data Integration, Information Extraction, Data Mining, and Knowledge Discovery; Knowledge Representation and Automated Inference); Computational Molecular Biology (Genetic Networks; Computational Characterization of Protein Sequence-Structure-Function Relationships and and Protein-Protein Interactions; Computational Genomics; Metabolic Pathways; Gene Expression Analysis; Computational Neuroscience; Evolutionary, Cellular, and Neural Computation); Distributed Information Networks (Distributed Knowledge Networks; Distributed Databases, Mediators, and Data Warehouses; Intelligent Agents, Mobile Agents, and Multi-Agent Systems); Applied Artificial Intelligence.

Examples of current projects in Honavar's laboratory on Distributed Intelligent Information Systems focuses on the design, analysis, and implementation of algorithms and software for information extraction, integration, organization, and visualization; and learning from from heterogeneous, distributed, dynamic, and autonomous data, information, and knowledge sources. In particular, we are developing ontology-driven information integration that enable analysis of data from multiple perspectives, algorithms with provable performance guarantees for distributed, incremental, and cumulative learning tasks; algorithms for learning from data and knowledge (including alternative ontologies), algorithms for learning from alternately structured (e.g. relational, graph, etc.) data; and algorithms for multi-agent learning.  This work is driven by large-scale applications of machine learning and automated inference for scientific discovery in Computational Molecular Biology and other data-rich domains.

In related work, topics in mobile agent infrastructures, inter-agent negotiation protocols, distributed problem solving, coordination and control structures for multi-agent systems, and agent-oriented software engineering are being investigated.

 Current research in Computational Molecular Biology emphasizes machine learning approaches to gene discovery, characterization of protein sequence-structure-function relationships, protein-protein interactions, discovery of genetic networks from expression data, and information theoretic, and grammatical analysis of DNA and protein sequences, and computational geometric analysis of protein structures.

Honavar's research is supported in part by grants from the National Science Foundation, Department of Defense, John Deere Foundation, Carver Foundation, Pioneer Hi-Bred, Inc., Department of Energy, and the ISU Graduate College.

 

Recent Representative Publications:

Andorf, C., Dobbs, D., and Honavar, V. (2002). Discovering Protein Function Classification Rules from Reduced Alphabet Representations of Protein Sequences. In: Proceedings of the Conference on Computational Biology and Genome

Informatics (part of the 2002 Joint Conference on Information Sciences). Durham, North Carolina.

 

Caragea, D., Silvescu, A., and Honavar, V. (2002). Invited Chapter. Multi-Agent Decision Tree Learning from Distributed Autonomous Data Sources. In: Intelligent Agent Software Engineering. Plekhanova, V. and Wermter, S. (ed.). Idea Group Publisher. In press.

 

Honavar, V., Andorf, C., Caragea, D., Dobbs, D., Reinoso-Castillo, J., Silvescu, A. (2002). Invited Chapter. Algorithmic and Systems Solutions for Computer Assisted Knowledge Acquisition in Bioinformatics and Computational Biology. In: Computational Biology and Genome Informatics. Wu, C., Wang,P., and Wang, J. (Ed.) World Scientific. In press.

 

Wang, X., Schroeder, D., Dobbs, D., and Honavar, V. (2002). Data-Driven Discovery of Protein Function Classifiers: Decision Trees Based on MEME Motifs Outperform Those Based on PROSITE Patterns and Profiles on Peptidase Families. In Proceedings of the Conference on Computational Biology and Genome Informatics (part of the 2002 Joint Conference on Information Sciences).

 

Balakrishnan, K. and Honavar, V. (2001). Evolving Neurocontrollers and Sensors for Artificial Agents. In: Advances in Evolutionary Synthesis of Intelligent Agents. Patel, M., Honavar, V. and Balakrishnan, K. (Ed). Cambridge, MA: MIT Press. pp. 109-152.

 

Caragea, D., Silvescu, A., and Honavar, V. (2001).  Invited Chapter. Analysis and Synthesis of Agents that Learn from Distributed, Dynamic Data Sources. Emergent Neural Computational Architectures. Wermter, S., Austin, J., and Willshaw, D. Springer-Verlag.

 

Caragea, D., Cook, D., and Honavar, V. (2001). Gaining Insights into Support Vector Machine Classifiers Using Projection-Based Tour Methods. In: Proceedings of the Conference on Knowledge Discovery and Data Mining (KDD-01). AAAI Press.

 

Helmer, G., Wong, J., Slagell, M., Honavar, V., Miller, L. and Lutz, R. (2001). A Software Fault Tree Approach to Requirements Analysis of an Intrusion Detection System. In: Proceedings of the Symposium on Requirements Engineering for Information Security, Indianapolis, IN, USA.

 

Mikler, A., Honavar, V. and Wong, J. (2001). Autonomous Agents for Coordinated Distributed Parameterized Heuristic Routing in Large Dynamic Communication Networks. Journal of Systems and Software.  56:231-246.

 

Parekh, R. and Honavar, V. (2001). DFA Learning from Simple Examples. Machine Learning. 44:9-35.

 

Polikar, R., Udpa, L., Udpa, S., and Honavar, V. (2001). Learn++: An Incremental Learning Algorithm for Multi-Layer Perceptron Networks. IEEE Transactions on Systems, Man, and Cybernetics. 31(4):497-508.

 

 

XIAOQIU HUANG, Associate Professor of Computer Science

 

B.S. 1982, Computer Science, Changsha Institute of Technology

M.S. 1989, Computer Science, Pennsylvania State University

Ph.D. 1990, Computer Science, Pennsylvania State University

 

Major Research Interests:

Computational biology, parallel and distributed applications.

 

Current Research:

Dr. Huang is interested in algorithms and software for solving computational problems in genome sequencing and analysis.  He has developed a number of computer programs for analysis of DNA and protein sequences.  Dr. Huang's programs have been included in a number of academic and commercial packages. Most of his programs can be used on WWW at http://bioinformatics.iastate.edu/aat/sas.html.

 

Dr. Huang is currently working on a DNA sequence assembly program for a whole-genome data set of 30 million sequences. The sequence assembly program is used to assemble short DNA sequences into long sequences in shotgun DNA sequencing projects. He is also working on a computer program for comparing all the DNA sequences of the human genome with  those of the mouse genome. The goal of this project is to develop a computer program that quickly computes

biologically interesting similarities between the two genomes. In the future, Dr. Huang will continue to work on computational programs in genome sequencing and analysis.

 

Recent Publications:

Huang, X., Wang, J., Aluru, S., Yang, S.-P. and Hillier, L. (2003). PCAP: A Whole-Genome Assembly Program, Genome Research, 13: 2164-2170.

 

Huang, X. and Chao, K.-M. (2003). A Generalized Global Alignment Algorithm, Bioinformatics, 19: 228-233.

 

Huang, X, and Madan, A. (1999).  CAP3: A DNA Sequence Assembly Program, Genome Research, 9: 868-877.

 

Huang, X, Adams, M.D., Zhou, H., and Kerlavage, A.R. (1997).  A Tool for Analyzing and Annotating Genomic Sequences, Genomics, 46(1):37-45.

 

Huang, X., and Zhang, J. (1996).  Methods for Comparing a DNA Sequence with a Protein Sequence, Computer Applications in the Biosciences, 12(6):497-506.

 

Huang, X. (1996). Fast Comparison of a DNA Sequence with a Protein Sequence Database, Microbial & Comparative Genomics, 1(4):281-291.

 

YAN-BIN JIA, Assistant Professor of Computer Science

 

B.S. 1988, Computer Science, University of Science and Technology of China

M.S. 1993, Robotics (and Computer Science), Carnegie Mellon University

Ph.D. 1997, Robotics (and Computer Science), Carnegie Mellon University

 

Major Research Interests:

Robotics, shape localization, reconstruction, and recognition, computational geometry, geometric modeling, curve computation, robot sensing, dexterous manipulation and control, hacking robot interfaces, optimization, nonlinear

control and observation, kinematics and dynamics of manipulation.

Internet: jia@cs.iastate.edu

 

Current Research:

"The hand is the cutting edge of the mind," and "The world can only be grasped by action, not by contemplation," says Bronowski in his book "The Ascent of Man".  Dr. Jia's main research objective is to make the robot execute real world tasks intelligently and skillfully.  

His investigation into robot dexterity has focused on seeking a coordinated understanding of computational and control issues in manipulation tasks. One objective of this study is dynamic retrieval of geometric information such as  shape and pose, and of mechanical information such as motion and force.  Another objective is careful engineering of the above information to make the robot exhibit skills during its execution of physical tasks. Through efforts balanced between theoretical inquiry and experimental demonstration, Dr. Jia hopes to gain in-depth knowledge about action and intelligence as they interact with each other.

For over two years Dr. Jia has been studying how to program a robotic hand to localize and recognize an object of curved shape and to execute basic operations as well as dextrous maneuvers.  This investigation makes primary use of one source of information which is ubiquitous in the physical world ---{\it contact} between two or more bodies.  He hopes to understand basic computational principles of touch sensing in the context of parts localization, model-based recognition, and shape reconstruction. 

The human learns skills through practice, so should the robot.  Dr. Jia is also interested in applying learning techniques to tackle tasks that would be computationally expensive or intractable otherwise. He would like to program the robot so that it will be able to give performances that approach the human level someday.

 

Representative Publications:

"Curvature-Based Computation of Antipodal Grasps", Yan-Bin Jia. Accepted by the IEEE International Conference on Robotics and Automation, Washington, D.C., May 11-15, 2002.

 

"Geometry and Computation of Antipodal Points on Plane Curves", Yan-Bin Jia. submitted to Computational Geometry: Theory and Applications.  Technical Report ISU-CS-01-04, CS Department, Iowa State University, Ames, IA, 2001.

 

"Localization on Curved Objects Using Tactile Information", Yan-Bin Jia. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 701-706, Maui, HI, Oct 29-Nov 3, 2001.

 

"Grasping Curved Objects through Rolling," Yan-Bin Jia. In Proceedings of the IEEE International Conference on Robotics and Automation, pp. 377-382, San Francisco, CA, April 2000. 

 

"Pose and Motion from Contact," Yan-Bin Jia and Michael Erdmann. International Journal of Robotics Research, 18(5):466-490, 1999.

 

"Local Observability of Rolling," Yan-Bin Jia and Michael Erdmann. In Robotics: The Algorithmic Perspective, P.K. Agarwal et al. (eds.), pp. 251-263, A. K. Peters, Boston, 1998. Also Proc. 3rd Int'l Workshop on the Algorithmic Foundations of Robotics, Houston, TX, March 1998. 

 

"Geometric Sensing of Known Planar Shapes," Yan-Bin Jia and Michael Erdmann. International Journal of Robotics Research, 15(4):365-392, 1996.

 

"The Complexity of Sensing by Point Sampling," Yan-Bin Jia and Michael Erdmann. In Algorithmic Foundations of Robotics, Ken Goldberg et al. (eds.), pp. 283-300, A. K. Peters, Boston, 1995. Also Proc. 1st Int'l Workshop on the Algorithmic Foundations of Robotics, San Francisco, CA, February 1994. 

 

 

GARY T. LEAVENS, Professor of Computer Science
 

      B.S. 1978, Computer & Communication Sciences, The University of Michigan

      M.S. 1980, Computer Science, The University of Southern California

      Ph.D. 1989, Computer Science, Massachusetts Institute of Technology

 

Major Interests:

Programming and specification language design and semantics, formal methods (program specification and verification), type theory, object-oriented programming languages, aspect-oriented programming languages, component-based systems,  information assurance, functional programming, distributed programming languages.

 

Current Research:

The long term goal of Dr. Leavens's research is to understand better how to solve programming problems: how to specify such problems, methods for thinking about such problems, notations for expressing solutions, ways to check that the solutions are correct, and tools for automating and assisting with these processes. In pursuing this goal, he has worked in two main areas: formal methods and programming languages.

 

Formal Methods

Dr. Leavens's work in formal methods has been focused on ways to specify and verify object-oriented (OO) software components.  The specification work involves the design and formal description of behavioral interface specification languages (BISLs).