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

 

May 17-19, 2011

Haifa, Israel

 

Tuesday, May 17

 

· Tuesday, May 17, 2011

9:30

Gathering and Greetings

10:00

Uri Zwick (Tel Aviv University)

Subexponential lower bounds for randomized pivoting rules for the simplex

algorithm

10:50

Break

11:00 -12:30

Session 1

11:00-11:30

Yefim Dinitz (Ben-Gurion University)

An O(|V||E|) Algorithm for Scheduling with AND/OR Precedence Constraints

11:30-12:00

Yakov Matsri (Tel Aviv University)

Multi-Hop Routing and Scheduling in Wireless Networks in the SINR Model

12:00-12:30

Elena Kleiman (University of Haifa)

On the Quality and Complexity of Pareto Equilibria in the Job Scheduling Game

12:30-14:00

Lunch Break

14:00-14:50

Ron Shamir (Tel Aviv University)

Dissecting regulatory networks and complex disease

 

14:50

Break

15:00-16:00

2nd Uri N. Peled Memorial Lecture

Remarks: Martin Golumbic and Dan Peled (University of Haifa)

Jayme Luiz Szwarcfiter (UFRJ and Brazilian Academy of Sciences)

Arboricity, h-Index and Dynamic Graph Algorithms

16:00

16:30-17:45

Coffee

Caesarea Rothschild Math & CS Distinguished Lecture I

 

 

 

17:45

Daniel Spielman (Yale University, USA)

Spectral and Electrical Graph Theory

Wine, Cheese and Renaissance Music (CRI, 6th Floor)

 

 

 

 

 

Wednesday, May 18

· Wednesday, May 18, 2011

 

9:45

 

Gathering

10:00

Tali Kaufman (Bar-Ilan University)

Locally Testable Codes and Expanders

10:50

Break

11:00 -13:00

Session 2

11:00-11:30

Dmitry Sotnikov (Tel Aviv University)

All-Pairs Shortest Paths in O(n2) Time with High Probability

11:30-12:00

Michael Dinitz (Weizmann Institute)

Directed Spanners via Flow-Based Linear Programs

12:00-12:30

Yahav Nussbaum (Tel Aviv University)

Improved Algorithms for Minimum Cuts and Maximum Flows in Undirected Planar

Graphs

12:30-13:00

David Tankus (Ariel University Center of Samaria)

Lower Bounds on the Ratio of Spectral Sets

13:00-14:15

Lunch Break

14:30

Caesarea Rothschild Math & CS Distinguished Lecture II

 

Daniel Spielman (Yale University, USA)

Solving Systems of Linear Equations in Graph Laplacians

16:00-18:00

Session 3

16:00-16:30

Ron Adany (Bar-Ilan University)

Polynomial Time Approximation Schemes for Personal Advertisement Assignment Problems

16:30-17:00

Sagi Hilleli (Ben-Gurion University)

Probabilistic Testing of Non-Feasibility of the OS Instances

17:00-17:30

Aleksander Vainer (Technion)

Benefit of Adaptivity in Stochastic Knapsack Problem with Dependence on State of Nature Assumption

17:30-18:00

Vadim E. Levit (Ariel University Center of Samaria)

A Family of Graphs with Polynomially Computable Cores

 

 

Thursday, May 19

· Thursday, May 19, 2011

 

9:15

 

Gathering

9:30

Session 4

9:30-10:00

Oren Weimann (Weizmann Institute)

Distance Oracles for Vertex-Colored Graphs

10:30-11:00

Gila Morgenstern (Ben-Gurion University)

Optimal Covering of Points inside Simple Regions

11:00

Caesarea Rothschild Math & CS Distinguished Lecture III

 

Daniel Spielman (Yale University, USA)

Spectral Sparsification of Graphs and Approximations of Matrices

12:30-14:00

Lunch Break

14:00-14:50

Gil Kalai (Hebrew University)

 

14:50-15:00

Break

15:00-16:00

Session 5

15:00-15:30

George B. Mertzios (CRI, University of Haifa)

Natural Models for Evolution on Networks

15:30-16:00

Nova Fandina (Ben-Gurion University)

Holographic Computation of Balanced Succinct Permanent Instances

16:15-17:45

Session 6

16:15-16:45

Nissim Halabi (Tel Aviv University)

Local Optimality Certificates for LP Decoding of Generalized Tanner Codes

16:45-17:15

Jonathan Goldfeld (Ben-Gurion University)

Efficient On-Line Detection of Timed Sequences

17:15-17:45

Moshe Cohen (Bar-Ilan University)

Dimer Models for the Alexander and Twisted Alexander Polynomials of Knots