Generic Case Complexity

August 13 to August 17, 2007

at the

American Institute of Mathematics, Palo Alto, California

organized by

Robert Gilman, Alexei Miasnikov, Vladimir Shpilrain, and Rebecca Wright

This workshop, sponsored by AIM and the NSF, will be devoted to exploring the potential contribution of generic-case complexity to cryptography. Generic-case complexity is a new complexity measure which seems to be useful for assessing the algorithmic security of public key cryptosystems. The intended intended participants include cryptographers, mathematicians, and students.

The main topics for the workshop are

Introduction to generic-case complexity
Relation of generic-case complexity to other complexity measures;
Application of generic-case complexity and generic properties of mathematical structures to the cryptanalysis of public key systems;
The generic structure of hard problems.

Participants will be encouraged to assemble in groups to consider questions like the following.

Generic methods have proved useful in cryptanalysis of braid group cryptosystems. To what extent do they apply to other systems?
Several hard problems e.g., the halting problem for Turing machines with semi-infinite tape, are generically easy. How general is this phenomenon? Find some decision problems which are not generically easy.
The relation of generic-case complexity to worst case and average case complexity is fairly well understood. What about other complexity measures?

There will also be introductory lectures and problem sessions.

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email workshops@aimath.org

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Go to the list of upcoming workshops.