Buchumschlag

Low-degree Security of the Planted Random Subgraph Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bogdanov, Andrej, Jones, Chris, Rosen, Alon, Zadik, Ilias
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Cryptography and Security Data Structures and Algorithms Statistics Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

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

The Planted Orthogonal Vectors Problem
von: Kühnemann, David, et al.
Veröffentlicht: (2025)

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

Stable Algorithms Lower Bounds for Estimation
von: Yu, Xifan, et al.
Veröffentlicht: (2026)

Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice
von: Luo, Ming-Xing
Veröffentlicht: (2026)

Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets
von: He, Yiyun, et al.
Veröffentlicht: (2023)

Transfer Learning Beyond Bounded Density Ratios
von: Kalavasis, Alkis, et al.
Veröffentlicht: (2024)

Instance-Optimal Private Density Estimation in the Wasserstein Distance
von: Feldman, Vitaly, et al.
Veröffentlicht: (2024)

A Bias-Accuracy-Privacy Trilemma for Statistical Estimation
von: Kamath, Gautam, et al.
Veröffentlicht: (2023)

Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
von: Lovig, Max, et al.
Veröffentlicht: (2025)

Compression with Privacy-Preserving Random Access
von: Chandar, Venkat, et al.
Veröffentlicht: (2025)

The Broader Landscape of Robustness in Algorithmic Statistics
von: Kamath, Gautam
Veröffentlicht: (2024)

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
von: Narayanan, Shyam
Veröffentlicht: (2023)

Optimal Rates for Differentially Private Hypothesis Testing with E-values
von: Jacobsen, Ben, et al.
Veröffentlicht: (2026)

CoinPress: Practical Private Mean and Covariance Estimation
von: Biswas, Sourav, et al.
Veröffentlicht: (2020)

Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
von: Menuhin, Boaz, et al.
Veröffentlicht: (2025)

Invertible Bloom Lookup Tables with Less Memory and Randomness
von: Fleischhacker, Nils, et al.
Veröffentlicht: (2023)

Fine-Grained Privacy Guarantees for Coverage Problems
von: Dhulipala, Laxman, et al.
Veröffentlicht: (2024)

Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues
von: Thießen, Thore, et al.
Veröffentlicht: (2024)

Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy
von: Dong, Wei, et al.
Veröffentlicht: (2024)

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2020)

Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
von: Zhou, Felix
Veröffentlicht: (2025)

Robust Detection of Planted Subgraphs in Semi-Random Models
von: Elimelech, Dor, et al.
Veröffentlicht: (2025)

An average case efficient algorithm for solving two-variable linear Diophantine equations
von: Deora, Mayank, et al.
Veröffentlicht: (2024)

Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach
von: Jiang, Bo, et al.
Veröffentlicht: (2024)

Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters
von: Haney, Samuel, et al.
Veröffentlicht: (2023)

Necessity of Block Designs for Optimal Locally Private Distribution Estimation
von: Gentle, Abigail
Veröffentlicht: (2025)

Differentially Private Densest Subgraph Detection
von: Nguyen, Dung, et al.
Veröffentlicht: (2021)

Random Subgraph Detection Using Queries
von: Huleihel, Wasim, et al.
Veröffentlicht: (2021)

A Classical Quadratic Speedup for Planted $k$XOR
von: Gupta, Meghal, et al.
Veröffentlicht: (2025)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
von: Kumar, Rajendra, et al.
Veröffentlicht: (2018)

Dynamic Accountable Storage: An Efficient Protocol for Real-time Cloud Storage Auditing
von: Goodrich, Michael T., et al.
Veröffentlicht: (2024)

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
von: Ghazi, Badih, et al.
Veröffentlicht: (2024)

Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
von: Chandra, Rishi, et al.
Veröffentlicht: (2024)

Adversary Resilient Learned Bloom Filters
von: Almashaqbeh, Ghada, et al.
Veröffentlicht: (2024)

On Learning Parities with Dependent Noise
von: Golowich, Noah, et al.
Veröffentlicht: (2024)

Differentially Private Substring and Document Counting with Near-Optimal Error
von: Bernardini, Giulia, et al.
Veröffentlicht: (2024)

On Wagner's k-Tree Algorithm Over Integers
von: Lin, Haoxing, et al.
Veröffentlicht: (2024)