RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Главная страница
О проекте
Программное обеспечение
Классификаторы
Полезные ссылки
Пользовательское
соглашение

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

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






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


Inform. Process. Lett., 2012, том 112, выпуск 7, страницы 267–271 (Mi ipl1)  

Exponential lower bound for bounded depth circuits with few threshold gates

V. V. Podolskii

Steklov Mathematical Institute, Gubkina str. 8, 119991, Moscow, Russia

Аннотация: We prove an exponential lower bound on the size of bounded depth circuits with $O(\log n)$ threshold gates computing an explicit function (namely, the parity function).
Previously exponential lower bounds were known only for circuits with one threshold gate. Superpolynomial lower bounds are known for circuits with $O(\log n)$ threshold gates.

DOI: https://doi.org/10.1016/j.ipl.2011.12.011


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

Тип публикации: Статья
Поступила в редакцию: 26.05.2011
Исправленный вариант: 07.12.2011
Язык публикации: английский

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

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:16

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018