On the public citation graph

On independent sets in random graphs

0 signed · 94 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-zopenalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-wopenalex-snapshot
Finding a large hidden clique in a random graph
inferredcites →https://doi.org/10.1002/(sici)1098-2418(200003)16:2<195::aid-rsa5>3.0.co;2-aopenalex-snapshot
Finding and certifying a large hidden clique in a semirandom graph
inferredcites →https://doi.org/10.1002/9781118032718openalex-snapshot
Random Graphs
inferredcites →https://doi.org/10.1002/rsa.20072openalex-snapshot
Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
inferredcites →https://doi.org/10.1002/rsa.3240030402openalex-snapshot
Large Cliques Elude the Metropolis Process
inferredcites →https://doi.org/10.1006/jagm.1996.0016openalex-snapshot
Analysis of Two Simple Heuristics on a Random Instance ofk-sat
inferredcites →https://doi.org/10.1007/3-540-08442-8_114openalex-snapshot
Expected Behavior of Graph Coloring Algorithms
inferredcites →https://doi.org/10.1007/978-3-540-27821-4_32openalex-snapshot
Maximum Weight Independent Sets and Matchings in Sparse Random Graphs
inferredcites →https://doi.org/10.1007/978-3-642-15369-3_33openalex-snapshot
Reconstruction Threshold for the Hardcore Model
inferredcites →https://doi.org/10.1007/978-3-642-22935-0_40openalex-snapshot
Independent Sets in Random Graphs from the Weighted Second Moment Method
inferredcites →https://doi.org/10.1007/bf02699376openalex-snapshot
Concentration of measure and isoperimetric inequalities in product spaces
inferredcites →https://doi.org/10.1007/s00039-014-0258-7openalex-snapshot
Limits of locally–globally convergent graph sequences
inferredcites →https://doi.org/10.1007/s10208-014-9215-yopenalex-snapshot
Finding Hidden Cliques of Size $$\sqrt{N/e}$$ N / e in Nearly Linear Time
inferredcites →https://doi.org/10.1007/s10955-011-0336-2openalex-snapshot
Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs
inferredcites →https://doi.org/10.1007/s11511-017-0145-9openalex-snapshot
Maximum independent sets on random regular graphs
inferredcites →https://doi.org/10.1016/0012-365x(90)90149-copenalex-snapshot
On the independence number of random graphs
inferredcites →https://doi.org/10.1016/0020-0190(84)90013-9openalex-snapshot
Backtrack: An O(1) expected time algorithm for the graph coloring problem
inferredcites →https://doi.org/10.1016/0020-0190(89)90200-7openalex-snapshot
Graphs with small chromatic numbers are easy to color
inferredcites →https://doi.org/10.1016/0196-6774(88)90005-3openalex-snapshot
Almost all k-colorable graphs are easy to color
inferredcites →https://doi.org/10.1016/0196-6774(89)90001-1openalex-snapshot
The solution of some random NP-hard problems in polynomial expected time
inferredcites →https://doi.org/10.1017/cbo9780511814075openalex-snapshot
Randomized Algorithms
inferredcites →https://doi.org/10.1017/s0305004100051124openalex-snapshot
On colouring random graphs
inferredcites →https://doi.org/10.1017/s0305004100053056openalex-snapshot
Cliques in random graphs
inferredcites →https://doi.org/10.1017/s0963548306007553openalex-snapshot
Finding Large Independent Sets in Polynomial Expected Time
inferredcites →https://doi.org/10.1063/1.1699114openalex-snapshot
Equation of State Calculations by Fast Computing Machines
inferredcites →https://doi.org/10.1073/pnas.0703685104openalex-snapshot
Gibbs states and the set of solutions of random constraint satisfaction problems
inferredcites →https://doi.org/10.1088/0305-4470/19/9/033openalex-snapshot
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
inferredcites →https://doi.org/10.1088/1742-6596/473/1/012021openalex-snapshot
The hard-core model on random graphs revisited
inferredcites →https://doi.org/10.1090/s0002-9904-1947-08785-1openalex-snapshot
Some remarks on the theory of graphs
inferredcites →https://doi.org/10.1093/acprof:oso/9780198570837.001.0001openalex-snapshot
Information, Physics, and Computation
inferredcites →https://doi.org/10.1103/physrevlett.88.025501openalex-snapshot
Lattice Glass Models
inferredcites →https://doi.org/10.1109/focs.2010.26openalex-snapshot
The Monotone Complexity of k-clique on Random Graphs
inferredcites →https://doi.org/10.1109/sfcs.1981.21openalex-snapshot
Maximum matching in sparse random graphs
inferredcites →https://doi.org/10.1109/sfcs.1997.646109openalex-snapshot
The analysis of a list-coloring algorithm on a random graph
inferredcites →https://doi.org/10.1126/science.1073287openalex-snapshot
Analytic and Algorithmic Solution of Random Satisfiability Problems
inferredcites →https://doi.org/10.1126/science.220.4598.671openalex-snapshot
Optimization by Simulated Annealing
inferredcites →https://doi.org/10.1137/090755862openalex-snapshot
Reconstruction and Clustering in Random Constraint Satisfaction Problems
inferredcites →https://doi.org/10.1137/1.9781611973082.12openalex-snapshot
On independent sets in random graphs
inferredcites →https://doi.org/10.1137/110839059openalex-snapshot
The Monotone Complexity of $k$-Clique on Random Graphs
inferredcites →https://doi.org/10.1137/s0097539701383844openalex-snapshot
On Counting Independent Sets in Sparse Graphs
inferredcites →https://doi.org/10.1145/2554797.2554831openalex-snapshot
Limits of local algorithms over sparse random graphs
inferredcites →https://doi.org/10.48550/arxiv.1004.3531openalex-snapshot
Reconstruction Threshold for the Hardcore Model
inferredcites →https://doi.org/10.48550/arxiv.1205.4356openalex-snapshot
Limits of local-global convergent graph sequences
inferredcites →https://doi.org/10.48550/arxiv.1304.7047openalex-snapshot
Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
inferredcites →https://doi.org/10.5555/251040.251043openalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.82444/warw.33656476openalex-snapshot
On independent sets in random graphs

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/cpa.22222openalex-snapshot
Tight Lipschitz hardness for optimizing mean field spin glasses
inferred← citeshttps://doi.org/10.1002/jgt.23225openalex-snapshot
Independent Sets of Random Trees and Sparse Random Graphs
inferred← citeshttps://doi.org/10.1002/rsa.21078openalex-snapshot
The largest hole in sparse random graphs
inferred← citeshttps://doi.org/10.1002/rsa.70044openalex-snapshot
Counting Independent Sets in Percolated Graphs via the Ising Model
inferred← citeshttps://doi.org/10.1007/978-3-030-83823-2_8openalex-snapshot
The Largest Hole in Sparse Random Graphs
inferred← citeshttps://doi.org/10.1007/978-3-031-48615-9_11openalex-snapshot
Cryptography from Planted Graphs: Security with Logarithmic-Size Messages
inferred← citeshttps://doi.org/10.1007/978-3-031-59205-8_3openalex-snapshot
A Simple Model of Influence: Details and Variants of Dynamics
inferred← citeshttps://doi.org/10.1007/s10955-016-1583-zopenalex-snapshot
Generalized Random Sequential Adsorption on Erdős–Rényi Random Graphs
inferred← citeshttps://doi.org/10.1016/j.ins.2016.08.053openalex-snapshot
An efficient local search framework for the minimum weighted vertex cover problem
inferred← citeshttps://doi.org/10.1016/j.jestch.2025.101995openalex-snapshot
A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm
inferred← citeshttps://doi.org/10.1017/fms.2024.6openalex-snapshot
Two-Point Concentration of the Independence Number of the Random Graph
inferred← citeshttps://doi.org/10.1017/s147474802510100xopenalex-snapshot
ALGEBRAIC DYNAMICAL SYSTEMS FROM LDPC CODES SATISFY A STRONG NEGATION OF THE WEAK PINSKER PROPERTY
inferred← citeshttps://doi.org/10.1038/s42005-024-01711-9openalex-snapshot
Message passing variational autoregressive network for solving intractable Ising models
inferred← citeshttps://doi.org/10.1038/s42256-022-00589-yopenalex-snapshot
Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
inferred← citeshttps://doi.org/10.1088/0256-307x/38/3/030304openalex-snapshot
Quantum Algorithm for Approximating Maximum Independent Sets
inferred← citeshttps://doi.org/10.1088/1742-5468/ab409dopenalex-snapshot
Constructing concrete hard instances of the maximum independent set problem
inferred← citeshttps://doi.org/10.1103/physreva.101.012318openalex-snapshot
Quantum independent-set problem and non-Abelian adiabatic mixing
inferred← citeshttps://doi.org/10.1103/physreve.100.013302openalex-snapshot
Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
inferred← citeshttps://doi.org/10.1103/physreve.94.022146openalex-snapshot
Spin-glass phase transitions and minimum energy of the random feedback vertex set problem
inferred← citeshttps://doi.org/10.1109/focs.2019.00078openalex-snapshot
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00038openalex-snapshot
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00048openalex-snapshot
Sum-of-Squares Lower Bounds for Sparse Independent Set
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00037openalex-snapshot
Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00061openalex-snapshot
Algorithms and Barriers in the Symmetric Binary Perceptron Model
inferred← citeshttps://doi.org/10.1109/isit50566.2022.9834647openalex-snapshot
The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers
inferred← citeshttps://doi.org/10.1137/20m1316044openalex-snapshot
The Average-Case Complexity of Counting Cliques in Erdoős–Reényi Hypergraphs
inferred← citeshttps://doi.org/10.1137/25m1805564openalex-snapshot
Some Recent Developments in Structural Ergodic Theory
inferred← citeshttps://doi.org/10.1145/3034781openalex-snapshot
The Freezing Threshold for k -Colourings of a Random Graph
inferred← citeshttps://doi.org/10.1145/3618260.3649703openalex-snapshot
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
inferred← citeshttps://doi.org/10.1214/16-aop1094openalex-snapshot
Local algorithms for independent sets are half-optimal
inferred← citeshttps://doi.org/10.1214/23-aap1953openalex-snapshot
Algorithmic obstructions in the random number partitioning problem
inferred← citeshttps://doi.org/10.1287/moor.2022.0215openalex-snapshot
Large Independent Sets in Recursive Markov Random Graphs
inferred← citeshttps://doi.org/10.1353/ajm.2022.0003openalex-snapshot
Sofic homological invariants and the Weak Pinsker Property
inferred← citeshttps://doi.org/10.21203/rs.3.rs-8969943/v1openalex-snapshot
Phase-Transition Structure as Foundation for Cryptographic Hardness
inferred← citeshttps://doi.org/10.21248/gups.68926openalex-snapshot
On the evidence for a statistical-computational gap raised by the Group Testing Problem
inferred← citeshttps://doi.org/10.22331/q-2025-10-22-1892openalex-snapshot
Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
inferred← citeshttps://doi.org/10.4171/msl/25openalex-snapshot
Optimal low-degree hardness of maximum independent set
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2022.57openalex-snapshot
On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs
inferred← citeshttps://doi.org/10.48550/arxiv.1512.04462openalex-snapshot
On the replica symmetry phase of the independent set problem
inferred← citeshttps://doi.org/10.48550/arxiv.1601.02658openalex-snapshot
Information-theoretic thresholds for community detection in sparse networks
inferred← citeshttps://doi.org/10.48550/arxiv.1810.09666openalex-snapshot
Online learning with feedback graphs and switching costs
inferred← citeshttps://doi.org/10.48550/arxiv.2004.07151openalex-snapshot
An algorithmic framework for colouring locally sparse graphs
inferred← citeshttps://doi.org/10.48550/arxiv.2006.04756openalex-snapshot
Independent Sets of Random Trees and of Sparse Random Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.2102.09289openalex-snapshot
Note on induced paths in sparse random graphs
inferred← citeshttps://doi.org/10.70675/cae60fe0z49d9z4c30za6f1z76158ca58aa5openalex-snapshot
Coloration de graphes épars
inferred← citeshttps://doi.org/10.70675/d8d31cecza123z48adz86b7ze8a30aaa7c58openalex-snapshot
Quantum many-body dynamics for combinatorial optimisation and machine learning
inferred← citeshttps://doi.org/10.7151/dmgt.2317openalex-snapshot
New results relating inependence and matchings
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.