Cover Image

Strong Low Degree Hardness for the Number Partitioning Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mallarapu, Rushil, Sellke, Mark
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Computational Complexity Data Structures and Algorithms Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

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

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)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
by: Yu, Xifan, et al.
Published: (2024)

Stable algorithms cannot reliably find isolated perceptron solutions
by: Gong, Shuyang, et al.
Published: (2026)

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

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

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

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

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
by: Sellke, Mark
Published: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Model-agnostic super-resolution in high dimensions
by: Chen, Xi, et al.
Published: (2025)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

Asymmetric Number Partitioning with Splitting and Interval Targets
by: Bismuth, Samuel, et al.
Published: (2022)

On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem
by: Lovig, Maxwell, et al.
Published: (2024)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

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

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

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

Sumplete is Hard, Even with Two Different Numbers
by: Ruangwises, Suthee
Published: (2023)

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
by: Ding, Jian, et al.
Published: (2023)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
by: Chen, Zongchen, et al.
Published: (2024)

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

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

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

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

An Instance-Based Approach to the Trace Reconstruction Problem
by: Mazooji, Kayvon, et al.
Published: (2024)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)