Jarosław Błasiok
  • Home
  • Publications
  • Contact
  • CV
  • Publications
    • The Lovász number of random circulant graphs
    • Efficient and Provable Algorithms for Covariate Shift
    • Hardness of clique approximation for monotone circuits
    • Semirandom Planted Clique and the Restricted Isometry Property
    • Smooth ECE: Principled Reliability Diagrams via Kernel Smoothing
    • Loss minimization yields multicalibration for large neural networks
    • When Does Optimizing a Proper Loss Yield Calibration?
    • Matrix Multiplication and Number On the Forehead Communication
    • A Unified Theory of Distance from Calibration
    • Communication Complexity of Inner Product in Symmetric Normed Spaces
    • What You See is What You Get: Distributional Generalization for Algorithm Design in Deep Learning
    • General Strong Polarization
    • Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
    • Optimal Streaming and Tracking Distinct Elements with High Probability
    • An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices
    • Induced minors and well-quasi-ordering
    • Towards Instance-Optimal Private Query Release
    • Polar Codes with Exponentially Small Error at Finite Block Length
    • Predicting Positive and Negative Links with Noisy Queries: Theory Practice
    • Chain Minors are {FPT}
    • Continuous Monitoring of $\ell_p$ Norms in Data Streams
    • Streaming symmetric norms via measure concentration
    • ADAGIO: Fast Data-Aware Near-Isometric Linear Embeddings
    • An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm

Semirandom Planted Clique and the Restricted Isometry Property

Oct 1, 2024·
Jarosław Błasiok
Jarosław Błasiok
,
Rares Buhai
,
Pravesh Kothari
,
David Steurer
· 0 min read
Cite arxiv
Publication
STOC 2024
Last updated on Oct 1, 2024
Jarosław Błasiok
Authors
Jarosław Błasiok
Postdoctoral Researcher in Computer Science - Simons Junior Fellow
← Hardness of clique approximation for monotone circuits Jan 16, 2025
Smooth ECE: Principled Reliability Diagrams via Kernel Smoothing Mar 15, 2024 →

Published with Hugo Blox Builder — the free, open source website builder that empowers creators.