Most computational task that arise in realistic scenarios are intractable, at least if one insists on exact solutions delivered with certainty within a strict deadline. Nevertheless, practical necessity dictates that acceptable solutions of some kind must be found in a reasonable time. Two important means for surmounting the intractability barrier are randomized computation , where the answer is optimal with high probability but not with certainty, or approximate computation , where the answer is guaranteed to be within, say, small percentage of optimality. More often than not, these two notions go hand-in-hand.

The seminar will be concerned with these phenomena. It will address the newest development in the design and analysis of randomized approximation algorithms, and the new fundamental insights into computational approximate feasibility, optimality, and the intractability of various computational problems. The main focus of the workshop is to be on two specific topics and the various interactions between them. The specific topics are the following:

• Approximation algorithms for optimization problems.
Randomization and de-randomizing techniques play a major role here, both in positive (upper bounds) and negative (lower bounds) results. It features for example in the "rounding" step of approximation algorithms based on linear or semidefinite programming relaxations; it is also at the heart of the theory of probabilistically checkable proofs (PCPs) that is the basis for the recent non-approximability results. A number of very significant new results were obtained here recently.
• Approximation algorithms for measurement problems.
The word "measurement" here is used to distinguish a class of problems-determining the cardinality of combinatorially or computationally defined sets, volume, expectation of random variables on configurations of complex systems, etc. - which are very different in flavor of the optimization problems. This theme is less developed than the previous one, but significant progress is currently being made, both in design of efficient approximation algorithms, and in proving the first approximation lower bounds based on the PCP-techniques mentioned before. It is aimed here at investigating further fundamental and intrinsic connections between the efficiency of approximating optimization problems and the efficiency of approximating measurement problems.

The main goal of the seminar is to bring together researchers working in the area of approximation algorithms and approximation complexity of computational problems, and focus on the newest developments (including practical implementations) within, and also in between the above main themes.