Cover Image

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries

Fuente: arXiv

Saved in:

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

Similar Items

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

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

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)

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

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

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

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

A Nearly Quadratic Improvement for Memory Reallocation
by: Farach-Colton, Martin, et al.
Published: (2024)

Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
by: Dürr, Christoph, et al.
Published: (2024)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

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

Estimating Hitting Times Locally At Scale
by: Haris, Themistoklis, et al.
Published: (2025)

A Tolerant Independent Set Tester
by: Seth, Cameron
Published: (2025)

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

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Clustering What Matters in Constrained Settings
by: Jaiswal, Ragesh, et al.
Published: (2023)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
by: Cardinal, Jean, et al.
Published: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2025)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
by: Bai, Tian
Published: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

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

Tight Localizations of Feedback Sets
by: Hecht, Michael, et al.
Published: (2020)

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

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
by: Dumitrescu, Adrian
Published: (2021)

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
by: Bshouty, Nader H., et al.
Published: (2026)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
by: Baswana, Surender, et al.
Published: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

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

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)