Generic Case Complexity

August 13 to August 17, 2007

at the

American Institute of Mathematics, San Jose, California

organized by

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

Original Announcement

This workshop 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

  1. Introduction to generic-case complexity
  2. Relation of generic-case complexity to other complexity measures;
  3. Application of generic-case complexity and generic properties of mathematical structures to the cryptanalysis of public key systems;
  4. The generic structure of hard problems.
Participants will be encouraged to assemble in groups to consider questions like the following. There will also be introductory lectures and problem sessions.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

Papers arising from the workshop:

The generic Hanna Neuman Conjecture and the Post Correspondence Problem
by  L. Ciobanu, A. Martino, and E. Ventura,
On generic properties of finitely presented monoids and semigroups
by  Mark Kambites
Quadratic equations over free groups are NP-complete
by  O. Kharlampovich, I. G. Lysenok, A. G Myasnikov, and N. W. M. Touikan.