32 citations · 63 across the 14 of their papers we have counts for
8 papers · 1 filter
Maximum Matching on Regular Nonbipartite Graphs
Varsha Dani, Thomas P. Hayes, Seth Pettie
Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in time, on both bipartite [HK73, Din70, Kar7…
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks
Varsha Dani, Aayush Gupta, Thomas P. Hayes +1
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for suc…
The Energy Complexity of BFS in Radio Networks
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +1
We consider a model of energy complexity in Radio Networks in which transmitting or listening on the channel costs one unit of energy and computation is free. This simplified model…
Interactive Communication with Unknown Noise Rate
Varsha Dani, Thomas P. Hayes, Mahnush Movahedi +2
Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring bits of noise-fre…
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation
Varsha Dani, Valerie King, Mahnush Movahedi +1
We describe an asynchronous algorithm to solve secure multiparty computation (MPC) over n players, when strictly less than a 1/8 fraction of the players are controlled by a static…
Scalable Mechanisms for Rational Secret Sharing
Varsha Dani, Mahnush Movahedi, Jared Saia
We consider the classical secret sharing problem in the case where all agents are selfish but rational. In recent work, Kol and Naor show that, when there are two players, in the n…