Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
| Original language | English |
|---|---|
| Title of host publication | Programs, Proofs, Processes - 6th Conference on Computability in Europe, CiE 2010, Proceedings |
| Pages | 239-245 |
| Number of pages | 7 |
| DOIs | |
| State | Published - 29 Jul 2010 |
| Event | 6th Conference on Computability in Europe, CiE 2010 - Ponta Delgada, Azores, Portugal Duration: 30 Jun 2010 → 4 Jul 2010 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 6158 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 6th Conference on Computability in Europe, CiE 2010 |
|---|---|
| Country/Territory | Portugal |
| City | Ponta Delgada, Azores |
| Period | 30/06/10 → 4/07/10 |
ID: 49825553