Cover Image

Semirandom Planted Clique via 1-norm Isometry Property

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Guruswami, Venkatesan, Wang, Hsin-Po
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Capacity-Achieving Gray Codes
by: Guruswami, Venkatesan, et al.
Published: (2024)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
by: Guruswami, Venkatesan, et al.
Published: (2023)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Planted clique recovery in random geometric graphs
by: Avrachenkov, Konstantin, et al.
Published: (2025)

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

Convergence Properties of the Asynchronous Maximum Model
by: Larkin, John
Published: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

Tight bounds for stream decodable error-correcting codes
by: Gupta, Meghal, et al.
Published: (2024)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
by: Pettie, Seth, et al.
Published: (2024)

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

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
by: Wang, Yulin, et al.
Published: (2023)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

Subquadratic Counting via Perfect Marginal Sampling
by: Chen, Xiaoyu, et al.
Published: (2026)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
by: Chen, Xiaoyu, et al.
Published: (2024)

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

Universal Perfect Samplers for Incremental Streams
by: Pettie, Seth, et al.
Published: (2024)

A Sampling Lovász Local Lemma for Large Domain Sizes
by: Wang, Chunyang, et al.
Published: (2023)

Decay of correlation for edge colorings when $q>3Δ$
by: Chen, Zejia, et al.
Published: (2025)

Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
by: He, Yuchen, et al.
Published: (2026)

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
by: Alon, Noga, et al.
Published: (2024)

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

Mixing of general biased adjacent transposition chains
by: Gheissari, Reza, et al.
Published: (2025)

Rapid Mixing on Random Regular Graphs beyond Uniqueness
by: Chen, Xiaoyu, et al.
Published: (2025)

The Mixed Birth-death/death-Birth Moran Process
by: Brewster, David A., et al.
Published: (2025)

Simple parallel estimation of the partition ratio for Gibbs distributions
by: Harris, David G., et al.
Published: (2025)

On Algorithmic Robustness of Corrupted Markov Chains
by: Gaitonde, Jason, et al.
Published: (2025)

Markov Chains Approximate Message Passing
by: Rajaraman, Amit, et al.
Published: (2025)

Thinning to improve two-sample discrepancy
by: Smirnov, Gleb, et al.
Published: (2025)

Improved Mixing of Critical Hardcore Model
by: Chen, Zongchen, et al.
Published: (2025)

Fixed-magnetization Ising on random graphs up to reconstruction
by: Gheissari, Reza, et al.
Published: (2025)

Distance Estimation for High-Dimensional Discrete Distributions
by: Kumar, Gunjan, et al.
Published: (2023)

Robust recovery for stochastic block models, simplified and generalized
by: Mohanty, Sidhanth, et al.
Published: (2024)

Reconstruction of geometric random graphs with the Simple algorithm
by: Stegehuis, Clara, et al.
Published: (2024)

On Sampling from Ising Models with Spectral Constraints
by: Galanis, Andreas, et al.
Published: (2024)

Spectral Alignment of Correlated Gaussian matrices
by: Ganassali, Luca, et al.
Published: (2019)

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
by: Liu, Kuikui, et al.
Published: (2024)