{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002118568,0.0008281451,0.001370906,0.002728161,0.001165743,0.001453122,0.0028572,0.001670405,0.005766219],"category_scores_gemma":[0.01730318,0.0007734277,0.001578179,0.00170053,0.002686513,0.006112031,0.003154515,0.002656335,0.0009592862],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002226359,"about_ca_system_score_gemma":0.001138695,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002165165,"about_ca_topic_score_gemma":0.001929677,"domain_scores_codex":[0.9981726,0.0004506955,0.00005076334,0.0005532228,0.0004940892,0.0002785266],"domain_scores_gemma":[0.9912149,0.004223936,0.001003107,0.002206093,0.0008033845,0.0005485748],"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.0001718607,0.0001185616,0.00277993,0.000174707,0.00009153837,0.0003094466,0.0004322763,0.2377785,0.007284858,0.713137,0.004139692,0.03358162],"study_design_scores_gemma":[0.00001256343,0.0000441906,0.0004962854,0.00001074924,0.00001777101,0.0001028583,0.00004277581,0.6596676,0.001655046,0.3359901,0.001936828,0.00002319443],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.06429873,0.0002923013,0.9284319,0.0004021201,0.00003700623,0.00005250078,0.0001488292,0.0008110411,0.005525503],"genre_scores_gemma":[0.8297811,0.0005383058,0.1599444,0.0003581744,0.000212661,0.0002622425,0.0005565583,0.0004685056,0.007878087],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.005766219,"threshold_uncertainty_score":0.01928991,"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."}}