most citedSub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

1 citations · 1 across the 2 of their papers we have counts for

collaborators

2 papers

cs.CC2024

Randomized query composition and product distributions

Swagato Sanyal

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)…

cs.CC2014★ 1 cited

Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

Swagato Sanyal

We prove that the Fourier dimension of any Boolean function with Fourier sparsity is at most . Our proof method yields an improved bound of $\widetilde{O…