{"id":"W4398886544","doi":"10.4230/lipics.ccc.2024.7","title":"Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy","year":2024,"lang":"en","type":"preprint","venue":"arXiv (Cornell University)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":2,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Fundação para a Ciência e a Tecnologia; European Commission; Natural Sciences and Engineering Research Council of Canada; Engineering and Physical Sciences Research Council; University of Waterloo; UK Research and Innovation; National Science Foundation","keywords":"Degeneracy (biology); Polynomial; Mathematics; Combinatorics; Pure mathematics; Mathematical analysis; Biology","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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.0002002968,0.000354513,0.0003365605,0.0003318676,0.000292523,0.0004964994,0.001251768,0.0002583783,0.000009810009],"category_scores_gemma":[0.00002489121,0.0004038198,0.000297623,0.0004072137,0.0001863736,0.0002542599,0.003733686,0.0005426413,0.00001610982],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0001202852,"about_ca_system_score_gemma":0.0001995517,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001659193,"about_ca_topic_score_gemma":0.00008613993,"domain_scores_codex":[0.9979513,0.00005162391,0.0001954722,0.00130541,0.00008444093,0.0004117755],"domain_scores_gemma":[0.9985408,0.0002034818,0.0001248612,0.0008586427,0.00009981391,0.0001724567],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0002201889,0.0004168158,0.002819431,0.001330768,0.0009878409,0.001586605,0.001806598,0.03319883,0.0004485294,0.8789134,0.02495266,0.05331834],"study_design_scores_gemma":[0.0005287587,0.0001115505,0.000512755,0.0002108182,0.0001363069,0.00001812937,0.00005534888,0.7931241,0.0002632722,0.192181,0.01210765,0.0007502825],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.5113714,0.0006979018,0.4812473,0.0003647686,0.003574459,0.0004663698,0.0001281338,0.0004595287,0.001690065],"genre_scores_gemma":[0.9898942,0.0001520971,0.007299482,0.00009722298,0.0003618794,0.000003206289,0.00001804456,0.00002484183,0.002149038],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.7599253,"threshold_uncertainty_score":0.9998414,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05976760516020513,"score_gpt":0.2013693260096444,"score_spread":0.1416017208494393,"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."}}