Cover Image

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries

Fuente: arXiv

Saved in:

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

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set 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)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
by: Geis, Lukas, et al.
Published: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

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

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

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

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

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Distances in Planar Graphs are Almost for Free!
by: Mozes, Shay, et al.
Published: (2026)

Local Search for Clustering in Almost-linear Time
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

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

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
by: He, Kaiwen, 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)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
by: Chaplick, Steven, et al.
Published: (2024)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

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)

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)

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

Partitioning Trillion Edge Graphs on Edge Devices
by: Chhabra, Adil, et al.
Published: (2024)

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

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, 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)

Graph Reconstruction via MIS Queries
by: Konrad, Christian, et al.
Published: (2024)

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

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

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
by: Eden, Talya, et al.
Published: (2025)

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

Efficient Trace Frequency Queries in Sparse Graphs
by: Awofeso, Christine, et al.
Published: (2025)