{"id":"W2263246245","doi":"","title":"Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky","year":2021,"lang":"en","type":"article","venue":"DSpace@MIT (Massachusetts Institute of Technology)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":53,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"","keywords":"Satisfiability; Randomized algorithm; Deterministic algorithm; Combinatorics; Mathematics; Matching (statistics); Discrete mathematics; Running time; Variable (mathematics); Key (lock); Binary logarithm; Algorithm; Computer science; Statistics","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.004269542,0.00117472,0.001188439,0.0009276421,0.001580878,0.001677569,0.002360441,0.001153472,0.008010346],"category_scores_gemma":[0.01622874,0.0007171131,0.001592532,0.001616535,0.002659066,0.005883696,0.004833837,0.003222109,0.001934614],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002925879,"about_ca_system_score_gemma":0.003890925,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003134918,"about_ca_topic_score_gemma":0.005670145,"domain_scores_codex":[0.9950821,0.002212429,0.0002548802,0.0008892164,0.001029748,0.0005315724],"domain_scores_gemma":[0.9903226,0.005386624,0.0005719073,0.002948373,0.0004800215,0.0002905577],"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.001883834,0.0002884142,0.00574295,0.0005145154,0.000224297,0.0002600404,0.0005309865,0.21427,0.01592569,0.5723943,0.02798183,0.1599833],"study_design_scores_gemma":[0.000183097,0.0001969971,0.0003969466,0.00003629651,0.00004993441,0.0001004229,0.00007447431,0.4596175,0.005705221,0.526745,0.006851817,0.00004239236],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1775437,0.0007103722,0.7924145,0.003885807,0.0003318027,0.0004453921,0.00114492,0.00494171,0.01858186],"genre_scores_gemma":[0.6554101,0.0003358947,0.3325037,0.001090837,0.000178122,0.0006514442,0.001345467,0.001034853,0.007449612],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.008010346,"threshold_uncertainty_score":0.02679729,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01209712053241457,"score_gpt":0.2434263904676279,"score_spread":0.2313292699352133,"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."}}