Sm@rt

Speaker: Luca Trevisan

Title: Pseudorandomness and Combinatorial Constructions

Date: Monday, December 17, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, Aula Seminari

In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science, probabilistic algorithms are sometimes simpler and more efficient than the best known deterministic algorithms for the same problem.

Despite this evidence for the power of random choices, the computational theory of pseudorandomness shows that, under certain complexity-theoretic assumptions, every probabilistic algorithm has an efficient deterministic simulation and a large class of applications of the probabilistic method can be converted into explicit constructions.

In this survey talk we describe connections between the conditional "derandomization" results of the computational theory of pseudorandomness and unconditional explicit constructions of certain combinatorial objects such as error-correcting codes and "randomness extractors."

Biographical Sketch

Luca Trevisan is an associate professor of computer science at U.C. Berkeley. He received his Laurea (BSc) degree in 1993 and his Dottorato (Ph.D.) in 1997, both from the University of Rome La Sapienza. Before joining U.C. Berkeley in 2000, he was a post-doc at MIT and at DIMACS, and an assistant professor at Columbia University.

Luca's research is in theoretical computer science, and most of his work has been in two areas: (i) the relation between pseudorandomness, derandomization, average-case complexity, coding theory, and the explicit construction of expander-like graphs; and (ii) the theory of probabilistically checkable proofs and its relation to the approximability of combinatorial optimization problems.

Luca received the STOC'97 student paper award (now known as the Danny Lewin award), the 2000 Oberwolfach Prize, the 2000 Sloan Fellowship, the NSF Career Award and the Okawa Foundation Research Fellowship.

Sm@rt

Sub-series: Milestones of Scientific Discovery

Speaker: Lorenzo Carlucci

Title: Unprovability after Gödel

Date: Monday, November 12, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, Aula Seminari

Since Gödel's famous discovery of the existence of an undecidable sentence in (first-order) Paeano Arithmetic in 1931, the relevance of the incompleteness phenomena for so-called "mainstream" mathematics has been intensively debated. The question roughly was: since Gödel's undecidable propositions are mathematically meaningless, does the incompleteness phenomenon matter for "normal mathematics" at all?

A breakthrough occured in the late Seventies, with the discovery by Paris and Harrington that a seemingly innocent variant of the finite Ramsey Theorem is unprovable in Peano Arithmetic (while the finite Ramsey Theorem is provable in a much weaker system).

From then on, a large number of other (more or less) "natural" combinatorial statements have been found to be unprovable in stronger and stronger systems of arithmetic, analysis and even set-theory.
Among the high points of this research is Harvery Friedman's proof that Robertson and Seymour's "Graph Minor Theorem" is unprovable from a strong (impredicative) system.

In other terms, many combinatorial theorems have been proved to be provable only under the assumption of some unexpectedly strong axiom of infinity.

We will give an overview of past and present research in the study of (arithmetic) unprovability. Research in this area features an interplay between proof theory, recursion theory, model theory, combinatorics, number theory etc. The basic concepts and proof techniques will be illustrated, as well as the current directions of research.

Biographical Sketch

Lorenzo Carlucci is currently affiliated with the Computer Science Department of the University of Rome "La Sapienza", as a Research Associate. He is also a Research Fellow of the "Scuola Normale Superiore di Pisa".
He got his Ph.D. in Theoretical Computer Science at the "Computer and Information Sciences Department" of the University of Delaware, USA. He got his Ph.D. in Mathematics (spec. Mathematical Logic and Theoretical Computer Science) at the Mathematics Department of the University of Siena.
His research interests include Mathematical independence results, proof theory, ordinal analysis and Recursion-theoretic learning theory.

Sm@rt

Speaker: Gábor Simonyi

Title: Perfect graphs: a tutorial

Date: Monday, October 15, 2007; Time: 3:00pm

Duration: about 90 min.

Venue: DI, Via Salaria 113, Aula Seminari

Perfect graphs were introduced by Berge in the early sixties along with two beautiful conjectures. The first was solved in 1972 by Lovász, its statement is known as the Perfect Graph Theorem. The second, which became known as the Strong Perfect Graph Conjecture was proven recently by Chudnovsky, Robertson, Seymour, and Thomas (Ann. Math. 164 (2006), 51-229).

The talk is a brief introduction to perfect graphs, and it consists of two parts of 45 minutes each. In the first part, I will try to convince the audience about the beauty and importance of this graph class by a selection of results. In the second half, after a short break, I plan to present, for those interested, Gasparian's elegant proof of Lovász's Perfect Graph Theorem.

Biographical Sketch

Gábor Simonyi is now a Visitor in our Department.
He is a member at the Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, since 1989, and Professor at the Department of Information Theory and Computer Science, Budapest University of Technology and Economics, since 1995. He obtained his Ph.D. in Mathematics from the Hungarian Academy of Sciences in 1991. He won several prizes, among them the Alfréd Rényi Prize of the Mathematical Institute of HAS and the Academy Prize for Junior Researchers of the Hungarian Academy of Sciences in 1995.
His research interests include graph theory, information theory, extremal combinatorics, and in particular, the behaviour of information theoretic functionals on graphs.

Sm@rt CANCELLED

Speaker: Rance DeLong

Title: A Common Criteria Authoring Environment Supporting Composition of High-Assurance Secure Systems*

Date: Monday, September 24, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, Aula Seminari

The talk will describe the Common Criteria Authoring Environment (CCAE), an automated support system for the authors of protection profiles (PPs) and security targets (STs), and a key part of a comprehensive approach to the compositional evaluation of systems composed from separately developed and evaluated high-assurance components.

Neither a protection profile template nor a "pushbutton" protection profile, the CCAE is a tool for experienced security analysts, evaluators and developers, analogous to a class library and a type checker for the construction of PPs and STs. It is a knowledge-based system that assists in building a semantically rich representation of a PP or ST that can be queried by reviewers and evaluators, and be measured against standards and the recommendations of experts. It is expected to be of particular utility in developing a coherent collection of high-quality PPs and STs for compositional system architectures, where coordination is critical to success.

The CCAE will alleviate much of the tedium of producing well-formed PPs and STs that are faithful to the CC and that can easily be maintained to track future CC revisions. Because the CCAE processes the semantic content as well as the form of a Common Criteria-based document, it is able to give substantive guidance while giving autonomy to the author. It will provide PP and ST authors, reviewers, evaluators, and developers with a collaborative vehicle for the coordination and enforcement of system architecture, trust relationships, interface contracts, standards and other constraints. Long term we vision a graphical Web services-based collaborative environment serving the security community.

By developing and refining the CCAE in a constrained domain while confronting the challenges of composition, we are confident that it could serve as an example for other communities and for future applications of the Common Criteria.

* This work is funded by the Air Force Research Lab and is being performed in collaboration with John Rushby at SRI International.

Biographical Sketch

Mr. Rance DeLong is a staff scientist at LynuxWorks, consultant to SRI International, and a member of the Center for Advanced Study and Practice of Information Assurance at Santa Clara University. Mr. DeLong has twenty-nine years of research, engineering and management experience with security-related technologies, software engineering, and product development. Twenty of those years have been devoted to security and methodologies for high-assurance. He has had key roles in five advanced secure system development efforts. His recent activities include a high-assurance separation kernel and research related to its application. Mr. DeLong has a BS in Physics/Math and a BA in Philosophy from Moravian College, and has done extensive postgraduate course work at Lehigh and Stanford Universities.

Sm@rt

Changing life in 20 minutes

Date: Thursday, July 26, 2007; Time: 3:00pm-5:00pm

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

Sometimes your life can change drastically in 20 minutes. The new EU body to sustain basic research for instance, the European Research Council, awards 1-million-euro grants based on 20 minute presentations. To master the art, we begin with our 2nd year students who will give 20 minute lectures presenting their work.

Duration: 20 min. each

Speaker: Alessio Carosi

Title: Can mobility improve WSNs performance?

The traditional view of the Wireless Sensor Networks paradigm, has been always based on static and low cost devices, that communicate wirelessly to collaborate for a common complex task. New paradigms can lead to different network architectures and designs, outperforming the traditional configurations in the metrics of interest. In this talk we discuss about a new paradigm of WSN based on the mobility of the sink. A new centralized Mixed Integer Linear Programming (MILP) model of the network is also introduced, and compared to a new decentralized heuristic (GMRE) and other simple distributed schemes. Finally we present our research directions and on-going work in this field.

Speaker: Mauro Conti

Title: Secure Ubiquitous Computing

Recent advances in Micro Electro Mechanical Systems (MEMS) are enabling the diffusion of ubuquitous computing: Wireless Sensor Networks (WSN) and Radio Fequency IDentification (RFID) systems are two examples of enabling technologies. However, the unattended nature of these systems rises some security issues that can delay the diffusion of this paradigma. Further, ubiquitous computing devices should be smaller and cheaper as possible. This implies several constraints: i.e. limited memory, limited energy, limited computation and no tamper proof devices. These constraints should be carefully taken into consideration in order to face with different security threats these systems are subject to. In this talk we will briefly overview the state of the art and our recent proposals for some security problems in WSN and RFID systems.

Speaker: Massimo Lauria

Title: Complexity of proofs in Polynomial Calculus

Automatic theorem proving is a remarkable computational task both in theoretical and applied computer science. Propositional proof complexity studies how difficult it is to prove theorems of propositional logic, using more and more powerful proof schemes.
We study Polynomial Calculus (PC), a proof scheme which relies on algebraic manipulation of polynomials and for which ideal membership algorithms work as automatic provers. This is a non trivial generalization of well-studied and widely-adopted Resolution system.
A short introduction of the area will be given in the talk. Then we will present a new result about the trade-off between two relevant complexity measures on PC proof.

Speaker: Emanuele Guido Fusco

Title: Algorithmic solutions for problems on wireless networks

Wireless networks are nowadays widely spread, due to technical advances that have made devices capable of wireless communication small and cheap. Many problems have to be considered and solved in order to make such networks useful and effective. This is why wireless networks are extremely interesting and challenging from an algorithmic point of view.
In this talk the concept of bounded treewidth will be briefly introduced, explaining how it is related with the channel assignment problem. This connection has driven our attention to graphs of bounded treewidth, leading us to search for a bijective code for k-trees.
A method to perform the simulation of the unfolding of physical phenomena using a collection of wireless devices will be presented in the second part of this talk. Some details of one problem related to this goal will be given, together with a brief description of our contribution.

Sm@rt

Speaker: Gul Agha, Director of the Open Systems Laboratory at the University of Illinois at Urbana-Champaign and Professor in the Department of Computer Science

Title: Programming the Future

Date: Monday, June 25, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

Three trends in computing are changing the nature of computing. Web services and P2P systems are increasing the free flow of information and services, thus creating a global village. Sensor networks promise to change mechanical devices into intelligent, networked machines--increasing our safety and efficacy by providing assisted living for the elderly, smart civil structures, and pervasive computing. Multicore architectures promise to make personal computers orders of magnitude faster than current ones. These trends require a paradigm shift in our programming models and languages: we must be able to support scalable parallel and distributed computing for a broad range of applications. I will discuss some key concepts that will help address the challenge of programming such systems: these include actors, adaptive distributed control, and probabilistic models of computation. I will illustrate the ideas based on our research.

BIOGRAPHY

Dr. Gul Agha is Professor of Computer Science at the University of Illinois at Urbana-Champaign. His seminal work on Actors is among the most widely cited. Dr. Agha is a Fellow of the IEEE, and a former ACM International Lecturer. Dr. Agha served as the Editor-in-Chief of the ACM Computing Surveys (1999-2007) and of IEEE Concurrency: Parallel, Distributed and Mobile Computing (1994-1998). He has published over 150 research articles, received over $7.5 million in individual research funding, and given over two dozen keynote and plenary lectures. Dr. Agha's area of research is models, languages, and applications of concurrent computation. Current research in his group focuses on formal methods, sensor networks, web computing, agents and P2P systems.

Sm@rt

Speaker: Francesco Lo Presti, Associate Professor, Department of Computer Sciences of the University "Roma 2", Rome

Title: Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures

Date: Monday, June 4, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

Network protocols in layered architectures have historically been obtained on an ad hoc basis. They may instead be analyzed and systematically designed as distributed solutions to some global optimization problems. This talk presents a survey of the recent efforts towards a systematic understanding of "layering" as "optimization decomposition", where the overall communication network is modeled by a generalized Network Utility Maximization (NUM) problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. There can be many alternative decompositions, each leading to a different layering architecture. This talk surveys the current status of decomposition techniques and its impact on congestion control, routing, scheduling, random access.

Sm@rt

Speaker: Lorenzo Alvisi, Associate Professor and Faculty Fellow (Alfred P. Sloan Research Fellow), Department of Computer Sciences, UT Austin

Title: BAR Gossip

Date: Monday, May 21, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

The promise of robustness and scalability in peer-to-peer systems can quickly evaporate without mechanisms to encourage faithful participation of the peers to the protocol and techniques to handle arbitrary behavior among peers. This talk will present FlightPath, the first peer-to-peer streaming application that guarantees predictable throughput and low-latency in the Byzantine-Altruistic-Rational (BAR) model, in which peers not following the protocol can behave in a self-serving (rational) or arbitrary (Byzantine) way.

At the core of our solution is a BARtolerant version of gossip, a well-known technique for scalable and reliable data dissemination. BAR Gossip relies on verifiable pseudo-random partner selection to eliminate non-determinism that can be used to game the system while maintaining the robustness and rapid convergence of traditional gossip. A novel fair enough exchange primitive entices cooperation among selfish nodes on short timescales, avoiding the need for long-term node reputations. Our initial experience provides evidence for BAR Gossip's robustness. Our BAR-tolerant streaming application provides over 99% convergence for broadcast updates when all clients are selfish but not colluding, and over 95% convergence when up to 40% of clients collude while the rest follow the protocol. BAR Gossip also performs well when the client population consists of both selfish and Byzantine nodes, achieving over 93% convergence even when 20% of the nodes are Byzantine.

Sm@rt

Speaker: Stefan Dziembowski, Department of Computer Science, University of Rome "La Sapienza"

Title: Private Information Retrieval

Date: Monday, May 14, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

One of the most attractive things about cryptography is that it allows to create tools that are seemingly impossible. Historically, first such an example was the public-key cryptography (discovered in 1970s), which was later followed by a number of other ideas (zero-knowledge, coin-tossing by telephone, multi-party computations, just to name some). In this talk I will give a short introduction to yet another primitive of this kind, namely the Private Information Retrieval (PIR).

PIR is a protocol between 2-parties: a client and a database. A PIR scheme enables the client to learn some entry from the database in such a way that the database does not get any information about the choice of the client. Moreover the total number of communicated bits is much smaller than the size of the database (in this way we exclude the trivial solutions where the database simply sends her entire contents to the client).

We will also discuss some possible directions for the future work in this field.

No prior knowledge of cryptography will be assumed.

Sm@rt

Speaker: Gene Tsudik, University of California, Irvine

Topics in Electronic Privacy

Date: Monday, April 23, 2007; Time: 3:00pm

Duration: about 120 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

The increasingly electronic world has contributed greatly to the erosion of privacy. Many routine electronic activities -- ranging from web browsing to using a cell phone -- are fraught with potential (and real) privacy leaks. This short course will cover several topics related to electronic privacy. At the start, we will look into data privacy and consider privacy for outsourced or remote databases, focusing on so-called Private Information Retrieval (PIR) and Outsourced Database (ODB) models. We will then consider privacy in the context of network services, such as naming and security services (such as authentication and digital signatures). The remainder of the course will cover privacy in Mobile Ad Hoc Networks (MANETs) and RFID tags.

Topics:
1) Privacy for Outsourced Data
2) Private Information Retrieval
3) Privacy-Preserving Authentication
4) Towards Privacy-Preserving Internet Services
5) Privacy in RFID systems
6) Privacy in MANETs

Schedule:

Time 15.00- 17.00
23 April - Aula Alfa - SM@RT seminar
3 May - Aula Seminari
4 May - Aula Seminari
8 May - Aula Seminari
11 May - Aula Seminari

Sm@rt

Sub-series: Bridge Seminar

Speaker: Andrei Broder, Fellow & VP Emerging Search Yahoo! Research

Title: The Next Generation Web Search and the Demise of the Classic IR model

Date: Monday, April 2, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

The classic IR model assumes a human engaged in activity that generates an information need. This need is verbalized and then expressed as a query to search engine over a defined corpus. In the past decade, Web search engines have evolved from a first generation based on classic IR algorithms scaled to web size and thus supporting only informational queries, to a second generation supporting navigational queries using web specific information (primarily link analysis), to a third generation enabling transactional and other "semantic" queries based on a variety of technologies aimed to directly satisfy the unexpressed "user intent", thus moving further and further away from the classic model. What is coming next? In this talk, we identify two trends, both representing short-circuits of the model: The first is the trend towards context driven Information Supply (IS), that is, the goal of Web IR will widen to include the supply of relevant information from multiple sources without requiring the user to make an explicit query. The information supply concept greatly precedes information retrieval; what is new in the web framework, is the ability to supply relevant information specific to a given activity and a given user, while the activity is being performed. Thus the entire verbalization and query-formation phase are eliminated. The second trend is social search driven by the fact that the Web has evolved to being simultaneously a huge repository of knowledge and a vast social environment. As such, it is often more effective to ask the members of a given web milieu rather than construct elaborate queries. This short-circuits only the query formulation, but allows information finding activities such as opinion elicitation and discovery of social norms, that are not expressible at all as queries against a fixed corpus.

Biography

Andrei Broder is a Yahoo! Research Fellow and Vice President of Emerging Search Technology. Previously he was an IBM Distinguished Engineer and the CTO of the Institute for Search and Text Analysis in IBM Research. From 1999 until early 2002 he was Vice President for Research and Chief Scientist at the AltaVista Company. He was graduated Summa cum Laude from Technion and did his Ph.D. in Computer Science at Stanford University under Don Knuth. Broder is co-winner of the Best Paper award at WWW6 (for his work on duplicate elimination of web pages) and at WWW9 (for his work on mapping the web). He has published more than seventy papers and was awarded twenty patents. He is an IEEE fellow and served as chair of the IEEE Technical Committee on Mathematical Foundations of Computing.

Sm@rt

Speaker: Giuseppe Persiano, DIA, Uni Salerno

Title: A gentle introduction to Zero Knowledge and its application to the design of secure protocols

Date: Monday, March 26, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

In this talk we will introduce the concept of a Zero Knowledge proof as a proof that yields only its validity. Our presentation will be example-driven and the protocol presented is of direct application in concrete scenarios. We will also hint at the wide applicability of the concept in the field of network security and in the design of secure protocols. No background necessary.

---

Download presentation PDF (667 KB)

Sm@rt

Speaker: Anupam Gupta, CMU, Computer Science Dept

Title: Metric Methods: Algorithms and Applications

Date: Monday, March 19, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

We all deal with metric spaces every day, whether it may be in navigating to work each day, or in finding good Traveling Salesperson tours, or in defining similarity measures to cluster and search on our data. In response to these and many other algorithmic applications, a large set of tools and techniques have been developed to deal with finite metric spaces.

I will talk about some of these ideas, and how they may be relevant to research in many areas of CS. Among other topics, I will talk about (a) why every metric space is close to being a tree, (b) why every metric space is close to being Euclidean, and (c) how to exorcise the curse of dimensionality to some extent. Given time, I will talk about (d) how to define and calculate the dimension of your favorite network, and why that may be a useful thing to do.

Title: XIX Cycle - Final Exam

Date: Monday, February 19, 2007; Time: 10:30am

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

Come cheer your favourite PhD candidate for the 2007 Doctorate Degree Final Exam. Talks start at 10:30 and each candidate will have approximately 45 minutes. Candidates will be evaluated in alphabetical order during two sessions, morning and afternoon, starting at 10:30 and 14:30 respectively.

Commitee members: Giuseppe F. Italiano, Giuseppe Persiano, and Piero Torasso

PhD candidates: Maria Calagna, Fabio De Rosa, Alessio Malizia, Roberto Navigli, Mauro Sozio, Giorgio Zanin.

Sm@rt

Speaker: Paolo Boldi, Computer Science Department (DSI) of the University of Milano

Title: Web: History, Architecture, Problems and Research Directions

Date: Monday, February 12, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, ground floor, Alpha Lecture Room

This talk will present the World-Wide Web as a research field, giving a broad overview of what it is and of the kind of questions people are trying to ask (and possibly answer) about its structure, function and future.

Sm@rt

Speaker: Alessandro Panconesi, Computer Science Department (DI), Sapienza University of Rome

Title: Unassailable Sensor Networks

Date: Monday, February 05, 2007; Time: 3:00pm

Duration: about 60 min.

Venue: DI, Via Salaria 113, 1st floor, Alpha Lecture Room

Random pre-distribution of keys is a very elegant key-management scheme originally introduced for sensor networks, but with potential applications to other scenarios e.g. peer-to-peer networks. In this talk we will show that the scheme enjoys extremely strong security and connectivity properties simultaneosly.

This research is a good example of the kind of good synergies that are possible within the department.

Joint work with: Roberto Di Pietro, Luigi Mancini, Alessandro Mei, and Jaikumar Radhakrishnan.