{"id":"W4234267841","doi":"10.1002/rsa.20225","title":"Sharp thresholds for constraint satisfaction problems and homomorphisms","year":2008,"lang":"en","type":"article","venue":"Random Structures and Algorithms","topic":"Constraint Satisfaction and Optimization","field":"Computer Science","cited_by":31,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Constraint satisfaction problem; Homomorphism; Constraint satisfaction; Mathematics; Satisfiability; Random graph; Constraint (computer-aided design); Hypergraph; Complexity of constraint satisfaction; Backtracking; Constraint graph; Discrete mathematics; Graph; Binary number; Combinatorics; Local consistency; Mathematical optimization; Statistics; Arithmetic","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.0001286594,0.0001596852,0.0002201051,0.00008394592,0.0003965097,0.0001306315,0.00008597368,0.00008202828,0.00002829283],"category_scores_gemma":[0.00002590434,0.0001333368,0.00005029632,0.00009958062,0.0001900387,0.0003134794,0.00004708815,0.00009440674,6.163061e-7],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00001384867,"about_ca_system_score_gemma":0.0000335508,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00003767593,"about_ca_topic_score_gemma":0.00001587016,"domain_scores_codex":[0.9990672,0.00002663923,0.0002137187,0.0003527708,0.0001447599,0.0001948687],"domain_scores_gemma":[0.9994723,0.0001106017,0.00008774404,0.0001504871,0.00006779077,0.0001110649],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000084926,0.00001666099,0.008414672,0.00007350939,0.0000804626,0.0000156882,0.001579031,0.00102942,0.0008933591,0.08726814,0.0004492506,0.9000949],"study_design_scores_gemma":[0.02720817,0.0005248731,0.3047879,0.00007585963,0.0000720942,0.004914505,0.0001988078,0.5576561,0.001384266,0.09550214,0.006355497,0.00131977],"study_design_candidate":"design_other","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.06678541,0.000487381,0.9308249,0.0005497221,0.0003698271,0.000620906,0.00003162236,0.0001263882,0.0002038016],"genre_scores_gemma":[0.9123018,0.0005570567,0.08679266,0.0001605667,0.00008377222,0.00003588161,0.00001053055,0.000008795943,0.00004888661],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.8987751,"threshold_uncertainty_score":0.5437316,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02129388212381518,"score_gpt":0.2314728767151354,"score_spread":0.2101789945913202,"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."}}