{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.006308025,0.0007220395,0.001554417,0.002536679,0.0009365246,0.004648176,0.001677328,0.00178741,0.004222754],"category_scores_gemma":[0.03989351,0.000854079,0.001759417,0.001458078,0.004564749,0.00748686,0.003745833,0.004558026,0.0003072391],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002772694,"about_ca_system_score_gemma":0.0008836817,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0009824767,"about_ca_topic_score_gemma":0.0007252552,"domain_scores_codex":[0.9942266,0.002038042,0.0004281938,0.0008341483,0.001619421,0.0008534801],"domain_scores_gemma":[0.9473813,0.04079875,0.003965092,0.003210932,0.001913236,0.002730662],"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.0002611699,0.0001092759,0.002613876,0.0001668568,0.00007514367,0.000305683,0.0005790889,0.0493832,0.004507758,0.9343064,0.001260228,0.006431193],"study_design_scores_gemma":[0.00005129741,0.00009072825,0.0009710601,0.00003159588,0.00002226001,0.0002597444,0.0001782455,0.1548621,0.002028523,0.8407093,0.0007593896,0.00003563625],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.5836156,0.001242933,0.393767,0.002496041,0.00007339702,0.0001525041,0.0003961789,0.0006706482,0.01758576],"genre_scores_gemma":[0.977126,0.0002167728,0.02071145,0.0002504046,0.00006206318,0.0001171827,0.000237477,0.00006459873,0.001214155],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.006308025,"threshold_uncertainty_score":0.03336042,"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."}}