HOME /

Publications

2018
Jarosław Błasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. 2018. “Towards an Optimal Algorithm for Concentrated Differential Privacy.” (Unpublished manuscript).
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan. 2018. “General Strong Polarization.” In 50th Annual ACM Symposium on the Theory of Computing (STOC 2018). Arxiv version general_strong_polarization.pdf
Jaroslaw Blasiok. 2018. “Optimal streaming and tracking distinct elements with high probability.” In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, Pp. 2432–2448. Arxiv version distinct_elements.pdf
(Best student paper award)
2017
Jaroslaw Blasiok and Marcin Jakub Kaminski. 2017. “Chain Minors are FPT.” Algorithmica, 79, 3, Pp. 698–707. Arxiv version chainminors.pdf

Preliminary version of this paper appeared in International Symposium on Parameterized and Exact Computation (IPEC 2013)

Jaroslaw Blasiok, Jian Ding, and Jelani Nelson. 2017. “Continuous Monitoring of l\_p Norms in Data Streams.” In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, Pp. 32:1–32:13. Arxiv version lp_tracking.pdf
Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang. 2017. “Streaming symmetric norms via measure concentration.” In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, Pp. 716–729. Arxiv version streaming_symmetric_norms.pdf
2016
Jaroslaw Blasiok and Charalampos E. Tsourakakis. 2016. “ADAGIO: Fast Data-Aware Near-Isometric Linear Embeddings.” In IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, Pp. 31–40. Arxiv version adagio.pdf
Jaroslaw Blasiok and Jelani Nelson. 2016. “An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm.” In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Pp. 44:1–44:14. Arxiv version dictionary_learning.pdf
2015
Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, and Théophile Trunck. 2015. “Induced minors and well-quasi-ordering.” Electronic Notes in Discrete Mathematics, 49, Pp. 197–201. Arxiv version im-wqo2.pdf