5 citations · 6 across the 5 of their papers we have counts for
8 papers
Beyond Worst Case Local Computation Algorithms
Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen +4
We initiate the study of Local Computation Algorithms on average case inputs. In the Local Computation Algorithm (LCA) model, we are given probe access to a huge graph, and asked t…
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld
We consider the problem of sampling and approximately counting an arbitrary given motif in a graph , where access to is given via queries: degree, neighbor, and pair, as…
Local Access to Random Walks
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
For a graph on vertices, naively sampling the position of a random walk of at time requires work . We desire local access algorithms supporting $\text{position}(G…
Testing Tail Weight of a Distribution Via Hazard Rate
Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran +1
Understanding the shape of a distribution of data is of interest to people in a great variety of fields, as it may affect the types of algorithms used for that data. We study one s…
Massively Parallel Algorithms for Distance Approximation and Spanners
Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari +2
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms -- usually subl…
Massively Parallel Algorithms for Small Subgraph Counting
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu +2
Over the last two decades, frameworks for distributed-memory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing p…
Local Access to Huge Random Objects through Partial Sampling
Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee
Consider an algorithm performing a computation on a huge random object. Is it necessary to generate the entire object up front, or is it possible to provide query access to the obj…
Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation
Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis +3
We study the problem of estimating the value of sums of the form when one has the ability to sample with probability proportional…