Jarosław Błasiok
  • Home
  • Publications
  • Contact
  • CV
  • Teaching
  • Teaching
    • Computer Science II (2026)
  • Publications
    • On efficient robust regression with subquadratic samples
    • Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
    • Efficient and Provable Algorithms for Covariate Shift
    • The Lovász number of random circulant graphs
    • 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

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR

Apr 11, 2026·
Jarosław Błasiok
Jarosław Błasiok
,
Paul Lou
,
Alon Rosen
,
Madhu Sudan
· 0 min read
arxiv
Last updated on Apr 11, 2026
Jarosław Błasiok
Authors
Jarosław Błasiok
Assistant Professor
← On efficient robust regression with subquadratic samples Jun 29, 2026
Efficient and Provable Algorithms for Covariate Shift Feb 23, 2026 →

Made with Hugo Blox Builder. Build your site →