Cover Image

Lower Bounds for Greedy Teaching Set Constructions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Compton, Spencer, Pabbaraju, Chirag, Zhivotovskiy, Nikita
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
by: Charikar, Moses, et al.
Published: (2023)

A Characterization of List Regression
by: Pabbaraju, Chirag, et al.
Published: (2024)

Learning with Monotone Adversarial Corruptions
by: Larsen, Kasper Green, et al.
Published: (2026)

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

Pareto-optimal Non-uniform Language Generation
by: Charikar, Moses, et al.
Published: (2025)

Exploring Facets of Language Generation in the Limit
by: Charikar, Moses, et al.
Published: (2024)

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

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
by: Harris, Blake, et al.
Published: (2024)

A Characterization of List Language Identification in the Limit
by: Charikar, Moses, et al.
Published: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
by: Bhore, Sujoy, et al.
Published: (2026)

Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
by: Compton, Spencer, et al.
Published: (2025)

High-Accuracy List-Decodable Mean Estimation
by: Chen, Ziyun, et al.
Published: (2025)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

Approximately Optimal Core Shapes for Tensor Decompositions
by: Ghadiri, Mehrdad, et al.
Published: (2023)

Combinatorial optimization of the coefficient of determination
by: Harary, Marc
Published: (2024)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

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

Lower bounds on collective additive spanners
by: Corneil, Derek G., et al.
Published: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

Quality control in sublinear time: a case study via random graphs
by: Marcussen, Cassandra, et al.
Published: (2025)

A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
by: Gu, Xiang, et al.
Published: (2026)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
by: Gutekunst, Samuel C.
Published: (2025)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

Lower bounds for graph reconstruction with maximal independent set queries
by: Michel, Lukas, et al.
Published: (2024)

Non-Clashing Teaching Maps for Balls in Graphs
by: Chalopin, Jérémie, et al.
Published: (2023)

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
by: Pabbaraju, Chirag, et al.
Published: (2025)

Optimal Bounds for Distinct Quartics
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
by: Diakonikolas, Ilias, et al.
Published: (2025)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
by: Chen, Yixin, et al.
Published: (2026)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)

Greedy Gray Codes for some Restricted Classes of Binary Words
by: Hassler, Nathanaël, et al.
Published: (2024)

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

Constructing disjoint Steiner trees in Sierpiński graphs
by: Yang, Chenxu, et al.
Published: (2023)