Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Viola E. — On the Power of Small-Depth Computation (Foundations and Trends in Theoretical Computer Science)
Viola E. — On the Power of Small-Depth Computation (Foundations and Trends in Theoretical Computer Science)

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: On the Power of Small-Depth Computation (Foundations and Trends in Theoretical Computer Science)

Автор: Viola E.

Аннотация:

In this monograph we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain:
A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0,1}.
An unpublished proof that small bounded-depth circuits (AC0) have exponentially small correlation with the parity function. The proof is due to Klivans and Vadhan; it builds upon and simplifies previous ones.
Valiant’s simulation of log-depth linear-size circuits of fan-in 2 by sub-exponential size circuits of depth 3 and unbounded fan-in. To our knowledge, a proof of this result has never appeared in full.
Applebaum, Ishai, and Kushilevitz’s cryptography in bounded depth.


Язык: en

Рубрика: Разное/

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 2009

Количество страниц: 74

Добавлена в каталог: 27.02.2016

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте