Image de couverture de livre

Learning Partitions with Optimal Query and Round Complexities

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Black, Hadley, Mazumdar, Arya, Saha, Barna
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Information Theory Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
par: Black, Hadley, et autres
Publié: (2025)

Clustering with Non-adaptive Subset Queries
par: Black, Hadley, et autres
Publié: (2024)

Actively Learning Halfspaces without Synthetic Data
par: Black, Hadley, et autres
Publié: (2025)

Random Subgraph Detection Using Queries
par: Huleihel, Wasim, et autres
Publié: (2021)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
par: Saha, Barna, et autres
Publié: (2024)

Learning sparse generalized linear models with binary outcomes via iterative hard thresholding
par: Matsumoto, Namiko, et autres
Publié: (2025)

Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
par: Matsumoto, Namiko, et autres
Publié: (2022)

Smoothed Score Queries and the Complexity of Sampling
par: Liu, Jingbo
Publié: (2026)

Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
par: Li, Xiaxin, et autres
Publié: (2025)

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
par: Chakraborty, Diptarka, et autres
Publié: (2026)

Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme
par: Li, Xiaxin, et autres
Publié: (2024)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
par: Black, Hadley
Publié: (2023)

Sample-Optimal Private Regression in Polynomial Time
par: Anderson, Prashanti, et autres
Publié: (2025)

Non-adaptive Learning of Random Hypergraphs with Queries
par: Austhof, Bethany, et autres
Publié: (2025)

Learning multivariate Gaussians with imperfect advice
par: Bhattacharyya, Arnab, et autres
Publié: (2024)

On the Statistical Complexity of Sample Amplification
par: Axelrod, Brian, et autres
Publié: (2022)

Learning DNF through Generalized Fourier Representations
par: Heidari, Mohsen, et autres
Publié: (2025)

Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries
par: Black, Hadley, et autres
Publié: (2025)

Optimal high-precision shadow estimation
par: Chen, Sitan, et autres
Publié: (2024)

Optimal Differentially Private Sampling of Unbounded Gaussians
par: Iverson, Valentio, et autres
Publié: (2025)

The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
par: Chen, Jiale, et autres
Publié: (2025)

Testing with Non-identically Distributed Samples
par: Garg, Shivam, et autres
Publié: (2023)

The SMART approach to instance-optimal online learning
par: Banerjee, Siddhartha, et autres
Publié: (2024)

Subsampling Suffices for Adaptive Data Analysis
par: Blanc, Guy
Publié: (2023)

A Framework for Searching in Graphs in the Presence of Errors
par: Dereniowski, Dariusz, et autres
Publié: (2018)

Entropy Coding of Unordered Data Structures
par: Kunze, Julius, et autres
Publié: (2024)

New Algorithmic Directions in Optimal Transport and Applications for Product Spaces
par: Beigi, Salman, et autres
Publié: (2025)

SpecTr: Fast Speculative Decoding via Optimal Transport
par: Sun, Ziteng, et autres
Publié: (2023)

Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
par: Li, Gen, et autres
Publié: (2023)

Optimal and Near-Optimal Adaptive Vector Quantization
par: Ben-Basat, Ran, et autres
Publié: (2024)

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
par: Asi, Hilal, et autres
Publié: (2024)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
par: Joshi, Nirmit, et autres
Publié: (2024)

Statistical Query Lower Bounds for Learning Truncated Gaussians
par: Diakonikolas, Ilias, et autres
Publié: (2024)

The Information Theory of Similarity
par: Phadke, Nikit
Publié: (2025)

Optimal Rates for Differentially Private Hypothesis Testing with E-values
par: Jacobsen, Ben, et autres
Publié: (2026)

Online Distribution Learning with Local Private Constraints
par: Sima, Jin, et autres
Publié: (2024)

Orthogonal Nonnegative Matrix Factorization with Sparsity Constraints
par: Basiri, Salar, et autres
Publié: (2022)

A Distribution Testing Approach to Clustering Distributions
par: Kumar, Gunjan, et autres
Publié: (2025)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
par: Diakonikolas, Ilias, et autres
Publié: (2025)

Distribution Learnability and Robustness
par: Ben-David, Shai, et autres
Publié: (2024)