Cover Image

Semirandom Planted Clique and the Restricted Isometry Property

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Błasiok, Jarosław, Buhai, Rares-Darius, Kothari, Pravesh K., Steurer, David
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Semirandom Planted Clique via 1-norm Isometry Property
by: Guruswami, Venkatesan, et al.
Published: (2025)

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

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

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

Lasso and Partially-Rotated Designs
by: Buhai, Rares-Darius
Published: (2025)

Robust Mixture Learning when Outliers Overwhelm Small Groups
by: Dmitriev, Daniil, et al.
Published: (2024)

Efficient and Provable Algorithms for Covariate Shift
by: Adil, Deeksha, et al.
Published: (2025)

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

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
by: Kothari, Pravesh K., et al.
Published: (2024)

Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
by: Rao, Shravas
Published: (2023)

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

On efficient robust regression with subquadratic samples
by: Adil, Deeksha, et al.
Published: (2026)

Spectral Refutations of Semirandom $k$-LIN over Larger Fields
by: Kocurek, Nicholas, et al.
Published: (2025)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
by: Kalavasis, Alkis, et al.
Published: (2026)

On optimal distinguishers for Planted Clique
by: Nagda, Ansh, et al.
Published: (2025)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
by: Bakshi, Ainesh, et al.
Published: (2026)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Learning Minimum Linear Arrangement of Cliques and Lines
by: Dallot, Julien, et al.
Published: (2024)

Quadratic Kernel for Cliques or Trees Vertex Deletion
by: Kumabe, Soh
Published: (2025)

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

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

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
by: Bhaskara, Aditya, et al.
Published: (2024)

A Reduction-based Algorithm for the Clique Interdiction Problem
by: Zhu, Chenghao, et al.
Published: (2025)

Exact Clique Number Manipulation via Edge Interdiction
by: Zhou, Yi, et al.
Published: (2026)

Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
by: Baguley, Samuel, et al.
Published: (2024)

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

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery
by: Xu, Xiaojia, et al.
Published: (2024)

Online Rounding for Set Cover under Subset Arrivals
by: Byrka, Jarosław, et al.
Published: (2025)

Grouped Color Deletion, Lasserre Exactness and Clique-Sum Locality for Rainbow Matching
by: Stamoulis, Georgios
Published: (2026)

Location-Restricted Stable Matching
by: Castro, Garret
Published: (2025)

Less is More: Faster Maximum Clique Search by Work-Avoidance
by: Vandierendonck, Hans
Published: (2025)

Efficient $k$-Clique Listing: An Edge-Oriented Branching Strategy
by: Wang, Kaixin, et al.
Published: (2023)

Online Disjoint Set Covers: Randomization is not Necessary
by: Bienkowski, Marcin, et al.
Published: (2024)