Finding cliques using few probes
© 2019 Wiley Periodicals, Inc. Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (Formula presented.) (and hence is likely to have a clique of s...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136529 |
| _version_ | 1826203739052048384 |
|---|---|
| author | Feige, Uriel Gamarnik, David Neeman, Joe Rácz, Miklós Z Tetali, Prasad |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Feige, Uriel Gamarnik, David Neeman, Joe Rácz, Miklós Z Tetali, Prasad |
| author_sort | Feige, Uriel |
| collection | MIT |
| description | © 2019 Wiley Periodicals, Inc. Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (Formula presented.) (and hence is likely to have a clique of size roughly (Formula presented.)), then for every δ<2 and constant ℓ, there is an α<2 (that may depend on δ and ℓ) such that no algorithm that makes nδ probes in ℓ rounds is likely (over the choice of the random graph) to output a clique of size larger than (Formula presented.). |
| first_indexed | 2024-09-23T12:42:16Z |
| format | Article |
| id | mit-1721.1/136529 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:42:16Z |
| publishDate | 2021 |
| publisher | Wiley |
| record_format | dspace |
| spelling | mit-1721.1/1365292023-02-22T17:12:15Z Finding cliques using few probes Feige, Uriel Gamarnik, David Neeman, Joe Rácz, Miklós Z Tetali, Prasad Sloan School of Management © 2019 Wiley Periodicals, Inc. Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (Formula presented.) (and hence is likely to have a clique of size roughly (Formula presented.)), then for every δ<2 and constant ℓ, there is an α<2 (that may depend on δ and ℓ) such that no algorithm that makes nδ probes in ℓ rounds is likely (over the choice of the random graph) to output a clique of size larger than (Formula presented.). 2021-10-27T20:35:48Z 2021-10-27T20:35:48Z 2020 2021-04-14T14:59:12Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136529 en 10.1002/RSA.20896 Random Structures and Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley arXiv |
| spellingShingle | Feige, Uriel Gamarnik, David Neeman, Joe Rácz, Miklós Z Tetali, Prasad Finding cliques using few probes |
| title | Finding cliques using few probes |
| title_full | Finding cliques using few probes |
| title_fullStr | Finding cliques using few probes |
| title_full_unstemmed | Finding cliques using few probes |
| title_short | Finding cliques using few probes |
| title_sort | finding cliques using few probes |
| url | https://hdl.handle.net/1721.1/136529 |
| work_keys_str_mv | AT feigeuriel findingcliquesusingfewprobes AT gamarnikdavid findingcliquesusingfewprobes AT neemanjoe findingcliquesusingfewprobes AT raczmiklosz findingcliquesusingfewprobes AT tetaliprasad findingcliquesusingfewprobes |