{"id":"W1532975866","doi":"10.1214/16-aop1094","title":"Local algorithms for independent sets are half-optimal","year":2017,"lang":"en","type":"article","venue":"The Annals of Probability","topic":"Limits and Structures in Graph Theory","field":"Mathematics","cited_by":85,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Mathematics; Combinatorics; Asymptotically optimal algorithm; Infinity; Discrete mathematics; Upper and lower bounds; Random graph; Poisson distribution; Tree (set theory); Algorithm; Statistics; Graph","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.003991961,0.001152207,0.002630126,0.001699981,0.001571894,0.003413984,0.004077737,0.002339198,0.01349183],"category_scores_gemma":[0.03511929,0.0009210882,0.001651338,0.002220309,0.002894571,0.01027629,0.004618049,0.003389928,0.003391506],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002942835,"about_ca_system_score_gemma":0.001896161,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0007937438,"about_ca_topic_score_gemma":0.001320122,"domain_scores_codex":[0.9963657,0.0009910297,0.0001942896,0.001189207,0.0008211014,0.0004386162],"domain_scores_gemma":[0.9749415,0.01623919,0.001562258,0.005154641,0.001128329,0.0009741643],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0008877598,0.0005383707,0.003467032,0.001227273,0.0002987486,0.0001175396,0.000625335,0.1568268,0.006798384,0.6758713,0.01518095,0.1381604],"study_design_scores_gemma":[0.0001542227,0.0002053343,0.0009110874,0.0001277813,0.00011011,0.0002212021,0.0001542886,0.3977693,0.005359905,0.5895891,0.005350666,0.000046977],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2293375,0.003319386,0.7135841,0.002737573,0.0001564059,0.0003390836,0.0008910953,0.003112335,0.04652247],"genre_scores_gemma":[0.8342757,0.001655431,0.1474501,0.0009742639,0.0003005307,0.0009172889,0.001216995,0.000873382,0.0123362],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01349183,"threshold_uncertainty_score":0.04513472,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.2213734033283845,"score_gpt":0.4079639967249845,"score_spread":0.1865905933966001,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}