Buchumschlag

Learning from Equivalence Queries, Revisited

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Braverman, Mark, Livni, Roi, Mansour, Yishay, Moran, Shay, Nissim, Kobbi
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Machine Learning Computational Complexity Information Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Credit Attribution and Stable Compression
von: Livni, Roi, et al.
Veröffentlicht: (2024)

The Optimal Approximation Factor in Density Estimation
von: Bousquet, Olivier, et al.
Veröffentlicht: (2019)

A Theoretical Framework for Statistical Evaluability of Generative Models
von: Aiyer, Shashaank, et al.
Veröffentlicht: (2026)

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
von: Aiyer, Shashaank, et al.
Veröffentlicht: (2026)

Optimality of Frequency Moment Estimation
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Learnability Gaps of Strategic Classification
von: Cohen, Lee, et al.
Veröffentlicht: (2024)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
von: Thornton, Mitchell A.
Veröffentlicht: (2026)

Bayesian Perspective on Memorization and Reconstruction
von: Kaplan, Haim, et al.
Veröffentlicht: (2025)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
von: Lou, Mengqi, et al.
Veröffentlicht: (2025)

Noisy Quantum Learning Theory
von: Cotler, Jordan, et al.
Veröffentlicht: (2025)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
von: Braverman, Mark, et al.
Veröffentlicht: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
von: Lowe, Angus, et al.
Veröffentlicht: (2022)

Information-theoretic generalization bounds for learning from quantum data
von: Caro, Matthias, et al.
Veröffentlicht: (2023)

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

On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
von: Molkaraie, Mehdi
Veröffentlicht: (2025)

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
von: Chen, Zhenyu, et al.
Veröffentlicht: (2025)

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
von: Bhargav, Jayanth, et al.
Veröffentlicht: (2024)

Algorithmic causal structure emerging through compression
von: Wendong, Liang, et al.
Veröffentlicht: (2025)

The Agent Capability Problem: Predicting Solvability Through Information-Theoretic Bounds
von: Lutati, Shahar
Veröffentlicht: (2025)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
von: Tsui, Darin, et al.
Veröffentlicht: (2025)

Adversarially robust quantum state learning and testing
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2025)

Efficient Pauli channel estimation with logarithmic quantum memory
von: Chen, Sitan, et al.
Veröffentlicht: (2023)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
von: Zhao, Haimeng, et al.
Veröffentlicht: (2025)

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

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
von: Chen, Sitan, et al.
Veröffentlicht: (2026)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
von: Saha, Barna, et al.
Veröffentlicht: (2024)

The Exact Replica Threshold for Nonlinear Moments of Quantum States
von: Zeng, Shuai
Veröffentlicht: (2026)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
von: Chen, Siyu, et al.
Veröffentlicht: (2025)

Optimal lower bounds for Quantum Learning via Information Theory
von: Hadiashar, Shima Bab, et al.
Veröffentlicht: (2023)

Online Set Learning from Precision and Recall Feedback
von: Cohen, Lee, et al.
Veröffentlicht: (2026)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
von: Li, Zihan, et al.
Veröffentlicht: (2024)

Exponential quantum advantage in processing massive classical data
von: Zhao, Haimeng, et al.
Veröffentlicht: (2026)

A learning theory for quantum photonic processors and beyond
von: Rosati, Matteo
Veröffentlicht: (2022)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
von: First, Uriya A., et al.
Veröffentlicht: (2024)

Learning High-dimensional Gaussians from Censored Data
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Probably Approximately Precision and Recall Learning
von: Cohen, Lee, et al.
Veröffentlicht: (2024)

We Should Separate Memorization from Copyright
von: Haviv, Adi, et al.
Veröffentlicht: (2026)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
von: Chen, Kean, et al.
Veröffentlicht: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
von: Tiegel, Stefan
Veröffentlicht: (2024)