Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
We consider Boolean circuits over the full binary basis. We prove a (3+1/86)n-o(n) lower bound onthe size of such a circuit for an explicitly definedpredicate, namely an affine disperser for sublinear dimension. This improves the 3n-o(n) bound of Norbert Blum (1984).The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.
Язык оригинала | английский |
---|---|
Название основной публикации | Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |
Издатель | Institute of Electrical and Electronics Engineers Inc. |
Страницы | 89-98 |
Число страниц | 10 |
ISBN (электронное издание) | 9781509039333 |
DOI | |
Состояние | Опубликовано - 14 дек 2016 |
Событие | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, Соединенные Штаты Америки Продолжительность: 9 окт 2016 → 11 окт 2016 |
Название | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|
Том | 2016-December |
ISSN (печатное издание) | 0272-5428 |
конференция | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |
---|---|
Страна/Tерритория | Соединенные Штаты Америки |
Город | New Brunswick |
Период | 9/10/16 → 11/10/16 |
ID: 49823726