Geodesic
Infinitely frequently one-sided function based on an assumption on complexity in the mean
Algebra i analiz, Tome 21 (2009) no. 3, pp. 130-144 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We assume the existence of a function $f$ that is computable in polynomial time but cannot be inverted by a randomized average-case polynomial algorithm. The cryptographic setting is, however, different: even for a weak one-way function, a successful adversary should fail on a polynomial fraction of inputs. Nevertheless, we show how to construct an infinitely-often one-way function based on $f$. 
@article{AA_2009_21_3_a4,
     author = {E. A. Hirsch and D. M. Itsykson},
     title = {Infinitely frequently one-sided function based on an assumption on complexity in the mean},
     journal = {Algebra i analiz},
     pages = {130--144},
     year = {2009},
     volume = {21},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AA_2009_21_3_a4/}
}
TY  - JOUR
AU  - E. A. Hirsch
AU  - D. M. Itsykson
TI  - Infinitely frequently one-sided function based on an assumption on complexity in the mean
JO  - Algebra i analiz
PY  - 2009
SP  - 130
EP  - 144
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AA_2009_21_3_a4/
LA  - ru
ID  - AA_2009_21_3_a4
ER  - 
%0 Journal Article
%A E. A. Hirsch
%A D. M. Itsykson
%T Infinitely frequently one-sided function based on an assumption on complexity in the mean
%J Algebra i analiz
%D 2009
%P 130-144
%V 21
%N 3
%U http://geodesic.mathdoc.fr/item/AA_2009_21_3_a4/
%G ru
%F AA_2009_21_3_a4
E. A. Hirsch; D. M. Itsykson. Infinitely frequently one-sided function based on an assumption on complexity in the mean. Algebra i analiz, Tome 21 (2009) no. 3, pp. 130-144. http://geodesic.mathdoc.fr/item/AA_2009_21_3_a4/

[1] Ben-David Shai, Chor Benny, Goldreich Oded, Luby Michael, “On the theory of average case complexity”, J. Comput. System Sci., 44:2 (1992), 193–219 | DOI | MR | Zbl

[2] Bogdanov A., Trevisan L., “Average-case complexity”, Found. Trends in Theor. Comput. Sci., 2:1 (2006), 1–106 | DOI | MR

[3] Goldreich O., Foundations of cryptography. Basic tools, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[4] Impagliazzo R., “A personal view of average-case complexity”, Structure in Complexity Theory (SCT' 95), 10th Annual Conference (Minneapolis, Minnesota, 1995), IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 134–147

[5] Impagliazzo R., Levin L., “No better ways to generate hard NP instances than picking uniformly at random”, 31st Annual Symposium on Foundations of Computer Science, Vol. II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 812–821

[6] Levin L., “Average case complete problems”, SIAM J. Comput., 15:1 (1986), 285–286 | DOI | MR | Zbl

[7] Levin L. A., “Odnostoronnie funktsii”, Probl. peredachi inf., 39:1 (2003), 103–117 | MR | Zbl