AMS Without 4-Wise Independence on Product Domains

Vladimir Braverman, Kai-Min Chung, Zhenming Liu +2

In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that 4-wise independence is sufficient to obtain good approximations of…