:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Ding, Jingqiu, Hua, Yiding, Lindberg, Kasper, Steurer, David, Storozhenko, Aleksandr
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2511.16613
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
by: Leake, Jonathan, et al.
Published: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
by: Chen, Hongjie, et al.
Published: (2025)

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

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

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
by: Chen, Hongjie, et al.
Published: (2024)

Finding Colorings in One-Sided Expanders
by: Buhai, Rares-Darius, et al.
Published: (2025)

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

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

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)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
by: Abbas, Amira, et al.
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)

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

Low degree conjecture implies sharp computational thresholds in stochastic block model
by: Ding, Jingqiu, et al.
Published: (2025)

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

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

Relative-error unateness testing
by: Chen, Xi, et al.
Published: (2025)

AdaBoost is not an Optimal Weak to Strong Learner
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

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)

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

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Subset Balancing and Generalized Subset Sum via Lattices
by: Gao, Yiming, et al.
Published: (2026)

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

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
by: Firbas, Alexander, et al.
Published: (2024)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
by: Grønlund, Allan, et al.
Published: (2024)

Linear Hashing Is Optimal
by: Jaber, Michael, et al.
Published: (2025)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)