RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Пробл. передачи информ., 2003, том 39, выпуск 1, страницы 103–117 (Mi ppi208)  

Эта публикация цитируется в 25 научных статьях (всего в 25 статьях)

Односторонние функции

Л. А. Левин


Аннотация: Одной из наиболее важных проблем теоретической информатики является вопрос о существовании односторонних функций. Эта статья рассматривает и уточняет ряд понятий, с ним связанных. В частности, впервые приводится явное комбинаторное построение полной односторонней функции (полнота означает, что эта функция является односторонней, если таковые вообще существуют). Основные концепции содержат неожиданно много тонкостей (частично уже упоминавшихся в литературе). Здесь предлагается некоторый единый подход.

Полный текст: PDF файл (2362 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Problems of Information Transmission, 2003, 39:1, 92–103

Реферативные базы данных:

УДК: 621.391:519.2

Образец цитирования: Л. А. Левин, “Односторонние функции”, Пробл. передачи информ., 39:1 (2003), 103–117; Problems Inform. Transmission, 39:1 (2003), 92–103

Цитирование в формате AMSBIB
\RBibitem{Lev03}
\by Л.~А.~Левин
\paper Односторонние функции
\jour Пробл. передачи информ.
\yr 2003
\vol 39
\issue 1
\pages 103--117
\mathnet{http://mi.mathnet.ru/ppi208}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2101668}
\zmath{https://zbmath.org/?q=an:1077.94007}
\transl
\jour Problems Inform. Transmission
\yr 2003
\vol 39
\issue 1
\pages 92--103
\crossref{https://doi.org/10.1023/A:1023634616182}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi208
  • http://mi.mathnet.ru/rus/ppi/v39/i1/p103

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


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

    Эта публикация цитируется в следующих статьяx:
    1. А. А. Семенов, “О сложности обращения дискретных функций из одного класса”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 11:4 (2004), 44–55  mathnet  mathscinet
    2. Freivalds R., “Knot theory, Jones polynomial and quantum computing”, Mathematical foundations of computer science 2005, Lecture Notes in Comput. Sci., 3618, Springer, Berlin, 2005, 15–25  crossref  mathscinet  zmath  isi
    3. Aaronson S., “The learnability of quantum states”, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 463:2088 (2007), 3089–3114  crossref  mathscinet  zmath  adsnasa  isi
    4. Д. Ю. Григорьев, А. Кожевников, С. И. Николенко, “Алгебраическая криптография: новые конструкции и их надёжность относительно доказуемого взлома”, Алгебра и анализ, 20:6 (2008), 119–147  mathnet  mathscinet  zmath; D. Grigoriev, A. Kojevnikov, S. J. Nikolenko, “Algebraic cryptography: new constructions and their security against provable break”, St. Petersburg Math. J., 20:6 (2009), 937–953  crossref  isi
    5. Dowe D.L., “Foreword re C. S. Wallace”, Computer Journal, 51:5 (2008), 523-560  crossref  isi  elib
    6. Hirsch E.A., Itsykson D.M., “An infinitely-often one-way function based on an average-case assumption”, Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence, 5110, 2008, 208–217  mathscinet  zmath  isi
    7. Kojevnikov A., Nikolenko S.I., “New combinatorial complete one-way functions”, Stacs 2008: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, 2008, 457–466  mathscinet  zmath  isi
    8. Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144  mathnet  mathscinet  zmath; E. A. Hirsch, D. M. Itsykson, “Infinitely frequently one-sided function based on an assumption on complexity in the mean”, St. Petersburg Math. J., 21:3 (2010), 459–468  crossref  isi
    9. А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118  mathnet  mathscinet  zmath; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  crossref  isi
    10. Hagar A., “Active fault-tolerant quantum error correction: the curse of the open system”, Philos. Sci., 76:4 (2009), 506–535  crossref  isi
    11. Birget J.C., “On the Circuit-Size of Inverses”, Internat J Found Comput Sci, 22:8 (2011), 1925–1938  crossref  mathscinet  zmath  isi
    12. С. Ю. Ерофеев, В. А. Романьков, “Построение односторонних функций на основе неразрешимости проблемы эндоморфной сводимости в группах”, ПДМ, 2011, приложение № 4, 32–33  mathnet
    13. А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 65–87  mathnet  mathscinet; A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46  crossref
    14. С. Ю. Ерофеев, В. А. Романьков, “О построении возможно односторонних функций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах”, ПДМ, 2012, № 3(17), 13–24  mathnet
    15. С. И. Николенко, Д. С. Тугарёв, “Полная односторонняя функция, основанная на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. научн. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 91–107  mathnet  mathscinet; S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module”, J. Math. Sci. (N. Y.), 192:3 (2013), 307–315  crossref
    16. Ерофеев С.Ю., Романьков В.А., “О возможности построения односторонних функций на основе неразрешимости проблемы эндоморфной сводимости в группах”, Вестник омского университета, 2012, № 2, 53–56  mathscinet  elib
    17. de Castro A., “One-Way-Ness in the Input-Saving (Turing) Machine”, Physica A, 415 (2014), 473–478  crossref  isi
    18. Birget J.C., “Semigroups and One-Way Functions”, Int. J. Algebr. Comput., 25:1-2 (2015), 3–36  crossref  mathscinet  zmath  isi
    19. Л. В. Сахарова, “Автомодельность задачи тепловой конвекции, осредненной по тонкому слою”, Междунар. науч.-исслед. журн., 2016, № 7-4(49), 94–97  mathnet  crossref
    20. de Castro A., “Quantum One-Way Permutation Over the Finite Field of Two Elements”, Quantum Inf. Process., 16:6 (2017), UNSP 149  crossref  mathscinet  isi  scopus
    21. Currin A., Korovin K., Ababi M., Roper K., Kell D.B., Day Ph.J., King R.D., “Computing Exponentially Faster: Implementing a Non- Deterministic Universal Turing Machine Using Dna”, J. R. Soc. Interface, 14:128 (2017), 20160990  crossref  isi  scopus
    22. Feinstein C.A., “Why Do We Live in a Quantum World?”, Phys. Essays, 30:1 (2017), 57–59  crossref  isi  scopus
    23. Kavokin A., Baumberg J., Malpuech G., Laussy F., “Microcavities, 2Nd Edition”, Microcavities, 2Nd Edition, Series on Semiconductor Science and Technology, 21, Oxford Univ Press, 2017, 1–592  crossref  isi
    24. Levin L.A., Venkatesan R., “An Average Case Np-Complete Graph Colouring Problem”, Comb. Probab. Comput., 27:5 (2018), 808–828  crossref  mathscinet  zmath  isi  scopus
    25. Sotiraki K. Zampetakis M. Zirdelis G., “Ppp-Completeness With Connections to Cryptography”, 2018 IEEE 59Th Annual Symposium on Foundations of Computer Science (Focs), Annual IEEE Symposium on Foundations of Computer Science, ed. Thorup M., IEEE Computer Soc, 2018, 148–158  crossref  mathscinet  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:1147
    Полный текст:388
    Литература:67
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019