{"id":"W2016263640","doi":"10.1145/2635822","title":"The complexity of the comparator circuit value problem","year":2014,"lang":"en","type":"article","venue":"ACM Transactions on Computation Theory","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":11,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"Seventh Framework Programme; Natural Sciences and Engineering Research Council of Canada","keywords":"Mathematics; Complexity class; Combinatorics; Bipartite graph; Conjecture; Discrete mathematics; Class (philosophy); P; Comparator; Oracle; Time complexity; Graph; Computer science","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.001822719,0.0007250195,0.001323324,0.001144558,0.001768705,0.006149995,0.002573702,0.002906965,0.01181619],"category_scores_gemma":[0.01815467,0.0006993582,0.002230217,0.002078408,0.002993708,0.0149256,0.003241522,0.005090623,0.0007087886],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.004397884,"about_ca_system_score_gemma":0.002445158,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003168469,"about_ca_topic_score_gemma":0.001631569,"domain_scores_codex":[0.9954162,0.0009745234,0.0002496397,0.001125515,0.001416632,0.0008175331],"domain_scores_gemma":[0.9821713,0.014742,0.0008169035,0.001176466,0.0006099254,0.0004834987],"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.0007122831,0.0003540334,0.00531233,0.0009088241,0.000199476,0.0004741583,0.0009703915,0.1088729,0.004335177,0.7898402,0.01765821,0.07036205],"study_design_scores_gemma":[0.0001073539,0.00005935162,0.0014044,0.00005169133,0.00004812481,0.0003248668,0.0002185287,0.1361396,0.002540591,0.8514711,0.007594892,0.00003947676],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.5095769,0.003676116,0.3798861,0.02204103,0.0003089885,0.0006872402,0.007240451,0.001734725,0.07484847],"genre_scores_gemma":[0.9254757,0.001438225,0.05651293,0.001036025,0.0004812808,0.0005377944,0.004123434,0.000297996,0.01009666],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.01181619,"threshold_uncertainty_score":0.03952903,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.04217450054507668,"score_gpt":0.2620574507414464,"score_spread":0.2198829501963697,"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."}}