{"id":"W247221977","doi":"10.1145/780591.780595","title":"Derandomizing polynomial identity tests means proving circuit lower bounds","year":2003,"lang":"en","type":"article","venue":"","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":42,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Mathematics; Nondeterministic algorithm; Polynomial; Discrete mathematics; Corollary; Arithmetic circuit complexity; Combinatorics; Identity (music); Arithmetic; Arbitrary-precision arithmetic","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.006343948,0.0012219,0.001811357,0.001107852,0.001605032,0.004663106,0.004252632,0.002335966,0.006951405],"category_scores_gemma":[0.04040701,0.0007500763,0.002627387,0.001199898,0.006333268,0.01061384,0.006002745,0.00818367,0.001202953],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005286797,"about_ca_system_score_gemma":0.003852435,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002401181,"about_ca_topic_score_gemma":0.002012682,"domain_scores_codex":[0.9895245,0.002963987,0.0005274235,0.002668465,0.002150767,0.002164903],"domain_scores_gemma":[0.9061319,0.0739935,0.002696625,0.01364732,0.00249239,0.001038368],"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.0009006013,0.0004308138,0.007948678,0.0006044968,0.0001790711,0.0004107956,0.0005722011,0.1806566,0.02401769,0.7152376,0.006677735,0.06236372],"study_design_scores_gemma":[0.0001079709,0.000189456,0.0009560766,0.00006267046,0.0001263632,0.0003058554,0.0001319265,0.419195,0.05112316,0.5211852,0.00655233,0.00006411004],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.159623,0.0005415046,0.8049604,0.005080609,0.0001922587,0.0003048717,0.0008059281,0.00242531,0.02606599],"genre_scores_gemma":[0.882804,0.000561793,0.1071911,0.001570556,0.0002696268,0.0005470719,0.001182006,0.0006775415,0.005196358],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.006951405,"threshold_uncertainty_score":0.03835857,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02633774209728651,"score_gpt":0.2543340318390336,"score_spread":0.2279962897417471,"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."}}