Average-case complexity of detecting cliques
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/62441 |
| _version_ | 1826189899851628544 |
|---|---|
| author | Rossman, Benjamin (Benjamin E.) |
| author2 | Madhu Sudan. |
| author_facet | Madhu Sudan. Rossman, Benjamin (Benjamin E.) |
| author_sort | Rossman, Benjamin (Benjamin E.) |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T08:28:25Z |
| format | Thesis |
| id | mit-1721.1/62441 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:28:25Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/624412022-01-13T07:54:29Z Average-case complexity of detecting cliques Rossman, Benjamin (Benjamin E.) Madhu Sudan. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Cataloged from PDF version of thesis. Includes bibliographical references (p. 79-83). The computational problem of testing whether a graph contains a complete subgraph of size k is among the most fundamental problems studied in theoretical computer science. This thesis is concerned with proving lower bounds for k-CLIQUE, as this problem is known. Our results show that, in certain models of computation, solving k-CLIQUE in the average case requires Q(nk/4) resources (moreover, k/4 is tight). Here the models of computation are bounded-depth Boolean circuits and unbounded-depth monotone circuits, the complexity measure is the number of gates, and the input distributions are random graphs with an appropriate density of edges. Such random graphs (the well-studied Erdos-Renyi random graphs) are widely believed to be a source of computationally hard instances for clique problems (as Karp suggested in 1976). Our results are the first unconditional lower bounds supporting this hypothesis. For bounded-depth Boolean circuits, our average-case hardness result significantly improves the previous worst-case lower bounds of Q(nk/Poly(d)) for depth-d circuits. In particular, our lower bound of Q(nk/ 4 ) has no noticeable dependence on d for circuits of depth d ; k- log n/log log n, thus bypassing the previous "size-depth tradeoffs". As a consequence, we obtain a novel Size Hierarchy Theorem for uniform AC0 . A related application answers a longstanding open question in finite model theory (raised by Immerman in 1982): we show that the hierarchy of bounded-variable fragments of first-order logic is strict on finite ordered graphs. Additional results of this thesis characterize the average-case descriptive complexity of k-CLIQUE through the lens of first-order logic. by Benjamin Rossman. Ph.D. 2011-04-25T15:59:14Z 2011-04-25T15:59:14Z 2010 2010 Thesis http://hdl.handle.net/1721.1/62441 711003585 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 83 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Rossman, Benjamin (Benjamin E.) Average-case complexity of detecting cliques |
| title | Average-case complexity of detecting cliques |
| title_full | Average-case complexity of detecting cliques |
| title_fullStr | Average-case complexity of detecting cliques |
| title_full_unstemmed | Average-case complexity of detecting cliques |
| title_short | Average-case complexity of detecting cliques |
| title_sort | average case complexity of detecting cliques |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/62441 |
| work_keys_str_mv | AT rossmanbenjaminbenjamine averagecasecomplexityofdetectingcliques |