Copertina

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Black, Hadley, Chakrabarty, Deeparnab, Seshadhri, C.
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
di: Chakrabarty, Deeparnab, et al.
Pubblicazione: (2024)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
di: Beretta, Lorenzo, et al.
Pubblicazione: (2025)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
di: Chakrabarty, Deeparnab, et al.
Pubblicazione: (2025)

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

Learning Partitions using Rank Queries
di: Chakrabarty, Deeparnab, et al.
Pubblicazione: (2024)

Counting hypertriangles through hypergraph orientations
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2026)

Fault-tolerant $k$-Supplier with Outliers
di: Chakrabarty, Deeparnab, et al.
Pubblicazione: (2023)

Clustering in Varying Metrics
di: Chakrabarty, Deeparnab, et al.
Pubblicazione: (2025)

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

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
di: Bogdanov, Andrej, et al.
Pubblicazione: (2025)

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

A Tolerant Independent Set Tester
di: Seth, Cameron
Pubblicazione: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
di: Kumar, Akash, et al.
Pubblicazione: (2026)

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

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2022)

Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
di: Liu, Quanquan C., et al.
Pubblicazione: (2024)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2024)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
di: Balakrishnan, Girish, et al.
Pubblicazione: (2023)

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

The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)

A note on approximating the average degree of bounded arboricity graphs
di: Eden, Talya, et al.
Pubblicazione: (2026)

On the Structure of Replicable Hypothesis Testers
di: Aamand, Anders, et al.
Pubblicazione: (2025)

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

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

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

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

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

A Refined Kernel for $d$-Hitting Set
di: Liu, Yuxi, et al.
Pubblicazione: (2025)

A Quantum Algorithm for the Classification of Patterns of Boolean Functions
di: Andronikos, Theodore, et al.
Pubblicazione: (2025)

Online Monotone Metric Embeddings
di: Coester, Christian, et al.
Pubblicazione: (2026)

Monotone Submodular Multiway Partition
di: Bi, Richard, et al.
Pubblicazione: (2024)

A Dynamic, Self-balancing k-d Tree
di: Brown, Russell A.
Pubblicazione: (2025)

TIMEST: Temporal Information Motif Estimator Using Sampling Trees
di: Pan, Yunjie, et al.
Pubblicazione: (2025)

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

An FPT algorithm for Matching Cut and d-cut
di: Aravind, N R, et al.
Pubblicazione: (2021)

Exploring Monotone Priority Queues for Dijkstra Optimization
di: Costa, Jonas, et al.
Pubblicazione: (2024)

Deterministic Monotone Min-Plus Product and Convolution
di: Jin, Ce, et al.
Pubblicazione: (2026)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
di: Huang, Chien-Chung, et al.
Pubblicazione: (2026)

Review of Three Algorithms That Build k-d Trees
di: Brown, Russell A.
Pubblicazione: (2025)