Cover Image

Private graphon estimation via sum-of-squares

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Hongjie, Ding, Jingqiu, d'Orsi, Tommaso, Hua, Yiding, Liu, Chih-Hung, Steurer, David
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Tight Differentially Private PCA via Matrix Coherence
by: d'Orsi, Tommaso, et al.
Published: (2025)

On Purely Private Covariance Estimation
by: d'Orsi, Tommaso, et al.
Published: (2025)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

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

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

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

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

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
by: d'Orsi, Tommaso, et al.
Published: (2024)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

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

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

Efficient and Private Property Testing via Indistinguishability
by: Dwork, Cynthia, et al.
Published: (2025)

Perturb-and-Project: Differentially Private Similarities and Marginals
by: Cohen-Addad, Vincent, et al.
Published: (2024)

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

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

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

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
by: Liu, Wei, et al.
Published: (2024)

Differentially Private Verification of Distribution Properties
by: Du, Elbert, et al.
Published: (2026)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Multi-View Stochastic Block Models
by: Cohen-Addad, Vincent, 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)

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

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)

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)

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)

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

A general framework for finding diverse solutions via network flow and its applications
by: Iwamasa, Yuni, et al.
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

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

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Quadratic Speedup for Computing Contraction Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)