{"id":"W2949591167","doi":"10.1137/1.9781611973082.52","title":"The Local Lemma is Tight for SAT","year":2011,"lang":"en","type":"preprint","venue":"","topic":"Constraint Satisfaction and Optimization","field":"Computer Science","cited_by":16,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Mathematics; Lemma (botany); Combinatorics; Variable (mathematics); Function (biology); Discrete mathematics; Binary tree; Class (philosophy); Binary number; Discretization; Upper and lower bounds; Order (exchange); Mathematical analysis; Computer science; 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.005212463,0.001512266,0.002966016,0.002653713,0.002777787,0.005600277,0.00497911,0.002059158,0.02453787],"category_scores_gemma":[0.0295464,0.00157259,0.003405399,0.003746216,0.004157965,0.01550229,0.007325049,0.01146847,0.005907066],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.004144928,"about_ca_system_score_gemma":0.002238227,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.004301762,"about_ca_topic_score_gemma":0.005988116,"domain_scores_codex":[0.9921672,0.001485872,0.0004167343,0.002349753,0.002026399,0.001554063],"domain_scores_gemma":[0.9688208,0.02073762,0.001217977,0.006364554,0.0022423,0.0006168546],"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.0006240032,0.0002612016,0.003700072,0.001176877,0.0002559095,0.0005021585,0.000621615,0.04913633,0.008360963,0.82035,0.02888215,0.08612869],"study_design_scores_gemma":[0.00009287066,0.0001763337,0.00179941,0.0002531263,0.0001810736,0.0006548231,0.0001863557,0.1404032,0.00979422,0.8202525,0.02612507,0.00008100067],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.02705137,0.00195928,0.9145121,0.004434226,0.0002441831,0.0001419706,0.001427781,0.003813967,0.04641509],"genre_scores_gemma":[0.6661153,0.002319636,0.294431,0.007523905,0.001020861,0.001073585,0.004160841,0.002968641,0.02038625],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.02453787,"threshold_uncertainty_score":0.08208734,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03308395663944832,"score_gpt":0.254220605228909,"score_spread":0.2211366485894607,"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."}}