{"id":"W4409748157","doi":"10.1214/25-aap2146","title":"Average-case and smoothed analysis of graph isomorphism","year":2025,"lang":"en","type":"article","venue":"The Annals of Applied Probability","topic":"Graph Theory and Algorithms","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"Science North","funders":"","keywords":"Isomorphism (crystallography); Graph isomorphism; Graph; Mathematics; Combinatorics; Computer science; Chemistry; Crystallography; Line graph","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001727571,0.0001162288,0.0003616573,0.0002296511,0.0001112751,0.00002360579,0.0005931698,0.00004704359,0.00001319642],"category_scores_gemma":[0.00003521044,0.00008005935,0.000178322,0.001887517,0.0004174936,0.00007585103,0.0002587428,0.0000974654,6.618242e-7],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0000026857,"about_ca_system_score_gemma":0.00002681469,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0000325046,"about_ca_topic_score_gemma":0.00001022543,"domain_scores_codex":[0.9989212,0.0001160624,0.0003494413,0.000312917,0.0001386944,0.0001617285],"domain_scores_gemma":[0.9983537,0.0003372492,0.0001640691,0.0009838573,0.0001216559,0.00003944567],"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.00008232894,0.0001863392,0.0004186959,0.00007773242,0.0006288783,0.000003773247,0.001307709,0.001356336,0.0007872785,0.970788,0.00004888728,0.02431405],"study_design_scores_gemma":[0.0001756281,0.00003448668,0.006265617,0.000007867611,0.0001369861,0.000002650491,0.00004626584,0.007984705,0.01526188,0.9699308,0.00006474418,0.00008840902],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.9051888,0.0001588588,0.0898414,0.001243378,0.0000375525,0.0003481821,0.00001800737,0.00003967914,0.003124119],"genre_scores_gemma":[0.9963542,0.0000200844,0.003240715,0.0003404581,0.000003355233,0.00001777497,0.000001078139,0.000002084453,0.00002031263],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.09116531,"threshold_uncertainty_score":0.3264725,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03725254636150752,"score_gpt":0.2841761287804059,"score_spread":0.2469235824188984,"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."}}