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

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

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



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






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


Зап. научн. сем. ПОМИ, 2012, том 399, страницы 65–87 (Mi znsl5221)  

Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле

А. П. Давыдовa, С. И. Николенкоb

a СПбАУ НОЦНТ РАН, Санкт-Петербург, Россия
b Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия

Аннотация: Работа посвящена исследованиям в области схемной сложности в контексте доказуемо надёжных криптографических конструкций. Основываясь на идеях доказуемо надёжных функций с секретом, ранее разработанных в (Hirsch, Nikolenko, 2009; Melanich, 2009), мы представляем новую линейную конструкцию доказуемо надёжной функции с секретом, имеющую порядок надёжности $5/4$, а также проводим подробный общий анализ метода исключения гейтов (gate elimination) для случая линейных функций. В работе также приводится неконструктивное доказательство нелинейных нижних оценок схемной сложности на линейные булевы функции и верхние оценки на реализацию линейных булевых функций схемами с уточнёнными константами. Библ. – 53 назв.

Ключевые слова: надёжность в слабом смысле, схемная сложность, функции с секретом, доказуемая надёжность.

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

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2013, 188:1, 35–46

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

Тип публикации: Статья
УДК: 519.6
Поступило: 31.01.2012

Образец цитирования: А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 65–87; J. Math. Sci. (N. Y.), 188:1 (2013), 35–46

Цитирование в формате AMSBIB
\RBibitem{DavNik12}
\by А.~П.~Давыдов, С.~И.~Николенко
\paper Схемная сложность линейных функций: метод исключения гейтов и надежность в~слабом смысле
\inbook Теория сложности вычислений.~X
\serial Зап. научн. сем. ПОМИ
\yr 2012
\vol 399
\pages 65--87
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl5221}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2945000}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2013
\vol 188
\issue 1
\pages 35--46
\crossref{https://doi.org/10.1007/s10958-012-1104-9}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84871935818}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl5221
  • http://mi.mathnet.ru/rus/znsl/v399/p65

    ОТПРАВИТЬ: 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
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:190
    Полный текст:45
    Литература:19
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020