{"id":"W2565821653","doi":"10.1109/focs.2016.51","title":"Exponential Lower Bounds for Monotone Span Programs","year":2016,"lang":"en","type":"article","venue":"","topic":"Cryptography and Data Security","field":"Computer Science","cited_by":69,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Monotone polygon; Mathematics; Upper and lower bounds; Discrete mathematics; Function (biology); Exponential function; Combinatorics; Polynomial; Rank (graph theory); Monotonic function; Bernstein's theorem on monotone functions; Applied mathematics; Strongly monotone; Mathematical analysis","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.00451344,0.002297801,0.001412373,0.002678601,0.001536262,0.004449412,0.004512157,0.001966022,0.01463494],"category_scores_gemma":[0.03305341,0.001031633,0.002043825,0.002969706,0.004866565,0.02215914,0.005998957,0.01063812,0.001797773],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005165905,"about_ca_system_score_gemma":0.00220314,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001230349,"about_ca_topic_score_gemma":0.001662338,"domain_scores_codex":[0.9922599,0.001338976,0.000247663,0.001417066,0.003066607,0.001669804],"domain_scores_gemma":[0.9542636,0.03593783,0.001796118,0.00442361,0.002531369,0.001047521],"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.000378303,0.0003056425,0.002003175,0.0004612845,0.00005746856,0.0001760399,0.0003606552,0.04587819,0.008622915,0.8893304,0.00710033,0.0453256],"study_design_scores_gemma":[0.00004092922,0.00009648717,0.0004665522,0.00006454866,0.0000428491,0.000171306,0.00006652281,0.2134592,0.0069273,0.7729937,0.005631613,0.00003896219],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.09878419,0.002768531,0.81837,0.00737741,0.0002052966,0.0002385155,0.001455295,0.001963651,0.06883712],"genre_scores_gemma":[0.8008686,0.004543338,0.1638846,0.002371031,0.001015679,0.0008647681,0.001911305,0.00150506,0.02303559],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01463494,"threshold_uncertainty_score":0.04895872,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01851735068226934,"score_gpt":0.2401144382655797,"score_spread":0.2215970875833103,"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."}}