Expected complexity of graph partitioning problems
From MaRDI portal
Recommendations
Cites work
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- Almost all k-colorable graphs are easy to color
- Graphs with small chromatic numbers are easy to color
- scientific article; zbMATH DE number 4213473 (Why is no real title available?)
- scientific article; zbMATH DE number 3608053 (Why is no real title available?)
- On colouring random graphs
- The chromatic number of random graphs
- The greedy coloring is a bad probabilistic algorithm
- The solution of some random NP-hard problems in polynomial expected time
Cited in
(41)- A simple spectral algorithm for recovering planted partitions
- Recovering nonuniform planted partitions via iterated projection
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On the hardness of designing public signals
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Computational barriers in minimax submatrix detection
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- The Ehrenfeucht-Fraïssé method and the planted clique conjecture
- The solution of some random NP-hard problems in polynomial expected time
- scientific article; zbMATH DE number 4043263 (Why is no real title available?)
- Optimal detection of sparse principal components in high dimension
- A nearly tight sum-of-squares lower bound for the planted clique problem
- The forgetfulness of balls and bins
- Comment on ``Hypothesis testing by convex optimization
- The Complexity of Public-Key Cryptography
- Finding a planted clique by adaptive probing
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Finding hidden cliques in linear time with high probability
- Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
- Hardness self-amplification: simplified, optimized, and unified
- Algorithms approaching the threshold for semi-random planted clique
- Cryptography from planted graphs: security with logarithmic-size messages
- How to hide a clique?
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property
- A note on edge-based graph partitioning and its linear algebraic structure
- How to hide a clique?
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- The complexity of explicit constructions
- Low-degree security of the planted random subgraph problem
- Finding planted cliques using gradient descent
- Almost-linear planted cliques elude the Metropolis process
- Random algebraic graphs and their convergence to Erdős-Rényi
- Simple probabilistic analysis to generalize bottleneck graph multi-partitioning
- Is the space complexity of planted clique recovery the same as that of detection?
- Finding planted cycles in a random graph
- Exact recovery of planted cliques in semi-random graphs
- Planted clique recovery in random geometric graphs
- On finding randomly planted cliques in arbitrary graphs
- A note on approximability of densest at-least-k-subgraph
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
This page was built for publication: Expected complexity of graph partitioning problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346695)
