:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Braverman, Mark, Livni, Roi, Mansour, Yishay, Moran, Shay, Nissim, Kobbi
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Computational Complexity Information Theory
Online Access:	https://arxiv.org/abs/2604.04535
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Credit Attribution and Stable Compression
by: Livni, Roi, et al.
Published: (2024)

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

A Theoretical Framework for Statistical Evaluability of Generative Models
by: Aiyer, Shashaank, et al.
Published: (2026)

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
by: Aiyer, Shashaank, et al.
Published: (2026)

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

Learnability Gaps of Strategic Classification
by: Cohen, Lee, et al.
Published: (2024)

Bayesian Perspective on Memorization and Reconstruction
by: Kaplan, Haim, et al.
Published: (2025)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
by: Braverman, Mark, et al.
Published: (2025)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

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

Noisy Quantum Learning Theory
by: Cotler, Jordan, et al.
Published: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
by: Lowe, Angus, et al.
Published: (2022)

Information-theoretic generalization bounds for learning from quantum data
by: Caro, Matthias, et al.
Published: (2023)

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

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
by: Chen, Zhenyu, et al.
Published: (2025)

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
by: Bhargav, Jayanth, et al.
Published: (2024)

Algorithmic causal structure emerging through compression
by: Wendong, Liang, et al.
Published: (2025)

The Agent Capability Problem: Predicting Solvability Through Information-Theoretic Bounds
by: Lutati, Shahar
Published: (2025)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
by: Tsui, Darin, et al.
Published: (2025)

Adversarially robust quantum state learning and testing
by: Aliakbarpour, Maryam, et al.
Published: (2025)

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

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

On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
by: Molkaraie, Mehdi
Published: (2025)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

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

The Exact Replica Threshold for Nonlinear Moments of Quantum States
by: Zeng, Shuai
Published: (2026)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

Online Set Learning from Precision and Recall Feedback
by: Cohen, Lee, et al.
Published: (2026)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
by: Chen, Siyu, et al.
Published: (2025)

We Should Separate Memorization from Copyright
by: Haviv, Adi, et al.
Published: (2026)

Exponential quantum advantage in processing massive classical data
by: Zhao, Haimeng, et al.
Published: (2026)

A learning theory for quantum photonic processors and beyond
by: Rosati, Matteo
Published: (2022)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
by: Janzer, Oliver, et al.
Published: (2024)

Probably Approximately Precision and Recall Learning
by: Cohen, Lee, et al.
Published: (2024)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
by: Li, Zihan, et al.
Published: (2024)

Can Copyright be Reduced to Privacy?
by: Elkin-Koren, Niva, et al.
Published: (2023)

Margin in Abstract Spaces
by: Ashlagi, Yair, et al.
Published: (2026)

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)