5 papers
Average-Distortion Sketching
Yiqiao Bao, Anubhav Baweja, Nicolas Menand +3
We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwis…
An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes
Anubhav Baweja, Justin Jia, David P. Woodruff
We present the first semi-streaming PTAS for the minimum feedback arc set problem on directed tournaments in a small number of passes. Namely, we obtain a -appro…
Efficient Parallel Self-Adjusting Computation
Daniel Anderson, Guy E. Blelloch, Anubhav Baweja +1
Self-adjusting computation is an approach for automatically producing dynamic algorithms from static ones. The approach works by tracking control and data dependencies, and propaga…
ForestDSH: A Universal Hash Design for Discrete Probability Distributions
Arash Gholami Davoodi, Sean Chang, Hyun Gon Yoo +3
In this paper, we consider the problem of classification of high dimensional queries to high dimensional classes where a…
A Constant Optimization of the Binary Indexed Tree Query Operation
Anubhav Baweja
There are several data structures which can calculate the prefix sums of an array efficiently, while handling point updates on the array, such as Segment Trees and Binary Indexed T…