Combinatorial Optimization and Disordered Materials:
Recent Progress and Algorithmic Challenges

FINAL SCHEDULE

- Lectures are to be held in the auditorium in the Core building, Rutgers Univ., New Jersey
- Buffet breakfasts and the coffee breaks will be provided outside the auditorium
- Lunches (Thursday, Friday and Saturday) and the reception (Thursday after the lectures) will be provided in the DIMACS lounge Rm. 401 Core Building

THURSDAY MORNING I (Chair - Aharony) - Percolation/Self avoiding walks
7:30-8:50am Breakfast and registration
8:50-9:00am Welcome by DIMACS and the organisers
9:00-9:30am J.Chayes (Microsoft research)
"Birth of the Infinite Cluster: Finite-Size Scaling in Percolation"
9:30-10:00am M. Aizenman (Physics, Princeton)
"Holder-continuity of the connecting paths, Tortuosity Exponents, and the Scaling Limits in some Stochastic-Geometric models"
10:00-10:30am A. Sokal (Physics, New York University)
"Monte Carlo Methods for the Self-Avoiding Walk"

10:30-11:00am Coffee

THURSDAY MORNING II (Chair - Franzblau) - Graph rigidity and rigidity algorithms
11:00-11:45am W. Whiteley (Mathematics and Statistics, York University)
" Generic rigidity: the molecular model."
11:45-12:15pm B. Hendrickson (Sandia National Laboratories)
"Efficient algorithms for generic rigidity percolation"

12:15 -1:45pm Lunch

THURSDAY AFTERNOON I (Chair - Leath) Rigidity percolation and glasses/Matching problems
1:45-2:30pm M.F. Thorpe (Physics, Michigan State University)
"Rigidity in glasses and macromolecules"
2:30-3:00pm C. Moukarzel (Physics, Niteroi)
``Matching algorithms for connectivity and rigidity percolation"
3:00-3:30pm Duxbury/Jacobs Discussion Leaders
"Discussion of algorithms and issues in percolation"

3:30-4:00pm Coffee

THURSDAY AFTERNOON II (Chair - Lebowitz) Averaging and MC of Quenched Systems
4:00-4:45pm A. Aharony(Physics, Tel Aviv)
"Absence of self averaging in quenched random systems near criticality"
4:45-5:30pm K. Binder(Physics, Mainz)
"What can straightforward Monte Carlo achieve in the study of disordered systems?"

Reception: 5:30-7:00pm

FRIDAY MORNING (Chair - Huse) - Interfaces, flux lines and flow optimization
7:30-8:30am Breakfast and registration
8:30-9:15am M. Kardar (Physics, MIT)
"Glassy behavior of Flux Lines in Random Media: Barriers and Entanglements"
9:15-10:00am A. Goldberg (NEC research)
``The Push-Relabel Method''

10:00-10:30am Coffee

10:30-11:00am M. Alava (Nordita)
"Min-cut/max-flow and interfaces: Random bonds, wetting and random fields"
11:00-11:30am A. Middleton (Physics, Syracuse)
"Studying Interfaces and Lines in Random Potentials Using Max-flow and Matching Algorithms"
11:30-12:00am H. Rieger (HLRZ, Forschungszentrum Juelich)
"Minimum-cost-flow algorithms and their application to flux lines, vortex glasses and random surfaces."

12:00-1:30pm Lunch

FRIDAY AFTERNOON (Chair - Binder) - Ground State of Spin Glasses and other frustrated systems
1:30-2:15pm D. Huse(Physics, Princeton)
"Review of spin glasses"
2:15-2:45pm F. Barahona (IBM, Yorktown)
"Ground states of Ising spin glasses, a survey of combinatorial optimization methods"
2:45-3:15pm D. Stein (Physics, Univ. Arizona)
``Greedy spin glass ground states and the invasion forest''

3:15-3:45pm Coffee

3:45-4:15pm A. Hartmann (Physics, Heidelberg)
"The degenerate ground states of random field systems and diluted antiferromagnets"
4:15-4:45pm O. Martin (Physics, Orsay)
"Dimensional dependence in bond disordered CO models (TSP, matching,...)"
4:45-5:15pm J. de Coninck (Physics, Universite de Mons-Hainaut)
``Wetting on heterogeneous substrates''

SATURDAY MORNING (Chair - Middleton) - Algorithms in disordered systems/Optimization/Complexity
7:30-8:30am Breakfast and Registration
8:30-9:00am A.L. Barabasi (Physics, Notre Dame)
"Invasion percolation and global optimization"
9:00-9:45am J. Gubernatis (Los Alamos)
"Cluster algorithms "
9:45-10:15am J. Machta (Physics, University of Massachusetts)
"New cluster algorithms for equilibrium phase transitions"

10:15-10:45am Coffee

10:45-11:15am E. Shamir (Mathematics, Hebrew University)
"Hard problems in Learning Theory"
11:15-11:45am F. Sullivan (Cntr. Comp. Sciences, Bowie)
"Approximating the permanent via importance sampling."
11:45-12:15pm E. Domany(Weizmann)
"Superparamagnetic clustering of data - The definitive solution to an ill-posed problem"

12:30-2:00pm Lunch

SATURDAY AFTERNOON
2:00-3:30pm Roundtable on optimization methods in disordered systems: Oportunities and open issues
Aharony, Domany, Duxbury, Franzblau, Goldberg, Hendrickson, Martin, Middleton, Rieger, Sullivan

Organizing Committee
P.M. Duxbury(Chair), D.S. Franzblau, P.L. Leath, J. Lebowitz