{"id":"W2952920300","doi":"10.1145/3013516","title":"Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method","year":2016,"lang":"en","type":"article","venue":"ACM Transactions on Computation Theory","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":2,"is_retracted":false,"has_abstract":true,"ca_institutions":"Université de Montréal","funders":"National Science Foundation","keywords":"Nondeterministic algorithm; Upper and lower bounds; Sublinear function; Branching (polymer chemistry); Computation; Boolean 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.00608315,0.001878739,0.001510119,0.002865084,0.001815926,0.004122657,0.0060297,0.002355312,0.01111436],"category_scores_gemma":[0.01696499,0.001227543,0.002647982,0.002888125,0.003854058,0.008675925,0.00492866,0.01037613,0.002598213],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.004509557,"about_ca_system_score_gemma":0.002352523,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001705636,"about_ca_topic_score_gemma":0.00175434,"domain_scores_codex":[0.9925127,0.002182722,0.0004948258,0.001454916,0.002629677,0.0007251857],"domain_scores_gemma":[0.9891762,0.005998189,0.0003656883,0.002652462,0.001466148,0.0003412377],"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.00004232712,0.00003357874,0.00007985068,0.0000924273,0.0000201831,0.00004190851,0.0000741723,0.009995705,0.0009890654,0.9694526,0.003752455,0.01542568],"study_design_scores_gemma":[0.00003466783,0.00004516383,0.000138782,0.00006437269,0.00003957318,0.0001077071,0.00002716634,0.1658451,0.003358479,0.8108824,0.01941155,0.00004510967],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.003061224,0.0005780085,0.9710671,0.001604557,0.0002118242,0.00008372749,0.0001672268,0.0002472683,0.02297897],"genre_scores_gemma":[0.2169576,0.001587193,0.7473661,0.002085218,0.0009218292,0.00129058,0.0006818808,0.0006928481,0.02841668],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01111436,"threshold_uncertainty_score":0.03718126,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03216755379160711,"score_gpt":0.3231520444204931,"score_spread":0.290984490628886,"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."}}