{"id":"W3108038062","doi":"10.1145/3488250","title":"Erasure-Resilient Sublinear-Time Graph Algorithms","year":2021,"lang":"en","type":"preprint","venue":"ACM Transactions on Computation Theory","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Simons Institute for the Theory of Computing, University of California Berkeley; Israel Science Foundation; National Science Foundation","keywords":"Sublinear function; Degree (music); Property testing; Social connectedness; Erasure; Adjacency list; Mathematics; Algorithm; Discrete mathematics; Graph property; Computer science; Graph; Time complexity; Combinatorics; Theoretical computer science; Line graph","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.004020106,0.002426852,0.002448941,0.001423927,0.001205168,0.003202551,0.006638112,0.002936722,0.006897452],"category_scores_gemma":[0.02713303,0.001090895,0.001798323,0.00286129,0.00284162,0.01246212,0.003799316,0.004019946,0.002047829],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003870862,"about_ca_system_score_gemma":0.002935064,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002053267,"about_ca_topic_score_gemma":0.002886542,"domain_scores_codex":[0.9943476,0.001691591,0.0003032277,0.001801895,0.0009704787,0.0008852242],"domain_scores_gemma":[0.967136,0.02178665,0.002151581,0.007379486,0.0009125558,0.0006336912],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.002076578,0.0006501171,0.002010227,0.0006648392,0.0002250159,0.0002350445,0.0005546018,0.7433994,0.008819671,0.08361429,0.01478662,0.1429635],"study_design_scores_gemma":[0.0001208449,0.0001129471,0.0001719905,0.00001586606,0.00004038347,0.0001197213,0.00004901943,0.9107625,0.004018187,0.08331966,0.001249046,0.0000198874],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1221698,0.001728118,0.849926,0.00437034,0.0002707909,0.0003543865,0.001194837,0.01133284,0.008652901],"genre_scores_gemma":[0.6737473,0.0006430035,0.3158371,0.001377666,0.0003058766,0.0004178577,0.001386643,0.0008552588,0.005429226],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.006897452,"threshold_uncertainty_score":0.02808517,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02675515628261876,"score_gpt":0.2754805988845482,"score_spread":0.2487254426019295,"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."}}