{"id":"W7109976180","doi":"10.4230/lipics.icalp.2025.135","title":"Deterministic Independent Sets in the Semi-Streaming Model","year":2025,"lang":"en","type":"article","venue":"DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Independent set; Randomized algorithm; Set (abstract data type); Deterministic algorithm; Graph; Simple (philosophy)","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.004261459,0.001195477,0.002286315,0.001076239,0.001316121,0.00287639,0.003896271,0.002021954,0.004951074],"category_scores_gemma":[0.01700118,0.0009235832,0.001984756,0.002402146,0.002743986,0.008872391,0.003106022,0.003845337,0.001125478],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002298613,"about_ca_system_score_gemma":0.001723635,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001824868,"about_ca_topic_score_gemma":0.001545259,"domain_scores_codex":[0.9937224,0.002215863,0.0003478753,0.001609044,0.001403632,0.0007011209],"domain_scores_gemma":[0.9760342,0.0157548,0.001674875,0.004379739,0.001252425,0.0009039567],"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.0007783044,0.0003199886,0.001587129,0.0005036092,0.0001680281,0.0004455582,0.0003798818,0.3715225,0.006489112,0.5728782,0.007861203,0.03706645],"study_design_scores_gemma":[0.00006895843,0.00008176007,0.0002224327,0.0000184993,0.00002547127,0.0001789941,0.00004261557,0.6335657,0.001507361,0.3618117,0.002451068,0.00002549351],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.06359271,0.0008298439,0.9247036,0.002165687,0.0001401828,0.0002434755,0.001126833,0.0006913982,0.006506306],"genre_scores_gemma":[0.6918467,0.001596671,0.2915401,0.0008566409,0.0006988238,0.0007210177,0.00222228,0.0002900641,0.01022759],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.004951074,"threshold_uncertainty_score":0.02253705,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02115686329120265,"score_gpt":0.2862342634690988,"score_spread":0.2650774001778962,"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."}}