The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
From MaRDI portal
Publication:5157395
DOI10.1137/20M1316044MaRDI QIDQ5157395
Enric Boix-Adserà, Guy Bresler, Matthew Brennan
Publication date: 18 October 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.08247
random graphsgraph algorithmsaverage-case complexityfine-grained complexityworst-case-to-average-case reductions
Combinatorial probability (60C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Improved Merlin-Arthur protocols for central problems in fine-grained complexity, Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Nuclear norm minimization for the planted clique and biclique problems
- Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
- Strong computational lower bounds via parameterized complexity
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence
- The monotone circuit complexity of Boolean functions
- Highly resilient correctors for polynomials
- Expected complexity of graph partitioning problems
- Decoding of Reed Solomon codes beyond the error-correction bound
- Hiding cliques for cryptographic security
- Upper tails for subgraph counts in random graphs
- Local algorithms for independent sets are half-optimal
- Computational barriers in minimax submatrix detection
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- The critical point of \(k\)-clique percolation in the Erdős-Rényi graph
- On the Choice Number of Random Hypergraphs
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Incoherence-Optimal Matrix Completion
- Hidden Cliques and the Certification of the Restricted Isometry Property
- On the probable behaviour of some algorithms for finding the stability number of a graph
- Clique percolation
- Factor Refinement
- Random-Self-Reducibility of Complete Sets
- Tight upper tail bounds for cliques
- On independent sets in random graphs
- The Complexity of Enumeration and Reliability Problems
- Large Cliques Elude the Metropolis Process
- On colouring random graphs
- Finding a Minimum Circuit in a Graph
- The infamous upper tail
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- Finding and certifying a large hidden clique in a semirandom graph
- Average-case fine-grained hardness
- Reducibility among Combinatorial Problems
- Worst-Case to Average-Case Reductions for Subclasses of P
- Finding cliques using few probes
- LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
- Clique is hard on average for regular resolution
- Finding Hidden Cliques in Linear Time with High Probability
- Statistical algorithms and a lower bound for detecting planted cliques
- A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Limits of local algorithms over sparse random graphs
- On lattices, learning with errors, random linear codes, and cryptography
