{"id":"W2134098997","doi":"10.1145/2077336.2077337","title":"Pebbles and Branching Programs for Tree Evaluation","year":2012,"lang":"en","type":"article","venue":"ACM Transactions on Computation Theory","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":23,"is_retracted":false,"has_abstract":true,"ca_institutions":"Université de Montréal; University of Toronto","funders":"","keywords":"Nondeterministic algorithm; Combinatorics; Upper and lower bounds; Mathematics; Branching (polymer chemistry); Boolean function; Tree (set theory); Binary decision diagram; Discrete mathematics; Algorithm","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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001242245,0.0001218269,0.0001085663,0.0001600772,0.0004064978,0.0001285123,0.0002839868,0.00004718304,0.00001274025],"category_scores_gemma":[0.00004968589,0.0001200391,0.00007750523,0.0002548767,0.00005942422,0.0006710665,0.00001126924,0.0001043067,0.000007880514],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00003206054,"about_ca_system_score_gemma":0.00002735888,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.000003378064,"about_ca_topic_score_gemma":0.000005723486,"domain_scores_codex":[0.9989229,0.0001929274,0.0001765942,0.0002401909,0.0002410726,0.0002263409],"domain_scores_gemma":[0.9987437,0.0007111786,0.00006441456,0.0002902228,0.0001069767,0.0000835133],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.00001598864,0.0001405428,0.0000241103,0.00001363825,0.00002299671,5.892403e-8,0.001222793,0.001478857,0.00003095772,0.05002008,0.00001331389,0.9470167],"study_design_scores_gemma":[0.0009342564,0.0001761445,0.002224584,0.00003564308,0.00005141463,0.00001785215,0.0002055084,0.3314813,0.0006913748,0.6632473,0.000695185,0.0002394481],"study_design_candidate":"design_other","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.01160017,0.0002409239,0.9861724,0.0004258148,0.0005814933,0.0005321671,0.000003636986,0.0001908459,0.0002525867],"genre_scores_gemma":[0.7811943,0.000006670761,0.2184245,0.0001352425,0.00006029243,0.000124313,0.000008977365,0.000008476538,0.0000373179],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.9467772,"threshold_uncertainty_score":0.4895052,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.06058992463226921,"score_gpt":0.3174479788893818,"score_spread":0.2568580542571126,"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."}}