Cover Image

Approximate Computation via Le Cam Simulability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Akdemir, Deniz
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Computational Complexity Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Le Cam Distortion: A Decision-Theoretic Framework for Robust Transfer Learning
by: Akdemir, Deniz
Published: (2025)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
by: Tang, Runshi, et al.
Published: (2026)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
by: Lou, Mengqi, et al.
Published: (2025)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
by: Bresler, Guy, et al.
Published: (2025)

Efficient Pauli channel estimation with logarithmic quantum memory
by: Chen, Sitan, et al.
Published: (2023)

Computational lower bounds for multi-frequency group synchronization
by: Kireeva, Anastasia, et al.
Published: (2024)

The Optimization of Random Tree Codes for Limited Computational Resources
by: Bacinoglu, B. Tan
Published: (2025)

Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
by: Tang, Runshi, et al.
Published: (2026)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
by: Buhai, Rares-Darius, et al.
Published: (2024)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
by: Wein, Alexander S.
Published: (2025)

Likelihood-Preserving Embeddings for Statistical Inference
by: Akdemir, Deniz
Published: (2025)

Computable one-way functions on the reals
by: Barmpalias, George, et al.
Published: (2024)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
by: Jeronimo, Fernando Granha, et al.
Published: (2026)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
by: Zhao, Haimeng, et al.
Published: (2025)

Computational hardness of estimating quantum entropies via binary entropy bounds
by: Liu, Yupan
Published: (2026)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
by: Gamarnik, David, et al.
Published: (2023)

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
by: Chen, Fan, et al.
Published: (2024)

Computation-Limited Signals: A Channel Capacity Regime Constrained by Computational Complexity
by: Queiroz, Saulo, et al.
Published: (2023)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

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

Recovering polynomials over finite fields from noisy character values
by: Kopparty, Swastik
Published: (2026)

Privacy-aware Berrut Approximated Coded Computing for Federated Learning
by: Luaña, Xavier Martínez, et al.
Published: (2024)

Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
by: Wei, Jing-Yuan
Published: (2026)

Oblivious Deletion Codes
by: Con, Roni, et al.
Published: (2025)

Space-bounded online Kolmogorov complexity is additive
by: Bauwens, Bruno, et al.
Published: (2025)

Decoding Balanced Linear Codes With Preprocessing
by: Bogdanov, Andrej, et al.
Published: (2025)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
by: Goyal, Rohan, et al.
Published: (2025)

Deterministic list decoding of Reed-Solomon codes
by: Chatterjee, Soham, et al.
Published: (2025)

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
by: Li, Songsong, et al.
Published: (2025)

Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
by: Bauwens, Bruno, et al.
Published: (2025)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2025)

Tight Quantum Time-Space Tradeoffs for Permutation Inversion
by: Akshima, et al.
Published: (2025)

Explicit Codes approaching Generalized Singleton Bound using Expanders
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
by: Drucker, Andrew, et al.
Published: (2024)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
by: Chen, Zitan
Published: (2023)

Relaxed Local Correctability from Local Testing
by: Kumar, Vinayak M., et al.
Published: (2023)

Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
by: Fawzi, Omar, et al.
Published: (2023)

Improved PIR Schemes using Matching Vectors and Derivatives
by: Ghasemi, Fatemeh, et al.
Published: (2024)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
by: Block, Alexander R., et al.
Published: (2026)

Explicit Constant-Alphabet Subspace Design Codes
by: Goyal, Rohan, et al.
Published: (2026)