8 citations · 22 across the 12 of their papers we have counts for
Showing 2009 · cs.CCShow all
2 papers · 2 filters
cs.CC2009★ 6 cited
Cell-Probe Lower Bounds for Prefix Sums
Emanuele Viola
We prove that to store n bits x so that each prefix-sum query Sum(i) := sum_{k < i} x_k can be answered by non-adaptively probing q cells of log n bits, one needs memory > n + n/lo…
cs.CC2009★ 2 cited
Bounded Independence Fools Halfspaces
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal +2
We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result…