{"id":"W4242600797","doi":"10.1137/1.9781611974331.ch87","title":"Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky","year":2015,"lang":"en","type":"article","venue":"","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":36,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Natural Sciences and Engineering Research Council of Canada; National Science Foundation","keywords":"Satisfiability; Randomized algorithm; Deterministic algorithm; Combinatorics; Mathematics; Matching (statistics); Running time; Discrete mathematics; Algorithm; Computer science; Statistics","routes":{"ca_aff":true,"ca_fund":true,"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.003860229,0.001259516,0.001445623,0.001039164,0.001478607,0.001926448,0.002804021,0.001301599,0.00644173],"category_scores_gemma":[0.02061022,0.0007613886,0.001941191,0.001775276,0.003027441,0.006246336,0.004976826,0.00340811,0.001526802],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00275247,"about_ca_system_score_gemma":0.003757693,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003632776,"about_ca_topic_score_gemma":0.005847618,"domain_scores_codex":[0.9954022,0.001835276,0.0002546193,0.0008850237,0.001060584,0.0005621912],"domain_scores_gemma":[0.987569,0.00682814,0.0008051444,0.0037704,0.000633877,0.0003934383],"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.002010265,0.0002884168,0.006553171,0.0004551633,0.0002008847,0.0002611534,0.0006189427,0.2320305,0.01479162,0.6043355,0.01658151,0.1218729],"study_design_scores_gemma":[0.0001860406,0.0001623335,0.0003923588,0.00003332064,0.00005221043,0.00009864899,0.00008405792,0.4527231,0.006116867,0.5362712,0.003831651,0.00004814113],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2004154,0.0004402464,0.7795484,0.003036104,0.0002183455,0.0002783301,0.0008497183,0.004053615,0.01115988],"genre_scores_gemma":[0.6709406,0.000246714,0.3205405,0.0009482396,0.0001449224,0.0004975243,0.001025617,0.0008030087,0.004852911],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.00644173,"threshold_uncertainty_score":0.02154976,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03425324003984173,"score_gpt":0.2612734967834293,"score_spread":0.2270202567435875,"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."}}