Probabilistic Methods in Computational Systems and Infrastructure

ISAT STUDY

Follow-up meeting:

Probability, Utility, and Foundations of Computation

Friday, July 16 1999

Microsoft Research

MS Research Conference Room (31/2053)

8:45 Breakfast

9:00 Introduction and Study Status

Eric Horvitz

Uncertainty, Probability, and Approximation

9:15-12:00

• A Decision-Theoretic Perspective on Computation

Eric Horvitz

• Online Algorithms: Current Directions and Future Opportunities

Anna Karlin

• Designing Algorithms for Expected Performance

Yuri Gurevich

Break

10:15-10:30

• Challenges and Opportunities with Approximation Procedures

Dimitris Achlioptas

• Probabilities in Optimization: Experiences from the CAD Community

Wray Buntine

Discussion: Opportunities in Uncertainty, Probability, and Approximation

12:00-1:30 Lunch

Understanding and Addressing Problem Hardness

1:30-3:00

• Leveraging "Universality" in Characterizing Problem Hardness

Bart Selman

• Toward Understanding the Structure of Phase Transitions in Satisfiability Problems

David Wilson

• Approaches to Analysis and Control of Restart Procedures in Search

Carla Gomes

Discussion: A Research Agenda on Problem Hardness

Break

3:00-3:15

Breakout Discussion

3:15-5:00

Probability, Utility, and Approximation

Breakout Room: 31/2027

Approaching Problem Hardness

Breakout Room: 31/2053 (main conf. room)

5:15 Adjourn

7:00-9:00 Dinner at Yarrow Bay Grill