Cover Image

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Black, Hadley
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
by: Black, Hadley, et al.
Published: (2023)

Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries
by: Black, Hadley, et al.
Published: (2025)

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

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)

Nearly Optimal Bounds for Stochastic Online Sorting
by: Hu, Yang
Published: (2025)

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

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

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams
by: Ta, Hoang, et al.
Published: (2026)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
by: Kosolobov, Dmitry
Published: (2024)

Clustering with Non-adaptive Subset Queries
by: Black, Hadley, et al.
Published: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
by: Grilnberger, Mara, et al.
Published: (2026)

Actively Learning Halfspaces without Synthetic Data
by: Black, Hadley, et al.
Published: (2025)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
by: Dürr, Anita
Published: (2022)

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
by: Pinto Jr, Renato Ferreira
Published: (2024)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

On Exact Learning of $d$-Monotone Functions
by: Bshouty, Nader H.
Published: (2025)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

Near-Optimal Generalized Private Testing
by: Chaturvedi, Anamay, et al.
Published: (2026)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

Optimal $k$-Secretary with Logarithmic Memory
by: Qiao, Mingda, et al.
Published: (2025)

Nearly Optimal Internal Dictionary Matching
by: Chen, Jingbang, et al.
Published: (2023)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
by: Zhu, Yanhui, et al.
Published: (2024)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
by: Ganczorz, Adam, et al.
Published: (2025)

Near-Optimal Sample Complexity for MDPs via Anchoring
by: Lee, Jongmin, et al.
Published: (2025)

Two New Upper Bounds for the Maximum k-plex Problem
by: Zheng, Jiongzhi, et al.
Published: (2023)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
by: Kuhnle, Alan
Published: (2026)

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)

Transposition is Nearly Optimal for IID List Update
by: Coester, Christian
Published: (2026)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)