| Presentation | 1996/10/31 Cirsuit Complexity and Approximate Operations Kazuyuki AMANO, Akira Maruoka, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Since Razborov(1985) obtained superpolynomial lower bounds for monotone circuits that detect cliques in graphs, several results has been reported to obtain an exponential lower bound for monotone circuits that compute a certain function in the various ways, e.g. Andreev(1985). Alon and Boppana(1987), Haken(1995) and Amano and Maruoka(1996). In this paper, we show that all proofs for these results employ the approximation method or can be regarded as the proofs based on this method. Moreover, the counting arguments used in those proofs are quite similar. We also show that this type of proofs is too weak to improve lower bounds for monotone circuits that detect cliques of size s, for fixed s. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | monotone circuit complexity / approximation method / bottleneck counting / clique function |
| Paper # | COMP96-37 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1996/10/31(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) | Cirsuit Complexity and Approximate Operations |
| Sub Title (in English) | |
| Keyword(1) | monotone circuit complexity |
| Keyword(2) | approximation method |
| Keyword(3) | bottleneck counting |
| Keyword(4) | clique function |
| 1st Author's Name | Kazuyuki AMANO |
| 1st Author's Affiliation | Graduate School of Information Sciences, Tohoku University() |
| 2nd Author's Name | Akira Maruoka |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| Date | 1996/10/31 |
| Paper # | COMP96-37 |
| Volume (vol) | vol.96 |
| Number (no) | 343 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |