CSE 600 (Ongoing Research Seminar)

Samir R. Das joined the computer science department in SUNY, Stony Brook in Fall 2002 as an associate professor. Previously he was on the faculty of University of Cincinnati and University of Texas, San Antonio. He received his PhD from Georgia Tech in 1994. His earlier education was in India, from Jadavpur University and Indian Institute of Science. His research interests are in mobile and wireless networking, performance evaluation and parallel discrete event simulation.

He received the National Science Foundation's CAREER award in 1998, and currently serves as a lecturer in the distinguished visitor program of IEEE Computer Society. In 2001 he co-chaired the technical program committee of ACM MobiHoc, the premier conference on ad hoc networking and computing.

A mobile ad hoc network is an autonomous system of mobile hosts connected by wireless links. There is no static infrastructure such as base stations. If two hosts are not within radio range, all message communication between them must pass through one or more intermediate hosts that double as routers. Since the hosts are mobile the routing protocols must be adaptive and able to maintain routes in spite of changing network connectivity. In addition, the protocols must be of low-overhead because of low bandwidth of wireless links and limited battery power of the mobile hosts. Aside from routing, another challenging issue is designing medium-access control protocols for efficient access to the shared radio medium. This talk will introduce mobile ad hoc networks and their applications, describe prominent dynamic routing protocols and medium-access control protocols for ad hoc networks and comment on their performances.

This talk will be in tutorial style, targeted for beginning graduate students.

Himanshu Gupta graduated with a Ph.D. in Computer Science from Stanford University in 1999. After his doctoral studies, he worked in the industry for a couple of years. He received his B.Tech. in Computer Science and Engineering from IIT, Bombay in 1992.

His broad research interests are database systems and theory. In particular, his interests lie in data warehousing, data mining, and physical database design. In this context, he is interested in materialized views, (multiple) query optimization, knowledge discovery, data analysis, and design of algorithms.

A data warehouse is a repository (database) that integrates information extracted from various remote data sources, with the
purpose of efficiently supporting decision support queries. The information stored at the warehouse is in the form of database
tables, referred to as materialized views. The two core issues that arise in the design of a data warehouse are: (i) selection
of views to materialize, and (ii) incremental maintenance of materialized views. We will address these design issues and
present comprehensive solutions for both problems.

Towards the end of the talk, I would discuss some of the recent problems/projects that I am working on.

Scott D. Stoller is an Assistant Professor in the Computer Science Department at the State University of New York at Stony Brook.  His research interests span distributed systems, programming languages, and formal methods.  His primary research is on developing techniques and tools for design, optimization, and validation of distributed systems, focusing on concurrency, fault-tolerance, and security.  His research also includes work on program analysis, program optimization, and incremental computation.  He received his Bachelor's degree in Physics, summa cum laude, from Princeton University (1990) and his Ph.D. degree in Computer Science from Cornell University (1997).  He received an NSF CAREER Award (1999) and an ONR Young Investigator Award (2002).

The difficulty of finding errors caused by unexpected interleavings of threads in concurrent programs is well known.  Model checkers can pinpoint such errors and verify correctness but are not easily scalable to large programs.  A more scalable but less systematic approach is to transform a given Java program by inserting calls to a "scheduling function" at selected points.  The scheduling function either does nothing or causes a context switch.  The simplest scheduling function makes the choice blindly using a pseudo-random number generator; more sophisticated scheduling functions use heuristics to weight the choices. We try to insert as few calls as possible while still ensuring that for each reachable deadlock and assertion violation, there is a sequence of choices by the scheduling function that leads to it; thus, there is a non-zero probability of finding it by testing the transformed program, regardless of the scheduling policies of the underlying Java Virtual Machine.

Our starting point is the formalism  of Rough Sets, used for description of imprecise information. Rough Sets are
increasingly used in applications such as data mining and classification. Rough sets are usually specified by a special
kind of decision tables, admitting contradictory decisions. We show that the Definite Extended Logic  Programs (DXL Programs) can be seen as generalization of such tables, hence as a specification language for Rough Sets. As  DXL Programs compile easily to Prolog they provide  a uniform framework for specifying, querying and computing Rough Sets. The talk will give an informal presentation of the above mentioned ideas and will illustrate them by examples.

Yanhong Annie Liu is an Associate Professor in the Computer Science Department at the State University of New York at Stony Brook.  She received her BS degree from Peking University, MEng degree from Tsinghua University, and MS and PhD degrees from Cornell University, all in Computer Science.

Her primary research interests are in the areas of programming languages, compilers, and software systems.  She is particularly interested in general and systematic methods for improving the efficiency of computations.  This includes (1) program analysis and transformation techniques for incremental computation and for parallel and concurrent computation, (2) applications in optimizing compilers, language-based interactive systems, real-time and reactive systems, algorithm design, program development, and software maintenance, and (3) supporting tools and user interfaces that allow convenient and efficient implementation of program analyses and transformations and facilitate their applications.

She has strong other interests in database management, document processing, and distributed systems.  These include, in particular, database query optimization, incremental database view maintenance, intelligent information retrieval, efficient document processing, efficient property detection for distributed systems, and systematic approaches to improving fault-tolerance.  She has also worked on uncertainty reasoning and expert systems.

Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each new output incrementally by making use of the previous output rather than computing from scratch.  The basic ideas can be traced back at least to the analytic difference engine of Charles Babbage in the 19th century.  Methods of incremental computation have wide applications in computer software, ranging from programming environments to interactive document processing, from distributed systems administration to database view maintenance, and from optimizing compilers to program development methods.

This talk surveys methods and techniques for incremental computation, as well as its history and applications.  We will examine the major issues involved and then examine the methods and techniques according to three classes: incremental algorithms, incremental evaluation frameworks, and incremental-program derivation methods.

Time: Friday, October 25, 2002, 2:15pm
Speaker: Phil Bernstein, Microsoft Research 

Phil Bernstein is a researcher at Microsoft Corporation. Over the past 25 years, he has been a product architect at Microsoft and at Digital Equipment Corp., a professor at Harvard University and Wang Institute of Graduate Studies, and a VP Software at Sequoia Systems. During that time, he has published over 100 articles on the theory and implementation of database systems, and coauthored three books, the latest of which is "Principles of Transaction Processing for the System Professional" (Morgan Kaufmann, 1997). He holds a B.S. from Cornell University and a Ph.D. from University of Toronto. A summary of his current research on meta data management can be found at http://www.research.microsoft.com/~philbe.

Abstract: Generic Model Management -- A Database Infrastructure for Schema Manipulation

Despite 30 years of research on database support for engineering applications, such applications remain complicated and hard to build. To improve this situation by an order of magnitude, a much higher level API is needed. We present such an interface, called Model Management. Its objects are models and mappings. By "model," we mean a complex structure that represents a design artifact, such as a relational schema, XML schema, object-oriented interface, UML model, web-site map,or software configuration. By "mapping," we mean an explicit representation of connections or transformations between two models. The main operations of Model Management are match, merge, diff, and compose. We explain how these operations can be used to solve classical meta data management problems and sketch a system architecture to implement them.

 www.cs.sunysb.edu/~cram

Most devices in day-to-day use are composed of many interacting components: hardware and/or software. As these systems become more complex, the process of creating and maintaining them becomes error prone. We are developing tools and techniques for doing program analysis and verification, which can be used to deduce many interesting properties of complex systems, including several "correctness" criteria.

In this talk, I will give an overview of the research I am currently doing, and a brief description of the directions of work I do as a part of the logic programming and verification groups.  Much of my research emphasises tool building, and so will the talk.

This is my second year at Stony Brook to which I came after receiving a Ph.D. at University of Utah. My interests include most areas of computer graphics with current emphasis on rendering algorithms, textures, and visual perception issues. If anyone cares, I'm teaching CSE528 (graduate computer graphics) this semester.

 In most cases not involving million dollar budgets, human observer has no diffuculty telling whether a given image is a photograph or was it generated by a computer. Qualitative understanding why computer graphics images differ from natural ones is a difficult problem requiring better knowledge about human visual system and visual perception than is currently available. In this talk, I will briefly present three recent projects which deal with obtaining such qualitative information and using it to the advantage of computer graphics. The first project explores second order image statistics as a possible source
of significant deviation between photographs and rendered images while the second one suggests a simple way to transfer color information from a photograph to a computer generated picture. Finally, the problem of mapping high dynamic range of real scenes to computer displays will be briefly discussed.

Prof Dimitris Samaras joined the CS Department in Stony Brook in September 2000 as an Assistant Professor. He has his Ph.D in Computer Science from the Univ. of Pennsylvania. His interests include 3D modeling and reconstruction for computer graphics and computer vision; scientific computation; deformable models; illumination modeling and estimation; face and human body modeling; human computer interaction; medical image analysis.

In this talk I will present work on issues regarding illumination in Computer Vision, Graphics  and Augmented Reality.
In current work we are presenting robust methods for the detection and estimation of multiple light sources from a single image of an object of arbitrary known geometry, combining information from critical points in shading, shadows and specularities. My Ph.D. thesis work has been in presenting a method for the incorporation of any type of illumination constraints in deformable model frameworks and in particular its application in the Shape from Shading (SFS) problem, with a reconstruction error of 15 to 40 percent less than the best results of previous methods. The applicability of the above methods is extended in real world situations, when some of the traditional SFS assumptions are violated, with a multiview method based on the integration of shape from shading (SFS) and stereo, for non-constant albedo and non-uniformly Lambertian surfaces.  This method was applied to face shape reconstruction and accurate texture recovery with the purpose of re-rendering.

Google has changed the way some parts of a search engine are built. I'll discuss some of the changes, as well as some experiences from my two years in the Google Research Department and the nature of research at a startup.