{"id":"W1480046334","doi":"10.5555/1496770.1496810","title":"Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures","year":2009,"lang":"en","type":"article","venue":"","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":15,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Tree (set theory); Rank (graph theory); Combinatorics; Mathematics; Satisfiability; Upper and lower bounds; Argument (complex analysis); Discrete mathematics; Exponential function","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.006313362,0.001221771,0.001243291,0.001634736,0.001762427,0.004687236,0.004201049,0.002023403,0.01519451],"category_scores_gemma":[0.0459591,0.001322972,0.002835545,0.001667305,0.004511379,0.0140092,0.005331118,0.007665327,0.002184889],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005186282,"about_ca_system_score_gemma":0.00354263,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001626026,"about_ca_topic_score_gemma":0.003087733,"domain_scores_codex":[0.9923509,0.002257712,0.0003951198,0.001165211,0.002444572,0.001386409],"domain_scores_gemma":[0.9371778,0.05055245,0.00228018,0.006646485,0.002224565,0.001118532],"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.00085411,0.000533386,0.002697976,0.0007136888,0.0001429942,0.0002646002,0.0008734087,0.1243004,0.01305266,0.7706782,0.007442626,0.07844598],"study_design_scores_gemma":[0.0001081505,0.000163383,0.000533734,0.0001295174,0.0001097047,0.0001743994,0.0001686904,0.3304003,0.01655055,0.6460201,0.005584384,0.00005708069],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1866695,0.001550795,0.7357081,0.006106771,0.0002213307,0.0005343609,0.0009664461,0.003397083,0.06484553],"genre_scores_gemma":[0.6645664,0.001138382,0.3154582,0.001611467,0.0002168655,0.0005989316,0.001483903,0.001735921,0.01318991],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01519451,"threshold_uncertainty_score":0.05083066,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01715841394339383,"score_gpt":0.2630786820417941,"score_spread":0.2459202680984003,"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."}}