Caltech Verification and Validation Workshop

	Connections II:
	Fundamentals of Network Science
	14-18 August 2006 Pasadena, CA

Agenda

Participants

Travel Info

CDS Home

Description

The Connections workshop series pulls together researchers in mathematics, science and engineering who bring together novel ideas and tools from outside their traditional training to influence problems in areas as diverse as networking protocols, systems biology, ecology, geophysics, finance, fluid mechanics, and multiscale physics. An underlying theme of this workshop is to look forward to ways in which future scientists can be educated in mathematical, computational, and quantitative methods, to prepare them to interact broadly from the time they are students and throughout their academic careers.

The first Connections workshop, held at Caltech in July 2004, brought together over 200 researchers in the fields of mathematics, biology, physics, engineering and other disciplines to participate in a 3 day conference exploring the connections between diverse applications and common underlying mathematics, particularly with regard to the role of uncertainty and robustness in complex systems. For the second Connections workshop, we plan to focus on the connections within the mathematics that would form the foundation of a theoretical framework for network science, still motivated by the diverse applications in science and technology that were focus of Connections I.

We are organizing the activities around three main themes (roughly one each day) of Hard Limits, Short Proofs, and Small Models, together with the crosscutting theme of Architecture:

• Hard limits - a major challenge in network science is to understand the fundamental limits on networks due to their components and their interconnection. One challenge is unifying and extending the previously fragmented hard limit theories that arise in thermodynamics, control, communications, and computing, and are often associated with the names Carnot, Bode, Shannon, and Turing. There are encouraging pairwise connections, like the Bode-Shannon theory developed by Martins et al and others, and this theme will explore the progress and potential for further integration. Also encouraging is the opportunity for overcoming hard limits when new connections are made, such as the relationship between proof complexity and problem fragility.

• Short proofs - in general, overcoming the apparent computational intractability of analysis and design of complex networks is a central challenge, from formal verification of programs and protocols to the robustness analysis of the dynamics of biological networks and advanced technologies. Here the apparent asymmetry between NP/coNP is as significant as that between P/NP, and moving from analysis to synthesis involves higher complexity classes in fundamental ways. Substantial progress has been made recently in creating frameworks to systematically search for short proofs, but the research communities involved and the results are again somewhat fragmented. Fortunately there is also encouraging progress in creating a more unified framework, motivated by new connections within mathematics, the pervasive role of duality, and the concept of "complexity implies fragility" from the first theme.

• Small models - an important route to short proofs is finding small models of complex phenomena through model identification from data, and model reduction. Again, there has been substantial recent progress within relatively fragmented research communities, with encouraging results that suggest the potential for a richer and more unified framework.

• Architecture - a cross-cutting theme in the background throughout the workshop will be the challenge of a theory of architecture, as in the claim that "the architecture of the cell and the Internet have enabled their robustness and evolvability." Despite its widespread usage, there is little formalization of the concept and essentially no theory. The existing hard limits theories all assume architectures a priori which are incompatible and incomparable, and thus offer little guidance in the tradeoffs associated with architecture design. Short proofs and small models also arise only in the context of a priori specified proof and modeling architectures. A diverse set of examples of successful and unsuccessful architectures in technology and biology are now available, and motivate the study of a theory. More unified theories of hard limits, short proofs, and small models appear to be essential first steps towards a theory of architecture.

Invited speakers (confirmed)

• Rajeev Alur, Univ of Pennsylvania
• Karl-Erik Arzen, Lund Univ
• Calin Belta, Univ of Boston
• Stephen Boyd, Stanford Univ
• Mani Chandy, Caltech
• Ed Clarke, Carnegie Mellon Univ
• Domitilla Del Vecchio, Univ of Michigan
• Eric Feron, Georgia Inst of Tech
• Gerard Holzmann, JPL
• Eric Klavins, Univ of Washington
• Nancy Leveson, MIT
• Rupak Majumdar, UCLA
• Sayan Mitra, Univ of Illinois
• Andrew Packard, UC Berkeley
• Andrea Platzer, Carnegie Mellos Univ
• Paulo Tabuada, UCLA
• Ashish Tiwari, SRI
• Stavros Tripakis, CNRS
• Brian Williams, MIT

Organizers

• Mani Chandy (Caltech, CS)
• Richard Murray (Caltech, CDS)
• Paulo Tabuada (UCLA, ECE)
• Ufuk Topcu (Caltech, CDS)

The Caltech Verification and Validation Workshop, 2009 is sponsored by Caltech's Center of the Mathematics of Information and the Air Force Office of Scientific Research (through the MURI "Specification, Design and Verification of Distributed Embedded Systems").