From: calendar@ALMADEN.IBM.COM (IBM Almaden Research Center Calendar)
Newsgroups: ba.seminars
Subject: IBM ARC seminars 5 - 9 OCT 92
Date: 2 Oct 92 18:08:26 GMT


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

                              CALENDAR

                          October 5-9, 1992


10/05 - CROSS PLATFORM VISUALIZATION, ANIMATION, AND MULTIMEDIA
J. W. Cooper, IBM T. J. Watson Research Center

Office of Director   Mon., October 5   2:00 p.m.   Room:  Aud. A

Visualizing molecules surfaces and theories has become an important
technique for increasing scientific understanding and insight.  While
visualization using high performance workstations has become
increasingly common in IBM and elsewhere, the ability to perform this
task from the office workstation has not been completely explored.

The Programming and Scientific Solutions group at IBM T. J. Watson
Research Center is engaged in two projects to improve this situation:
the development of cross platform programming tools and the development
of multimedia video compression and decompression schemes for both
RS-6000s and PS/2s.

Jim Cooper, manager of the Programming and Scientific Solutions group,
will discuss both of these projects and their obvious intersection at
this seminar.
Host:  C. Munce


10/05 - BOOLEAN COMPLEXITY AND PROPOSITIONAL PROOFS
M. Ajtai, Discrete Mathematics, Computer Science

Comp. Sci. Sem.    Mon., October 5    3:00 p.m.    Room:  Aud. A

A propositional formula is an expression built from Boolean variables
with the Boolean operations AND, OR, and NOT.  A formula is called valid
if, for every truth assignment for the variables, the value of the
formula is TRUE.  Cook has shown 20 years ago that the problem of
deciding whether a formula is valid is co-NP complete, that is, it is in
co-NP and if it has an efficient solution then every problem in NP and
in co-NP has an efficient solution.  A consequence of this is that to
prove that NP and co-NP are different, it is sufficient to show that the
validity problem is not in NP, i.e., it is sufficient to show that in
general, valid formulas require super-polynomially long proofs.  We may
try to decide the validity of a propositional formula by proofs that
consist of only propositional formulas (such a proof is called a Frege
proof).  Our goal is to get a non-polynomial lower bound on the length
of certain Frege proofs.  This is weaker than "validity is not in NP",
since it is conceivable that valid propositional formulas have short
proofs in a nonpropositional proof system.

The Pigeonhole Principle for a number n is the statement that there is
no one-to-one function from a set of size n into a set of size n-1.  It
can be expressed as a valid propositional formula of size quadratic in
n.  The main result is the following theorem:  There is no
constant-depth subexponential-size Frege proof for the Pigeonhole
Principle.  (The constant-depth restriction is a technical restriction
on the depth of nesting of Boolean operations in the formulas of the
proof.)
Host:  R. Fagin


10/06 - TRACKPOINT IN-KEYBOARD-POINTING DEVICE--PSYCHOPHYSICS WE LEARNED
ALONG THE WAY
T. Selker, T. J. Watson Research Center, Yorktown

Comp. Sci. Sem.    Tues., October 6    2:00 p.m.    Room:  B2-307

Two of IBM's fall 1992 notebook computer keyboards will feature a unique
integrated pointing device called Trackpoint.  It provides smooth
control in the popular mixed type-and-point interfaces, without taking
hands away from typing position.  The time loss and distraction of
reaching for an extra device is eliminated.  The notebook is GUI-ready,
with nothing extra to carry about and find space for.  Typing, pointing,
selecting and dragging all become parts of a single process using a
single device, the Trackpoint.  It can be used equally by either hand.

Trackpoint is the result of a new understanding of the behavioral-motor
issues at play in rate control devices.  If the cursor moves faster than
the eye can track, the user loses sight of it.  If the unsteadiness of
the user's hand affects cursor speed, movement becomes unpredictable.
These psycho-motor realities have guided the design of a special
algorithm for using a rate-control device to guide a cursor for positive
control for useful speeds.

The ideas which make Trackpoint useful were the result of learning from
many peoples' criticisms, and numerous human psychomotor studies.
Host:  A. Chandra


10/07 - OPTICAL MODELING OF "REAL MATERIALS"
D. W. Whiten, Stanford University

Phys. Sci. Sem.    Wed., October 7    2:00 p.m.    Room:  J2-601

Infra-red reflecting interference filters have a substrate capable of
transmitting visible energy and a surface with a procoat layer adherent
thereto that is formed of a thin layer of material, and a layer of
silver deposited on the thin layer having a thickness so that it is
highly transmitting of visible energy and highly reflecting of infra-red
energy.  A dielectric layer is deposited directly on the silver layer.
The index of refraction of the dielectric layer affects the width of the
passband in the visible spectrum.

The standard approach to optical modeling of these thin films begins
with the Characteristic Matrix method derived from Maxwell's equations.
The material properties (n and k) used in the layers may be measured on
laboratory samples f or may be from handbook data.  The calculated
performance based on these material properties often does not match
production material, particularly on such instruments as a sputter roll
coater.  The method presented here utilizes a simple physical model of
the material properties with parameters that can then be related to
actual process conditions.  The model is intended to account for the
major features in the optical spectra of typical dielectrics and noble
metals, and has been used to provide production process feedback.
Host:  J. Kaufman


10/09 - CONDUCTING POLYMERS:  THE PROMISE OF THE 1970'S IS REALITY IN
1992
A. J. Heeger, Inst. for Polymers and Organic Solids, UCSB, Santa Barbara

Phys. Sci. Sem.    Fri., October 9    1:30 p.m.    Room:  Aud. A

This review of the current status of conducting polymers will focus on
recent progress which demonstrates that the initial promise of the late
1970's has become reality in 1992.  Conducting polymers are now
available as materials with truly unique properties:  the important
electronic and optical properties of semiconductors and metals in
combination with the attractive mechanical properties and processing
advantages of polymers.  The field has progressed to a level of maturity
consistent with a new set of opportunities--opportunities to develop a
wide range of applications based upon conducting polymers as materials
for industrial products.
Host:  J. Scott


10/09 - THE COMPLEXITY OF TRACKING A MOBILE USER
L. Stockmeyer, IBM Almaden Research Center

Comp. Sci. Sem.    Fri., October 9    1:30 p.m.    Room:  G2-301

In large networks it may be useful to allow users to move freely around
the network and communicate with one another.  This raises the problem
of maintaining information about the current location of each user.
Motivated by problems of this type, Auerbuch and Peleg defined the
theoretical problem of on-line tracking of a mobile user.  An input to a
distributed algorithm for this problem is a sequence of requests which
are invoked at nodes of the network.  There are two types of requests:
the Move request for moving the user from one node to another, and the
Find request for sending a message to the user.  The algorithm must
process the requests on-line in a distributed manner.  For example, when
a node issues a Find request, the part of the algorithm residing at that
node will not know the current location of the user if it was not
informed during the most recent Move.  The efficiency of a distributed
on-line algorithm can be given by its competitive ratio, which measures
the cost of the algorithm (in this case, the communication cost)
relative to the cost of a global off-line algorithm which has complete
knowledge of the entire request sequence in advance.  The talk will
cover results showing, for certain classes of networks including
hypercubes, that no on-line algorithm for this problem can have constant
competitive ratio, that is, constant independent of the size of the
network.  This is joint work with Noga Alon, Gil Kalai, and Moty
Ricklin.
Host:  C. Dwork

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

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.