{"id":"W1980190601","doi":"10.1145/1721837.1721842","title":"Comparison-based time-space lower bounds for selection","year":2010,"lang":"en","type":"article","venue":"ACM Transactions on Algorithms","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":42,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"","keywords":"Upper and lower bounds; Binary logarithm; Mathematics; Combinatorics; Log-log plot; Streaming algorithm; Running time; Space (punctuation); Mathematical proof; Selection (genetic algorithm); Discrete mathematics; Randomized algorithm; Deterministic algorithm; Time complexity; Algorithm; Computer science","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.01063844,0.003665762,0.004645961,0.003003168,0.003948686,0.008690389,0.008493712,0.004247738,0.02652756],"category_scores_gemma":[0.05833688,0.001953393,0.004831475,0.006526199,0.006574535,0.03367518,0.009762943,0.01159238,0.005346808],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.007550335,"about_ca_system_score_gemma":0.006010574,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001968152,"about_ca_topic_score_gemma":0.002315704,"domain_scores_codex":[0.9788291,0.004733439,0.000961372,0.004519468,0.006297282,0.004659244],"domain_scores_gemma":[0.8934503,0.08047304,0.005316256,0.01422699,0.003861266,0.002672148],"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.004937831,0.001581663,0.007687297,0.001990397,0.0004400612,0.0005660555,0.001106306,0.2530101,0.02788321,0.4696181,0.03448113,0.1966978],"study_design_scores_gemma":[0.0003552492,0.0007681978,0.001529279,0.0001904554,0.0002878627,0.0006748633,0.0002601979,0.46524,0.01570187,0.5023503,0.01251858,0.0001230619],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.07369122,0.006154881,0.8527517,0.01026867,0.0006889009,0.0005151188,0.001403165,0.003828711,0.05069763],"genre_scores_gemma":[0.6776325,0.00388163,0.2808081,0.003990192,0.00282518,0.002007572,0.002093577,0.003462176,0.02329905],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.02652756,"threshold_uncertainty_score":0.08874351,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02494796243462718,"score_gpt":0.2988886896203971,"score_spread":0.2739407271857699,"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."}}