Jarosław Błasiok
  • Home
  • Publications
  • Contact
  • CV
  • Teaching
  • Teaching
    • Computer Science II (2026)
    • Fundamentals of Computer Science 30398 (Fall 2026)
      • Lecture 6 - String, tuples and basic recursion
      • Lecture 5 (Lists and Eratosthenes Sieve)
      • Lecture 4 (Functions)
      • Lecture 3 (Loops)
      • Lecture 2 (Variables and Conditions)
  • 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

Hardness of clique approximation for monotone circuits

Jan 16, 2025·
Jarosław Błasiok
Jarosław Błasiok
,
Linus Meierhöfer
· 0 min read
arxiv DOI
Last updated on Jan 16, 2025
Jarosław Błasiok
Authors
Jarosław Błasiok
Assistant Professor
← The Lovász number of random circulant graphs Feb 22, 2025
Semirandom Planted Clique and the Restricted Isometry Property Oct 1, 2024 →

Made with Hugo Blox Builder. Build your site →