From: calendar@ALMADEN.IBM.COM (IBM Almaden Research Center Calendar)
Newsgroups: ba.seminars
Subject: IBM ARC seminars 03 - 7 AUG 92
Date: 31 Jul 92 17:51:28 GMT


                     IBM Almaden Research Center
                           650 Harry Road
                       San Jose, CA 95120-6099

                              CALENDAR
                          August 3 - 7, 1992

08/03 - OPTIMIZATION PROBLEMS: EXPRESSIBILITY, APPROXIMABILITY AND
EXPECTED ASYMPTOTIC GROWTH OF OPTIMAL SOLUTIONS
E. Graedel, University of Basel, Switzerland

Comp. Sci. Sem.    Monday, Aug. 3    2:00 p.m.    Room: G2-301

The NP-completeness of a decision problem rules out the possibility
finding optimal solutions of the corresponding optimization problem in
polynomial time, unless P = NP.  However, for many optimization problems
with NP-complete decision problems, there are efficient algorithms that
produce solutions differing from optimal solutions by at most a constant
factor.  The "structural" reasons for the different approximation
properties of NP optimization problems are not yet sufficiently
understood.

Papadimitriou and Yannakakis provided a new perspective by relating the
approximation properties of optimization problems to their logical
representation.  They defined the classes MAX SNP and MAX NP and showed
that all problems in these classes are approximable in polynomial time
up to a constant factor.

We extend these optimization classes in several ways, most importantly
by allowing the formulae to contain fixpoint definitions.  The extended
class MAX NP(FP) also contains only approximable problems.  We separate
the extended classes and prove that some important problems are not in
MAX NP(FP).  To do this we introduce a new method, that characterizes
rates of growth of expected optimal solution sizes.

This describes joint work with Kevin Compton (University of Michigan,
Ann Arbor and INRIA, Rocquencourt).
Host:  M. Vardi


08/05 - IMPLEMENTATION AND PERFORMANCE EVALUATON OF A PARALLEL
TRANSITIVE CLOSURE ALGORITHMS ON PRISMA/DB
M. Houtsma, University of Twente, The Netherlands

Comp. Sci. Sem.    Wednesday, Aug. 5    10:00 a.m.    Room: G2-301

We describe an experimental performance study of the parallel
computation of transitive closure operations on a parallel database
system. This work brings two research efforts together.  The first is
the development of an efficient execution strategy for the parallel
computation of path problems, called the Disconnection Set Approach.
The second is the development and implementation of a parallel,
main-memory DBMS, called PRISMA/DB.  Here, we report on the
implementation of the disconnection set approach on PRISMA/DB, showing
how the latter's design allowed us to easily extend the functionality of
the system.

It is shown that the parallel implementation of the disconnection set
approach yields good performance characteristics, and that linear
speedup with respect to a special purpose single processor algorithm is
achieved.  Finally, we describe a number of experiments that show to
what extent data fragmentation issues influence the performance of the
disconnection set approach.
Host:  R. Agrawal


08/05 - TOTALLY INTEGRATED AND MINIATURIZED OPTICAL MEASURING SENSORS
Dr. R. Kunz, Paul Scherrer Institute Zurich, Switzerland

Phys. Sci. Sem.   Wednesday, Aug. 5    10:30 a.m.    Room: J2-609

Various schemes are presented for realizing compact, truly integrated
optical sensors based on a single technology or at least a sequence of
compatible processes for their fabrication.  These totally integrated
sensor modules not only eliminate the need for external components and
their respective alignment, but also achieve reduced size and weight,
improved stability, mass-production potential, and the possibility of
single chip multi-element sensor arrays.  Some of the principles also
lend themselves to realizing novel types of integrated optical sensor
components for use in miniature hybrid sensor systems and for realizing
sensor/actuator modules.  Main applications are in the fields of
chemical, biochemical and environmental sensing.  First results of
numerical and experimental investigations will be presented.
Host:  M. Philpott


08/03 - DEGREES OF BELIEF, RANDOM WORLDS, AND MAXIMUM ENTROPY
J. Halpern, IBM Almaden Research Center

Comp. Sci. Sem.    Wednesday, Aug. 5    1:00 p.m.    Room: G2-301

Consider an agent who has a knowledge base KB consisting of first-order
and statistical information.  (The agent could be, say, a doctor, with a
database of information regarding diseases and symptoms.)  To make
decisions, it is often useful for the agent to assign a numerical
"degree of belief" to measure the strength of his belief in a given
statement A.  We study in depth one principled method, called the
random-worlds method, for doing so.  For any given domain size, we
consider the proportion of models satisfying A among models of that size
satisfying KB.  If we know that the domain is large, we can take the
degree of belief in A given KB to be the limit of this fraction.  In
many cases that arise in practice, the random worlds method converges,
and gives answers that match heuristic assumptions made in many standard
AI systems. We show that when restricted to unary predicates, the answer
provided by the random worlds method can often be computed using maximum
entropy.  On the other hand, we also show that there are limitations to
the approach. If the language includes binary predicates, typically
there will not be convergence. Moreover, almost all the questions one
might want to ask are highly undecidable.  Even for monadic languages,
computing the asymptotic probability is #EXP-complete.  Our techniques
show the close connections between this approach and the theory of
zero-one laws.
This represents joint work with Adam Grove and Daphne Koller.
Host:  R. Fagin


08/05 - AN APPLICATION OF AB INITIO QUANTUM CHEMISTRY IN
PARAMETERIZATION OF A CLASSICAL CONFORMATIONAL ENERGY FORCE-FIELD FOR A
POLYMER
G. Smith, NASA Ames Research Center

Phys. Sci. Sem.    Wednesday, Aug. 5    1:30 p.m.    Room: D3-450

Atomistic modeling of polymer systems, which includes molecular
mechanics (energy minimization) techniques as well as Monte Carlo and
molecular dynamics simulations, is a rapidly expanding field.
Fundamental to these modeling efforts is the parameterization of
classical force-fields which describe both inter- and intramolecular
interatomic interactions.  Intermolecularly it is necessary to describe
dispersion and polar interactions.  Intramolecularly, one must also
consider bond stretching, bending, and most importantly for polymers,
torsional terms.  Traditionally, polymer force-fields have been
parameterized based upon a limited amount of spectroscopic and
thermodynamic data for small model molecules which resemble repeat units
of the polymer of interest.  Ab initio quantum chemistry calculations on
such model molecules can either supplement empirical data or provide a
complete data base for force-field parameterization.  Here I will
discuss the use of quantum chemistry in parameterization of a
force-field for poly(vinyl chloride) (PVC). Implementation of the
force-field in a molecular dynamics simulation of PVC will also be
considered.
Host:  J. Carter


08/06 - CHEMISTRY WITHIN MOLECULAR VAN DER WAALS CLUSTER
Prof. J. Garvey, SUNY Buffalo, Department of Chemistry, Buffalo,
New York

Polym. Sci. & Tech. Sem.   Thursday, Aug. 6   1:00 p.m.   Room: J2-601

I will present recent work from our group involving novel
"intramolecular" reactions which occur within van der Waals cluster ions
produced via electron impact ionization.  That is, we observe new
ion-molecule reactions not apparent in bimolecular experiments, but
which occur within the solvated environs of a cluster.  In particular
the observation of "magic numbers" will be used to help elucidate this
unique type of chemistry and cluster ion structure.

We will also present results of photodynamics within heteroclusters of
1/8M(CO)6`S(n) (where S is the solvent molecule and M = Cr, Mo, W).  To
probe the intermediate regime between the two extremes of gas-phase and
solution behavior, we observed the 248 nm MPI mass spectrum of Cr(CO)6
solvated within a cluster of methanol molecules.  The plethora of ion
peaks observed can be ascribed to a general empirical formula
S(n)1/8Cr(CO)x` + where S is the CH3OH molecule and x = 0, 1, 2, 5, 6.
The MPI spectrum of Cr(OC)6 complexed with deuterated methanol gives
again a series of peaks which can be given the general formula
S(n)1/8Cr(CO)x`+, but for x = 0, 1, 2, 6 (i.e., the sequence
corresponding to S(n)1/8Cr(CO)5`+ is absent).  This change in the MPI
mass spectra of Cr(CO)6/CH3OH clusters and Cr(CO)6/CD3OD clusters we
attribute to the differing efficiencies of CH3OH and CD3OD for
relaxation of the excited nascent photoions through intracluster
V-V energy transfer.

This research was supported by the Office of Naval Research and the
Alfred P. Sloan Foundation.
Host:  R. Jackson


08/07 - REQUIREMENT FOR DEADLOCK-FREE, ADAPTIVE PACKET ROUTING
R. Cypher, IBM Almaden Research Center

Comp. Sci. Sem.    Friday, Aug. 7    11:00 a.m.    Room: B2-307

In this talk we study the problem of deadlock-free packet routing in
parallel and distributed architectures.  In particular, we focus on
asynchronous routing algorithms in which a packet is allowed to move
from one queue to another based solely on the queues involved and on the
packet's source and destination.  Our goal is to characterize those
properties which such an algorithm must have in order to be free of
deadlock.  We present three main results.

First, we show that the standard technique of ordering the queues so
that every packet always has the possibility of moving to a higher
ordered queue is not necessary for deadlock-freedom.  Second, we show
that every deadlock-free, adaptive packet routing algorithm can be
restricted, by limiting the adaptivity available, to obtain an oblivious
algorithm which is also deadlock-free.  Third, we show that any packet
routing algorithm for a cycle or torus network which is free of deadlock
and which uses only minimal length paths must require at least three
queues in some node.  This matches the known upper bound of three queues
per node for deadlock-free, minimal packet routing on cycle and torus
networks.

This is joint work with Luis Gravano from IBM Almaden and IBM Argentina.
Host:  S. Bruck

-----------------------------------------------------------------------

For further information on individual talks, please contact the host
listed above.

Visitors, please arrive 15 minutes early.  IBM's Almaden Research
Center (ARC) is located adjacent to Santa Teresa County Park, between
Almaden Expressway and U.S. 101, about 10 miles south of Interstate
280.  From U.S. 101, exit at Bernal Road, and follow Bernal Road west
past Santa Teresa Blvd. into the hills (ignoring the left turn for
Santa Teresa Park).  Alternatively, follow Almaden Expressway to its
southern terminus, turn left onto Harry Road, then go right at the ARC
entrance (about a quarter of a mile later) and go up the hill.  For
more detailed directions, please phone the ARC receptionist at (408)
927-1080.

IBM Almaden Research Center electronically distributes both its
complete calendar of seminars and a subset of Computer Science
seminars only.  Send requests for inclusion in either electronic
mailing list to CALENDAR@ALMADEN.IBM.COM (CALENDAR at ALMADEN on
BITNET), specifying either the complete calendar or the Computer
Science subset.