5 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…