{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002018458,0.0009259291,0.001148996,0.001078474,0.002207609,0.004209945,0.002399096,0.001826092,0.01154301],"category_scores_gemma":[0.01080487,0.000893698,0.002940537,0.001399216,0.003404285,0.009514596,0.004572121,0.006296098,0.00150385],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002943672,"about_ca_system_score_gemma":0.003008246,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003066269,"about_ca_topic_score_gemma":0.003560595,"domain_scores_codex":[0.9951261,0.000783511,0.0003038019,0.00112819,0.00149246,0.00116582],"domain_scores_gemma":[0.980746,0.011329,0.0009653561,0.005141194,0.001197948,0.000620575],"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.001184282,0.0007951324,0.004866862,0.001007818,0.0001948356,0.0007478555,0.0008771123,0.06570696,0.01860105,0.7951568,0.02186597,0.0889953],"study_design_scores_gemma":[0.0001091106,0.0001548194,0.0008548257,0.00004372779,0.000154466,0.0004377743,0.0001956724,0.08747629,0.01756307,0.8824291,0.01053196,0.00004905577],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.4559388,0.0008636385,0.4116639,0.008029073,0.0005835519,0.0005103652,0.001642956,0.005639066,0.1151286],"genre_scores_gemma":[0.9054968,0.0003841732,0.07260496,0.001598098,0.0003448673,0.0002770843,0.001873386,0.0007009729,0.01671956],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.01154301,"threshold_uncertainty_score":0.03861523,"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."}}