Loopy Belief Propagation Algorithm and Applications

Evergrow SP3-4 Workshop
Call for participation in the Evergrow SP3-4 Workshop - Loopy Belief Propagation Algorithm and Applications.
 
 February 19-21, 2006, HUJI, Jerusalem, Israel
Outline Structure Agenda Organization committee Participants Hotels Venue Facilities Workshop pictures

Outline

One of the main goals of the Evergrow Project is to utilize message passing algorithms from the complex systems domain to be used in practical systems over the Internet. Those algorithms has very appealing properties since all nodes in the network are performing the same simple local computation but in many cases reach an optimal or near optimal global system state. The algorithms invovle only local interaction between nodes in the network and work even using asynchrounous settings. Specifically we are interested in the loopy belief propagation algorithm and its applciations. Currently in our project several groups are using those algorithms for solving numerous communication related problems like: data indexing in P2P networks, local churn estimation, data dissemination, skewed keys partitioning, clustering in sensor networks and others.

To this end, we would like to group together researchers from the various workgroups of the Evergrow project, that are interested and using those algorithms for solving many different problems. We will hold a workshop of several days, with targeted audiance of either physics (especially statistical mechanichs) background or P2P researchers that apply LBP for various problems.

The meeting is a part of the

   Evergrow EU project

Structure

We will allocate slots for people to describe their work in depth (since we assume the target audiance is well aqionted with the LBP algorithm) and allow enough time for discussions and working in small group tackling some problems.

Perliminary list of discussed topics:

  • Gaussian Belief Propagation and its application for social netowrks (Danny)
  • LBP used for clustering in sensor networks (Bracha)
  • Optimizing the number of messages sent in LBP using P2P networks (Roman)
  • Creating small world networks dynamically in skered key distributions (Sarunas)
  • LBP used for local estimation of churn in P2P networks (Boriss)

    Agenda

    Monday 19.2.06 - Ross Buidling, Room 201 (2nd floor)

    Morning - P2P session

    Roman Schmidt - EPFL 10:00 - 11:00

    Efficient implementation of BP in P2P networks for reducing communication cost (specifically number of messages). ppt

    Sarunas Girdzijauskas - EPFL 11:00 - 12:00

    Distributed estimation of skewed distributions in P2P networks and construction of efficient routing. ppt

    Boriss Mejias - UCL 12:00 - 12:30

    Local churn estimation using BP for P2P networks. pdf

    Lunch Break 12:30 - 13:30

    Afternnoon - Physics session

    John Ardelius - SICS 13:30 - 14:30

    'Solution space structure and behaviour of local search methods on combinatorial optimization problems.' Focus will be on SAT problems and I will give a brief introduction to the area as well as presentation of our method, ASAT and its properties. Our interest in BP seems to be towards maintaining structured overlays in distributed and dynamic (ad hoc) systems and also in information aggregation in sensor networks. I would also very much like to here your opinion about the relation between BP and other gossiping protocols (epidemics). ppt

    Lenka Zdeborova - Orsay - 14:30 - 15:30

    Survey propagation

    Coffe Break 15:30 - 16:00

    Marco Tarzia - Orsay 16:00 - 17:00

    Lattice glass models and the cavity merhod

    Scott Kirkpatrick - HUJI - 17:00 - 17:30

    The sudoku puzzle as an cool example where message passing algoirthms can help us.

    Tuesday 20.2.07 - Ross Building, Room 63 (first floor)

    Morning - Sensor networks, social networks, IR and Gaussian BP

    Bracha Hod - HUJI 10:00 - 11:00

    Clustering in sensor networks using the BP algorithm

    Danny Bickson - HUJI 11:00 - 12:30

    Tutorial for Gaussian Belief Propagation: theory and applicaitons.

    Christos Tryfonopoulos - UOA 14:00 - 14:30

    TBA Afternoon - Finding common areas for research

    Wednesday 21.2.07 - Ross Building, Room 63 (first floor)

    Morning - small working groups, finding common areas for research

    Afternoon - excrusion to the old city

    Organization Committe

    Local organization:

    Participants

    You can register to EverGrow Everywhere Workshop by sending an email to the local organization committee. Confirmed list of participants (ordered by country):
    Boris Mejias, (UCL, Belgium)
    Marco Tarzia and Lenka Zdeborova (Orsay, France)
    Christos Tryfonopoulos (Greece/Germany)
    Shai Carmi,(Bar Ilan University, Israel)
    Danny Bickson, Uri Gordon, Bracha Hod, Scott Kirkpatrick (HUJI, Israel)
    John Ardelius (SICS, Sweden)
    Sarunas Girdzijauskas and Roman Schmidt (EPFL, Switzerland)

    Hotels

    We have reserved a block of rooms in the University Guest House (Belgium House)

    HUJI University - Givaat Ram Campus Map

    Venue


    Arriving to Israel

    Israel has only one internation airport - the Ben Guyrion international airport. On the flight you will be asked to fill a form stating the reason for your visit. There is a passport inspection line after landing that sometimes takes up to half an hour. It is advised to have with you a printout of the conference website. Please write down that I am (Danny Bickson) your host in Israel, my cell phone is +972-545-487421, University phone: 02-6585706.
    The currency in israel is the New Israeli Shekel (NIS) where 4.2 NIS = 1 $.

    Getting to the hotel from the airport

    Driving Directions:
    Ben Gurion International Airport Take the main highway (Route 1) east to Jersusalem's main city entrance (about 45 km). Turn right onto Herzl Boulevard and at third traffic light turn left to hotel Jerusalem Park Plaza.
    By Taxi:
    A special taxi from the airport to the hotel should take about 45-50 mintues and cost around 230 NIS (about 50$). There is a line of taxis waiting at the airport at any hour.
    There are service taxis ("Nesher" taxis) which goes hourly and the ride is about 45 NIS per person (about 10$) but they are MUCH slower.
    You can ask the taxi to enter into the hebrew university in Givaat Ram, Jerusalem, and take you directly to the "Beit Belgia" which is located INSIDE the campus.

    Getting to the meeting room

    The meetings will be held on Ross Building, the adjacent building to beit belgia. (See the map: HUJI University - Givaat Ram Campus Map)

    Internet Access

    There is a public wireless network in the Beit Belgia hotel for Internet access (in the main lobby and in some of the rooms). There is a public wireless network in Ross building.

    Power supply

    We use 220V power. Power outlet

    Workshop pictures

    Pics by Danny Bickson here

    Website deisgn by Manfred Hauswirth