|
Department of Computer Science Iowa State University Birthplace of the Electronic Digital Computer |
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. 16th 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, “I3: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.
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).