On the limits of gate elimination

Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov

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

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

Аннотация

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of 3 186n-o(n). All known lower bounds are based on the so-called gate elimination technique. A typical gate elimination argument shows that it is possible to eliminate several gates from an optimal circuit by making one or several substitutions to the input variables and repeats this inductively. In this note we prove that this method cannot achieve linear bounds of cn beyond a certain constant c, where c depends only on the number of substitutions made at a single step of the induction.

Язык оригиналаанглийский
Название основной публикации41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
РедакторыAnca Muscholl, Piotr Faliszewski, Rolf Niedermeier
ИздательSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (электронное издание)9783959770163
DOI
СостояниеОпубликовано - 1 авг 2016
Событие41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krakow, Польша
Продолжительность: 22 авг 201626 авг 2016

Серия публикаций

НазваниеLeibniz International Proceedings in Informatics, LIPIcs
Том58
ISSN (печатное издание)1868-8969

конференция

конференция41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Страна/TерриторияПольша
ГородKrakow
Период22/08/1626/08/16

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

  • Программный продукт

Fingerprint

Подробные сведения о темах исследования «On the limits of gate elimination». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать