{"id":"W7110023545","doi":"10.4230/lipics.itcs.2025.19","title":"Differential Privacy and Sublinear Time Are Incompatible Sometimes","year":2025,"lang":"en","type":"article","venue":"DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)","topic":"Privacy-Preserving Technologies in Data","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Defense Advanced Research Projects Agency; National Science Foundation","keywords":"Sublinear function; Differential privacy; Simple (philosophy); Graph; Differential (mechanical device)","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.01492557,0.001597348,0.002848253,0.001364196,0.002273676,0.01011543,0.0044223,0.004450268,0.007616357],"category_scores_gemma":[0.0672655,0.001379608,0.002427456,0.003095825,0.01224431,0.03077812,0.01042309,0.01812559,0.002442652],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005477653,"about_ca_system_score_gemma":0.004039088,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0006916961,"about_ca_topic_score_gemma":0.0005702961,"domain_scores_codex":[0.9708279,0.008341759,0.001607452,0.007990352,0.008132731,0.003099917],"domain_scores_gemma":[0.8758873,0.08522675,0.004427678,0.02747561,0.004476116,0.002506505],"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.0004904967,0.00008334997,0.0006057314,0.0002243292,0.00005532152,0.00006512459,0.0002885437,0.009524886,0.001475411,0.9656144,0.004113435,0.0174589],"study_design_scores_gemma":[0.00003912463,0.00003913765,0.0001275832,0.0000294689,0.00001834569,0.00009976914,0.00005482482,0.0288194,0.001747106,0.9641954,0.004815194,0.00001455192],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.03255252,0.00303681,0.9108169,0.02585281,0.0005195181,0.0001179764,0.00074446,0.001053824,0.02530521],"genre_scores_gemma":[0.6648439,0.004226399,0.2978718,0.01091816,0.001908111,0.0009074031,0.00103612,0.001397634,0.01689055],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01492557,"threshold_uncertainty_score":0.07893491,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01297844764835011,"score_gpt":0.2597744655268951,"score_spread":0.246796017878545,"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."}}