Thursday, April 29, 2010

Schedule: 10th Haifa Graph Workshop (23-24 May) and Memorial for Uri N. Peled

10th Haifa Workshop on Interdisciplinary Applications of Graph Theory,
Combinatorics and Algorithms
In memory of Uri Natan Peled, ?"?
Caesarea Rothschild Institute, University of Haifa
May 23-25, 2010, Haifa (Israel)

Location: May 23 morning, 570 Education Building
May 23 afternoon, Safdie Auditorium, Multi-purpose Building
May 24 all day, 570 Education Building
May 25 excursion


Program:

Sunday May 23, 2010
9:00 Registration, Tea and Coffee
9:15 Greetings
9:30 Seffi Naor (Technion, Israel)
"Online Algorithms, Linear Programming, and the k-Server Problem"
10:15 break
10:30--11:45 Sessions 1 and 2

Session 1
10:30--10:55 Mark Korenblit (Holon Institute of Technology, Israel)
"The decomposition method for generating algebraic expressions of square rhomboids"
10:55--11:20 Nathan Keller (Hebrew University, Israel)
"A tight quantitative version of Arrow's impossibility theorem"
11:20--11:45 Yefim Dinitz (Ben-Gurion University, Israel)
"Hybrid Bellman-Ford-Dijkstra algorithm"

Session 2
10:30--10:55 Shiri Chechik (Weizmann Institute, Israel)
"Forbidden-Set distance labels for graphs of bounded doubling dimension"
10:55--11:20 Oren Ben-Zwi (University of Haifa, Israel)
"A hat trick"
11:20--11:45 Rami Puzis (Ben-Gurion University, Israel)
"Expressing centrality in terms of routing betweeness"

11:45 break
12:00--12:50 Sessions 3 and 4

Session 3
12:00--12:25 Noam Goldberg (Technion, Israel)
"Sparse weighted voting classifier selection and its LP relaxation"
12:25--12:50 Eugene Levener (Holon Institute of Technology and
Bar-Ilan University, Israel)
"A fully polynomial algorithm for a cyclic scheduling problem on
graphs with interval data"

Session 4
12:00--12:25 Yuval Emek (Tel-Aviv University, Israel)
"Sparse reliable graph backbones"
12:25--12:50 Michael Borokhovich (Ben-Gurion University, Israel)
"Tight bounds for algebraic gossip on graphs"

12:50 Lunch -- Caesarea Rothschild Institute, 6th floor

Remembering Uri N. Peled

Safdie Auditorium, Multipurpose Building, University of Haifa

14:00--15:30 Mathematical Lectures

14:00 Bill Cunningham (University of Waterloo, Canada)
"Split decomposition"
14:45 Gyorgy Turan (University of Illinois at Chicago and University of Szeged)
"Horn formulas - a survey of recent results"

15:30 Reception

16:00--18:15 Memorial Session and General Lectures
chairs: Martin Golumbic and Dan Peled

- Messages from friends and family; the Mathematics of Uri N. Peled

- General Lectures:

Hon. Zvi Tal (former Justice of the Supreme Court, Israel) (uncle)
"Reflections on Human Dignity" (in Hebrew)

Jonathan (Tsoni) Peled (Albert Einstein College of Medicine, Yeshiva University, USA) (son)
"Studies on Lymphoma Tumors of Mice as a Model for Human Non-Hodgkin's Lymphoma"

Elana Zion-Golumbic (Columbia University Medical Center,
and Nathan Kline Institute for Psychiatric Research, USA) (family friend)
"Selective attention at a cocktail party: Insights from intracranial EEG in humans"

The three general lectures will be for non-specialists,
reflecting the broad interests of Uri Peled, z"l
and his love for family, friends, science and the humanities.


Monday, May 24, 2010

9:00 Registration, Tea and Coffee
9:30 Ronitt Rubinfeld (Tel-Aviv University, Israel and MIT, USA)
"Maintaining a large matching or a small vertex cover"

10:15 break
10:30--11:45 Sessions 5 and 6

Session 5
10:30--10:55 Yahav Nussbaum (Tel-Aviv University, Israel)
"Linear-time recognition of probe interval graphs"
10:55--11:20 George Mertzios (Technion, Israel)
"Recent results on tolerance graphs and related classes"
11:20--11:45 Eliah Ninyo (University of Haifa, Israel)
"Characterization of alternately orientable graphs that are weakly-chordal"
Session 6
10:30--10:55 Tomer Kotek (Technion, Israel)
"A representation theorem for holonomic sequences"
10:55--11:20 Alexander Zadorojniy
"A new pivoting rule for the simplex algorithm"
11:20--11:45 Yona Cherniavsky (Ariel University Center of Samaria, Israel)
"Weighted Coxeter graphs, geometric representation and generalized numbers game"

11:45 break

12:00 Fedor Fomin (University of Bergen, Norway)
"Kernelization"

12:50 Lunch -- Caesarea Rothschild Institute, 6th floor

14:00 Alek Vainstein (University of Haifa, Israel)
"Geometry of planar directed trivalent networks"
14:45 Michael Elkin (Ben-Gurion University, Israel)
"Distributed deterministic graph coloring"

15:30 break

15:45--17:00 Sessions 7 and 8

Session 7
15:45--16:10 Bryce Zimny (University of Toronto, Canada)
"On sum coloring for restricted families of graphs"
16:10--16:35 Panagiotis Cheilaris (Ben-Gurion University, Israel)
"Graph unique-maximum and conflict-free colorings"
16:35--17:00 Moti Medina (Tel-Aviv University, Israel)
"An O(log n)-competitive online centralized randomized packet-routing
algorithms for lines"

Session 8
15:45--16:10 David Tankus (Ariel University Center of Samaria, Israel)
"Well-covered graphs without C4, C6 and C7"
16:10--16:35 Yulia Kempner (Holon Institute of Technology, Israel)
"Poly-dimension of antimatroids"
16:35--17:00 Vadim Levit (Ariel University Center of Samaria, Israel)
"On the independence polynomial of a threshold graph"

17:00 break

17:10--18:30 Sessions 9 and 10

Session 9
17:10--17:35 Irith Ben-Arroyo Hartman (Int'l. Institute for
Information Technology, Bangalore, India)
"Contractors' minimum spanning tree"
17:35--18:00 Eyal Ackerman (University of Haifa at Oranim, Israel)
"On the number of edges in graphs with orthogonal crossings"

Session 10
17:10--17:35 Yelena Yuditsky (Ben-Gurion University, Israel)
"Polychromatic coloring for half-planes"
17:35--18:00 Amir Sapir (Sapir College, Israel)
"Which multi-peg tower of hanoi problems are exponential?"
18:00--18:30 Oren Weimann (Weizmann Institute, Israel)
"Replacement paths via fast matrix multiplication"

19:00 dinner

Tuesday May 25, 2010

9:30-12:00 Informal scientific discussions
12:00- 17:00 Excursion
The Caesarea Rothschild Institute at the University of Haifa
invites you to participate in our workshop:

--------------------------------------------------------------------
10th Haifa Workshop on Interdisciplinary Applications of
Graph Theory, Combinatorics and Algorithms

Dedicated in Memory of Uri N. Peled, z"l

Sunday-Monday, May 23-24, 2010

Registration at: http://www.cri.haifa.ac.il
Program and Schedule below

INVITED SPEAKERS:

Bill Cunningham (University of Waterloo, Canada)
Michael Elkin (Ben-Gurion University, Israel)
Fedor Fomin (University of Bergen, Norway)
Seffi Naor (Technion, Israel)
Ronitt Rubinfeld (Tel-Aviv University, Israel)
Gyorgy Turan (University of Illinois / Chicago, USA)
Alek Vainshtein (University of Haifa, Israel)


PROGRAM AND SCHEDULE


10th Haifa Workshop on Interdisciplinary Applications of Graph Theory,
Combinatorics and Algorithms
In memory of Uri Natan Peled, ?"?
Caesarea Rothschild Institute, University of Haifa
May 23-25, 2010, Haifa (Israel)

Location: May 23 morning, 570 Education Building
May 23 afternoon, Safdie Auditorium, Multi-purpose Building
May 24 all day, 570 Education Building
May 25 excursion


Program:

Sunday May 23, 2010
9:00 Registration, Tea and Coffee
9:15 Greetings
9:30 Seffi Naor (Technion, Israel)
"Online Algorithms, Linear Programming, and the k-Server Problem"
10:15 break
10:30--11:45 Sessions 1 and 2

Session 1
10:30--10:55 Mark Korenblit (Holon Institute of Technology, Israel)
"The decomposition method for generating algebraic expressions of square rhomboids"
10:55--11:20 Nathan Keller (Hebrew University, Israel)
"A tight quantitative version of Arrow's impossibility theorem"
11:20--11:45 Yefim Dinitz (Ben-Gurion University, Israel)
"Hybrid Bellman-Ford-Dijkstra algorithm"

Session 2
10:30--10:55 Shiri Chechik (Weizmann Institute, Israel)
"Forbidden-Set distance labels for graphs of bounded doubling dimension"
10:55--11:20 Oren Ben-Zwi (University of Haifa, Israel)
"A hat trick"
11:20--11:45 Rami Puzis (Ben-Gurion University, Israel)
"Expressing centrality in terms of routing betweeness"

11:45 break
12:00--12:50 Sessions 3 and 4

Session 3
12:00--12:25 Noam Goldberg (Technion, Israel)
"Sparse weighted voting classifier selection and its LP relaxation"
12:25--12:50 Eugene Levener (Holon Institute of Technology and
Bar-Ilan University, Israel)
"A fully polynomial algorithm for a cyclic scheduling problem on
graphs with interval data"

Session 4
12:00--12:25 Yuval Emek (Tel-Aviv University, Israel)
"Sparse reliable graph backbones"
12:25--12:50 Michael Borokhovich (Ben-Gurion University, Israel)
"Tight bounds for algebraic gossip on graphs"

12:50 Lunch -- Caesarea Rothschild Institute, 6th floor

Remembering Uri N. Peled

Safdie Auditorium, Multipurpose Building, University of Haifa

14:00--15:30 Mathematical Lectures

14:00 Bill Cunningham (University of Waterloo, Canada)
"Split decomposition"
14:45 Gyorgy Turan (University of Illinois at Chicago and University of Szeged)
"Horn formulas - a survey of recent results"

15:30 Reception

16:00--18:15 Memorial Session and General Lectures
chairs: Martin Golumbic and Dan Peled

- Messages from friends and family; the Mathematics of Uri N. Peled

- General Lectures:

Hon. Zvi Tal (former Justice of the Supreme Court, Israel) (uncle)
"Reflections on Human Dignity" (in Hebrew)

Jonathan (Tsoni) Peled (Albert Einstein College of Medicine, Yeshiva University, USA) (son)
"Studies on Lymphoma Tumors of Mice as a Model for Human Non-Hodgkin's Lymphoma"

Elana Zion-Golumbic (Columbia University Medical Center,
and Nathan Kline Institute for Psychiatric Research, USA) (family friend)
"Selective attention at a cocktail party: Insights from intracranial EEG in humans"

The three general lectures will be for non-specialists,
reflecting the broad interests of Uri Peled, z"l
and his love for family, friends, science and the humanities.


Monday, May 24, 2010

9:00 Registration, Tea and Coffee
9:30 Ronitt Rubinfeld (Tel-Aviv University, Israel and MIT, USA)
"Maintaining a large matching or a small vertex cover"

10:15 break
10:30--11:45 Sessions 5 and 6

Session 5
10:30--10:55 Yahav Nussbaum (Tel-Aviv University, Israel)
"Linear-time recognition of probe interval graphs"
10:55--11:20 George Mertzios (Technion, Israel)
"Recent results on tolerance graphs and related classes"
11:20--11:45 Eliah Ninyo (University of Haifa, Israel)
"Characterization of alternately orientable graphs that are weakly-chordal"
Session 6
10:30--10:55 Tomer Kotek (Technion, Israel)
"A representation theorem for holonomic sequences"
10:55--11:20 Alexander Zadorojniy
"A new pivoting rule for the simplex algorithm"
11:20--11:45 Yona Cherniavsky (Ariel University Center of Samaria, Israel)
"Weighted Coxeter graphs, geometric representation and generalized numbers game"

11:45 break

12:00 Fedor Fomin (University of Bergen, Norway)
"Kernelization"

12:50 Lunch -- Caesarea Rothschild Institute, 6th floor

14:00 Alek Vainstein (University of Haifa, Israel)
"Geometry of planar directed trivalent networks"
14:45 Michael Elkin (Ben-Gurion University, Israel)
"Distributed deterministic graph coloring"

15:30 break

15:45--17:00 Sessions 7 and 8

Session 7
15:45--16:10 Bryce Zimny (University of Toronto, Canada)
"On sum coloring for restricted families of graphs"
16:10--16:35 Panagiotis Cheilaris (Ben-Gurion University, Israel)
"Graph unique-maximum and conflict-free colorings"
16:35--17:00 Moti Medina (Tel-Aviv University, Israel)
"An O(log n)-competitive online centralized randomized packet-routing
algorithms for lines"

Session 8
15:45--16:10 David Tankus (Ariel University Center of Samaria, Israel)
"Well-covered graphs without C4, C6 and C7"
16:10--16:35 Yulia Kempner (Holon Institute of Technology, Israel)
"Poly-dimension of antimatroids"
16:35--17:00 Vadim Levit (Ariel University Center of Samaria, Israel)
"On the independence polynomial of a threshold graph"

17:00 break

17:10--18:30 Sessions 9 and 10

Session 9
17:10--17:35 Irith Ben-Arroyo Hartman (Int'l. Institute for
Information Technology, Bangalore, India)
"Contractors' minimum spanning tree"
17:35--18:00 Eyal Ackerman (University of Haifa at Oranim, Israel)
"On the number of edges in graphs with orthogonal crossings"

Session 10
17:10--17:35 Yelena Yuditsky (Ben-Gurion University, Israel)
"Polychromatic coloring for half-planes"
17:35--18:00 Amir Sapir (Sapir College, Israel)
"Which multi-peg tower of hanoi problems are exponential?"
18:00--18:30 Oren Weimann (Weizmann Institute, Israel)
"Replacement paths via fast matrix multiplication"

19:00 dinner

Tuesday May 25, 2010

9:30-12:00 Informal scientific discussions
12:00- 17:00 Excursion

----------------------------

REGISTRATION

There is no registration fee -- but please register in advance
in order that we may provide sufficient refreshments.

On-line at: http://www.cri.haifa.ac.il
Follow the links to the workshop registration page
Telephone: 04-828-8337

The Workshop is open to the public.