Cover Image

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Adar, Tomer, Fischer, Eldar, Levi, Amit
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Support Testing in the Huge Object Model
by: Adar, Tomer, et al.
Published: (2023)

Optimal mass estimation in the conditional sampling model
by: Adar, Tomer, et al.
Published: (2025)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Refining the Adaptivity Notion in the Huge Object Model
by: Adar, Tomer, et al.
Published: (2023)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

Tight simulation of a distribution using conditional samples
by: Adar, Tomer
Published: (2025)

Instance-optimal estimation of L2-norm
by: Adar, Tomer
Published: (2026)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
by: Chakraborty, Sourav, et al.
Published: (2024)

A basic lower bound for property testing
by: Fischer, Eldar
Published: (2024)

Equivalence Testing: The Power of Bounded Adaptivity
by: Chakraborty, Diptarka, et al.
Published: (2024)

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
by: Dudek, Bartłomiej, et al.
Published: (2026)

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

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
by: Dumitrescu, Adrian
Published: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

A General Reduction for High-Probability Analysis with General Light-Tailed Distributions
by: Attia, Amit, et al.
Published: (2024)

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

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Encodings for Range Minimum Queries over Bounded Alphabets
by: Jo, Seungbum, et al.
Published: (2026)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

Testing $C_k$-freeness in bounded-arboricity graphs
by: Eden, Talya, et al.
Published: (2024)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
by: Hu, Ivan, et al.
Published: (2022)

Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
by: Brown, Nathaniel K., et al.
Published: (2026)

Direct Access for Answers to Conjunctive Queries with Aggregation
by: Eldar, Idan, et al.
Published: (2023)

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
by: Bringmann, Karl, et al.
Published: (2026)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

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

Learning Partitions using Rank Queries
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
by: Chen, Xi, et al.
Published: (2024)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Improving Pinwheel Density Bounds for Small Minimums
by: Mishra, Ahan, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)