:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Liu, Jingbo
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Information Theory Machine Learning
Online Access:	https://arxiv.org/abs/2605.27769
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)

On the Statistical Complexity of Sample Amplification
by: Axelrod, Brian, et al.
Published: (2022)

Random Subgraph Detection Using Queries
by: Huleihel, Wasim, et al.
Published: (2021)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

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

Non-adaptive Learning of Random Hypergraphs with Queries
by: Austhof, Bethany, et al.
Published: (2025)

Smoothed Analysis of Learning from Positive Samples
by: Lee, Jane H., et al.
Published: (2025)

Optimal Differentially Private Sampling of Unbounded Gaussians
by: Iverson, Valentio, et al.
Published: (2025)

Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples
by: Afzali, Mohammad, et al.
Published: (2023)

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

Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
by: Tasnim, Naima, et al.
Published: (2025)

Learning DNF through Generalized Fourier Representations
by: Heidari, Mohsen, et al.
Published: (2025)

The SMART approach to instance-optimal online learning
by: Banerjee, Siddhartha, et al.
Published: (2024)

Subsampling Suffices for Adaptive Data Analysis
by: Blanc, Guy
Published: (2023)

A Framework for Searching in Graphs in the Presence of Errors
by: Dereniowski, Dariusz, et al.
Published: (2018)

Learning multivariate Gaussians with imperfect advice
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Entropy Coding of Unordered Data Structures
by: Kunze, Julius, et al.
Published: (2024)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
by: Chen, Jiale, et al.
Published: (2025)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination
by: Diakonikolas, Ilias, et al.
Published: (2026)

Smooth Nash Equilibria: Algorithms and Complexity
by: Daskalakis, Constantinos, et al.
Published: (2023)

The Information Theory of Similarity
by: Phadke, Nikit
Published: (2025)

Query Lower Bounds for Diffusion Sampling
by: Xun, Zhiyang, et al.
Published: (2026)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

Complexity of Non-Log-Concave Sampling in Fisher Information
by: Chewi, Sinho, et al.
Published: (2026)

Distribution Learnability and Robustness
by: Ben-David, Shai, et al.
Published: (2024)

A Distribution Testing Approach to Clustering Distributions
by: Kumar, Gunjan, et al.
Published: (2025)

Learning sparse generalized linear models with binary outcomes via iterative hard thresholding
by: Matsumoto, Namiko, et al.
Published: (2025)

Planted Bipartite Graph Detection
by: Rotenberg, Asaf, et al.
Published: (2023)

Orthogonal Nonnegative Matrix Factorization with Sparsity Constraints
by: Basiri, Salar, et al.
Published: (2022)

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
by: Hanneke, Steve, et al.
Published: (2026)

Improved classical shadows from local symmetries in the Schur basis
by: Grier, Daniel, et al.
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)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

DDPM Score Matching and Distribution Learning
by: Chewi, Sinho, et al.
Published: (2025)

Statistical Query Lower Bounds for Learning Truncated Gaussians
by: Diakonikolas, Ilias, et al.
Published: (2024)

On Unbiased Low-Rank Approximation with Minimum Distortion
by: Barnes, Leighton Pate, et al.
Published: (2025)

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
by: Blanca, Antonio, et al.
Published: (2022)