From: ventre@ICSI.Berkeley.EDU (Giorgio Ventre)
Subject: Intl. Computer Science Institue, Berkeley. Call for Italian
Organization: International Computer Science Institute, Berkeley, CA, U.S.A.
Date: Sat, 23 Jan 1993 01:48:17 GMT

Applicants 
Keywords: 


===================================================================
	
             International Computer Science Institute
                 1947 Center Street, Suite 600
               Berkeley, California  94704-1105
                     Phone: (510) 643-9153
                       Fax: (510) 643-7684


GENERAL INFORMATION FOR APPLICANTS
==================================

The International Computer Science Institute (ICSI) is a non-profit 
basic research institute physically near and loosely affiliated with
the University of California at Berkeley.

ICSI conducts research in several areas of parallel and distributed 
computation including theory, realization and applications of
massively parallel systems, and the design of multimedia distributed
systems and very high-speed networks.

There are two different programs for visiting researchers:

o  ICSI Postdoc Program: This program is intended for researchers who 
   have recently completed their doctorate or who have at least three
   or four years of experience in computer science research. Postdocs 
   will work with the Institute and UCB faculty and staff on current 
   projects.

   Postdoctoral positions run for one year and usually start in 
   September. Financial support is provided by a fellowship of
   $42,000. Additionally, ICSI will pay for economy round trip
   airfare, relocation expenses up to $1,000, and travel expenses up 
   to $500 per dependent.

o  ICSI Senior Visitor Program: This program is intended for senior 
   researchers and faculty on sabbatical from their home institution. 
   The applicants can propose projects of any length and character 
   within the scope of ICSI projects.

   Starting time and duration for senior visitor positions are
   flexible. ICSI provides a living allowance of $2,000 per month and 
   economy roundtrip air fare.

   Postdocs and Senior Visitors from outside the U.S. usually require 
   a J-1 (exchange visitor) visa. ICSI will help with visa, travel, 
   housing and other arrangements.

Selection will be based on overall qualifications and compatibility
with ICSI research plans.

For further information about ICSI please refer to the included
OVERVIEW and OUTLINE OF RESEARCH. The ICSI RESEARCH PLAN contains a 
more detailed description of ongoing projects at the Institute.

To apply for either a postdoctoral fellowship or a senior visitor 
position, please observe the following:

1. Please complete the enclosed application form in ENGLISH.

2. Mail your application together with selected publications to the
   following addresses.

   o Prof. Alberto Conti
     Ufficio Relazioni Scientifiche
     e Progetti di Cooperazione Internazionali
     Consiglio Nazionale Delle Ricerche (CNR)
     Piazzale Aldo Moro 7
     I-00100 Roma
     Fax: (06) 4 46 98 33
     Phone: (06) 49 93 39 77

   o Prof. Jerome A. Feldman, Director
     International Computer Science Institute
     1947 Center Street, Suite 600
     Berkeley, CA 94704-1105, U.S.A.
     Internet/CSnet: info@icsi.berkeley.EDU
     Fax: (510) 643-7684
     Phone: (510) 643-9153

3. Ask references to send their letters (preferably in English) to the
   same addresses so that their letters of evaluation arrive at about 
   the same time as the other application materials.

4. Postdocs will have to join ICSI before the end of December
   of the year in which their stay is supposed to start.

5. Deadline: Complete applications must be received by January 15, 1993.
   Second deadline for senior visiting positions only: May 15, 1993.

************************************************************************

             International Computer Science Institute
                 1947 Center Street, Suite 600
               Berkeley, California  94704-1105
                     Phone: (510) 643-9153
                       Fax: (510) 643-7684

APPLICATION
===========


for a [please check]:

       ___ POSTDOC FELLOWSHIP      ___ SENIOR VISITOR POSITION


LENGTH OF DESIRED STAY: _____________________________________________


PERIOD OF DESIRED STAY:	_____________________________________________



DESIRED AFFILIATION WITH ICSI GROUP [please check]:


___ APPLICATIONS (AI)   ___ THEORY   ___ REALIZATION   ___ NETWORKS

___ OTHER [please specify]: _________________________________________



NAME, FIRST NAME(S); ACADEMIC TITLE(S):

_____________________________________________________________________


DOCTORATE OR LATEST UNIVERSITY DEGREE:	_____________________________


SPONSOR COUNTRY: ____________________________________________________


PROFICIENCY IN ENGLISH:	oral: ____________  written: ________________


ADDRESS: ____________________________________________________________

_____________________________________________________________________

_____________________________________________________________________

_____________________________________________________________________

PHONE:	_________________________  FAX: _____________________________

EMAIL:  _____________________________________________________________

HOME INSTITUTION: ___________________________________________________

_____________________________________________________________________

_____________________________________________________________________

_____________________________________________________________________


                           ---PAGE TWO---
EDUCATION:



DISSERTATION [please give title and state of doctoral dissertation if
applicable]:



SCIENTIFIC AND PROFESSIONAL ACTIVITIES:




                            ---PAGE THREE---


AREAS OF INTEREST / RESEARCH PROPOSAL FOR YOUR STAY AT ICSI:



                            ---PAGE FOUR---

REFERENCES [Please give names and complete addresses of at least two 
references]:

Note: In order to save time, applicants should ask their references to
write directly to the given address so that letters of evaluation
reach ICSI at about the same time as the other application materials.



                            ---PAGE FIVE---


SELECTED PUBLICATIONS [please include copies of some of your recent 
publications]:



DATE: _________________	SIGNATURE: ___________________________________


**********************************************************************



                 INTERNATIONAL COMPUTER SCIENCE INSTITUTE
                                 Overview


The International Computer Science Institute is an independent, non-
profit basic research institute affiliated with the University of 
California campus in Berkeley, California. ICSI was started in 1986 
and inaugurated in 1988 as a joint project of the Computer Science 
Division of U.C. Berkeley and the German National Research Center for
Computer Science (GMD). German and Swiss support of the Institute is 
now provided by a government-industry consortium and organized by a 
sponsoring association (Foerderverein). Italian support of the 
Institute is provided by the Consiglio Nazionale delle Ricerche (CNR).
The Institute also receives support from a variety of U.S. sources.

There is an average of about sixty scientists in residence at ICSI
including permanent staff, postdocs, visitors and affiliated faculty 
and students. The Institute occupies a newly designed 21,000 square
foot research facility at 1947 Center Street, just off the central
U.C. campus in downtown Berkeley. The selection of Berkeley for the 
Institute was based on the outstanding reputation of the U.C. Berkeley
Computer Science Faculty and on their enthusiasm for the project.

The establishment of ICSI was motivated by a recognition of the lack
of an international facility for fundamental research in the field 
of computer science. The supporting nations expect the participation
of visiting scientists to do for fundamental computer science what 
such international collaboration has done for the field of physics.
They also expect to benefit from the experience that young scientists
will gain from participation in the work of the Institute and from 
increased international recognition of the work that goes on in their 
own countries. 

The core of the Institute's program is the intramural research effort.
The International Computer Science Institute strives to maintain 
ongoing basic research projects of the highest standard in selected 
areas of computer science and engineering. Only by maintaining
research projects at the forefront of technology can ICSI have the
strength to meet its other goals in international cooperation.

The particular areas of concentration are chosen for their fundamental
importance and their compatibility with the strengths of the Institute
and U.C. Berkeley staff. ICSI conducts research in several areas of 
parallel and distributed computation including theory, realization and
applications of massive parallelism and the design of multimedia 
distributed systems and very high-speed networks. An extensive 
description of work is available in the ICSI Research Plan.

In addition to its intramural research efforts, ICSI maintains a
number of other programs in support of international cooperation in 
advanced computer science and engineering. These include a post-
doctoral program, exchange visits, summer internships for graduate 
students and partial support of selected international workshops. One
of the principal advantages of ICSI is its ability to act quickly and
thus gain maximum leverage from its resources. As a basic research 
organization, ICSI does not engage in product development. The 
Institute does help in practical realization of its research results
and grants non-exclusive, royalty-free licenses to supporting 
institutions. 

All of the ICSI programs place special attention on cooperation with
sponsor nations. The post-doctoral program is fairly conventional. 
A committee of sponsor-nation and ICSI scientists selects among 
applicants on the basis of overall scientific potential and the 
availability of an appropriate project at ICSI or U.C. Berkeley.
Fellowship stipends are competitive and relocation expenses are paid 
by ICSI. Exchange visits by more senior investigators and researchers 
from sponsor companies can be of any length and are arranged at the 
mutual convenience of the host and visitor. These are often supported
by other funds, but ICSI can provide full support where this is 
warranted. Several of these visits have led to new or strengthened 
international collaborations.

As part of its mission to further international cooperation in
computer science, ICSI sponsors a student summer internship program.
ICSI recruits qualified and interested students and supplies their 
credentials to institutions in sponsor countries. The hosting
laboratory selects and pays the summer interns. ICSI pays for the 
travel cost to the host organization and offers assistance with 
general arrangements. For most students this is the first contact 
with European research programs. Now in its third year, the summer 
internship program has been very successful. An indication of the 
success of the program and the quality of the students selected is 
the fact that frequently students have been invited by their host 
institutions to return the following year. The idea, again, is that 
a small expenditure of Institute funds and effort can have a 
significant effect.

ICSI also provides financial and organizational support to
international workshops of particular importance. Recent meetings
partially sponsored by the Institute have all had significant 
impacts on their respective fields. 

Professor Jerome A. Feldman, of the Electrical Engineering and 
Computer Science Faculty in the College of Engineering at U.C. 
Berkeley, is Director of ICSI and head of the Applications Group.
Professor Feldman came to Berkeley from the University of Rochester,
where he was John H. Dessauer Professor of Computer Science, 
Electrical Engineering and Visual Science. He received his Ph.D. 
in 1964 from Carnegie-Mellon University. In recent years, he has 
been best known for his pioneering work in Connectionist Models for 
massive parallelism.

Professor Domenico Ferrari was founding Deputy Director of ICSI and 
remains as the head of the Networks and Distributed Systems Group.
Professor Ferrari received a Dr. Ing. degree in electronic engineering
from the Politecnico di Milano in 1963, and joined the U.C. Berkeley
faculty in 1970. 

Dr. Joachim Beer serves as Associate Director of the Institute. Before
joining ICSI as a permanent staff member, Dr. Beer was with the 
German National Research Center for Computer Science (GMD). He
received his Dr. Ing. degree from the Technische Universitaet Berlin 
in 1987.

Professor Mike Luby is the head of the Theory Group. He received his 
Ph.D. from U.C. Berkeley. After holding a faculty position at the 
University of Toronto, he returned to Berkeley to join ICSI. He is 
also Adjunct Professor at U.C. Berkeley.

The Realization Group is led by Dr. Nelson Morgan.  Dr. Morgan 
received his Ph.D. from U.C. Berkeley in 1980. He is also Adjunct
Professor at U.C. Berkeley.

The Institute is governed by a distinguished international Board of 
Trustees, including Provost J. Cerny representing the Office of the 
Chancellor of U.C. Berkeley; Professor E. Engeler, ETH Zuerich,
Switzerland; Professor G. Fabri, Italtel Group, Italy; Professor D.
Ferrari, EECS, U.C. Berkeley; Professor G. Goos, Universitaet
Karlsruhe; Professor D. Hodges, Dean, College of Engineering, U.C. 
Berkeley; Professor R. Karp, EECS, U.C. Berkeley; R. Kay, Acting 
Director of ICSI until 1988; Professor J. Noe, University of 
Washington at Seattle; Professor D. Patterson, Chairman of the CS 
Division of EECS, U.C. Berkeley; Professor M. Rabin of Harvard and 
Hebrew University of Jerusalem; Professor H. Schwaertzel of Siemens
AG; Professor K. Triebold of Atlas Elektronik GmbH; and Professor 
Tsichritzis of the German National Research Center for Computer 
Science (GMD).

Retired members of the Board of Trustees include Professors R. Fateman
and E. Kuh, EECS, U.C. Berkeley; Professor M. Minsky of MIT; Professor
R. Reddy of Carnegie-Mellon University; and Professor N. Szyperski
who, as head of the GMD, was the originator of ICSI.

German and Swiss support of the Institute is organized by a sponsoring 
association (Foerderverein). The Foerderverein members are Daimler 
Benz AG; Deutsches Forschungszentrum fuer Kuenstliche Intelligenz 
(DFKI); the German National Research Center for Computer Science
(GMD); Krupp GmbH; Siemens AG; Standard Elektrik Lorenz AG; 
Verlagsgruppe Bertelsmann International GmbH; Dr. Erich Haeusser, 
President of Deutsches Patentamt (German Patent Office); as well as 
the Schweizer Gesellschaft zur Foerderung der Informatik und ihrer 
Anwendung. The Foerderverein also operates a Secretariat in Heidelberg 
which is the German/Swiss contact point for ICSI. Selection of German 
and Swiss postdocs is organized by the Foerderverein and 
representatives from ICSI. Italian support of the Institute is 
organized by the Consiglio Nazionale delle Ricerche (CNR). The CNR-
ICSI Committee, consisting of representatives of the two organizations 
and Italian university professors, examines research programs, selects 
post-doctoral and visitor applications, and oversees Italian 
participation in ICSI activities.

ICSI and the original sponsors of the Institute have provided for a 
limited number of additional sponsor countries. In each case there has
been significant participation by the science or research ministries 
of the sponsor nations, but the original initiative came from 
individual computer scientists and laboratories. The final result is a
multinational contract involving the Institute, the existing sponsors 
and the new sponsor nation. ICSI provides information on how to 
initiate this process and can help arrange contacts.

ICSI has now been operating for a few years and has established areas 
of technical strength, an internal working style and several modes of
cooperation with sponsors and other laboratories. The original 
experiment of a cooperative international institute in the highly 
competitive field of computer science has been successful and is being 
expanded. By maintaining its focus on open, basic research and 
international exchanges, ICSI hopes to provide continuing service to 
science and to international understanding.


Address Inquiries to:

   International Computer Science Institute
   1947 Center Street, Suite 600
   Berkeley, CA  94704-1105
   Phone (510) 643-9153;  FAX (510) 643-7684;  info@icsi.berkeley.edu

In Germany/Switzerland:

   GMD Heidelberg Secretariat
   Im Weiher 12
   D-6900 Heidelberg
   GERMANY
   Phone +49 6221 46081;  FAX +49 6221 480279;  kunz@kmx.gmd.dbp.de

In Italy:

   Consiglio Nazionale delle Ricerche (CNR)
   Ufficio Relazioni Scientifiche
   e Progetti di Cooperazione Internazionali
   Piazzale Aldo Moro 7
   I-00100 Roma
   ITALY
   Phone +39 6 49 93 39 77;  FAX +39 6 4 46 98 33


**********************************************************************



                 INTERNATIONAL COMPUTER SCIENCE INSTITUTE
                            Outline of Research


The International Computer Science Institute is an independent, non-
profit basic research institute affiliated with the University of 
California campus in Berkeley, California. ICSI was started in 1986 
and officially inaugurated in 1988 as a joint project of the Computer
Science Division of U.C. Berkeley and the German National Research 
Center for Computer Science (GMD). German and Swiss support of the 
Institute is now provided by a government-industry consortium and 
organized by a sponsoring association (Foerderverein). Italian 
support of the Institute is provided by the Consiglio Nazionale delle 
Ricerche (CNR). The Institute also receives support from a variety 
of U.S. sources.

There is an average of about sixty scientists in residence at ICSI
including permanent staff, postdocs, visitors and affiliated faculty
and students. The Institute occupies a newly designed 21,000 square
foot research facility at 1947 Center Street, just off the central 
U.C. campus in downtown Berkeley. The selection of Berkeley for the 
Institute was based on the outstanding reputation of the U.C. Berkeley
Computer Science Faculty and on their enthusiasm for the project.

German and Swiss support of the Institute is organized by a sponsoring
association (Foerderverein). The Foerderverein members are Daimler 
Benz AG; Deutsches Forschungszentrum fuer Kuenstliche Intelligenz 
(DFKI); the German National Research Center for Computer Science 
(GMD); Krupp GmbH; Siemens AG; Standard Elektrik Lorenz AG; 
Verlagsgruppe Bertelsmann International GmbH; Dr. Erich Haeusser, 
President of Deutsches Patentamt (German Patent Office); as well as 
the Schweizer Gesellschaft zur Foerderung der Informatik und ihrer 
Anwendung. The Foerderverein also operates a Secretariat in Heidelberg
which is the German/Swiss contact point for ICSI. Italian support of 
the Institute is organized by the Consiglio Nazionale delle Ricerche 
(CNR).

The International Computer Science Institute strives to maintain 
ongoing basic research projects of the highest standard in selected 
areas of computer science and engineering. Only by maintaining 
research projects at the forefront of technology can ICSI have the 
strength to meet its other goals in international cooperation.

The particular areas of concentration are chosen for their fundamental
importance and their compatibility with the strengths of the Institute
and U.C. Berkeley staff. ICSI conducts research in several areas of 
parallel and distributed computation including theory, realization and
applications of massive parallelism and the design of multimedia 
distributed systems and very high-speed networks. An extensive 
description of work is available in the ICSI Research Plan.

It has been clear for some years that parallel computation is the key
to many desirable applications. Distributed and parallel systems of 
moderate scale are now fairly well understood and widely employed. 
However, the problems involved with millions or billions of
independent computations appear to be different and to require new
techniques. ICSI is currently addressing issues in four key areas: 
Applications of Massively Parallel Systems, Realization of Such 
Systems, Very Large Distributed Systems, and Theory of Parallel 
Computation.

The primary focus of the Applications of Massive Parallelism group is
the field of artificial intelligence (AI). The tasks studied in AI are
of enormous practical and scientific importance and have proven to be
quite difficult for conventional programming techniques. Human brains
evolved to excel at vision, motor control, speech, language 
understanding and so on, and are much better at these tasks than 
artificial systems. The ICSI effort, along with many others, is 
exploring the possibility that computational models and techniques 
based on natural intelligence will prove useful in AI tasks.

The ICSI project differs from most others in its emphasis on 
structured networks, strong methods that exploit scientific knowledge 
and extensive interaction with other computer science techniques and 
theory. Our structured approach to massively parallel computation 
requires sophisticated tools for building and working with complex 
networks. The ICSI connectionist simulator (ICSIM) project is a
collaboration between the Realization and Application groups and 
attempts to qualitatively improve the state of such tools and to apply
them in our own efforts. Particular applications under study at the 
Institute are in the areas of vision, geometric structures and 
algorithms, speech, knowledge representation and learning.

The ICSI vision work is concerned with efficient and rigorous 
solutions to central problems in visual recognition. Particular 
problems currently under investigation include: invariant feature 
extraction by statistical and geometrical methods, categorizing the 
utility of features and the representation and matching of curved 
boundaries, and the recognition of known three-dimensional objects 
from images. The study of connectionist techniques for matching complex 
structures is being continued. In addition to a direct connectionist 
realization, it is of great interest to apply the techniques of 
computational geometry and complexity theory to yield efficient 
sequential versions of key algorithms. In our current research, 
connectionist models and procedures that appear to be promising are 
explored. These include the development of modules which efficiently 
implement a wide variety of geometric operations using geometric data
structures and a systematic framework within which geometric and 
symbolic information can be integrated in a natural way.

As part of our applications effort, we have developed the object-
oriented programming system, Sather. Sather combines the rigor of 
strongly-typed languages with the efficiency of more machine-oriented 
systems and appears to be an excellent design for a range of
applications. The Sather libraries are incorporating a large variety
of advanced data structures and algorithms from many areas of computer
science. Sather is available under a non-restrictive license and has 
been distributed to several hundred sites. A parallel version of 
Sather has been running since summer 1991 and will also be made 
available for experimental use.

A major emphasis of our work is on the related issues of knowledge 
representation and inference in massively parallel systems. The goal 
is to construct systems that perform certain tasks well and are 
consistent with the known biological, behavioral and computational 
constraints. Recent efforts have involved interpretation of adjective-
noun metaphors, connectionist unification networks, constraint
networks and applications to higher level vision. Learning in this 
paradigm is accomplished by recruitment of uncommitted units in 
addition to simple weight adjustment.

Many of the basic concerns of the group are embodied in our new L0
project on miniature language acquisition. The goal is to produce a 
system that will learn natural language from the presentation of a 
sequence of picture-sentence pairs. The domain involves simple two-
dimensional scenes of geometric figures and requires only twenty words
in English. However, the L0 task seems to be well beyond the scope of
any existing systems or theories. Our preliminary efforts have already
changed our thinking about several issues and the L0 task may well 
provide a touchstone for connectionist and other theories of 
perception, language, knowledge representation and learning.

The goals of the second major group, Realization of Massively Parallel
Systems, are to answer fundamental questions about the use of 
architectures and technology, to implement massively parallel systems,
and to implement connectionist algorithms for machine perception 
and intelligence in problem areas such as natural language 
understanding, speech, vision and biomedical signal processing. In
particular, members of this group are collaborating closely with
members of the Applications Group to design systems with a 
demonstrable capability for some limited problems in speech and 
vision. By its nature, the realization effort covers a broad spectrum
of issues.

Major areas of research in this group are:

    o	Systems Design - to design fast and flexible systems for the 
	implementation of connectionist algorithms. The first such
	system built at ICSI was the Ring Array Processor (RAP), which
	executed hundreds of millions of connections per second using
	commercial digital signal processor (DSP) chips and an object-
	oriented programming paradigm. The current design project is
	the Connectionist Network Supercomputer (CNS-1), which will 
	target much larger networks with sparse connectivity and two
	orders of magnitude higher performance levels.

    o	Integrated Circuit Design - to develop libraries and tools for
	the implementation of fast digital VLSI for connectionist 
	algorithms, particularly for the computational and
	communications functions of CNS-1. A current project is
	focused on a microprogrammed SIMD array for fast
	implementation of a fixed-point version of back-propagation.

    o	Applications Work - Speech Recognition - to continue the 
	development of a hybrid Multi-Layer-Perceptron/Hidden-Markov-
	Model (MLP/HMM) continuous speech recognizer. Current
	developments include robust features for recognition in 
	variable environments and methods for the integration of 
	MLP-based probability estimation with state-of-the-art HMM 
	approaches.

     o	Architectural Studies - to formally evaluate current parallel 
	architectures, both commercial and theoretical. Some of the 
	architectural issues are: data structures, interconnection 
	topologies, node processor requirements, dynamic versus static
	structures of Artificial Neural Networks (ANNs), learning in 
	ANNs and node update regimens. Many of these studies will be 
	applied to the development of CNS-1.

     o	Simulators - to develop network, architectural and IC design 
	and evaluation tools. In particular, the ICSIM (a 
	connectionist simulator based on Sather) incorporates software
	engineering principles such as reusability and modularity,
	support for loosely coupled multiprocessors, object-oriented
	programming paradigms and bitmap graphic user interfaces.

The Realization Group maintains close working relationships with 
several U.C. Berkeley faculty members from Electrical Engineering 
and Computer Science. ICSI is using many of the hardware tools 
developed in the EECS department, and is developing both the CNS-1 
design and the related VLSI work in close collaboration with the
faculty and students.

The research program in the field of Very Large Distributed Systems
is particularly concerned with the operating system requirements of
such systems. Technological, architectural and application evolution 
during the next decade will profoundly modify operating system design 
requirements. None of the existing (or planned) operating systems can
meet these future requirements, which will be especially severe in 
such areas as remote service accessibility, security, high-speed real-
time communication, support for heterogeneity in all aspects of the 
system, support for massive distributed computations, efficient 
exploitation of architectural parallelism and others. Even in those 
areas in which they seem adequate, current networks and distributed 
operating systems are often based on structures and policies that 
do not scale well to the sizes (millions of machines) that future 
distributed systems are expected to reach.

The ICSI efforts in this field -- the DASH and Tenet projects -- are
conducted in collaboration with U.C. Berkeley. The main goal is to
study the principles that should be adopted in designing very large 
distributed operating systems and very large networks. The viability
of the proposed principles is investigated by applying them in the 
design and implementation of a kernel and of a gigabit-per-second 
testbed, and experimenting with them in a variety of real or simulated 
environments. The gigabit-per-second network (XUNET) will be built in
cooperation with AT&T Bell Laboratories and the Universities of 
Illinois and Wisconsin as part of the Gigabit Testbed Project 
sponsored by the Corporation for National Research Initiatives.

To support the high-speed communication that will be made possible by
the broad-band networks of the future, and which will be needed by the
applications, a virtual memory system has been designed to maximize 
the speed with which large amounts of data can be moved locally 
between address spaces. The design is based on a very carefully 
implemented virtual memory remapping which has been found to provide 
a throughput at least one order of magnitude larger than software 
copying of memory in a Sun-3/50 machine. Also, a communication 
architecture based on the parametrized message channel (or simply 
channel) abstraction is being explored to determine its viability in
a very large distributed system. The parameters of a channel allow the
client to specify its security and performance needs; the channel 
provider verifies the communication system's request. The performance
parameters include deterministic, statistical and best-effort delay 
bounds, as well as the maximum message loss rate. The feasibility of 
providing such guarantees in current and future networks to support 
the real-time constraints of digital audio and digital video 
communication is being investigated by the Tenet Group.

The Theory Group is pursuing a program of research emphasizing
parallel computation, computational learning theory, randomized 
computation, analysis of heuristic algorithms, theory of program
checking and foundations of complexity theory for scientific 
computation. Although the topics are diverse, the general goal is to
understand the fundamental laws that govern the efficiency with which
computational tasks can be performed and, subject to these laws, to 
devise the most efficient computational methods possible.

Our research on parallel computation is currently focused on four 
areas: the solution of combinatorial search problems on highly
parallel computers (using methods such as backtrack search, game tree 
search and branch-and-bound computation); the investigation of 
parallel computation models that are more realistic than traditional 
models and which, in particular, take into account phenomena related
to synchronization, interprocessor communication and memory 
contention; the design of efficient algorithms for certain basic 
problems that occur as subroutines in a wide variety of higher level
parallel algorithms; and the development of fundamental algorithmic 
techniques, such as general methods of converting randomized parallel
algorithms to deterministic methods.

In computational learning theory, we have been particularly interested
in Valiant's model of PAC (Probably Approximately Correct) learning, 
in which the learner formulates a hypothesis on the basis of examples 
randomly drawn from some probability distribution. We have obtained a 
number of results about the effect of storage limitations on the 
convergence rate of PAC learning. We have also devised efficient 
algorithms for learning certain classes of Boolean functions using 
queries. Finally, we have established the computational intractability 
of certain problems related to the construction and analysis of neural 
networks. We hope to extend this work in the direction of 
understanding which inductive learning tasks can be carried out 
efficiently by such networks.

Our work on randomized computation stems from the observation that 
providing algorithms with the ability to toss coins often allows them
to be simpler and/or more efficient. We have succeeded in finding 
efficient Monte Carlo approximation algorithms for a number of
practically important counting problems for which there is no known 
efficient deterministic algorithm. While we hope to discover further 
uses for randomization along these lines, we are also working on 
techniques that can reduce the number of random bits required by 
certain algorithms or, in some cases, even remove the need for 
randomization altogether. In this connection, we have done fundamental
work on the construction of pseudo-random number generators; these are
algorithms whose output is very hard to distinguish from a long random
string even though it is, in fact, deterministically generated from a
short random string.

One of the fundamental mysteries in the field of combinatorial 
optimization is the ability of simple heuristic algorithms to give 
near-optimal solutions to typical instances of hard combinatorial 
problems. We have been working on the probabilistic analysis of such 
algorithms. For a wide variety of problems, including set partitioning, 
bin packing, linear programming and the traveling-salesman problem, 
we have shown that fast, simple heuristics perform well on the average 
when the input data are drawn from simple probability distributions.

We have introduced a new theory of program checking as an alternative 
to the traditional approaches of program testing and program 
verification. Given an input x and a program P that allegedly computes 
a function f, the goal of a checker is either to confirm that P 
correctly computes f(x), or else to establish that P is incorrect on 
some input (not necessarily x). The checker is allowed to execute P on
x, or on other inputs derived from x. We have devised efficient
checkers for a number of algebraic and graph-theoretic problems. This
work has led us to the stronger notion of a self-testing/correcting
pair for f. Intuitively, a self-testing program allows us to test
whether or not P computes f correctly for a large fraction of the 
inputs. If P is not too faulty then, on any input x, the self-
correcting program can compute f(x) correctly by calling P on inputs
derived from x. We have already developed self-testing/correcting 
pairs for a variety of numerical problems.

Finally, we have defined a model of computation analogous to the 
Turing Machine in which the basic operations act on real or complex 
numbers instead of on integers. A universal machine exists in this 
model, akin to a Universal Turing Machine. Within the model, we have 
defined appropriate concepts of undecidability and NP-completeness. 
The Julia sets, which arise in the study of chaotic dynamical systems, 
are undecidable; the problem of deciding whether a fourth-degree 
polynomial with integer coefficients has a zero is NP-complete. Our
new model seems very appropriate for the study of the foundations of 
scientific computing, and we are actively investigating the properties
of the model.

The various topics that we are considering have many links among 
themselves, as well as connections to the broader interests of ICSI.
For example, virtually every topic that we work on is enriched by 
considering it in the context of parallel computation and bringing 
randomized methods into play; our work on the probabilistic analysis 
of heuristics can shed light on the performance of heuristic learning
algorithms and heuristic geometric algorithms; and our work on 
computation over the reals involves consideration of dynamical 
systems, and thus may shed light on the dynamic behavior of neural 
nets.

The ICSI research program is oriented towards problems where 
interaction among Institute sub-disciplines is likely to be 
productive. The subgroup boundaries are loose, and most staff members 
have interests in more than one area. There is also an explicit effort 
to develop cooperative research programs with both local and i
nternational groups. In addition to the major areas of concentration,
ICSI maintains smaller efforts on problems of particular interest.
ICSI is an experiment in cooperation in a highly competitive field. By
maintaining its emphasis on open, basic research and interacting with 
other centers, the Institute hopes to contribute to international 
understanding as well as to computer science and engineering.


Address inquiries to:

   International Computer Science Institute
   1947 Center Street, Suite 600
   Berkeley, CA  94704-1105
   Phone (510) 643-9153;  FAX (510) 643-7684;  info@icsi.berkeley.edu

In Germany/Switzerland:

   GMD Heidelberg
   Im Weiher 12
   D-6900 Heidelberg
   GERMANY
   Phone +49 6221 46081;  FAX +49 6221 480279;  kunz@kmx.gmd.dbp.de

In Italy:

   Consiglio Nazionale delle Ricerche (CNR)
   Ufficio Relazioni Scientifiche
   e Progetti di Cooperazione Internazionali
   Piazzale Aldo Moro 7
   I-00100 Roma
   ITALY
   Phone +39 6 49 93 39 77;  FAX +39 6 4 46 98 33<R>

**********************************************************************




=============================================================================
Giorgio Ventre
International Computer Science Institute     Tel:+1 510 642-4274 Ext. 134
1947 Center Street, Suite 600                Fax:+1 510 643-7684
Berkeley, CA 94704                           e-mail: ventre@icsi.Berkeley.edu
=============================================================================


Newsgroups: soc.culture.italian