A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

15 Цитирования (Scopus)

Аннотация

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 окт 201611 окт 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/1611/10/16

Предметные области Scopus

  • Компьютерные науки (все)

Fingerprint

Подробные сведения о темах исследования «A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать