Cover Image

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Sitan, Ding, Jingqiu, Majid, Mahbod, McKelvie, Walter
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity Information Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Robustness Implies Privacy in Statistical Estimation
by: Hopkins, Samuel B., et al.
Published: (2022)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

Private Mean Estimation with Person-Level Differential Privacy
by: Agarwal, Sushant, et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
by: Chen, Sitan, et al.
Published: (2025)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
by: Saha, Barna, et al.
Published: (2024)

Sample-Optimal Private Regression in Polynomial Time
by: Anderson, Prashanti, et al.
Published: (2025)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation
by: Chen, Sitan, et al.
Published: (2024)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

Optimal certification of constant-local Hamiltonians
by: Lee, Junseo, et al.
Published: (2025)

Simple algorithms to test and learn local Hamiltonians
by: Gutiérrez, Francisco Escudero
Published: (2024)

Hamiltonian Property Testing
by: Bluhm, Andreas, et al.
Published: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
by: Srivastava, Shashank, et al.
Published: (2025)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
by: Al-okaily, Anas
Published: (2024)

Improved Decoding of Tanner Codes
by: Zhou, Zhaienhe, et al.
Published: (2025)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
by: Ko, Young Kun
Published: (2026)

Quantum Multi-Level Estimation of Functionals of Discrete Distributions
by: Chen, Kean, et al.
Published: (2026)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)

Sample-Efficient Private Learning of Mixtures of Gaussians
by: Ashtiani, Hassan, et al.
Published: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
by: Blanchard, Moise
Published: (2024)

An optimal tradeoff between entanglement and copy complexity for state tomography
by: Chen, Sitan, et al.
Published: (2024)

Optimal high-precision shadow estimation
by: Chen, Sitan, et al.
Published: (2024)

Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
by: Wang, Qisheng
Published: (2024)

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
by: Wang, Qisheng, et al.
Published: (2024)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
by: Dvijotham, Krishnamurthy, et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
by: Goldenberg, Elazar, et al.
Published: (2024)

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
by: Ganian, Robert, et al.
Published: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

Differentially Private Verification of Distribution Properties
by: Du, Elbert, et al.
Published: (2026)

Efficient and Private Property Testing via Indistinguishability
by: Dwork, Cynthia, et al.
Published: (2025)