{"id":"W1598457899","doi":"10.1145/2540088","title":"Graph Isomorphism is Not AC0-Reducible to Group Isomorphism","year":2013,"lang":"en","type":"article","venue":"ACM Transactions on Computation Theory","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":1,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Nondeterministic algorithm; Upper and lower bounds; Isomorphism (crystallography); Mathematics; Graph isomorphism; Quasigroup; Combinatorics; Discrete mathematics; Bounded function; Group (periodic table); Group isomorphism; Parity (physics); Graph; Automorphism; Automorphism group; Line 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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow","insufficient_payload"],"consensus_categories":[],"category_scores_codex":[0.0004524167,0.0003275465,0.0002868085,0.0006912423,0.000650108,0.0003567763,0.001588216,0.0001208922,0.0008032244],"category_scores_gemma":[0.00003358842,0.0003386855,0.0002487943,0.001380111,0.000145163,0.0008964206,0.00006233762,0.0003792356,0.00194852],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00006823735,"about_ca_system_score_gemma":0.00005008528,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001213172,"about_ca_topic_score_gemma":0.000007288391,"domain_scores_codex":[0.9975102,0.0002408046,0.000449901,0.0008121462,0.000514151,0.0004728063],"domain_scores_gemma":[0.9974416,0.0006744619,0.0001150005,0.001254676,0.0002178183,0.0002964092],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.00004731842,0.0006354603,0.000006329607,0.00002281833,0.0001310925,0.00000889794,0.003335641,0.009674122,0.002073959,0.152705,0.005461391,0.825898],"study_design_scores_gemma":[0.0009691716,0.0005266464,0.001731584,0.0000681064,0.00003270117,0.00005434944,0.0002250215,0.04354226,0.008327588,0.9398653,0.003892917,0.0007643589],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.01123037,0.00003893842,0.9747881,0.0108868,0.00132649,0.0006157247,0.00002665432,0.0005500634,0.0005369022],"genre_scores_gemma":[0.7651397,0.0000204157,0.222965,0.01065383,0.00008078548,0.0002051624,0.000009548147,0.00003363609,0.0008919344],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.8251336,"threshold_uncertainty_score":0.9999065,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02684005737958888,"score_gpt":0.2585651682899363,"score_spread":0.2317251109103474,"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."}}