85 citations · 294 across the 35 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.CC2017★ 1 cited
Sparse juntas on the biased hypercube
Irit Dinur, Yuval Filmus, Prahladh Harsha
We give a structure theorem for Boolean functions on the -biased hypercube which are -close to degree in , showing that they are close to sparse juntas. Our structur…
cs.CC2017★ 2 cited
Agreement tests on graphs and hypergraphs
Irit Dinur, Yuval Filmus, Prahladh Harsha
Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreemen…
cs.CC2017★ 30 cited
On polynomial approximations over
Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan
We study approximation of Boolean functions by low-degree polynomials over the ring . More precisely, given a Boolean function $F:\{0,1\}^n \rightarrow \{…