{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.005493077,0.00386884,0.00362598,0.002367923,0.003499209,0.005743394,0.009068414,0.003992842,0.02245556],"category_scores_gemma":[0.0424506,0.001542882,0.004507278,0.003641733,0.00563192,0.029031,0.009604502,0.01810498,0.007179621],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005289351,"about_ca_system_score_gemma":0.004652316,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.004025712,"about_ca_topic_score_gemma":0.004591459,"domain_scores_codex":[0.9913931,0.001316533,0.000361131,0.001768972,0.003059828,0.002100416],"domain_scores_gemma":[0.9492093,0.03285301,0.002272428,0.01015615,0.00313995,0.002369152],"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.002898186,0.001322939,0.007011754,0.002266714,0.0003623889,0.0008165421,0.001992534,0.1265099,0.02021329,0.6441796,0.05548935,0.1369367],"study_design_scores_gemma":[0.0001530243,0.0003153268,0.00139424,0.0002330374,0.0002022344,0.000450513,0.0003890233,0.3341126,0.009615807,0.6373822,0.0156615,0.00009037461],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1288044,0.006412853,0.7399178,0.01669951,0.0008755059,0.0005723223,0.003181325,0.006417688,0.09711879],"genre_scores_gemma":[0.7034613,0.005107214,0.2353636,0.00460759,0.002013041,0.001305636,0.004376592,0.004365171,0.03939981],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.02245556,"threshold_uncertainty_score":0.07512128,"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."}}