6 citations · 9 across the 3 of their papers we have counts for
3 papers
cs.CE2009★ 1 cited
A Computational View of Market Efficiency
Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola
We propose to study market efficiency from a computational viewpoint. Borrowing from theoretical computer science, we define a market to be \emph{efficient with respect to resource…
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…