Franco Fest 2006: Talk Abstracts & Speaker Biographies

Excursions in Algorithmics:
A late festschrift for Franco P. Preparata

Brown University, October 27-28, 2006

Talk Abstracts & Speaker Biographies

Workshop Speakers

Monotony and Surprise
Alberto Apostolico
Georgia Institute of Technology & Accademia Nazionale dei Lincei

The problem of characterizing and detecting recurrent sequence patterns such as substrings or motifs and related associations or rules is pursued ubiquitously in order to compress data, unveil structure, infer succinct descriptions, extract and classify features, etc. The discovery, particularly on a massive scale, of significant patterns and correlations thereof poses interesting methodological and algorithmic problems, in so far as it often exposes scenarios in which tables and descriptors grow faster and bigger than the phenomena they are meant to encapsulate. While part of this problem is endemic, part of it can be attributed to the traditional approaches to the definition of a pattern, that hinge alternatively on syntactic or statistical properties alone. It has been seen recently that at least this part of the problem may be mitigated by more prudent paradigms, in which the syntactic description of a pattern and the list of all of its occurrences are tightly intertwined. This approach leads to identify regions of monotonicity for some scores of surprise in use, within which it is enough to consider and weigh only extremal terms and values. This talk reviews concepts, constructs, and application results obtained along this line of research.

Alberto Apostolico's research interests are in the areas of algorithms analysis and design, and applications. His work deals with algorithms and data structures for combinatorial pattern matching and discover. His collaboration with Franco Preparata on this subject led to papers for finding repetitions in strings and for computing exhaustive substring statistics. He is a co-editor (with Z. Galil) of the books ''Combinatorial Algorithms on Words'' (Springer- Verlag) and ''Pattern Matching Algorithms'' (Oxford Univ.Press), serves on the editorial boards of Parallel Processing Letters, Theoretical Computer Science, Journal of Computational Biology, Chaos Theory and Applications, International J. of Bioinformatics Research and Applications, International Journal on Foundations of Computer Science, Springer-Verlag Lecture Notes on Bioinformatics, and as guest editor for a special issues of Algorithmica, Information Sciences, Journal of Discrete Algorithms, PPL, and TCS.

A founding member of the steering committee of the International Symposia on Combinatorial Pattern Matching , the Proceedings of which he co-edited in 1993, 1994, 1997, 2002, and 2005, he also serves on the steering committees of the International Conferences on Discovery Science, and of the Symposia on String Processing and Information Retrieval. With Franco Preparata he was founding executive committee member of the Fibonacci Institute for the Foundations of Computer Science, which held Summer Research Schools in Trento from 1987 to 1993. He has served on the program committees of many international conferences, most recently, Research in Computational Biology (RECOMB), Workshop on Algorithms in Bioinformatics (WABI), IEEE Data Compression Conference, String Processing and Information Retrieval (SPIRE), Combinatorial Pattern Matching (CPM), among others, and as an invited speaker at numerous international conferences and advanced research schools.

In his career, Alberto Apostolico has held visiting and permanent appointments in the U.S. (CMU, UIUC, Rensselaer, Purdue, IBM, GATech) and Europe (U. of Salerno, U. of L' Aquila, U. of Padova, IASI-CNR, U. of Paris, U. of London, King's College, Zif-Bielefeld, Renyi-Hungarian Acad. of Science). He has been the (co-)recipient of US (Air Force, NIH, NSF, IBM), British, French, Italian, Collaborative (Israel, Korea, Japan), and International (Fulbright, NATO, ESPRIT) research grants.

On-Line Algorithms, Real-Time, the Virtue of Laziness and the Power of Clairvoyance
Giorgio Ausiello
University of Rome "La Sapienza"

In several circumstances we have to solve a problem whose instance is not completely known in advance. Situations of this kind occur in computer systems and networks management, in financial decision making, in robotics etc. Problems of this kind are called on-line problems. In most applications (e.g. paging) an agent is required to serve requests in an on line fashion and a request has to be served by the agent before a new request is revealed. In such cases the notion of time is simply used to refer to a totally ordered sequence of discrete instants (t0, t1, ..., tn). Both requests and agent's service actions occur instantanaously in one of these moments. The actual time intercurring between two instants is not specified and inessential under any respect. A different situation occurs instead in other problems where the time dimension is continuous and plays a specific role. We call this kind of problems real time on-line problems. In this paper we address a specific class of real time on-line problems: vehicle routing problems. By examining the properties of this paradigmatic type of problems, we put in evidence the role of real time in the design of competitive algorithms, in the construction of adversarial arguments and in the definition of clairvoyancy.

(joint work with L. Allulli, V. Bonifaci, L. Laura)

Giorgio Ausiello graduated in Physics in 1966 at the University of Rome "La Sapienza". He is Full Professor of Theoretical Computer Science at the Faculty of Engineering of the same university since 1980. Over the years, his research activity has addressed the following domains: computational complexity, database theory, approximation of NP-hard optimization problems, dynamic and on line algorithms. On these topics he published 9 books and over 100 papers in major journals and conferences. In 1973 he has been one of the founders of the European Association for Theoretical Computer Science (EATCS) and he has been member of the EATCS Council almost continuously since the foundation. Since 1980 he belongs to the Advisory Board of the Springer series of EATCS monographs. Since January 2001 he is Editor in Chief of the Elsevier journal Theoretical Computer Science (Series A: Algorithms, automata, complexity and games). He is also Editor of the International Journal of Foundatiosn of Computer Science. From 1996 to 2000 he coordinated a group of eleven Universities in the EU Basic Research ALCOM-IT project (Algorithms and Complexity in Information Technology). Since January 1997 to December 2002 he has been Chairman of the IFIP Technical Committee on Foundations of Computer Science (TC1). Since 1996 to 2000 he has served in the Board of Trustees of the International Computer Science Institute (ICSI) in Berkeley, Ca. In 1996 he has been elected member of Academia Europaea. In 2004 he has been granted the title of Doctor Honoris Causa of Dauphine University (Paris).

How Well Can Physical Machines Approximate the Ideal RAM?
Gianfranco Bilardi
University of Padova & IBM Research

It is widely agreed that machines based on sequential programming are increasingly inadequate to fully exploit the potential of present and forthcoming technologies. However, a rigorous quantitative assessment of the inherent limitations of the sequential approach does not seem to be available. In this context, we take a look at two interrelated issues:

We will present some results sheding light on the above questions as well as a few open problems.

Gianfranco Bilardi has earned his Ph.D. in Electrical Engineering in 1985, from the Department of Electrical Engineering of the University of Illinois at Urbana Champaign, with a thesis supervised by Franco Preparata. He first joined Computer Science at Cornell University as an Assistant Professor. In 1990, he became a Professor of Computer Science at the University of Padova, where he is currently the Coordinator of the Center of Excellence "Science and Applications of Advanced Computing Paradigms." Since 2000, he has also been affiliated with the T.J. Watson Research Laboratory of IBM. Bilardi's research interests lie in the areas of theory of computation, and algorithms and architectures for high performance computing.

Non-Linear Computational Geometry: an Introduction
Jean-Daniel Boissonat
INRIA Sophia-Antipolis

Franco's book (co-authored by M. Shamos) "Computational Geometry : an Introduction", the very first text book in Computational Geometry, was devoted to Linear Geometry: points, lines, triangles, rectangles were the objects of primary interest. 20 years later, Non-Linear Computational Geometry is emerging as a new exciting area. The talk will revisit some chapters of Franco's book from this perspective, discuss some recent results on proximity problems and the geometry of spheres, and present some applications in Information Computational Geometry and Geometric Approximation.

Jean-Daniel Boissonnat graduated from the Ecole Superieure d'Electricité in 1976. He obtained a Ph.D. in Control Theory from Rennes University in 1979. He joined INRIA-Rocquencourt in 1980 and started working there on surface reconstruction while reading M. Shamos's thesis (which, after Franco's collaboration, became the first text book in Computational Geometry). He moved to INRIA Sophia-Antipolis in 1986 where he successively led the PRISME and Geometrica projects devoted to Discrete and Computational Geometry and their applications, most notably geometric modeling, surface reconstruction, mesh generation and motion planning. He initiated the development of the CGAL library at INRIA and, partly in collaboration with Franco, contributed to robust geometric computing. He co-authored, with M. Yvinec, the book ``Algorithmic Geometry'' (Ediscience International and Cambridge University Press). He has received the IBM award in Computer Science in 1987, the FIAT/French Academy of Science award in 1989 and has been elected Chevalier de l'Ordre National du Mérite in 2006. He is currently on the editorial board of four international journals devoted to algorithms, computational geometry and graphics. He co-chaired the program committee of the 20th ACM Symposium on Computational Geometry. Jean-Daniel met Franco for the first time at the Ecole Normale Superieure in Paris in 1987 where Franco was on sabbatical leave from the University of Illinois. Since then, they worked together on fundamental geometric algorithms, robust computation and motion planning.

Data-Powered Algorithms
Bernard Chazelle
Princeton University

Motivated by the need to cope with data that is massive, high-dimensional, noisy, uncertain, unevenly priced, low-entropic, or all of the above, algorithm design is undergoing profound changes. I will discuss some of these developments; in particular, sublinear algorithms, online reconstruction, self-improving algorithms, and dimension reduction.

Bernard Chazelle is professor of computer science at Princeton University, where he has been on the faculty since 1986. He has held research and faculty positions at Carnegie-Mellon University, Brown University, Ecole Polytechnique, Ecole Normale Superieure, University of Paris, INRIA, Xerox Parc, DEC SRC, and NEC Research. He received his Ph.D in computer science from Yale University in 1980.

Computing Equilibria for Markets and Games
Bruno Codenotti
Italian National Research Council (CNR)

I will present some recent results on the computation of equilibria both in game-theoretic and economic scenarios. I will particularly focus on problems which pose significant challenges to algorithmists.

Bruno Codenotti is a Research Director of the Italian National Research Council. He was the Director of the Institute for Computational Mathematics in Pisa. He has been a visiting professor at several institutions in the US, including the University of Illinois at Urbana Champaign, ICSI in Berkeley, Cornell University, Sandia National Labs, The University of Chicago, University of Iowa, and TTI-Chicago. He has taught undergraduate and graduate courses in Italy, China, and the US. His research interests are in algorithmics, particularly problems with an algebraic flavor. In the last few years he has worked extensively on the computation of equilibria for markets and games.

Succinct Representations of Triangulations and Planar Maps
Olivier Devillers
INRIA Sophia-Antipolis

In this talk, we address the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on designing data structures that preserve the possibility of answering incidence queries in constant time. We propose in particular the first optimal representation for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. Optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-c planar graphs, and 1.62 bits per triangle or equivalently 3.24 bits per vertex for triangulations. This work presents a rather theoretical point of view, in conclusion we will discuss the possibility of more practical versions.

This is joint work with Luca Castelli Aleardi, Abdelkrim Mebarki and Gilles Schaeffer.

Olivier Devillers is a former student of École Normale Supérieure in Paris and he received his PhD in computer graphics in 1988 (Claude Puech advisor) from Paris XI University. Then his interest focused on computational geometry and he obtained his Habilitation à diriger des recherches in 1993 from Nice Sophia-Antipolis University.

Olivier Devillers' work happened in a period where computational geometry was evolving from a combinatorial and rather theoretical point of view to a more practical one. He participated in this evolution through his work on the design on simpler randomized algorithms, the treatment of robustness issues and the development of the Computational Geometry Algorithms Library. His Delaunay hierarchy algorithm for Delaunay computation mixed up all these ingredients and is available in CGAL.

Olivier Devillers has been collaborating with Franco Preparata since 1990, and visited him several times in Brown University. They co-authored the following papers :

Inspirations in Parallelism and Computational Geometry
Michael T. Goodrich
University of California, Irvine

In this talk I will survey areas of research I have been involved in that have been inspired by work pioneered by Franco Preparata. Topics include algorithms for problems involving parallelism and computational geometry. This talk will be presented at a level that should be of interest to theory and non-theory people alike.

Dr. Michael Goodrich is a Professor of Computer Science at University of California, Irvine, where he has served since 2001. Prior to that he was a Professor of Computer Science at Johns Hopkins University for 14 years. He received his PhD in Computer Sciences from Purdue University, in West Lafayette, Indiana, in 1987 and his B.A. in Mathematics and Computer Science at Calvin College, in Grand Rapids, Michigan, in 1983.

He has published nearly 200 research papers and is a co-author on three textbooks: Data Structures and Algorithms in Java, which is now in its 4th edition, Data Structures and Algorithms in C++, and Algorithm Design: Foundations, Analysis, and Internet Examples. He is on the editorial board of Journal of Computer and Systems Sciences, Computational Geometry: Theory and Applications, International Journal of Computational Geometry and Applications, and Journal of Graph Algorithms and Applications. In 1996 he received an ACM Recognition of Service Award and in 2002 he received a Technology Transfer Award from DARPA. He is a member of ACM, a senior member of IEEE, and a member of the Sigma Xi Scientific Research Honor Society. His research has been funded by grants from NSF, including two ITR grants and a Research Initiation Award, as well as grants from DARPA, NSA, and a MURI grant from ARO led by Franco Preparata as Principle Investigator.

Dr. Goodrich has done research in parallel algorithms, computational geometry, combinatorial algorithms, and computer security. He has also published several pioneering papers on external memory algorithms for problems in graph algorithms and computational geometry.

Matching Algorithms for Structural Bioinformatics
Concettina Guerra
University of Padova & Georgia Institute of Technology

The analysis of 3D structures of objects and the identification of regions of similarity among structures arises in diverse applications and has been the subject of much study. In computational biology, the search for common structural motifs in a set of proteins is believed to help reveal functional relationships among different proteins and to lead to the discovery of evolutionary relations not evident from the amino-acid sequence alone. In this talk, I discuss various matching techniques and present recent approaches to protein surface comparison that can be useful in docking applications.

Concettina Guerra earned her Dr. Sc. Degree in Mathematics (with honors) from the University of Naples in 1972. She has been on the Faculty of the Dept. of Computer Sciences of Purdue University, of the Dept. of Informatics of University of Rome and has visited several Institutions in the US and in Europe, including Carnegie Mellon University, Rensseleaer Polytechnic and University of Helsinki.

Concettina Guerra works in the areas of Computational Biology and Computer Vision. Her recent interests fall in the domains of protein classification, recognition and docking, where she develops geometric approaches to such tasks as protein comparison and identification of sites on molecular surfaces that are likely to be of biological interest.

She has organized and served on several meetings; more recently, she has been conference chair of RECOMB (2006), co-director of the Lipari School on Proteomes and Proteins (2006), and co-chair and a founding member of the steering committee of 3DPVT (2002).

Stable Matching Problems
Kazuo Iwama
Kyoto University

Stable matching is one of the oldest problems studied from an algorithmic point of view. Also it has a lot of real-world applications, including the National Resident Matching Program in the US which started in 1952. Thus the problem has a very long history of research, but there still remains many interesting problems. For example, for its most general version, allowing both ties and incomplete lists, nothing was known until 1999 for its complexity. Very recently, Iwama, Miyazaki and Yamauchi found its approximation algorithm whose approximation factor is strictly less than two (SODA 07). This talk explain why this problem is so interesting and deep, from several different angles including the newest result above mentioned.

PhD from Kyoto University in 1980, with Kyoto Sangyo University (1978-90), Kyushu University (90-97) and Kyoto University (97-present). Now Professor in the School of Informatics. Editorial board of Information Processing Letters, Parallel Computing, International Journal of Foundations of Computer Science and so on. Council Member of European Association for Theoretical Computer Science (EATCS), Steering Committee Member of European Symposium on Algorithms (ESA), and Chair of the New Horizons in Computing (NHC) project.

Franco Preparata loves Kyoto and has had a long relation (since well before I knew him) with the research group of Shuzo Yajima and Yahiko Kambayashi, Kyoto University. After I joined this group, Franco occasionally visited us; the two important ones for me are in mid 80's and in 97. It was him who pointed out that the string problem I was working on in early 80's was nothing other than parallel computation, which just led me to that topic and more importantly to algorithms from automata theory. Also, he gave a very impressive talk on Grover's algorithm in 97, which again made me interested in quantum computation that is now one of my most important research topics.

Algorithms for Sequence Finding and Selection Problems
Der-Tsai "D.T." Lee
Academia Sinica & National Taiwan University

In this talk we present an overview of problems related to sequence manipulation, including searching subsequences of maximum density or maximum sum, and selecting subsequences of a certain density or a given rank, with or without length restrictions. Problem transformation and utilization of efficient data structures or problem-solving methods will be presented. The problem-solving methods are fundamental to computational problems, which arise, for example, in bioinformatics. (Joint work with Tien-Ching Lin.)

Dr. Lee received his B.S. degree in Electrical Engineering from the National Taiwan University in 1971, and the M.S. and Ph. D. degrees in Computer Science from the University of Illinois at Urbana-Champaign in 1976 and 1978 respectively. Dr. Lee has been with the Institute of Information Science, Academia Sinica, Taiwan, where he is Director and a Distinguished Research Fellow since July 1, 1998. Prior to joining the Institute, he was a Professor of the Department of Electrical Engineering and Computer Science, Northwestern University, where he has worked since 1978. Dr. Lee holds a joint appointment with the Department of Computer Science and Information Engineering, and the Graduate Institute of Electronics Engineering, National Taiwan University, also serves as Director of the Taiwan Information Security Center (TWISC) and the Chief Executive Officer of the National Digital Archives Program, both sponsored by the National Science Council, Taiwan.

Dr. Lee's research interests include design and analysis of algorithms, computational geometry, web-based computing, algorithm visualization, software tools development, bio-informatics, digital libraries, and software security. He has published over 120 technical articles in scientific journals and conference proceedings, and he also holds three U.S. patents, and one R.O.C patent. He is Editor of Algorithmica, Editor of ACM Journal on Computers and Cultural Heritage, Co-Chief Editor of Int'l Journal of Computational Geometry & Applications, Editor-in-Chief of Journal of Information Science and Engineering, and Series Editor of Lecture Notes Series on Computing for World Scientific Publishing Co., Singapore. He is Fellow of IEEE, Fellow of ACM and elected Member of Academia Sinica, 2004.

During the years 1974 -1978, D. T. was a graduate student of the Department of Computer Science, University of Illinois at Urbana-Champaign, and worked at the Coordinated Science Laboratory, from 1975 through 1978 under the supervision of Prof. Franco Preparata. The Coordinated Science Laboratory was established in 1951, and is one of the premier laboratories in the U.S. in information technology and telecommunications. It was during these years with Franco, that D.T. received this excellent training in research, and problem-solving skills in the scientific discipline. And it was during these years with Franco, that D.T. was constantly and consistently under his influence of being a sound and whole individual, striving for knowledge in ancient culture and modern world, and living a life full of energy, affection, hope and respect.

Drawing Colored Graphs on Colored Sets of Points
Giuseppe "Beppe" Liotta
University of Perugia

Semantic constraints for the vertices of a graph G define the placement that these vertices must have in a readable visualization of G. For example, in the context of data base design some particularly relevant entities of an ER schema may be required to be represented in the center and/or along the boundary of the diagram. An effective way of modelling semantic constraints is to map groups of semantically related vertices to corresponding given sets of points in the plane.

This talk surveys some recent findings about drawing algorithms that receive as input a planar graph G, a partitioning of the vertices of G into k different semantic categories V0, ..., Vk-1, and k disjoint sets S0, ..., Sk-1 of points in the plane with |Vi|=|Si| (i in {0, ..., k-1}). The desired output is a planar drawing such that the vertices of Vi are mapped onto the points of Si and such that the curve complexity of the edges (i.e. the number of bends along each edge) is kept small. Particular attention will be devoted to proving lower bounds and upper bounds on the curve complexity of these types of drawings for the apparently innocent cases of just two or three semantic categories.

Giuseppe "Beppe" Liotta received a Ph.D. in Computer Engineering from the University of Rome ``La Sapienza'' in 1995. From May 1995 to September 1996 he was a Post Doc at Brown University , where he worked with Franco Preparata and Roberto Tamassia mainly on computational geometry problems and more specifically on questions of robust geometric computing. The many exciting hours of research spent under the supervision of Franco during those years not only produced scientific results but also strongly influenced the next years of Beppe's scientific career.

From October 1996 to October 1998 Beppe was assistant professor (ricercatore) at the Department of Computer Engineering of the University of Rome ``La Sapienza''. He then joined the Department of Electrical Engineering and Computer Science of the University of Perugia, where he served as associate professor from 1998 to 2002. From 2002 Beppe is a professor of computer science and currently serves as the chair of the studies in Computer Science and Electrical Engineering of the University of Perugia.

His research interests are mainly directed at the design of algorithms for solving problems motivated from graph drawing, computational geometry, and information visualization. On these topics he edited special issues, wrote book chapters and surveys, organized conferences and workshops, and published about 100 research papers. He received awards by EATCS and by ACM. His research has been funded by MIUR, CNR, NATO, EU, and by several industrial sponsors.

Compressing and Searching XML Data Via Two Zip
Fabrizio Luccio
University of Pisa

XML is fast becoming the standard format to store, exchange and publish over the web. Two challenges in handling XML are its size (the XML representation of a document is significantly larger than its native state) and the complexity of its search (XML search involves path and content searches on labeled tree structures). We address the basic problems of compression, navigation and searching of XML documents. Adopting some algorithms proposed in FOCS 05 for succinct tree representations, we design and implement a compressed index for XML, called XBzipINDEX, in which the XML document is maintained in a highly compressed format, and both navigation and searching can be done uncompressing only a tiny fraction of the data. Detailed experiments show that XBzipINDEX has compression ratio up to 35% better than the ones achievable by other tools, and its time performance on some path and content search operations is order of magnitudes faster. The method is being patented by the University of Pisa.

Joint work with Paolo Ferragina, Giovanni Manzini, and S. Muthu Muthukrishnan.

Fabrizio Luccio was born in Tripoli, Axis of Evil, in 1938. Citizen of Italy. He received the Dr.Ing. degree in electrical engineering from the Politecnico di Milano, in 1962, and the Libera Docenza in electronic computers from the Italian university system in 1968. He is currently a Professor of Informatics at the University of Pisa.

After industrial experience with Olivetti, he taught and conducted research in various fields of C.S. at the Politecnico di Milano, M.I.T. (Project MAC), the University of Southern California, and New York University, before returning permanently to Italy. where he became a professor at the University of Pisa, serving as department chairman for six years, and as coordinator of the Ph.D. program in Informatics for other six years. He spent several sabbatical periods as a visiting professor at U.C.L.A., the University of Illinois, the National University of Singapore, Carleton University in Canada, and the B.U.A.P. in Puebla, Mexico. He has been a visiting scientist at T.J. Watson Research Center of IBM, USA, and a distinguished foreign scholar at the NTT LSI Laboratories in Morinosato, Japan. He has also been a distinguished scientist in the city of Ottawa, Canada, invited by the municipality to carry on cooperative research with the local universities. He has pursued intense activities with UNESCO, for the dissemination of informatics at the university level in developing countries. He received several scientific and academic prizes, and is a Life Fellow of the IEEE.

For a long time his major scientific interest has been in computing systems, particularly in parallel and distributed processing. It is now in algorithms and data structures, with attention to Web problems. He is author of more than one hundred and fifty papers published in international research journals and conference proceedings, and of four major university text books published in Italy.

Fragmented Data Storage in Sensor Networks
Piero Maestrini
University of Pisa & CNR

We consider a scenario where sensing devices equipped with wireless transceivers are distributed over a remote area to acquire and store data. Stored data are then collected by a mobile data host (e.g. an aircraft) visiting sporadically the area and establishing wireless communication with the sensors. Sensors are inexpensive devices possessing limited storage and limited, renewable power sources (e.g., tiny batteries fed by solar cells). In any single visit, the mobile host may be unable to establish communication with any single sensor, due to temporary depletion of battery or to obstacles shadowing the sensor. The same sensor may be again able to connect to the host and to upload data in a later visit, but some acquired data may be lost if the local storage capacity has meantime been exceeded. Security issues are also a major concern if sensors are set to collect sensible data in a hostile environment. Reliable and secure data collection in this scenario is a challenging task and redundancy appears the only reasonable approach. Setting multiple sensors to collect the same data is easily feasible, since sensors are cheap resources.

We propose an approach exploiting redundancy, where the same data are acquired by multiple sensors. Acquired data are encoded in a Residue Number System with Non-Pairwise-Prime Moduli (RNS-NPM). RNS-NPM are defined over a set M of composite moduli and a set P of pairwise-prime factors, where every factor p in P divides exactly two moduli in M. Every sensor is tied to a modulus mi in M and stores the residue digit modulo mi of the local readings. Information is thus fragmented and dispersed over the sensors: the residue digits are the fragments; every sensor stores a fragment and every fragment is stored in at least one sensor. Given the redundancy of the code, the information can be reconstructed from the fragments in any subset D' of the set D of all digits, provided the cardinality d' of D' is no less than a threshold depending on the code redundancy. With this approach, in every visit the mobile host attempts connection with all sensors. Some sensors may fail to respond, but the temporary loss of communication does not prevent reconstructing the full information, as long as at least d' residue digit can be collected. It should be observed that sensors acquire data independently from each other, and thus different sensors may read different values, although the readings can be expected to be very close in value, unless some fault occurs. Since every sensor stores a single digit of the residue encoding of its reading and the mobile data hosts collects every digit from a different sensor, the set of collected digits may be inconsistent. Reconstructing the information from the raw digits may thus produce a wrong result. However, a nice property of RNS-NPM enables the decoding procedure to guess the average of the readings, as long as every reading is within d/4 from the average, where d is the minimum of factors in set P. Fragmentation and dispersal of data also saves the scarce storage resources of sensors and contributes to data security. In fact the data acquired by sensors cannot be reconstructed unless all digits in a subset D' of sufficient cardinality are collected and the association of every sensor to a unique modulus in M is known. Eavesdropping communication between sensors and the data host, or even seizing sensors, cannot allow reconstruction, unless the above condition are satisfied. Of course, this feature can be combined with encryption of residue digits.

Joint work with Stefano Chessa.

[BM1980] Barsi, F. and Maestrini, P. "Error codes constructed in residue number systems with non-pairwise-prime moduli". Information and Control, vol. 46 n. 1 (1980), pp. 16-25.

Piero Maestrini received the Laurea degree in Electronic Engineering from the University of Pisa and the Scuola Superiore SantAnna in 1962. In 1971 he was also granted the Libera Docenza, a national academic degree, in Switching Theory and Electronic Computers. From 1962 to 1981 he was a member of research staff of the Istituto di Elaborazione dell'Informazione of the National Science Council (IEI-CNR, Pisa). From 1981 to present he has been full professor of Computer Science in the Computer Science Department of the University of Pisa. From 1974 to 1981 he chaired the System Architecture Department of IEI-CNR, and from 1974 to 1977 he also directed a common Research Center of IEI-CNR and Selenia SpA. In 1986 and 1987 he was the delegate for research of the Rector of the Pisa University. From 1987 to 1990 he was the Dean of the Faculty of Science of the University of Pisa. From 1995 to 2002 he was the director of the IEI-CNR, Pisa, and subsequently, from 2002 to June 2006, he has been the director of the Istituto di Scienza e Tecnologie dellInformazione A. Faedo of the National Science Council (ISTI-CNR, Pisa). In 1992 he has been honored by the University of Pisa with the Ordine del Cherubino. He has visited the University of California at Los Angeles, the University of Illinois at Urbana-Champaign, the IBM Thomas J. Watson Research Center, Yorktown Heights, NY, the Tata Institute of Fundamental Research, Bombay, India, and the Centre for the Development of Advanced Computing (C-DAC), Pune and Bangalore, India. He has been the author or co-author of about 100 published papers and two books, in Computer Arithmetic and Operating Systems. Early research addressed Computer Architecture and Design and Computer Arithmetic. The bulk of subsequent production has been in Coding Theory, with major contributions to Arithmetic Residue Codes, and in many theoretic and algorithmic aspects of Self-Diagnosis of Multiprocessor Systems. Recent and present research addresses Wireless, Mobile Networks and Sensor Networks, with prevailing emphasis on routing algorithms, dependability and data security.

Personal Note: I first met Franco in the early seventies, when for a while he joined the University of Pisa, and I was inspired by his early work on System Level Diagnosis, a topic which he initiated and became a recurrent topic of my research. In 1977-78 I visited the University of Illinois and, beside being associated with his research, I found support and friendship from him and his family. From 1998 to 2005, Franco has been the most distinguished member of the Advisory Board of IEI-CNR and ISTI-CNR, and I owe gratitude to him for invaluable advice and encouragement.

Reliable and Efficient Geometric Computing
Kurt Mehlhorn
Max-Planck-Institute for Computer Science

Reliable implementation of geometric algorithms is a notoriously difficult task. In fact, most implementations (academic and commercial) of geometric algorithms fail on some input instances, i.e., crash or give an incorrect answer.

In the introductory part of the talk, we illustrate the pitfalls of geometric computing [ClassRoomExample] and explain for one algorithm in detail where the problem lies and what goes wrong.

In the main part of the talk, we discuss a recent approach to reliable and efficient geometric computing: controlled perturbation. The approach was introduced by D. Halperin and co-workers {Halperin-Shelton:perturbation,Halperin-Raab:perturbation,Halperin-Leiserowitz} and refined by us [Controlled-Perturbation-General-Strategy,controlled-perturbation]. We show that the approach applies to a large class of geometric algorithms, in particular, most algorithms in CGAL (Computational Geometry Algorithms Library), and yields correct and efficient implementations. The method is easy to use.

Prof. Dr. Kurt Mehlhorn is the Director at the Max-Planck-Institute for Computer Science, Saarbrucken, Germany. He was born 1949, received his Ph.D. from Cornell University in 1974, and has been a professor in Saarbrucken since 1975. He is the recipient of many awards, including: Leibniz-Preis der deutschen Forschungsgemeinschaft (1986), Humboldt-Award (1989), Karl-Heinz-Beckurts-Award (1994), Member of Academia Europaea (1995), Konrad-Zuse-Award (1995), ACM Fellow (1999), Honorary doctorate degrees from Magdeburg and Waterloo, Berlin-Brandenburg Academy of Science, Leopoldina. His research interests include data structures, graph algorithms, computational geometry, parallel algorithms, implementation of algorithms, algorithm engineering. He has published extensively, including 6 books and close to 200 articles in scientific journals and conferences.

Kurt and Franco have shared two research visits - Kurt spent the summer of 1982 at UIUC and Franco spent the summer of 1985 in Saarbrucken. These visits resulted in a number of joint publications, including

Perfect Simulation of Normal-Form Mechanisms
Silvio Micali
Massachusetts Institute of Technology

We prove a general result bridging the fields of Secure Protocols and Game Theory.

In game-theoretic terms, we show that ANY normal-form mechanism Has an equivalent UNMEDIATED, extensive-form mechanism played with ballots and a ballot box---the venerable devices used throughout the world to privately and correctly compute the tally of secret votes.

In cryptographic terms, we show that, in ANY joint computation, security can be achieved based solely on the players' RATIONALITY, rather than on the HONESTY of some of them.

Our result has broad implications for Mechanism Design; in particular, it enables One to design mechanisms in a MODULAR and COMPETITIVE fashion.

Joint work with Sergei Izmalkov and Matt Lepinski.

Silvio Micali received his Laurea in Mathematics from the University of Rome in 1978, and his Ph.D. in Computer Science form the University of California at Berkeley in 1982. He joined MIT's faculty in 1983, where is the co-founder and co-leader of the Information and Computer Security Group. His research focuses on developing the modern theory of pseudo-random generation, encryption, digital signatures and secure protocols. A member of the American Academy of Arts and Sciences, he has won the Goedel Prize in theoretical computer science, and the RSA prize in cryptography.

More importantly, Silvio has befriended Franco for 30 years, and continues to share with him jokes and serious thoughts in huge and equal amounts. Important lessons that Silvio learned from Franco:

  1. "if you are serious about a scientific career, leave!" (inspiring advice after an inspiring talk at the University of Rome in the 70's);
  2. "Whatever your destination, pack your slides before the toothbrush."
  3. "Never trust a man who does not like to laugh."
  4. The more you live abroad, the more Italian you get. (Personal deduction after seeing Franco and Rosa Maria in action for 30 years.)
  5. Marry the right person. (Similarly personal deduction).

Grazie Franco!

Medical Embedded Systems
Majid Sarrafzadeh
University of California, Los Angeles

Light-weight embedded systems are now gaining more popularity due to recent technological advances in fabrication of more powerful tiny processors. In particular, the field of pervasive computing and medical monitoring is emerging due to the development of tiny and low-profile computing nodes, mated with sensors and actuators, in close proximity to the human.

In distributed embedded systems, often battery-powered, it is critical to extend the system lifetime for each individual node in order to retain the functionality of the entire network for the longest possible time. We will describe an -optimal polynomial time technique that evenly distributes the communication load over the nodes. This formulation can be exploited to optimize system power consumption or to enhance network reliability. Both power and reliability issues are among the most significant concerns in medical embedded systems.

Majid Sarrafzadeh (M'87, SM'92,F'96) ( received his Ph.D. in 1987 from the University of Illinois at Urbana-Champaign in Electrical and Computer Engineering under the supervision of Professor Franco Preparata. He joined Northwestern University as an Assistant Professor in 1987. In 2000, he joined the Computer Science Department at University of California at Los Angeles (UCLA). His recent research interests lie in the area of Embedded and Reconfigurable Computing, VLSI CAD, and design and analysis of algorithms. Dr. Sarrafzadeh is a Fellow of IEEE for his contribution to "Theory and Practice of VLSI Design". He has served on the technical program committee of numerous conferences in the area of VLSI Design and CAD, including ICCAD, DAC, EDAC, ISPD, FPGA, and DesignCon. He has served as committee chair of a number of these conferences. He is on the executive committee/steering committee of several conferences such as ICCAD, ISPD, and ISQED. He was the program committee and the general chair of ICCAD in 2004 and 2005, respectively, the premiere conference in CAD.

Professor Sarrafzadeh has published approximately 350 papers, co-authored 5 books, and is a named inventor on 6 US patents. Dr. Sarrafzadeh is an Associate Editor of ACM Transaction on Design Automation (TODAES) and an Associate Editor of IEEE Transactions on Computers and a number of other journals.

Dr. Sarrafzadeh has collaborated with many industries in the past fifteen years including IBM and Motorola and many CAD industries and was the architect of the physical design subsystem of Monterey Design Systems - Synopsys acquired the company. He was a co-founder of Hier Design, Inc. Hier Design was acquired by Xilinx in 2004.

Professor Sarrafzadeh has graduated about 30 PhD students, 11 of who are working in academia.

Personal Note: I took a course with Franco in 1981 on Advanced Logic. I loved his style of teaching and loved the topic. I decided to work with him. As I entered grad school in 1982 he offered me an RA, the best news of my life at the time. I studied Channel Routing for my PhD. The kind of things I do today have nothing to do with Channel Routing and are not always deeply theoretical, however, the foundation I have obtained as Franco's student has proved most valuable. Quoting the famous Chinese proverb, one of Franco's favorite sayings, "Give a man a fish and you feed him for a day. Teach a man to fish and you feed him for a lifetime." I must say that I had the best fishing instructor.

From VLSI to Nanotechnology
John E. Savage
Brown University

Franco Preparata has had a major influence on the research directions that many of us have pursued. In this talk I will reminisce about his impact on my involvement in VLSI as well as describe my current work on nanotechnology that was inspired by the early work. The academic community was introduced to the problems of VLSI in the 1970s by interlocutors who bridged the world of chip manufacture and academia. Very quickly theoreticians formulated and addressed many new and interesting questions. As we enter the age of nanotechnology similar interesting questions arise. I will give an overview of VLSI research as well as provide a quick introduction to the new problems of nanotechnology.

John Savage began his research career as a coding and information theorist within electrical engineering. The observed complexity of decoders for error-correcting codes propelled him to investigate the complexity of decoders. This naturally led into a study of tradeoffs between computational resources and to the study of circuit complexity, a fundamental computational measure in terms of which tradeoffs can be expressed. Much of this work was captured in his 1976 book The Complexity of Computing which made evident the importance of circuit complexity to theoretical computer science. He has also written a textbook for a computer literacy course with two undergraduates in the mid-1980s and a nearly comprehensive introduction to theoretical computer science in the late 1990s.

A recurring theme in Prof. Savages work is the development of fundamental limits on computation, a theme that emerged in the study of decoder complexity. It has been expressed in the development of lower bounds, whether they be on a single resource, such as circuit size or depth, or expressed as tradeoffs between computational resources, such as space and time in serial computation, area and time in VLSI computation, or primary storage capacity and I/O operations in I/O-limited computations. It has also been seen in the classification of problems by their membership in traditional complexity classes, such as P, NP, and BPP. Another recurring theme has been the design and analysis of algorithms, which has been expressed in several areas including serial and parallel computer aided design, distributed computing for scientific computation, and his recent work on computational nanotechnology. The challenge of the latter area is to produce deterministic computing elements when the assembly process is stochastic and unpredictable. Computer architecture, probability theory, and complexity analysis play important roles here.

Graphs: From VLSI Layout to Biomedical Informatics
Ioannis "Yanni" G. Tollis
University of Crete

Graphs are important tools for solving many problems in a multitude of application areas. In this talk we will describe several results from VLSI layout, graph drawing, computational geometry, and biomedical informatics. The common underline theme is that in order to obtain these results we use graphs combined with geometry, a combination originally taught to me by the master, Franco Preparata.

Dr. Ioannis (Yanni) G. Tollis is a Professor of Computer Science at the University of Crete, and the head of the Biomedical Informatics Laboratory (BMI lab.) at the Institute of Computer Science at FORTH (ICS-FORTH). He received his Ph. D. degree in Computer Science from the University of Illinois at Urbana-Champaign in 1987. His Ph.D. thesis dealt with Algorithms for VLSI Layout and was done under the guidance of Franco Preparata. The nice mix of graphs, geometry, and VLSI theory that Franco provided through his advise and insight was extremely important not only for the thesis itself, but for the rest of Yanni's carreer.

After his Ph.D. he joined the faculty of The University of Texas at Dallas, where he was a Professor of Computer Science, and director of the CAD and Visualization lab. until 2004 (now a research professor).

He has published seven books, over 110 journal and conference papers, and has given more than 50 invited lectures world-wide. His research has been funded by numerous funding agencies and companies. He is the owner of a U.S. patent and several of his projects have been licensed by companies for commercial distribution. He is editor-in-chief of the electronic Journal of Graph Algorithms and Applications and was a member of the editorial board of the IEEE Transactions on Computers (2000-2004). He has served in several program committees of conferences including, among others, the International Symposium on Graph Drawing, and is a founding member of the steering committee for Graph Drawing.

The Combinatorics of Sequencing by Hybridization
Eli Upfal
Brown University

Sequencing by hybridization is a novel DNA sequencing technique in which an array (SBH chip) of short sequences of nucleotides (probes} is brought in contact with a solution of (replicas of) the target DNA sequence. A biochemical method determines the subset of probes that bind to the target sequence (spectrum of the sequence), and a combinatorial method is used to reconstruct the DNA sequence from the spectrum. Since technology limits the number of probes on the SBH chip, a challenging combinatorial question is the design of a smallest set of probes that can sequence almost all DNA string of a given length. We'll present combinatorial designs that improve the performance of SBH, using universal bases (bases that bind to any nucleotide), and related methods. The talk will focus on the combinatorial and algorithmic issues, with only brief introduction to the micro-biology background. (Joint work with Franco Preparata and Alan Frieze.)

Eli Upfal is a professor of computer science at Brown University and since 2002 also the department chair. Before coming to Brown in 1998, he was a researcher and project manager at the IBM Almaden Research Center in California, and a professor at the Weizmann Institute in Israel. He received an undergraduate degree in mathematics and statistics and a doctorate degree in computer science from the Hebrew University in Jerusalem, Israel.

His research focuses on the design and analysis of algorithms. In particular he is interested in randomized algorithms and probabilistic analysis of algorithms. Applications range from combinatorial and stochastic optimization to routing and communication networks, computational biology, and computational finance.

Francofest Home