Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
In this note, we use lower bounds on Boolean multiplicative complexity to prove lower bounds on Boolean circuit complexity. We give a very simple proof of a 7n/3-c lower bound on the circuit complexity of a large class of functions representable by high degree polynomials over GF(2). The key idea of the proof is a circuit complexity measure assigning different weights to XOR and AND gates.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings |
| Страницы | 239-245 |
| Число страниц | 7 |
| DOI | |
| Состояние | Опубликовано - 29 июл 2010 |
| Событие | 6th Conference on Computability in Europe, CiE 2010 - Ponta Delgada, Azores, Португалия Продолжительность: 30 июн 2010 → 4 июл 2010 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 6158 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 6th Conference on Computability in Europe, CiE 2010 |
|---|---|
| Страна/Tерритория | Португалия |
| Город | Ponta Delgada, Azores |
| Период | 30/06/10 → 4/07/10 |
ID: 49825553