Constructing concrete hard instances of the maximum independent set problem

DOI10.1088/1742-5468/ab409dzbMath1456.68134arXiv1807.03739OpenAlexW3098383736MaRDI QIDQ5149679

Publication date: 12 February 2021

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.03739

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
More on average case vs approximation complexity
Spectra of graphs
Random constraint satisfaction: easy generation of hard (satisfiable) instances
The asymptotic distribution of short cycles in random regular graphs
Differential equations for random processes and random graphs
The resolution complexity of independent sets and vertex covers in random graphs
Proof of the Satisfiability Conjecture for Large k
Critical Behavior in the Satisfiability of Random Boolean Expressions
Typical performance of approximation algorithms for NP-hard problems
The large deviations of the whitening process in random constraint satisfaction problems
On independent sets in random graphs
Expander graphs and their applications
Average-Case Complexity
Relations between average case complexity and approximation complexity
Information, Physics, and Computation
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
Determining the Stability Number of a Graph
Sharp thresholds of graph properties, and the $k$-sat problem
On the independence number of random cubic graphs
The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
Sum of squares lower bounds for refuting any CSP
Number Theory
The threshold for SDP-refutation of random regular NAE-3SAT
From average case complexity to improper learning complexity
Computational Complexity
Determining computational complexity from characteristic ‘phase transitions’
Gibbs states and the set of solutions of random constraint satisfaction problems
Phase Transitions in Combinatorial Optimization Problems
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
On the solution-space geometry of random constraint satisfaction problems
On lattices, learning with errors, random linear codes, and cryptography
Limits of local algorithms over sparse random graphs

This page was built for publication: Constructing concrete hard instances of the maximum independent set problem