11 citations · 27 across the 9 of their papers we have counts for
9 papers
When Hashing Met Matching: Efficient Spatio-Temporal Search for Ridesharing
Chinmoy Dutta
Carpooling, or sharing a ride with other passengers, holds immense potential for urban transportation. Ridesharing platforms enable such sharing of rides using real-time data. Find…
Maximum Weight Online Matching with Deadlines
Itai Ashlagi, Maximilien Burq, Chinmoy Dutta +3
We study the problem of matching agents who arrive at a marketplace over time and leave after d time periods. Agents can only be matched while they are present in the marketplace.…
Online Matching in a Ride-Sharing Platform
Chinmoy Dutta, Chris Sholley
We propose a formal graph-theoretic model for studying the problem of matching rides online in a ride-sharing platform. Unlike most of the literature on online matching, our model,…
A Sampling Technique of Proving Lower Bounds for Noisy Computations
Chinmoy Dutta, Jaikumar Radhakrishnan
We present a technique of proving lower bounds for noisy computations. This is achieved by a theorem connecting computations on a kind of randomized decision trees and sampling bas…
How Hard is Computing Parity with Noisy Communications?
Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath +1
We show a tight lower bound of on the number of transmissions required to compute the parity of input bits with constant error in a noisy communication networ…
Global Information Sharing under Network Dynamics
Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman +2
We study how to spread tokens of information to every node on an -node dynamic network, the edges of which are changing at each round. This basic {\em gossip problem} can be…
On Zarankiewicz Problem and Depth-Two Superconcentrators
Chinmoy Dutta, Jaikumar Radhakrishnan
We show tight necessary and sufficient conditions on the sizes of small bipartite graphs whose union is a larger bipartite graph that has no large bipartite independent set. Our ma…
Information Spreading in Dynamic Networks
Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman +1
We study the fundamental problem of information spreading (also known as gossip) in dynamic networks. In gossip, or more generally, -gossip, there are pieces of information…
On Strong Graph Partitions and Universal Steiner Trees
Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan +2
We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph and a root node , we seek a single spanning tree of minimum {\em stretc…