Cover Image

Refining the Adaptivity Notion in the Huge Object Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Adar, Tomer, Fischer, Eldar
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

Support Testing 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 vs Estimation for Index-Invariant Properties in the Huge Object Model
by: Chakraborty, Sourav, et al.
Published: (2024)

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

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

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

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

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

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

Stability Notions for Hospital Residents with Sizes
by: Balasundaram, Haricharan, et al.
Published: (2025)

Load Balancing with Duration Predictions
by: Azar, Yossi, et al.
Published: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

From Donkeys to Kings in Tournaments
by: Abboud, Amir, et al.
Published: (2024)

Nearly Optimal Attention Coresets
by: Liberty, Edo, et al.
Published: (2026)

Witness-Sensitive Detection of Induced Diamonds
by: Censor-Hillel, Keren, et al.
Published: (2026)

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

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
by: Ezra, Tomer, et al.
Published: (2024)

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

Sumsets, 3SUM, Subset Sum: Now for Real!
by: Fischer, Nick
Published: (2024)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
by: Fischer, Manuela, et al.
Published: (2021)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All
by: Panda, Atasi, et al.
Published: (2022)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Unrolled denoising networks provably learn optimal Bayesian inference
by: Karan, Aayush, et al.
Published: (2024)

On the Complexity of Minimising the Moving Distance for Dispersing Objects
by: Honorato-Droguett, Nicolás, et al.
Published: (2025)

Adaptive Quotient Filters
by: Wen, Richard, et al.
Published: (2024)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
by: Brinkop, Hauke, et al.
Published: (2025)

Structural Results for High-Multiplicity Scheduling on Uniform Machines
by: Brinkop, Hauke, et al.
Published: (2022)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection
by: Peng, Cheng, et al.
Published: (2024)

Adaptively Robust Resettable Streaming
by: Cohen, Edith, et al.
Published: (2026)