Publications

Jarosław Błasiok, Preetum Nakkiran (2023). Smooth ECE: Principled Reliability Diagrams via Kernel Smoothing. Unpublished manuscript.

Cite arxiv

Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran (2023). When Does Optimizing a Proper Loss Yield Calibration?. NeurIPS 2023.

Cite arxiv

Josh Alman, Jarosław Błasiok (2023). Matrix Multiplication and Number On the Forehead Communication. CCC 2023.

Cite arxiv

Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalak, Preetum Nakkiran (2023). Loss minimization yields multicalibration for large neural networks. Unpublished Manuscript.

Cite arxiv

Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran (2023). A Unified Theory of Distance from Calibration. STOC 2023.

Cite arxiv

Alexander Andoni, Jarosław Błasiok, Arnold Filtser (2023). Communication Complexity of Inner Product in Symmetric Normed Spaces. Innovations in Theoretical Computer Science (ITCS 2023).

Cite arxiv

Bogdan Kulynych, Yao{-}Yuan Yang, Yaodong Yu, Jarosław Błasiok, Preetum Nakkiran (2022). What You See is What You Get: Distributional Generalization for Algorithm Design in Deep Learning. NeurIPS 2022.

Cite DOI arxiv

Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan (2022). General Strong Polarization. J. ACM.

Cite DOI arxiv

Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola (2021). Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021).

Cite DOI arxiv

Jarosław Błasiok (2020). Optimal Streaming and Tracking Distinct Elements with High Probability. ACM Trans. Algorithms; Best Student Paper Award at SODA 2018.

Cite DOI arxiv

Jarosław Błasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke (2019). Towards Instance-Optimal Private Query Release. SODA 2019.

Cite arxiv

Jarosław Błasiok, Marcin Kaminski, Jean{-}Florent Raymond, Th{\'{e}}ophile Trunck (2019). Induced minors and well-quasi-ordering. J. Comb. Theory, Ser. B.

Cite DOI arxiv

Jarosław Błasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek, Shravas Rao (2019). An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices. 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019.

Cite DOI arxiv

Jarosław Błasiok, Venkatesan Guruswami, Madhu Sudan (2018). Polar Codes with Exponentially Small Error at Finite Block Length. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA.

Cite DOI arxiv

Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang (2017). Streaming symmetric norms via measure concentration. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017.

Cite DOI arxiv

Jarosław Błasiok, Jian Ding, Jelani Nelson (2017). Continuous Monitoring of $\ell_p$ Norms in Data Streams. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA.

Cite DOI arxiv

Jarosław Błasiok, Marcin Jakub Kaminski (2017). Chain Minors are {FPT}. Algorithmica.

Cite DOI arxiv

Jarosław Błasiok, Jelani Nelson (2016). An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy.

Cite DOI arxiv