In this talk we will discuss an alternative definition of one-way function using the concepts of the generic case complexity. This relatively new approach allows one to analyze the behavior of an algorithm on ``most" inputs in a simple and intuitive fashion which has some practical advantages over classical methods based on averaging.

We show that the new definition is equivalence to the standard one. In addition we demonstrate the convenience of the new approach by giving a short proof that extending adversaries to a larger class of partial algorithms with errors does not change the strength of the security assumption.

Alexey Myasnikov received his PhD in Computer Science from City University of New York. His research interests include Statistical pattern recognition, Computational Algebra, Cryptography, Generic and Cryptographic complexity. In particular he is interested in applications of pattern recognition and machine learning to fundamental problems in abstract algebra and algebraic cryptography.

His previous positions include senior researcher at Umbanet Inc. (NIST Advanced Technology Program), senior software developer at Magnus Software Project of the New Your Group Theory Cooperative and research assistant at the Pattern Recognition Lab (the Graduate Center of CUNY). Currently, Alexey is a research faculty member of the Department of Mathematical Sciences and the Algebraic Cryptography Center at Stevens Institute of Technology.