1 citations · 1 across the 5 of their papers we have counts for
7 papers
Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
Jarosław Błasiok, Paul Lou, Alon Rosen +1
In the noisy -XOR problem, one is given and must distinguish between uniform and , where is the adjacency matrix of a -left-regula…
The Lovász number of random circulant graphs
Afonso S. Bandeira, Jarosław Błasiok, Daniil Dmitriev +3
This paper addresses the behavior of the Lovász number for dense random circulant graphs. The Lovász number is a well-known semidefinite programming upper bound on the independence…
Efficient and Provable Algorithms for Covariate Shift
Deeksha Adil, Jarosław Błasiok
Covariate shift, a widely used assumption in tackling {\it distributional shift} (when training and test distributions differ), focuses on scenarios where the distribution of the l…
Hardness of clique approximation for monotone circuits
Jarosław Błasiok, Linus Meierhöfer
We consider a problem of approximating the size of the largest clique in a graph, with a monotone circuit. Concretely, we focus on distinguishing a random Erdős-Renyi graph $\mathc…
Semirandom Planted Clique and the Restricted Isometry Property
Jarosław Błasiok, Rares-Darius Buhai, Pravesh K. Kothari +1
We give a simple, greedy -time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds when…
Matrix Multiplication and Number On the Forehead Communication
Josh Alman, Jarosław Błasiok
Three-player Number On the Forehead communication may be thought of as a three-player Number In the Hand promise model, in which each player is given the inputs that are supposedly…
Fourier growth of structured -polynomials and applications
Jarosław Błasiok, Peter Ivanov, Yaonan Jin +3
We analyze the Fourier growth, i.e. the Fourier weight at level (denoted ), of various well-studied classes of "structured" -polynomials. This stud…