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

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

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


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




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

Записки научных семинаров ПОМИ, 2012, том 399, страницы 65–87 (Mi znsl5221)  
Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле

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

a СПбАУ НОЦНТ РАН, Санкт-Петербург, Россия
b Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия
PDF полного текста (343 kB)
Список литературы:
PDF
HTML
Аннотация: Работа посвящена исследованиям в области схемной сложности в контексте доказуемо надёжных криптографических конструкций. Основываясь на идеях доказуемо надёжных функций с секретом, ранее разработанных в (Hirsch, Nikolenko, 2009; Melanich, 2009), мы представляем новую линейную конструкцию доказуемо надёжной функции с секретом, имеющую порядок надёжности $5/4$, а также проводим подробный общий анализ метода исключения гейтов (gate elimination) для случая линейных функций. В работе также приводится неконструктивное доказательство нелинейных нижних оценок схемной сложности на линейные булевы функции и верхние оценки на реализацию линейных булевых функций схемами с уточнёнными константами. Библ. – 53 назв.
Ключевые слова: надёжность в слабом смысле, схемная сложность, функции с секретом, доказуемая надёжность.
Поступило: 31.01.2012
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2013, Volume 188, Issue 1, Pages 35–46
DOI: https://doi.org/10.1007/s10958-012-1104-9
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.6
Образец цитирования: А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. 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://mathscinet.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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84871935818}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl5221
  • https://www.mathnet.ru/rus/znsl/v399/p65
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:654
    PDF полного текста:72
    Список литературы:44
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024