-
Prof. Erik Aurell (KTH), Mikko Alava (HUT, Espoo, Finland)15/05/2008, 09:00
-
Dr Supriya Krishnamurthy (SICS)15/05/2008, 09:20Overlay networks are application-level networks, or networks of acquaintances, established on top of physical networks, such as the Internet. Peer-to-Peer (P2P) systems are one class of overlay networks, in which all nodes in the system are equivalent and all tasks are carried out without the presence of any central authority. Despite their relatively short history, peer-to-peer overlays...Go to contribution page
-
Prof. Riccardo Zecchina (Politecnico di Torino)15/05/2008, 10:00Given an undirected graph with positive weights on the edges, the Minimum Weight Steiner Tree (MST) problem consists in finding a connected subgraph of minimum weight that contains a selected set of ``terminal'' vertices. Such construction may require the inclusion of some non-terminal nodes which are called Steiner nodes. Clearly, an optimal sub-graph must be a tree. Solving MST is a...Go to contribution page
-
Dr Luca Dall'Asta (Abdus Salam ICTP)15/05/2008, 11:00Many efforts have been devoted to characterize the onset of congestion in communication networks. Numerical simulations performed using complex routing protocols have revealed that congestion always occurs as an effect of traffic increase, but with specific features that strictly depend on the local routing scheme. (For instance, the continuous or discontinuous character of the...Go to contribution page
-
Jakob Nordström (KTH)15/05/2008, 11:20Most state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The main bottleneck for such algorithms, other than the obvious one of time, is the amount of memory used. In the field of proof complexity, the resources of time and memory correspond to the length and space of resolution proofs. There has been a long line of...Go to contribution page
-
Jeremy Stribling (MIT CSAIL)15/05/2008, 13:00It is a challenge to build applications that need to share data and are distributed across hundreds or thousands of computers in a wide-area network (e.g., PlanetLab or on a Grid). In order to cope with high latency, throughput bottlenecks, and temporary failures, such applications typically implement their own storage plan or use special-purpose storage solutions (e.g., DISC,...Go to contribution page
-
Danny Bickson (The Hebrew University of Jerusalem)15/05/2008, 14:00The canonical linear-algebraic problem of solving a system of linear equations arises in numerous contexts in the mathematical sciences and engineering. In this talk, we introduce an efficient Gaussian belief propagation (GaBP) solver that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution...Go to contribution page
-
Dr Dimos Dimarogonas (KTH)15/05/2008, 14:20Multi-agent consensus problems where agents aim to attain a common value of some quantity under limited communication have received increasing attention recently, due to their application in multi-vehicle and multi-robot systems, as well as distributed estimation and filtering in networked systems. In this talk we present two recent results on consensus problems. The first part of the...Go to contribution page
-
Dr Meesoon Ha (KAIST)15/05/2008, 15:00A finite-size-scaling (FSS) theory is proposed for various models in complex networks. In particular, we focus on the FSS exponent, which plays a crucial role in analyzing numerical data for finite-size systems. Based on the droplet-excitation (hyperscaling) argument, we conjecture the values of the FSS exponents for the Ising model, the susceptible-infected-susceptible model, and the...Go to contribution page
-
Prof. Olav Tirkkonen (TKK)15/05/2008, 15:20
-
Mikko Alava (HUT, Espoo, Finland)15/05/2008, 16:00
-
Dr György Dan (KTH)15/05/2008, 16:20A large number of peer-to-peer streaming systems has been proposed and deployed in recent years. Yet, there is no clear understanding of how these systems scale and how multi-path and multihop transmission, properties of all recent systems, affect the quality experienced by the peers. In this talk we present an analytical study that considers the relationship between delay and loss for...Go to contribution page
-
Prof. Bernhard Mehlig (Chalmers University of Technology)15/05/2008, 16:40
-
Prof. Massimo Vergassola (Institut Pasteur)16/05/2008, 09:00
-
Prof. Elena Dubrova (KTH)16/05/2008, 10:00Random Boolean Networks (RBNs) were introduced by Kaufmann in 1969 in the context of gene expression and fitness landscapes. They were applied to the problems of cell differentiation, immune response, evolution, and neural networks. They have also attracted the interest of physicists due to their analogy with the disordered systems studied in statistical mechanics, such as the mean...Go to contribution page
-
Prof. Joachim Krug (University of Cologne)16/05/2008, 10:20The evolutionary search of a finite population in a rugged fitness or energy landscape with many local optima is a paradigmatic problem that connects evolutionary biology to the statistical physics of disordered systems and computer science. In this brief presentation I summarize the results of two recent studies which addressed different aspects of this problem. A detailed numerical...Go to contribution page
-
Prof. Haijun Zhou (Chinese Academy of Sciences)16/05/2008, 11:00The mutual influence of structure and dynamical processes in a complex networked system is an active yet challenging research topic. In the present report we approach this problem by studying a simple model system, namely the local majority-rule (LMR) dynamics on an evolving network. We first show analytically and by computer simulation that the structure of the network can have a...Go to contribution page
-
Prof. Scott Kirkpatrick (School of Engineering and CS, HUJI)16/05/2008, 13:00Statistical mechanics turned a corner with Mezard and Zecchina's realization that its methods could be applied to solve individual combinatorial problems as well as to characterize the expected outcome of classes of problems. But the methods, such as message passing or simulated annealing, that stay closest to the physical analogies can be extremely time-consuming and may not scale to...Go to contribution page
-
Dr Luis Lafuente (MIT CBA)16/05/2008, 14:00Linear Programming can solve some unlikely problems, like decoding parity check codes, sorting, and other things. A lovely old theorem by Birkhoff and von Neumann distinguishes the cases in which the solution is guaranteed to lie on the integers 0 and 1. Unfortunately, this result fails to apply to NP-Complete problems -- it guarantees to solve the 8 rooks problem, but not the 8...Go to contribution page
-
Prof. Mads Dam (KTH)16/05/2008, 14:20Distributed aggregation is the problem of computing, in a decentralized and scalable way, global functions of local values residing at nodes in a network. Interesting aggregation functions include average, counting, sum, min/max, voting, medians and quantiles, and thresholds. In network management applications, our primary domain of interest, such aggregates can be useful indicators of...Go to contribution page
-
Prof. Ilkka Niemelä (TKK)16/05/2008, 15:00Tools for solving the propositional satisfiability (SAT) problem have advanced dramatically during the last ten years and are now standardly used in industrial applications such as hardware design verification and automatic test pattern generation. SAT solvers are also becoming widely used search engines in areas with challenging computation problems such as automated planning,...Go to contribution page
-
Prof. John Hertz (NORDITA)16/05/2008, 16:00We can learn something about how large neuronal networks function from models of the spike pattern distributions constructed from data. In our work, we do this for data generated from simulated models of local cortical networks, using the approach introduced by Schneidman et al, modeling this distribution by an Ising model: P[S] = Z^{-1}exp(½Σ_{ij}J_{ij}S_iS_j+Σ_i h_i S_i). To estimate...Go to contribution page
-
Prof. Heiko Rieger (Universität des Saarlandes)16/05/2008, 16:20Targeted transport of vesicles, organelles and other types of cargo is necessary for living cells to maintain their complex internal structure. Molecular motors attached to this cargo power the long-range traffic of cargo along microtubules in a bidirectional way. The attachment of two kinds of motors, one pulling towards the cell periphery and one towards the cell center, lead to a...Go to contribution page
-
Prof. Neil Gershenfeld (MIT CBA)16/05/2008, 17:00Computer Science has served to isolate programs (and programmers) from knowledge of the underlying physical mechanisms used for computation. However, in the limit in which the number of computational and physical degrees of freedom become equivalent it's no longer possible to maintain this fiction. I will explore the benefits of exposing rather than hiding the boundary between bits...Go to contribution page
-
Prof. Johan Håstad (KTH)17/05/2008, 09:00
-
Dr Petteri Kaski (HIIT)17/05/2008, 10:00The deletion--contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin--Kasteleyn in statistical physics. Prior to this...Go to contribution page
-
Prof. Pekka Orponen (TKK)17/05/2008, 10:20We present a combinatorial method for the uniform sampling of local energy minima in square and hexagonal 2D Ising spin glass lattices. The method has been used to estimate the number and energy distribution of local minima in lattices of up to 2000 spins.Go to contribution page
-
Dr Ashish Sabharwal (Cornell)17/05/2008, 11:00We consider the problem of estimating the model count (number of solutions) of Boolean formulas, and present two techniques that compute estimates of these counts, as well as either lower or upper bounds with different trade-offs between efficiency, bound quality, and correctness guarantee. For lower bounds, we use a recent framework for probabilistic correctness guarantees, and exploit...Go to contribution page
-
Prof. Alexander Hartmann (University of Oldenburg)17/05/2008, 13:00
-
Lenka Zdeborova (U Paris-Sud)17/05/2008, 14:00We introduce the random `locked' constraint satisfaction problems. When increasing the density of constraints, they display a broad `clustered' phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely challenging from the algorithmic point of view: the best known...Go to contribution page
-
Prof. Florent Krzakala (ESPCI, Paris)17/05/2008, 14:20In this talk, we will discuss (some) of the consequences of the phase transitions that arise in random constraint satisfaction problems, and present a simple strategy that allows to understand why it is so easy to find solutions in the clustered phase.Go to contribution page
-
Prof. Matteo Marsili (Abdus Salam ICTP)17/05/2008, 15:00
-
Dr Petter Holme (Coputational Biology)17/05/2008, 16:00In spite of advances in hospital treatment, hospitals continue to be a breeding ground for several airborne diseases and for diseases that are transmitted through close contacts like SARS, methicillin-resistant Staphylococcus aureus (MRSA), norovirus infections and tuberculosis (TB). Here we extract contact networks for up to 295,108 inpatients for durations up to two years from...Go to contribution page
-
Prof. Federico Ricci-Tersenghi (Roma)17/05/2008, 16:20
-
Prof. Matteo Palassini (Barcelona)17/05/2008, 16:40
Choose timezone
Your profile timezone: