Pith. sign in

REVIEW 1 cited by

Large independent sets on random $d$-regular graphs with fixed degree $d$

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2003.12293 v2 pith:OGKC32P5 submitted 2020-03-27 cs.DS

Raffaele Marino , Scott Kirkpatrick This is my paper · ORCID
classification cs.DS
keywords algorithmboundsdegreefixedindependentlargelowerrandom
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

This paper presents a linear prioritized local algorithm that computes large independent sets on a random $d$-regular graph with small and fixed degree $d$. We studied experimentally the independence ratio obtained by the algorithm when $ d \in [3,100]$. For all $d \in [5,100]$, our results are larger than lower bounds calculated by exact methods, thus providing improved estimates of lower bounds.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum-informed surrogate sampling for combinatorial optimization

    quant-ph 2026-07 conditional novelty 6.0 of 10

    QISS classically samples a pairwise model built from O(N) low-weight QAOA correlators and outperforms standard QAOA at larger depths on MaxCut and MIS benchmarks.

Pith tools