2 citations · 3 across the 4 of their papers we have counts for
4 papers
Improved Approximation for the Directed Spanner Problem
Arnab Bhattacharyya, Konstantin Makarychev
We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of , for all k >= 3. This improv…
Steiner Transitive-Closure Spanners of d-Dimensional Posets
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu +3
Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diamet…
A Unified Framework for Testing Linear-Invariant Properties
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufma…
Separations of Matroid Freeness Properties
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström +1
Properties of Boolean functions on the hypercube invariant with respect to linear transformations of the domain are among the most well-studied properties in the context of propert…