Cover Image

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Sourav, Fischer, Eldar, Ghosh, Arijit, Levi, Amit, Mishra, Gopinath, Sen, Sayantan
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)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
by: Bishnu, Arijit, et al.
Published: (2024)

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

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
by: Adar, Tomer, et al.
Published: (2024)

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

Testing Distributions of Huge Objects
by: Goldreich, Oded, et al.
Published: (2022)

Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
by: Bishnu, Arijit, et al.
Published: (2025)

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

Instance Dependent Testing of Samplers using Interval Conditioning
by: Bhattacharyya, Rishiraj, et al.
Published: (2025)

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)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

Testing Sparse Functions over the Reals
by: Arora, Vipul, et al.
Published: (2026)

Testing (Conditional) Mutual Information
by: Seyfried, Jan, et al.
Published: (2025)

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

Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
by: Gayen, Sutanu, et al.
Published: (2024)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

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

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

RSVP: Beyond Weisfeiler Lehman Graph Isomorphism Test
by: Dutta, Sourav, et al.
Published: (2024)

Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling
by: Joshi, Amit
Published: (2025)

Space-Efficient Text Indexing with Mismatches using Function Inversion
by: Bibbens, Jackson, et al.
Published: (2026)

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
by: Joshi, Amit
Published: (2025)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
by: Chang, Yi-Jun, et al.
Published: (2024)

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)

Engineering an Efficient Approximate DNF-Counter
by: Soos, Mate, et al.
Published: (2024)

Property Testing of Computational Networks
by: Czumaj, Artur, et al.
Published: (2025)

Quantum property testing in sparse directed graphs
by: Apers, Simon, et al.
Published: (2024)

Structural Parameterization of Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Testing Graph Properties with the Container Method
by: Blais, Eric, et al.
Published: (2023)

Optimal non-adaptive algorithm for edge estimation
by: Bishnu, Arijit, et al.
Published: (2025)

Distribution Testing Meets Sum Estimation
by: Pradhan, Pinki, et al.
Published: (2025)

Online versus Offline Adversaries in Property Testing
by: Kelman, Esty, et al.
Published: (2024)

Polynomial Property Testing
by: Gishboliner, Lior, et al.
Published: (2025)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
by: Blais, Eric, et al.
Published: (2024)

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
by: Chang, Yi-Jun, et al.
Published: (2024)

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)