Pages that link to "Item:Q2012245"
From MaRDI portal
The following pages link to Local algorithms for independent sets are half-optimal (Q2012245):
Displaying 44 items.
- Finding one community in a sparse graph (Q892403) (← links)
- Spectral measures of factor of i.i.d. processes on vertex-transitive graphs (Q1700413) (← links)
- Entropy and expansion (Q2028943) (← links)
- The overlap gap property in principal submatrix recovery (Q2067659) (← links)
- Ising model on trees and factors of IID (Q2071790) (← links)
- Minimum 2-dominating sets in regular graphs (Q2091810) (← links)
- Optimal low-degree hardness of maximum independent set (Q2113266) (← links)
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition (Q2131259) (← links)
- Total domination in regular graphs (Q2132388) (← links)
- Computational barriers to estimation from low-degree polynomials (Q2149001) (← links)
- The overlap gap property and approximate message passing algorithms for \(p\)-spin models (Q2227713) (← links)
- Entropy inequalities for factors of IID (Q2319838) (← links)
- Energy landscape for large average submatrix detection problems in Gaussian random matrices (Q2363657) (← links)
- Suboptimality of local algorithms for a class of max-cut problems (Q2421823) (← links)
- On the almost eigenvectors of random regular graphs (Q2421826) (← links)
- Asymptotic bounds on total domination in regular graphs (Q2659200) (← links)
- Improved replica bounds for the independence ratio of random regular graphs (Q2687694) (← links)
- A tale of two balloons (Q2689430) (← links)
- Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem (Q2968165) (← links)
- Optimal Randomized Algorithms for Local Sorting and Set-Maxima (Q4032937) (← links)
- Correlation Bounds for Distant Parts of Factor of IID Processes (Q4601049) (← links)
- Sofic homological invariants and the Weak Pinsker Property (Q5024867) (← links)
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs (Q5157395) (← links)
- Mutual information decay for factors of i.i.d. (Q5235118) (← links)
- Walksat Stalls Well Below Satisfiability (Q5267998) (← links)
- Factor of IID Percolation on Trees (Q5298168) (← links)
- Brief Announcement (Q5361922) (← links)
- Colouring graphs with forbidden bipartite subgraphs (Q5885184) (← links)
- Simple and local independent set approximation (Q5915922) (← links)
- Local approximation of the maximum cut in regular graphs (Q5918122) (← links)
- The largest hole in sparse random graphs (Q6052472) (← links)
- A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels (Q6068420) (← links)
- Free Energy Wells and Overlap Gap Property in Sparse PCA (Q6074556) (← links)
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks (Q6098526) (← links)
- Algorithmic obstructions in the random number partitioning problem (Q6139686) (← links)
- Borel fractional colorings of Schreier graphs (Q6159728) (← links)
- Shattering versus metastability in spin glasses (Q6180708) (← links)
- Optimizing mean field spin glasses with external field (Q6186448) (← links)
- Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics (Q6203476) (← links)
- Greedy maximal independent sets via local limits (Q6541390) (← links)
- Cryptography from planted graphs: security with logarithmic-size messages (Q6581792) (← links)
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property (Q6616866) (← links)
- On perfectly friendly bisections of random graphs (Q6634425) (← links)
- Tight Lipschitz hardness for optimizing mean field spin glasses (Q6641018) (← links)
