The question of the power of randomness in computation is a central theme within the theory of intractability. The central question is: "are there problems that are intractable using deterministic computation that are tractable using randomized computation?" Research on this question, which points to a negative answer, has focused around the study of the constructibility of pseudo-random generators, and the constuctibility of these generators has been shown to be closely connected to the existence of computational problems that are suitably intractable. The development of the probabilistic method in combinatorics has led to a variety of non-constructive proofs of existence of combinatorial objects satisfying certain specified properties: graphs whose clique and independence numbers are both very small (Ramsey graphs), graphs with strong connectivity properties, such as expanders, and large codes with optimal distances. It has long been of interest to find explicit constructions of objects with these properties.
These two areas are brought together by the realization that the problem of designing pseudorandom generators, and related problems such as that of making randomized algorithms robust in the presence of imperfections in the random source, can be formulated as problems of explicit construction of combinatorial objects. Thus the study of such constructions has become an important part of the theory of probabilistic computation The problem of proving lower bounds on computational problems (at least in non-uniform models) can be viewed as that of finding an explicit hard function, where it is known non-constructively that most functions are hard.
The computational point of view has motivated new problems in combinatorics and also led to new techniques for constructing objects like expanders that are better than any known before. This symbiosis is also evident in the connection between the theory of derandomization in computational geometry and discrepancy theory within combinatorial geometry.
This workshop will focus on this common area of interest, focusing on problems and techniques for construction of combinatorial objects arising in computer science, graph theory, and coding theory. In recent years, these techniques have included methods from such diverse areas as representation theory and algebraic geometry, and one aim of the workshop is to expose a broader range of researchers to these techniques.
The plenary talks will be given by:
Noga Alon, Tel Aviv University
Ramsey Type Graphs
Amin Shokrollahi, Bell Labs
Codes Over Algebraic Curves
Luca Trevisan, Columbia University
Extractors and Pseudorandom Generators
Avi Widgerson, IAS and Hebrew University
Open Problems
Next: Call for Participation
Workshop Index
DIMACS Homepage