Cover Image

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dell, Holger, Lapinskas, John, Meeks, Kitty
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

The Complexity of Counting Small Sub-Hypergraphs
by: Bressan, Marco, et al.
Published: (2025)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
by: Abbas, Amira, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Solution independence and self-referential instances
by: Zhou, Guangyan, et al.
Published: (2026)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
by: Fu, Daniel, et al.
Published: (2026)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
by: Björklund, Andreas, et al.
Published: (2025)

On optimal distinguishers for Planted Clique
by: Nagda, Ansh, et al.
Published: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

The communication complexity of distributed estimation
by: Gopalan, Parikshit, et al.
Published: (2025)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
by: Yang, Yang
Published: (2024)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
by: Bengali, Vedangi, et al.
Published: (2024)

Amplitude amplification and estimation require inverses
by: Tang, Ewin, et al.
Published: (2025)

Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
by: Mary, Arnaud
Published: (2024)

A lossless a priori splitting rule for split-delivery routing problems
by: Jones, Bo, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
by: Madathil, Jayakrishnan, et al.
Published: (2024)

Beating full state tomography for unentangled spectrum estimation
by: Pelecanos, Angelos, et al.
Published: (2025)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

Fast quantum algorithm for differential equations
by: Bagherimehrab, Mohsen, et al.
Published: (2023)

On the instance optimality of detecting collisions and subgraphs
by: Ben-Eliezer, Omri, et al.
Published: (2023)

On estimating the quantum $\ell_α$ distance
by: Liu, Yupan, et al.
Published: (2025)

On estimating the trace of quantum state powers
by: Liu, Yupan, et al.
Published: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
by: Srivastava, Shashank, et al.
Published: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)