Colloquium Series Spring 2000

Prof. Snehasis Mukhopadhyay

We will consider several interconnection models for developing systems of multiple automated decision-makers (agents), where the agents are represented as artificial neural networks, other learning modules, or, decentralized adaptive controllers. Algorithms will be presented for decision-making, control, and adaptation in these systems. We will also present on-going work on the development of multi-agent information filtering systems which identify information within very large volumes of data that is most relevant to some specified set of criteria (e.g., a given user's personal interests).

Dr. Saswati Sarkar

This presentation is about our recent research in fairness and congestion control in multicast networks with multirate capabilities. In multirate transmission, the source hierarchically encodes the signal into several layers, and receivers subscribe to appropriate number of layers. It may or may not be possible to allocate fractional layers, depending on the system constraints. We present distributed algorithms for computation of fair service rates, when fractional layers can be allocated. Fair allocation of network resources become significantly more challenging, if fractional layers cannot be allocated. We show that traditional fair allocations either do not exist, or are computationally NP-hard in this case. We introduce a new notion of fairness, maximal fairness for such scenarios. Maximally fair rate allocation is polynomial complexity computable and has many intuitively appealing fairness properties. Next, we introduce utility functions connecting service rates with quality of service, and discuss fair allocation of arbitrary utilities. Computation of fair rates is not always possible on account of insufficient knowledge of system parameters, and message exchange overhead limitations. For this purpose, we present a scheduling policy which attains fair rates, without computing them beforehand. Towards the end of this talk, I shall discuss congestion control via routing and scheduling, and present a throughput optimal congestion control scheme for multicast networks.

Prof. Gary Benson

The ultimate goal of the human genome project is to understand the functioning of living organisms at the molecular level. Such understanding holds enormous promise for early detection and treatment of human disease. The first step has been to sequence the DNA of a variety of organisms. Subsequent interpretation of function will depend in large part on computational and mathematical analysis. One very informative approach is the search for repetitive patterns.

DNA molecules are subject to a variety of mutational events. One of the less well understood is tandem duplication. In this process, a stretch of nucleotides is duplicated to produce two or more adjacent copies, resulting in a tandem repeat. Over time, individual copies may undergo additional, uncoordinated mutations so that typically, only approximate tandem copies are present./p>

Tandem repeats occur frequently in the human genome, including in the centromeres and telomeres which are important chromosomal components. They have been shown to cause inherited human diseases, may play a variety of regulatory and evolutionary roles, and because of their polymorphic character, are important laboratory tools for genetic linkage analysis and DNA fingerprinting. Accurate characterization of the properties of tandem repeats has been limited by the inability to easily detect them. In this talk I will discuss an efficient algorithm for detecting tandem repeats in genomic sequence data. Detection is based on k-tuple matching and a collection of statistical filtering criteria. Current problems in the analysis of tandem repeats will also be discussed.

Dr. Xiong Wang

In this talk, I will present a framework for finding information (more precisely, active patterns) in three dimensional (3D) graphs. Each node in a graph is an undecomposable or atomic unit and has a label. Edges are links between the atomic units. Patterns are rigid substructures that may occur in a graph after allowing for an arbitrary number of whole-structure rotations and translations as well as a small number of edit operations in the patterns or in the graph. The three possible edit operations include inserting a node, deleting a node, or relabeling a node. The proposed method is based on the geometric hashing technique which hashes node- triplets of the graphs into a 3D table and compresses the label-triplets in the table. To demonstrate the utility of our algorithms, we discuss two applications of them in scientific data mining. We also extend our algorithms for processing a class of similarity queries in databases of 3D graphs.

Prof. Murali Sitaraman

A central objective of software engineering is to enable a modular style of software construction using components built by different programmers. To use a component built by someone else effectively, a typical programmer attempts to predict the behavior of that component informally using mental, metaphorical models. These models are usually much simpler than those that might be required to understand detailed implementation of the component. This talk explains why and how this modeling process should be formalized. It presents a modular and sound system for construction of predictable, and practical component-based software.

Prof. Yang Xiang

Bayesian networks (BNs) provide a coherent and effective formalism for modeling a probabilistic problem domain. The domain dependencies are modeled by a directed acyclic graph where nodes correspond to domain variables, links signify direct dependencies, and the graphical separation represents conditional independence. The strength of the probabilistic dependencies are quantified by localized probability distributions. BNs are increasingly being used for probabilistic inference in artificial intelligence.

Multiply sectioned Bayesian networks (MSBNs) are an extension of BNs for flexible modeling and distributed probabilistic inference. The framework is particularly suited to very large problem domains which can be partitioned naturally into distributed subdomains. A MSBN models the subdomains by a set of Bayesian subnets. Once modeling is complete, a set of verification and compilation operations converts a MSBN into a runtime model to support effective inference computation. Inference can be performed using thesesubnets in a distributed fashion while answers to queries are identical to what would be obtained in a centralized setting.

We consider application of MSBNs to multiagent equipment monitoring and diagnosis. A large and complex equipment usually consists of multiple components physically distributed. Each component can be modeled as a subnet in a MSBN. The subnet models the causal dependency among devices and their input/output, as well as the normal and faulty behavior of each device. Recent advance in the MSBN theory shows that the coherence of inference can be maintained even when the internal model for each component is kept private from others. Hence a monitor/diagnosis system can be integrated for a very large equipment from submodels built by different vendors with vendors' know-how protected.

Prof. Sanjay Kumar Madria

The growth of the internet has dramatically changed the way in which information is managed and accessed. This information is placed independently by different organization or individual users, thus documents containing related information may appear at different web-sites.

To provide users powerful and friendly web data management tools for accessing information on the web, we have built a warehouse of web data to provide effective mechanisms to manipulate this information of interest to garner additional useful information. The talk deals with the querying and management of unstructured and semi-structured data. In particular, I will discuss building a web warehouse using the database approach of managing and manipulating the warehouse containing strategic information coupled from the web. This includes discussion on web data model, web algebra, query language and knowledge discovery in the context of WHOWEDA (Warehouse of Web Data) project. The key objective is to design and implement a web warehouse that materializes and manages useful information from the web. If time permits, my talk may include some overview discussion on web change management and web data mining.

Ron Wolf

Three topics of interest to Statisticians, Software Developers, and Network Engineers will be covered. First, we'll look at an overview of Keynote's unique business and solutions. During this overview we'll take a quick look at the architecture of Keynote's world wide distributed measurement infrastructure.

Next, we'll dig into (hopefully live) the variety of graphs and other data visualizations that can be created with Keynote's myKeynote, a web based reporting tool.

As you might imagine, measuring the internet, the largest most complex mechanisim ever built, requires many unique, and sometimes quite fascinating, implementations. We will conclude the presentation by discusing the need for and the design of an surprising algorithm developed by his team at Keynote that we call the Unscheduler.

Dr. Terran Lane

With the recent phenomenal growth of the availability and connectivity of computing resources and the advent of e-commerce, more valuable and private data is being stored online than ever before. But with greater value and availability comes greater threat. In this talk we examine the information security problem of anomaly detection --- recognizing the occurrence of ``out of the ordinary'' events which may prove to be hazardous. We evaluate this problem as a machine learning task and describe the application of two machine learning techniques: instance-based learning (IBL) and hidden Markov models (HMMs). This work focuses on anomaly detection at the user level (as opposed to the network or system call level), which introduces a number of interesting and complex issues from a machine learning standpoint. In particular, we explore privacy, resource constraints, non-stationarity (a.k.a. concept drift), and performance issues and give empirical analyses based on real user data. We close with some thoughts on extensions to this work and on other areas of application.

Dr. Costas Busch

We present new hot-potato communication algorithms for the mesh network. In hot-potato routing, the nodes of the network have no buffer to store messages in transit, thus causing the messages to move from node to node each time, namely, the messages are treated like "hot-potatoes." Hot-potato routing has immediate applications in optical networks, where the messages are made from light which cannot be stored in any medium. An interesting class of hot-potato routing algorithms are the so called "greedy" algorithms in which the messages simply try to get closer to their destinations. It has been observed that the greedy algorithms perform extremely well in practice, however, there has been no adequate formal analysis that could explain this good behavior. The hot-potato algorithms we present in this talk are greedy with improved theoretical bounds, which give the first formal explanation of the good behavior of greedy algorithms. A key technique in our algorithms is the use of randomization to adjust message priorities.

Prof. Eunice E. Santos

A parallel algorithm is represented by three important items: (a) initial data distribution, (b) communication schedule, and (c) local computational tasks. Depending on the constraints imposed on these three factors, different problems arise which might require distinct approaches to handle them. In this talk, we will discuss the issues involved in determining and designing optimal and/or efficient parallel numerical algorithms based on problem classification of these three criteria.

One goal of utilizing such a classification is to determine ways to optimize existing algorithms for specified parallel machines and/or general models and to provide software tools to automatically perform the optimization. Working with general models may further aid algorithm designers by taking into account issues such as portability.

In this talk, we shall present a mathematical framework for classifying parallel algorithms and its application to parallel numerical computing. We shall also discuss results we have obtained working based on this framework.

Prof. Xiaoqiu Huang

A shotgun sequencing strategy is widely used to determine the sequence of a segment of DNA. In this strategy, multiple copies of the DNA segment are randomly cut into small pieces. The sequence of each piece is read by an automated sequencing machine, which can produce a sequence read of length 500 to 1000 letters. The sequence of the large DNA segment is reconstructed by a computer program from short sequence reads. The sequence assembly problem is to assemble short reads into long sequences. A typical instance of the problem contains 1,000 to 5,000 reads with a total of 1 to 5 million letters.

There are a number of difficulties with solving the sequence assembly problem. DNA consists of two complementary strands. It is not known whether a read is from the plus strand or the minus strand of the DNA. A good portion of a read contains errors at a rate of 1% to 5%. Much more errors occur at the ends of a read. A read sometimes contains a bit of DNA at its left end, which is not from the DNA segment to be sequenced. This bit of DNA comes from a cloning vector or other source. A read occasionally consists of two pieces which are from different locations of the DNA segment. This read is called a chimeric read. Another difficulty to the assembly program is that the DNA segment contains repetitive regions, which are highly similar in sequence.

We have developed three generations of the CAP sequence assembly program (Huang, 1992; Huang, 1996; Huang and Madan, 1999). The CAP program works in three major phases. In phase 1, overlaps between reads are computed. In phase 2, reads are joined to form contigs in decreasing order of overlap scores. A contig is an ordered list of overlapping reads. In phase 3, a multiple sequence alignment of reads is constructed and a consensus sequence is computed for each contig. A number of computational techniques are used to make the CAP3 program accurate and efficient. In this talk, I will describe the computational techniques used in CAP3 for addressing the difficulties mentioned above.

Prof. Xiaoqiu Huang

In this talk, Dr. Huang will describe the 3rd generation of the CAP sequence assembly program. The CAP3 program includes a number of improvements and new features. The program has a capability to clip 5' and 3' low-quality regions of reads. It uses base quality values in computing overlaps between reads, constructing multiple sequence alignments of reads, and generating consensus sequences. It also uses forward-reverse constraints to correct assembly errors and link contigs. The strengths and weaknesses of CAP3 will also be discussed. The CAP3 program is useful in assembly of EST sequences without quality values. CAP3 has been used to assemble EST sequences at TIGR, NCBI, and EBI.

Prof. James J. Lu

Recent advances in compute-intensive reasoning techniques have made them viable approaches for implementing complex reasoning tasks. This talk explores the idea of compute-intensive meta-reasoning techniques as a way to further enhance the capabilites of reasoning procedures. Implementation of and preliminary experimental results with one such technique will be presented. Some connections to the speaker's prior work on Hybrid Knowledge Bases will be discussed to establish the broader context and scope for the research project.

Dr. R.N. Uma

We discuss, from both a theoretical and a practical perspective, the relationship between linear-programming based lower bounds and combinatorial lower bounds for some scheduling problems. We evaluate the performance of heuristics based on these lower bounds. Finally we discuss the implications for real-life scheduling problems based on experiments with actual application data.

(This is joint work with Martin W.P.Savelsbergh (Georgia Institute of Technology), Joel Wein (Akamai Technologies and Polytechnic University) and David P. Williamson (IBM T.J. Watson Research Center).)

Prof. Sviatoslav Braynov

I will present different models of multiagent cooperation:

• Stable multiagent contracts and plans: I will propose a formal model of stable against deviations multiagent plans and give sufficient conditions for stability.
• Dependence and power in multiagent plans, I will present a decision-theoretic model of power and dependence in multiagent interaction. According to the model almost every group activity, whether it is cooperation on exploitation, has its origins in resolving some dependence or power relation.
• Trust in E-commerce contracts. I will present a formal model of trust in multiagent negotiation. I will address the question of when should an agent trust another agent and to what degree trust should exist.

If time permits I will talk about:

• Social agents. I developed a model of social agents, i.e., agents which take into account other agents' preferences. Social agents can be pro-social and anti-social. I analyzed altruistic and envious agents as two generic types of social agents. I will provide sufficient conditions for preference balance in multiagent plans. Preferences are balanced if the agent who is providing help is altruistic enough to help and the agent who receives help is selfish enough to be helped.
• E-commerce auctions. I will prove that the Vickrey revenue equivalence theorem ceases to hold in some e-commerce applications. The failure of the revenue equivalence theorem means that different auctions yield different expected revenues. Therefore, auction designers should be careful when choosing auction rules.
• Representing and processing infinite belief hierarchies. I will address the problem of how infinite belief hierarchies can be represented in a computationally tractable way. I will generalize the technique of backward induction to the case of infinite belief trees.

Prof. Prasad Tadepalli

The most common paradigm of machine learning consists of propositional representation of examples and hypotheses, and a passive supervised learner. In contrast, human learning involves richer knowledge representations, and an active participation of the learner by asking questions and solving problems. In this talk, we relax the above common limitations of machine learning and consider active learning of first order horn programs. We show that non-recursive single-predicate horn programs are exactly learnable from examples when the learner can also ask questions. We generalize this algorithm and apply it to learning goal decomposition rules for planning. Instead of training examples of solved problems, the teacher only gives a set of graded exercises, which are solved by the learning program in the increasing order of difficulty. The program answers its own questions by making up new problems and trying to solve them using its hypothesized rules. We show empirical results in 2 planning domains, and conclude with the implications of our work to theories of human and machine learning.

Dr. Louxin Zhang

This work studies a set of string(or sequence) problems that are at the core of several biological problems such as discovering potential drug targets, creating diagnostic probes, finding universal primers and conserved sequences. All these problems reduce to the task of finding a pattern that, with some error, occurs in one set of strings (the Closest String Problem) and does not occur in another set (Farthest String Problem). In this paper, we break down the problem into several subproblems and prove the following results.

1. There is a polynomial time approximation scheme for the Farthest String Problem based on a linear programming relaxation technique.
2. There is a polynomial-time 4/3-approximation algorithm for the problem of finding a string that is close to each string (rather than its substring) in a set. Using this algorithm, we also provide an efficient heuristic algorithm for the Closest String Problem.
3. The problem of finding a string that is at least Hamming distance d from as many strings in a set as possible, cannot be approximated within n^b in polynomial time for some fixed constant b unless NP=P.
4. There is a polynomial-time 2-approximation for finding a string that is both the Closest String to one set, and the Farthest String from another set.

This is a joint work J. Lanctot, M. Li, B. Ma and S. Wang.

Dr. Andrew Miner

High-level models are excellent tools for describing system behavior. Model analysis has a wide variety of applications, including verification of asynchronous circuits, protocols, and distributed algorithms, and performance evaluation of web servers, communication systems, and manufacturing systems. In practice, however, the analysis of such systems is severely limited by the large number of states of the system.

This talk presents techniques for dealing with the state explosion problem that make use of multi-valued decision diagrams (MDDs). Armed with this data structure and efficient manipulation routines for MDDs, we can verify models containing an enormous number of reachable states (10^600 in some cases) on a typical desktop machine.

We describe the concept of MDDs, illustrate examples of their efficiency, and discuss their application in the area of performance evaluation of complex computer systems. When the underlying process of the system is a continuous-time Markov chain, we can compute approximate steady-state probabilities by using a new aggregation technique that is based on the MDD representation of the state space. This technique requires only a small fraction of the memory and CPU required for an exact solution, and allows for performance studies of very large systems.

Prof. Richard M. Karp

A fundamental problem in molecular biology is to determine how genes and proteins work in concert to control the functioning of living cells. This talk will be a survey of algorithmic approaches to this problem, drawn from the fields of combinatorial optimization, statistics, machine learning, dynamical systems and stochastic simulation.

Proteins are the active elements that perform cellular functions. Proteins are manufactured by transcribing genes into mRNA and then translating mRNA into protein. The rates at which specific transcription and translation processes take place depend on the environment of the cell and on the abundances and spatial distribution of different species of mRNA and protein. Thus the cell can be viewed as a complex feedback control system.

The DNA microarray is a recently developed tool capable of measuring the transcription rates of thousands of genes in a single experiment. Technology is being developed to measure large numbers of protein abundances in a single experiment. Such high-throughput experimental tools will give a panoramic view of the state of a tissue or collection of cells. By measuring transcription one can distinguish normal tissue from neoplastic tissue, or cells treated with a drug from untreated cells. By measuring the effects of artificially inducing or inhibiting the transcription of particular genes one can explore the structure of genetic regulation.

This talk will be concerned with the acquisition and interpretation of large scale gene expression data. We will discuss algorithms for clustering or classifying tissues on the basis of their gene expression patterns, as well as algorithms to efficiently learn the structure of genetic regulatory networks on the basis of judiciously chosen experiments.

Dr. Antonio Piccolboni

Pedigree analysis is a central component of many current efforts to locate genes that contribute to diseases or to valuable traits. The analysis usually involves solving one of two very computation-intense problems. We analyze the complexity of these two problems. Surprisingly, we show that both problems are computationally intractable even in the very simple setting of single-locus genotype and inbreeding-free pedigrees.

(This is joint work with Dan Gusfield)

Dr. Alexander Dekhtyar

Dyreson and Snodgrass have drawn attention to the fact that in many temporal database applications, there is often uncertainty present about the start time of events, the end time of events, the duration of events, etc. When the granularity of time is small (e.g. milliseconds), a statement such as ``Packet p was shipped sometime during the first 5 days of January, 1998'' leads to a massive amount of uncertainty (5 * 24 * 60 * 60 * 1000) possibilities. Past attempts to deal with uncertainty in databases have been restricted to relatively small amounts of uncertainty in attributes. Dyreson and Snodgrass have taken an important first step towards solving this problem.

In this work, we first introduce the syntax of Temporal-Probabilistic (TP) relations and then show how they can be converted to an explicit, significantly more space-consuming form called Annotated Relations.

Next, we present a Temporal Probabilistic Algebra (TPA) and Theoretical Annotated Theoretical Algebra. The former operates on TP-relations, while the latter extends classical relational algebra onto Annotated relations. We show that our definition of the TP-Algebra provides a correct implementation of TATA despite the fact that it operates on implicit, succinct TP-relations instead of the overwhelmingly large annotated relations. We also study query equivalence in TPA.

Finally, we report on timings for an implementation of the TP-Algebra built on top of ODBC.

Dr. Markus Lumpe

In this talk we present a formal language for software composition that is based on the Pi-calculus. More precisely, we present the PiL-calculus, a variant of the Pi-calculus in which agents communicate by passing extensible, labeled records, or so-called "forms", rather than tuples. This approach makes it much easier to model compositional abstractions than it is possible in the plain Pi-calculus, since the contents of communication are now independent of position, agents are more naturally polymorphic since communication forms can be easily extended, and environmental arguments can be passed implicitly. The PiL-calculus is developed in three stages: (i) we analyse whether the Pi-calculus is suitable to model composition abstractions, (ii) driven by the insights we got using the Pi-calculus, we define a new calculus that has better support for software composition (e.g., provides support for inherently extensible software construction), and (iii), we define a first-order type system with subtype polymorphism that allows us to check statically an agent system in order to prevent the occurrences of runtime errors.

Prof. Robyn Lutz

A software product line is a group of similar products that share a base architecture and a common, managed set of features satisfying the needs of a market or mission area. Anticipated advantages include reduced time to market, potential for mining legacy systems, reduced workload for system integration, and, perhaps, reduced risk. However, the current extension of product lines to safety-critical applications (e.g., turbine control, train scheduling, spacecraft) requires improved architectural analysis techniques that focus on safe reuse. This talk describes recent results from a collaborative investigation with Dr. Gerald Gannod, Arizona State University, into architectural analysis of existing product line architectures. A "good" product line architecture is first defined in terms of those quality attributes required by the particular product line under development. The architecture is then evaluated against these criteria by both manual and tool-supported methods. The phased approach provides a structured analysis of an existing product line architecture using: (1) formal specification of the architecture, (2) analysis of scenarios to exercise the architecture's support for required variations among the product line members, and (3) model checking of critical behaviors at the architectural level that are required for all systems in the product line. Results of an application to a software product line of spaceborne telescopes are used to explain and evaluate the approach.

Dr. Stephen Altschul

Multiple alignments of the sequences from a protein family can illuminate residues or sequence regions that are highly or completely conserved, and other regions where substantial variation is allowed. This information may be abstracted into what are variously called profiles, position-specific score matrices (PSSMs), or hidden Markov models (HMMs). It is generally easier to detect distant homologues by searching a database using a profile as query than by using a simple sequence, or even the set of sequences from which the profile was constructed. Profile search programs may be further enhanced by adding newly found relatives to the original multiple alignment, and iterating the process.

While all these ideas have been in circulation for many years, database search programs using profiles have until recently been slow, and their use has often required a fair amount of expertise. The PSI-BLAST program altered the terrain in several ways. First, it wedded the BLAST search heuristic to profile alignment, rendering profile searches almost as rapid as traditional protein similarity searches. Second, it fully automated the construction of profiles from the output of database searches. Third, by incorporating accurate estimates of statistical significance for profile alignments, it allowed automatic iteration.

While PSI-BLAST is easy to use, particular care must be taken not to misunderstand the meaning of the significance estimates it produces. However, properly deployed, PSI-BLAST has pushed back the edge of the "twilight zone" for sequence comparison methods that use no structural information.

Dr. Altschul's lecture is sponsored by the Plant Sciences Institute, the Lawrence H. Baker Center for Bioinformatics and Biological Statistics, the Bioinformatics and Computational Biology Graduate Program, and the Integrative Graduate Education and Research Training Program.

Dr. Oliver Eulenstein

Evolution proceeds via gene duplication and modification; it is through their successive application that nature has created the vast diversity of current genes. Knowing precisely when ancestral gene duplications occurred is indispensable for reconstructing reliable evolutionary relationships. In turn, this allows us to refine the prediction of a genetic function. For example, this method allows us to illuminate the evolutionary history of vision.

We designed an algorithm that extends a successful yet informal model built by biologists. This algorithm predicts gene duplications by exploiting inconsistencies in two phylogenetic trees, a gene tree and a species tree. The gene tree represents the phylogeny of a set of current genes. The species tree represents the phylogeny of the species containing those genes.

As output, the algorithm recalculates the gene tree, modified by the predicted gene duplications. For all practical applications, this algorithm runs in linear time in the size of the given gene tree.

Based on this theoretical work, we built the GDPT (Gene Duplication Prediction Tool). GDPT is written as a JAVA applet, so biologists can easily access it via the Internet to study phylogenies with gene-duplications.

GDPT predicts gene duplications from already constructed phylogenies. We are currently working on reconstructing perfect phylogenies from incomplete characters.

Prof. Kirk Pruhs

In the context of approximating NP-hard optimization problems, and in the context of online problems, one compares the performance of a limited algorithm (one that can only run in polynomial time, and one that has no knowledge of the future, respectively) against a omnipotent clairvoyant adversary. If the competitive/performance ratio of a problem is O(1) then this is generally considered a positive result. Resource augmentation is an analysis technique for those problems where the competitive ratio is omega(1). In resource augmentation analysis, the limited algorithm is given more resources, in a scheduling problem this might be faster processors or more processors, than the adversary. I will explain the rationale behind resource augmentation analysis, and survey the literature on these types of results. This talk is aimed at a general audience.

Prof. Alexander received his MSEE in 1988 from the University of Kansas. After holding research positions with the Telecommunications and Information Sciences Lab and The Center for Excellence in Computer Aided Systems Engineering, both at the University of Kansas, he earned his Ph.D. in Electrical and Computer Engineering in 1992. From 1992 to 1999, he was a professor at the University of Cincinnati, where he founded and was director of The Knowledge-Based Software Engineering Laboratory. Prof. Alexander returned to the University of Kansas in June 1999 and is a professor in the EECS Department and the Information and Telecommunication Technology Center. His current research focuses on formal methods and systematic design practices in software engineering and digital design.

Visit Prof. Perry Alexander's hompage here.

BACK

Prof. Gary Leavens

Prof. Gary Leavens received his PhD in Computer Science from MIT in 1989. He is currently an Associate Professor in the Department of Computer Science at Iowa State University. The long term goal of his 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, and ways to check that the solutions are correct. In pursuing this goal, Prof. Leavens has worked in two main areas: formal methods and programming languages.

Visit Prof. Gary Leavens's hompage here.

BACK

Prof. Snehasis Mukhopadhyay

Dr. Mukhopadhyay is an Assistant Professor of Computer and Information Science at the Indiana University Purdue University, Indianapolis. He received his Ph.D. from Yale University and was at General Motors research center previously. He is a member of the program committee of the 1999 IEEE International Symposium on Intelligent Systems/Intelligent Control, and the 1999 Conference on Information and Knowledge Management. He is also a member of the IEEE Technical Committee on Intelligent Control. Dr. Mukhopadhyay is a recipient of the National Science Foundation CAREER award.

Visit Prof. Snehasis Mukhopadhyay's hompage here.

BACK

Dr. Saswati Sarkar

Saswati Sarkar obtained her Bachelor of Engineering from Jadavpur University in 1994 and Master of Engineering from Indian Institute of Science, Bangalore, in 1996. She joined the Phd program in Department of Electrical and Computer Engineering in University of Maryland, College Park in 1997 , and is currently a Phd candidate there. She was a summer student at IBM T. J. Watson Lab in 1998 summer. She received the Motorola Medal for the best of Master of Engineering student in the division of Electrical Sciences in Indian Institute of Science. Her current research interests are in resource allocation and quality of service provisioning in high speed networks.

Visit Dr. Saswati Sarkar's hompage here.

BACK

Prof. Gary Benson

Prof. Benson is an Assistant Professor at the Mount Sinai School of Medicine. He is currently working in algorithm development for DNA sequence analysis, with an emphasis on detection and analysis of repeating patterns in DNA. He received his Ph.D. in Computer Science in 1992 from the University of Maryland.

Visit Prof. Gary Benson's hompage here.

BACK

Dr. Xiong Wang

Xiong Wang received his MS in computer science from Fudan University in Shanghai, China, and the Ph.D. degree in computer science from New Jersey Institute of Technology. During the last 3 years, Dr. Wang has published 8 papers in refereed conferences and journals such as ACM SIGKDD and Knowledge and Information Systems. Dr. Wang was a referee for ACM CIKM'98, ACM CIKM'99, Information Sciences, and Knowledge and Information Systems. He is a member of ACM and IEEE.

Visit Dr. Xiong Wang's hompage here.

BACK

Prof. Murali Sitaraman

Murali Sitaraman is an Associate Professor of Computer Science at West Virginia University, where he directs the Reusable Software Research Group. He received a Ph. D. in Computer & Information Science from The Ohio State University in 1990. His publications and interests span the spectrum of foundational, practical, and educational aspects of software engineering. Sitaraman served as the program chairman of the IEEE Computer Society Fourth International Conference on Software Reuse in 1996 and as the Co-Chairman of the Workshop on Foundations of Component-Based Systems in 1997. He co-guest edited a special section on software reuse for the IEEE Transactions on Software Engineering in 1997. Sitaraman is a member of the ACM and IEEE Computer Society.

Visit Prof. Murali Sitaraman's hompage here.

BACK

Prof. Yang Xiang

Dr. Yang Xiang is an Associate Professor of Computer Science at the University of Regina, where he directs the Normative Intelligent Decision Support Systems Laboratory. He received a Ph. D. from University of British Columbia in 1992. His research areas are in distributed reasoning and decision making with uncertain knowledge, multiagent systems and data mining. They are about building intelligent distributed systems. The main theoretical results were presented in Artificial Intelligence and Machine Learning in recent years. A project to develop a distributed monitor/diagnosis system for a chemical plant is ongoing. Prof. Xiang is writing a book on distributed probabilistic reasoning during his current sabbatical at UMass, Amherst. He is also involved in a new research team on e-commerce with people in several Canadian universities.

Visit Prof. Yang Xiang's hompage here.

BACK

Prof. Sanjay Kumar Madria

Sanjay Madria has received his Ph.D. in Computer science from Indian Institute of Technology, Delhi, India in 1995. He is currently Visiting Assistant Professor in the Department of Computer Science at Purdue University. In the past, he was with Center for Advanced Information Systems, Nanyang Technological University, Singapore. He has collaborative projects with universities in Australia, Singapore, Japan and USA. He has published many papers in the areas of web warehousing, mobile computing and nested transaction management and performance issues. He was the workshop organizer and PC chair for "Internet Data Management" workshop at Florence, Italy held in Sept. 1999. He is guest-Editor of WWW Journal and Data and Knowledge Engineering for Sp. Issues on Web data management and data warehousing. He is Chair for EC&WEB 2000 conference to be held in London in Sept. 2000. He is serving as PC member of various database conferences and workshops and reviewer for many database journals. He is a regular panelist in NSF. He is giving an invited tutorial on web warehouseing in EDBT'2000.

Visit Prof. Sanjay Kumar Madria's hompage here.

BACK

Ron Wolf

Ron Wolf is Senior Director of Engineering for Keynote Systems. At Keynote we measure internet performance. It's quite a challenging task. For instance, right now, 24 hours a day, we are taking and storing and processing nearly 1M measurements/hour. Nothing quite like this has ever been done. There is a wealth of information in our data. Our customers are the largest of the e-commerce field. Customers such as Microsoft, Dell, Amazon, and Schwab; over 800 of them. We have built an interesting and very real business. We went public last Fall and the current valuation of the company is nearly $3B (today anyway :-). We have a solid business model and rapidly growing revenue. With the recent hacker attacks on major web sites, you may have read about us in the news. In Feburary alone Keynote has had front page coverage in the Wall Street Journal, USA Today, and the San Francisco Chronicle. Keynote is growing very rapidly ( 52% revenue increase last quarter alone!). Unlike many internet companies, Keynote has a very solid business based on the subscription sales of our data. Nowhere else can you find the wealth of web performance data that is captured in our 500M row database.

Visit Ron Wolf's hompage here.

BACK

Dr. Terran Lane

Terran Lane is a Ph.D. student in the Machine Learning Laboratory at Purdue University, where he studies time series analysis. In collaboration with the Center for Education and Research in Information Assurance and Security (CERIAS) he studies applications of ML time series analysis techniques to information security issues. He received his Bachelor's degree in computer and electrical engineering in 1994 from the Purdue department of Electrical and Computer Engineering and immediately entered the graduate program on the Purdue Presidential Honors Fellowship. His research interests include modeling of non-stationary time series data, human behavioral modeling, classifier performance evaluation, and anomaly detection.

Visit Dr. Terran Lane's hompage here.

BACK

Dr. Costas Busch

Busch is currently a Ph.D. student in the Department of Computer Science of Brown University. The focus of his Ph.D. research has been on the area of distributed computing where he studied distributed data structures and routing algorithms for communication networks. In 1995 he obtained a MS degree in the area of digital design and computer architecture from the department of Computer Science at University of Crete, Greece. In 1991 he received his Bachelor's degree from the same department.

Visit Dr. Costas Busch's hompage here.

BACK

Prof. Eunice E. Santos

Eunice E. Santos is an Assistant Professor in the Department Electrical Engineering and Computer Science at Lehigh University. She received a Ph.D. in Computer Science at the University of California, Berkeley in 1995. She has also obtained B.S. and M.S. degrees in both Mathematics and Computer Science. Her research interests include: parallel & distributed computing, scientific & numerical computing, and algorithms & complexity. Dr. Santos has over 30 publications and has been funded through NSF, ARO, and AT&T. She is a current NSF CAREER awardee.

BACK

Prof. Xiaoqiu Huang

Dr. Huang is a principal scientist at Paracel, Inc in Pasadena, CA, and an associate professor at Keck Graduate Institute in Claremont, CA. He has developed a number of computer programs for analysis of DNA and protein sequences, which include a local sequence alignment program (SIM), a multiple sequence alignment program (MAP), a DNA sequence assembly program (CAP), and a set of gene finding programs (AAT). Some of his programs are used to analyze genomic DNA sequences from large-scale genome projects.

BACK

Prof. Xiaoqiu Huang

Dr. Huang is a principal scientist at Paracel, Inc in Pasadena, CA, and an associate professor at Keck Graduate Institute in Claremont, CA. He has developed a number of computer programs for analysis of DNA and protein sequences, which include a local sequence alignment program (SIM), a multiple sequence alignment program (MAP), a DNA sequence assembly program (CAP), and a set of gene finding programs (AAT). Some of his programs are used to analyze genomic DNA sequences from large-scale genome projects.

BACK

Prof. James J. Lu

James Lu received his Ph.D from Northwestern University in 1992. He is currently an Associate Professor of Computer Science at Bucknell University, and has been a Visiting Professor at the Universities of Maryland (1994-95) and Karlsruhe (1996). His primary research interest is in automated reasoning techniques and their applications to data and knowledge bases.

Visit Prof. James J. Lu's hompage here.

BACK

Dr. R.N. Uma

Uma is finishing her Ph.D in Computer Science at Polytechnic University, Brooklyn and expects to graduate by July, 2000. She received her B.Sc degree in Mathematics from the University of Madras, Chennai (formerly Madras), India and her M.E. in Computer Science at the Indian Institute of Science, Bangalore, India. Her research interests are in resource allocation issues in communication networks and distributed systems, scheduling theory and datamining.

Visit Dr. R.N. Uma's hompage here.

BACK

Prof. Sviatoslav Braynov

Braynov obtained his Ph.D. from the Computer Center of Russian Academy of Sciences. At present Braynov is a research associate at Washington University, St. Louis, MO and assistant professor at the Institute of Mathematics and Computer Science, Bulgarian Academy of Sciences (on leave for 2 years). His background is in computer science, mathematics and economics. His research interests include e-commerce, multiagent systems and artificial intelligence. Braynov has presented papers at the first ACM Conference on E-commerce, American National Conference on AI, European Conference on AI, COLING, etc.

BACK

Prof. Prasad Tadepalli

Dr. Prasad Tadepalli is an Associate Professor in Computer Science at Oregon State University. He has a Ph.D. in Computer Science from Rutgers University, and has research interests in machine learning, computational learning theory, artificial intelligence, and cognitive science.

Visit Prof. Prasad Tadepalli's hompage here.

BACK

Dr. Louxin Zhang

Louxin Zhang obtained his Ph.D. from University of Waterloo in 1995. Currently he is a principle investigator and the head, Computational Biology Group, in BioInformatics Centre, National University of Singapore. He was awarded Lee Kuan Yew Research Fellowship in 1997. His current research is mainly in bioinformatics.

BACK

Dr. Andrew Miner

Miner received his BS in Computer Science and Physics in 1993 from Randolph-Macon college. He received his MS in Computer Science in 1995 from William and Mary. He plans to complete his PhD in Computer Science at William and Mary this spring.

Visit Dr. Andrew Miner's hompage here.

BACK

Prof. Richard M. Karp

Richard M. Karp was born in Boston, Massachusetts in 1935 and was educated at the Boston Latin School and Harvard University, where he received the Ph.D. in Applied Mathematics in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor of Computer Science, Mathematics and Operations Research at the University of California, Berkeley. From 1988 to 1995 he was also associated with the International Computer Science Institute (ICSI) in Berkeley. In 1995 he became a Professor of Computer Science and Engineering and an Adjunct Professor of Molecular Biotechnology at the University of Washington. This summer he will return to Berkeley as a University Professor. His principal appointment will be in Computer Science, and he will also hold appointments in Mathematics and Bioengineering. In addition, he will again be a research scientist at ICSI.

The unifying theme in Karp's work has been the study of combinatorial algorithms. His most significant work is the 1972 paper ``Reducibility Among Combinatorial Problems,'' which shows that many of the most commonly studied combinatorial problems are disguised versions of a single underlying problem, and thus are all of essentially the same computational complexity. Much of his subsequent work has concerned the development of parallel algorithms, the probabilistic analysis of combinatorial optimization problems, and the construction of randomized algorithms for combinatorial problems. His current research is concerned with strategies for sequencing the human genome, the physical mapping of large DNA molecules, the analysis of gene expression data, and other combinatorial problems arising in molecular biology.

Karp has received the U.S. National Medal of Science, the Harvey Prize (Technion), the Turing Award (ACM), the Centennial Medal (Harvard University) the Fulkerson Prize(AMS and Math. Programming Society), the von Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann Lectureship (SIAM) and the Distinguished Teaching Award (Berkeley). He is a member of the National Academy of Sciences, the National Academy of Engineering and the American Philosophical Society, as well as a Fellow of the American Academy of Arts and Sciences. He holds four honorary degrees.

BACK

Dr. Antonio Piccolboni

Antonio Piccolboni received a Ph.D. degree in Computer Science from the University of Milan in 1997. Since then, he has been a postdoctoral fellow at the University of California, Davis and the International Computer Science Institute. He also visited the Sandia National Laboratories. His interests include computational issues in protein folding, combinatorial chemistry and human genetics.

BACK

Dr. Alexander Dekhtyar

Alexander Dekhtyar is currently a Ph. D. student at the Department of Computer Science at the University of Maryland at College Park. He expects to recieve his Ph. D. degree in summer 2000. He recieved his undergraduate degree in Applied Mathematics and Computer Science from Tver State University, Russia. His current research interests are dealing with uncertain information in databases and artificial intellegence, agent-based systems information retrieval.

Visit Dr. Alexander Dekhtyar's hompage here.

BACK

Dr. Markus Lumpe

Dr. Markus Lumpe received his PhD. in Computer Science from the University of Berne, Switzerland. He is currently working as a post-doctoral research assistant in the Software Composition Group at the University of Berne. His major research interests are in programming languages, modern compiler construction, and component technology. His primary long-term goal is the development of a robust formal model to specify applications as composition of distributed components.

Visit Dr. Markus Lumpe's hompage here.

BACK

Prof. Robyn Lutz

Robyn R. Lutz is a senior engineer at Jet Propulsion Laboratory, California Institute of Technology. She is also an Affiliate Assistant Professor in the Department of Computer Science at Iowa State University, Ames, Iowa, where she teaches software engineering. Dr. Lutz has worked on spacecraft projects in fault protection, real-time commanding, and software requirements and design verification. Her research interests include software safety, software certification, safe reuse of product families, formal methods for requirements analysis, and fault recovery strategies for spacecraft.

Visit Prof. Robyn Lutz's hompage here.

BACK

Dr. Stephen Altschul

Biography currently unavailable.

BACK

Dr. Oliver Eulenstein

Oliver Eulenstein received his Ph.D. in Computer Science from the University of Bonn in 1998. Since then he has been a postdoctoral fellow associated with Dan Gusfield at the University of California Davis. In the 1999 academic year he has also held a lecturer position. His main research interest is computational biology. Currently, he is focusing on designing algorithms for constructing phylogenetic trees and adapting them for practical application.

Visit Dr. Oliver Eulenstein's hompage here.

BACK

Prof. Kirk Pruhs

Professor Pruhs earned a BS in computer science and mathematics from Iowa State in 1984 and a PhD from the University of Wisconsin in 1989. He is currently an associate professor of computer science at the University of Pittsburgh.

Visit Prof. Kirk Pruhs's hompage here.

BACK

---

Contacts

Thank you for visiting this page. Please send your suggestions and comments to one of us in the Computer Science colloquium committee.

• Soma Chaudhuri . chaudhur@cs.iastate.edu
• Giora Slutzki. slutzki@cs.iastate.edu
• Curtis Clifton. cclifton@cs.iastate.edu

(Top)

---

mayuresh@cs.iastate.edu