Presentation | 2011-06-30 On the Constant Depth Circuit Complexity of Subgraph Isomorphism on Random Graphs Koutarou NAKAGAWA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The AC^0 circuit complexity of k-clique on random graphs is already known. Rossman established the lower bound n^<ω(k/4)> in 2008, and Amano establishd the upper bound n^ |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | |
Paper # | COMP2011-20 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2011/6/23(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 | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | On the Constant Depth Circuit Complexity of Subgraph Isomorphism on Random Graphs |
Sub Title (in English) | |
Keyword(1) | |
1st Author's Name | Koutarou NAKAGAWA |
1st Author's Affiliation | Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology() |
Date | 2011-06-30 |
Paper # | COMP2011-20 |
Volume (vol) | vol.111 |
Number (no) | 113 |
Page | pp.pp.- |
#Pages | 5 |
Date of Issue |