{"id":"W4235156957","doi":"10.1145/3196275","title":"Completeness for First-order Properties on Sparse Structures with Algorithmic Applications","year":2018,"lang":"en","type":"article","venue":"ACM Transactions on Algorithms","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":14,"is_retracted":false,"has_abstract":true,"ca_institutions":"Memorial University of Newfoundland","funders":"Division of Computing and Communication Foundations; Natural Sciences and Engineering Research Council of Canada; Simons Institute for the Theory of Computing, University of California Berkeley; University of California, San Diego; National Science Foundation","keywords":"Tuple; Exponential time hypothesis; Mathematics; Completeness (order theory); Property (philosophy); Combinatorics; Time complexity; Set (abstract data type); Order (exchange); PSPACE; Exponential function; Class (philosophy); Discrete mathematics; Data structure; Algorithm; Computational complexity theory; Computer science","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.004140086,0.001060277,0.001571014,0.002177521,0.002057209,0.005635804,0.002850867,0.001781544,0.007231442],"category_scores_gemma":[0.023983,0.001283639,0.004352021,0.003727217,0.004263288,0.01613237,0.004481963,0.006198704,0.001305727],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0027743,"about_ca_system_score_gemma":0.003909753,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003261763,"about_ca_topic_score_gemma":0.004747536,"domain_scores_codex":[0.9930119,0.001361429,0.0005376403,0.001538119,0.002522463,0.001028456],"domain_scores_gemma":[0.9609891,0.02575382,0.001824855,0.008431007,0.002392214,0.000609132],"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.0005933434,0.0004336349,0.005461806,0.0009017421,0.0001629778,0.0002508948,0.001630317,0.07606535,0.008259245,0.8096154,0.00997973,0.08664548],"study_design_scores_gemma":[0.00005902979,0.00004846072,0.0006725613,0.0000372938,0.00003842427,0.0001390345,0.0001539118,0.08505834,0.004953278,0.9056723,0.003142145,0.000025265],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2001765,0.0006995055,0.7696335,0.004490992,0.00008378163,0.0002348311,0.002982798,0.003689705,0.01800834],"genre_scores_gemma":[0.6986037,0.0006940312,0.2850123,0.0009799635,0.0003738926,0.0003539782,0.006189622,0.0009215269,0.00687091],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.007231442,"threshold_uncertainty_score":0.02419162,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05092610085438685,"score_gpt":0.2667640654076113,"score_spread":0.2158379645532245,"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."}}