Cover Image

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dhawan, Abhishek, Wang, Yuzhou
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Data Structures and Algorithms Combinatorics Probability Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sharp Online Hardness for Large Balanced Independent Sets
by: Dhawan, Abhishek, et al.
Published: (2025)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2026)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Strong Low Degree Hardness for the Number Partitioning Problem
by: Mallarapu, Rushil, et al.
Published: (2025)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
by: Gribanov, Dmitry, et al.
Published: (2022)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Hypergraph Samplers: Typical and Worst Case Behavior
by: Alev, Vedat Levi, et al.
Published: (2026)

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)

A computational phase transition for learning-to-sample from Ising models
by: Risteski, Andrej, et al.
Published: (2026)

Deciding if a DAG is Interesting is Hard
by: De Carufel, Jean-Lou, et al.
Published: (2025)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

Inference of rankings planted in random tournaments
by: Kunisky, Dmitriy, et al.
Published: (2024)

Statistical inference of a ranked community in a directed graph
by: Kunisky, Dmitriy, et al.
Published: (2024)

The stochastic block model has the overlap graph property for modularity
by: Bhamidi, Shankar, et al.
Published: (2026)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

Fast Mixing in Sparse Random Ising Models
by: Liu, Kuikui, et al.
Published: (2024)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
by: R., Abhishek Hegade K., et al.
Published: (2025)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Analysis of a Random Local Search Algorithm for Dominating Set
by: Higl, Hendrik
Published: (2026)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Tensor cumulants for statistical inference on invariant distributions
by: Kunisky, Dmitriy, et al.
Published: (2024)

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
by: Bhore, Sujoy, et al.
Published: (2026)

Non-Clashing Teaching Maps for Balls in Graphs
by: Chalopin, Jérémie, et al.
Published: (2023)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

(Independent) Roman Domination Parameterized by Distance to Cluster
by: Ashok, Pradeesha, et al.
Published: (2024)