The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
The complexity of clique problems on Erds-Rényi random graphs has become a central topic in average-case complexity. Algorithmic phase transitions in these problems have been shown to have broad connections ranging from mixing of Markov chains and statistical physics to information-computation gaps...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129934 |
| _version_ | 1826197119596232704 |
|---|---|
| author | Boix-Adsera, Enric Brennan, Matthew Bresler, Guy |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Boix-Adsera, Enric Brennan, Matthew Bresler, Guy |
| author_sort | Boix-Adsera, Enric |
| collection | MIT |
| description | The complexity of clique problems on Erds-Rényi random graphs has become a central topic in average-case complexity. Algorithmic phase transitions in these problems have been shown to have broad connections ranging from mixing of Markov chains and statistical physics to information-computation gaps in high-dimensional statistics. We consider the problem of counting k-cliques in s-uniform Erds-Rényi hypergraphs G(n, c, s) with edge density c and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: •Dense Erds-Rényi hypergraphs: Counting k-cliques on G(n, c, s) with k and c constant matches its worst-case complexity up to a polylog(n) factor. Assuming ETH, it takes nΩ(k) time to count k-cliques in G(n, c, s) if k and c are constant. • Sparse Erds-Rényi hypergraphs: When c = Θ(n-α), for each fixed α our reduction yields different average-case phase diagrams depicting a tradeoff between runtime and k. Assuming the best known worst-case algorithms are optimal, in the graph case of s = 2, we establish that the exponent in n of the optimal running time for k-clique counting in G(n, c, s) is ωk/3-C α (k/2) + O-k, α (1), where ω/9 ≤ C ≤ 1 and ω is the matrix multiplication constant. In the hypergraph case of s ≥ 3, we show a lower bound at the exponent of k-α (k/s) + O-k, α (1) which surprisingly is tight against algorithmic achievability exactly for the set of c above the Erds-Rényi k-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdos-Renyi hypergraphs based on a worst-case hardness assumption. We also analyze several natural algorithms for counting k-cliques in G(n, c, s) that establish our upper bounds in the sparse case c = Θ(n-α). |
| first_indexed | 2024-09-23T10:42:48Z |
| format | Article |
| id | mit-1721.1/129934 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:42:48Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1299342022-09-27T14:28:00Z The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs Boix-Adsera, Enric Brennan, Matthew Bresler, Guy Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The complexity of clique problems on Erds-Rényi random graphs has become a central topic in average-case complexity. Algorithmic phase transitions in these problems have been shown to have broad connections ranging from mixing of Markov chains and statistical physics to information-computation gaps in high-dimensional statistics. We consider the problem of counting k-cliques in s-uniform Erds-Rényi hypergraphs G(n, c, s) with edge density c and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: •Dense Erds-Rényi hypergraphs: Counting k-cliques on G(n, c, s) with k and c constant matches its worst-case complexity up to a polylog(n) factor. Assuming ETH, it takes nΩ(k) time to count k-cliques in G(n, c, s) if k and c are constant. • Sparse Erds-Rényi hypergraphs: When c = Θ(n-α), for each fixed α our reduction yields different average-case phase diagrams depicting a tradeoff between runtime and k. Assuming the best known worst-case algorithms are optimal, in the graph case of s = 2, we establish that the exponent in n of the optimal running time for k-clique counting in G(n, c, s) is ωk/3-C α (k/2) + O-k, α (1), where ω/9 ≤ C ≤ 1 and ω is the matrix multiplication constant. In the hypergraph case of s ≥ 3, we show a lower bound at the exponent of k-α (k/s) + O-k, α (1) which surprisingly is tight against algorithmic achievability exactly for the set of c above the Erds-Rényi k-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdos-Renyi hypergraphs based on a worst-case hardness assumption. We also analyze several natural algorithms for counting k-cliques in G(n, c, s) that establish our upper bounds in the sparse case c = Θ(n-α). 2021-02-19T21:51:27Z 2021-02-19T21:51:27Z 2020-01 2019-11 2020-12-03T17:29:56Z Article http://purl.org/eprint/type/ConferencePaper 9781728149523 2575-8454 https://hdl.handle.net/1721.1/129934 Boix-Adsera, Enric et al. "The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs." IEEE 60th Annual Symposium on Foundations of Computer Science, November 2019, Institute of Electrical and Electronics Engineers, January 2020. © 2019 IEEE en http://dx.doi.org/10.1109/focs.2019.00078 IEEE 60th Annual Symposium on Foundations of Computer Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Boix-Adsera, Enric Brennan, Matthew Bresler, Guy The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs |
| title | The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs |
| title_full | The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs |
| title_fullStr | The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs |
| title_full_unstemmed | The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs |
| title_short | The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs |
| title_sort | average case complexity of counting cliques in erdos renyi hypergraphs |
| url | https://hdl.handle.net/1721.1/129934 |
| work_keys_str_mv | AT boixadseraenric theaveragecasecomplexityofcountingcliquesinerdosrenyihypergraphs AT brennanmatthew theaveragecasecomplexityofcountingcliquesinerdosrenyihypergraphs AT breslerguy theaveragecasecomplexityofcountingcliquesinerdosrenyihypergraphs AT boixadseraenric averagecasecomplexityofcountingcliquesinerdosrenyihypergraphs AT brennanmatthew averagecasecomplexityofcountingcliquesinerdosrenyihypergraphs AT breslerguy averagecasecomplexityofcountingcliquesinerdosrenyihypergraphs |