{"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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow","sts"],"consensus_categories":[],"category_scores_codex":[0.000167203,0.0004051044,0.0003328986,0.0003361409,0.001378491,0.0002596014,0.001779492,0.0001213355,0.00006499121],"category_scores_gemma":[0.00001871626,0.0003199335,0.0001490783,0.001041038,0.0004664405,0.0003831388,0.00003510526,0.0003097048,0.00009059356],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00007539761,"about_ca_system_score_gemma":0.0001127483,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00006266345,"about_ca_topic_score_gemma":0.0001471478,"domain_scores_codex":[0.9976553,0.00004961737,0.0003460063,0.0009005719,0.0004841912,0.0005642845],"domain_scores_gemma":[0.997243,0.0002559859,0.0001157226,0.001746019,0.0004646053,0.0001746843],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0002036659,0.000833329,0.000009678924,0.00008624747,0.0002559635,0.000006583178,0.001303118,0.004191274,0.0002062369,0.02835878,0.0003317008,0.9642134],"study_design_scores_gemma":[0.006573449,0.007685511,0.001914101,0.0003686411,0.0002161575,0.0002867511,0.0006623112,0.6436961,0.03268001,0.142,0.1608927,0.003024189],"study_design_candidate":"design_other","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.0006168013,0.00004810978,0.9936321,0.002995963,0.0005559009,0.001364067,0.0001084875,0.0004722215,0.0002063269],"genre_scores_gemma":[0.2084847,0.00002967548,0.7877857,0.001125556,0.0004858498,0.001692732,0.00001543852,0.00006154105,0.0003187719],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.9611892,"threshold_uncertainty_score":0.9999253,"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."}}