Listing of Talks   Abstracts   

Listing of Talks

 
Abstracts

1. Dynamic Compressed Hyperoctrees with Applications.

Srinivas Aluru.

Hyperoctree is a popular data structure for organizing multidimensional point data. The main drawback of this data structure is that its size and the run-time of operations supported by it are dependent upon the distribution of the points. In this talk, I will present a new data structure termed the Distribution-Independent Adaptive Tree (DIAT), aimed at fixing the problems with hyperoctrees. DIAT tree is essentially a compressed hyperoctree that supports efficient search and update algorithms. I will present optimal algorithms for construction of DIAT trees and searching, insertion and deletion in DIAT trees. Applications of this data structure to the N-body problem and all nearest neighbors will be discussed.             BACK
 

2. Separating Classes.

Lance Fortnow.

One of the greatest challenges in theoretical computer science and computational complexity is to separate complexity classes. We have very few interesting cases where we can show that one class of languages strictly contains another other than by straightforward simulation and diagonalization. In this talk we look at the possibility of separating the complexity classes L (problems solvable in logarithmic space) and NP (problems solvable in nondeterministic polynomial time). While answering this question will not settle the famous P versus NP question, it would still separate two important complexity classes. We will discuss two recent approaches to this problem. The first approach tries to settle this question by trading off time by alternation. We show that if Boolean formula satisfiability, the seminal NP-complete problem, requires a small amount of time we can simulate a large number of alternations with a small amount of time. We can then contrast this with an extension of a result of Nepmonjascii showing that large number of alternations require a large amount of space. Combining these ideas yields new time-space tradeoffs for satisfiability and may lead to a separation of nondeterministic time (NP) and space (L). The second approach follows along the lines of Post's program. We will try to separate classes by looking at properties of classes. We examine some recent work how using autoreducibilities of complete sets may lead to the separation of NP and L.             BACK
 

3. TOPAZ: A Programming Environment for Parallel Software

Matthew O'Keefe

In this talk I describe our work in developing tools for parallel software development. TOPAZ performs program flow and data dependence analysis that allows optimizations to be performed across whole program regions, not just loop nests. These optimizations are critical for exploiting highly parallel computers with more than 10 processors. We have applied TOPAZ to 4 significant production codes in fluid dynamics and electromagnetics and report our results.          BACK
 

4. A Structured Communication and Synchronization Model for Task Parallelism

Bruno Raffin

The study of parallel programming models that allow to express communications and synchronizations structured by the syntax is an important problem. On MIMD architectures the model of parallel tasks communicating by message passing permits to develop high-performance programs. However, the cohabitation of two modes of control not integrated, the former dictated by synchronizations and the latter imposed by control structures, leads to side effects that prevent an easy control of the program semantics. In particular, programs are not guaranteed to be deterministic and deadlock free. The data parallel model, used for HPF for instance, allows to express a structured parallelism by imposing an ordering on the execution of the instructions that follows the syntactic structure of programs. Debugging and formal validation are so eased. Determinism and deadlock freedom are guaranteed. But at this time this model appears to be limited when considering irregular applications: present compilers have difficulties to manage irregularity while ensuring satisfactory performances. We present here an intermediate model that associates a structured expression of communications to a loosely synchronized execution model. It relies on a coding of the precedence of the instructions by a lexicographical ordering on multi-level counters called structural clocks. The introduction of several levels of counters allows to easily control the desynchronization of dynamic structures such as while loops. This model permits to express unpredictable and irregular dependence schemes, while guaranteeing deadlock free and deterministic programs. We prove that it is possible to define a synchronous programming model that provides a simple semantic vision favoring the control, the optimization and the formal validation of programs. The interest of this approach is illustrated by irregular applications stemming from sparse matrix computations, neural networks, data bases or real-time systems. Compared with a message passing library such as MPI, the developed implementations highlight good performances and substantial advantages for writing and debugging irregular applications. Papers related to these researches can be found at the following web address: http://jupiter.univ-orleans.fr/Lab-Info/Members/raffin/                BACK
 

5. NOTE: Cookies and lemonade will be served for the lecture

Mobile Computing and Global Information Sharing Process.

A.R. Hurson

The traditional notion of timely and reliable access to global information in a distributed or multidatabase system must be expanded. Users are becoming much more demanding in that they desire and sometimes even require access to information anytime, anywhere. The extensive diversity in the range of information that is accessible to a user at any given time is also growing at a rapid rate. This information can include data from legacy database systems, database systems, data warehouses, information services, and the almost limitless information on the Internet and World Wide Web. Furthermore, rapidly expanding technology is making available a wide breadth of devices through which access to this enormous amount of diverse data is possible. For example, the user may access information from a desktop workstation connected to a LAN, or from a laptop computer via modem, or from a hand held device via a wireless connection. All of these devices have different memory, storage, display, and computational power. This talk investigates various effects of mobile computing on database issues and proposes a new global information sharing environment. Finally, several research directions within this new environment is addressed.             BACK
 

6. Virtual Reality as a New Discipline in Science, Engineering and Art.

Carolina Cruz-Neira.

Since the early 1980s, scientists and engineers have been working on developing virtual reality (VR) technology and constantly exploring its potential and benefits for a variety of fields, ranging from medicine to engineering to entertainment. These groups have provide the field with very strong theoretical and applied technical skills to accomplish the hard task of turning the concept of VR into a reality. However, we need to acknowledge the enthusiastic participation of artists and entrepreneurs, who have had a significant impact on the development of the technology towards more accessible and easy to use implementations. They have provided a rich pool of ideas and applications that have motivated the technology to leave research laboratories and reach the general public. More recently, we are seeing a growing interest coming from industry about VR applications and its benefits. VR technology has proven itself and it is already being accepted that VR has a great potential in many disciplines. The challenge now is on how to apply virtual reality, and for that, we need to understand virtual reality independently of today's technology, we have to be aware of the limitations imposed by the current technology, and, we require to establish design approaches that will lead to the creation of successful virtual experiences. This talk explores the concept of VR and how science, engineering and art are integrated to successfully develop effective applications using VR technology.             BACK
 

7. Integrating Computer Vision into Robot Motion Planning

Rajeev Sharma

The configuration space (C-space) has been used as a unifying computational framework for defining geometric motion planning problems in robotics. However, for a robot operating in an uncertain and dynamic environment when sensing plays a critical role, the traditional C-space approach may be inadequate. For example, to utilize the sensor feedback effectively, the motion plans should also account for properties of the sensed data. We introduce a general motion planning framework using the concept of perceptual control manifold (PCM) that augments the C-space with a parameter space defined on sensor data. For example, the PCM could involve a set of image features that are used for visually controlling a robot. The framework allows the motion plans to incorporate various constraints and optimality criteria derived from the robot kinematics, the control system, and the sensing mechanism. In computer vision, one such constraint is the ability of the camera system to perceive the instantaneous motion of an object in its field of view. We formulate this constraint in terms of the PCM and show how it leads to better motion plans. We then discuss related issues including representation and learning of the PCM and active vision. We will also briefly describe some ongoing projects where computer vision is being used for building novel interfaces to virtual reality.             BACK



8. JML: A Java Modeling Language

Gary Leavens & Al Baker

JML is a behavioral interface specification language tailored to Java. It also allows assertions to be intermixed with Java code, as an aid to verification and debugging. JML is designed to be used by working software engineers, and requires only modest mathematical training. To achieve this goal, JML uses Eiffel-style assertion syntax combined with the model-based approach to specifications typified by VDM and Larch. However, JML supports quantifiers, specification-only variables, frame conditions, and other enhancements that make it more expressive for specification than Eiffel. This talk will discuss the goals of JML, the overall approach, and describes the language through examples.             BACK



9. Exploiting Known Geometric Structure and Scene Dynamics in Visual Servo Control

Seth Hutchinson


Many of the difficult issues in visual servo control derive from the difficulty of the associated computer vision problems. In this talk, I will describe methods for exploiting geometric and probabilistic information to improve the performance of the vision component of a visual servo system. In particular, the talk will address recent work on motion perceptibility and on exploiting scene dynamics for 3D tracking of moving objects (including both rigid and articulated objects). Motion perceptibility provides a quantitative measure of the ability of a camera setup to observe the changes in image features due to relative motion. It has many applications in evaluating a robot hand/eye setup with respect to the ease of achieving vision-based control, and steering away from singular configurations. It can be combined with the traditional notion of manipulability, into a composite perceptibility/manipulability measure. After presenting the formulation for motion perceptibility, we will describe a number of its applications, including optimal camera placement, active camera trajectory planning, robot trajectory planning, and feature selection for visual servo control. The robustness of visual tracking can be further improved by using explicit models for the objects being tracked. Geometric and dynamic models describe what feature velocities to expect, and what those velocities reveal about object motion. We characterize the tracking problem as one of parameter estimation from incomplete feature tracking data, and apply the Extended Kalman Filtering algorithm to the situation. Having an object model integrated into the tracking system over-constrains feature trackers, so that erroneous tracking results are selectively ignored and feasible tracking results are used to optimally update the object configuration estimate. Furthermore we can directly exploit the information contained in the shape of the correlation surface to weight observations against predictions in a manner that naturally compensates for degraded feature extraction, and to some extent for external occlusion.             BACK



10. Algorithms for gene identification by sequence inspection

Volker Brendel


High-throughput genome projects generate an abundance of genomic sequence data that must increasingly be annotated by computer algorithms. I describe several algorithms currently in use and in development in our group. These algorithms try to locate exons and introns of potential genes either from a genomic sequence input alone or by maximizing similarity with known proteins. I will try to give a perspective on open problems.             BACK

---

Back to the Com Sci Colloquium page.

Contacts

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

• Les Miller lmiller@cs.iastate.edu
• Akhilesh Tyagi tyagi@cs.iastate.edu
• Prem Uppuluri

(Top)

---