RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra i Analiz: Year: Volume: Issue: Page: Find

 Algebra i Analiz, 2009, Volume 21, Issue 3, Pages 130–144 (Mi aa1142)

Research Papers

Infinitely frequently one-sided function based on an assumption on complexity in the mean

E. A. Hirsch, D. M. Itsykson

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: 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$.

Full text: PDF file (262 kB)
References: PDF file   HTML file

English version:
St. Petersburg Mathematical Journal, 2010, 21:3, 459–468

Bibliographic databases:

MSC: 68Q15

Citation: E. A. Hirsch, D. M. Itsykson, “Infinitely frequently one-sided function based on an assumption on complexity in the mean”, Algebra i Analiz, 21:3 (2009), 130–144; St. Petersburg Math. J., 21:3 (2010), 459–468

Citation in format AMSBIB
\Bibitem{HirIts09} \by E.~A.~Hirsch, D.~M.~Itsykson \paper Infinitely frequently one-sided function based on an assumption on complexity in the mean \jour Algebra i Analiz \yr 2009 \vol 21 \issue 3 \pages 130--144 \mathnet{http://mi.mathnet.ru/aa1142} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2588765} \zmath{https://zbmath.org/?q=an:1205.68164} \transl \jour St. Petersburg Math. J. \yr 2010 \vol 21 \issue 3 \pages 459--468 \crossref{https://doi.org/10.1090/S1061-0022-10-01103-9} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000277451000005} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84861235113} 

• http://mi.mathnet.ru/eng/aa1142
• http://mi.mathnet.ru/eng/aa/v21/i3/p130

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Hirsch E.A., Itsykson D., Monakhov I., Smal A., “On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography”, Theory Comput. Syst., 51:2 (2012), 179–195
•  Number of views: This page: 265 Full text: 78 References: 25 First page: 24