| Presentation | 1995/4/21 On Negation-Limited Circuit Complexity of Symmetric Functions Keisuke Tanaka, Tetsuro Nishino, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A combinational circuit using a limited number of NOT gates is said to be negation-limited. The complexity of negation-limited circuits which compute symmetric functions is investigated, and lower bounds on the size and the depth of negation-limited circuits computing various symmetric functions are shown. For example, 4n+3log(n+k)-5k-c and 4log(n+k)-k-c lower bounds are given on the size and the depth of circuits computing modular functions using [log(n+1)-1] NOT gates, respectively. Furthermore, nonlinear lower bounds on the size of certain kinds of negation-limited circuits computing symmetric functions are shown. Finally, we shall consider a relationship between the size of circuits and the number of NOT gates in circuits. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | circuit complexity / negation / symmetric function / upper bound / lower bound |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1995/4/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Negation-Limited Circuit Complexity of Symmetric Functions |
| Sub Title (in English) | |
| Keyword(1) | circuit complexity |
| Keyword(2) | negation |
| Keyword(3) | symmetric function |
| Keyword(4) | upper bound |
| Keyword(5) | lower bound |
| 1st Author's Name | Keisuke Tanaka |
| 1st Author's Affiliation | School of Information Science Japan Advanced Institute of Science and Technology-Hokiiriku() |
| 2nd Author's Name | Tetsuro Nishino |
| 2nd Author's Affiliation | Department of Communications and Systems Engineering The University of Electro-Communications |
| Date | 1995/4/21 |
| Paper # | |
| Volume (vol) | vol.95 |
| Number (no) | 13 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |