VDVarsha Dani

Varsha Dani

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Varsha Dani has a total of 12 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Interactive communication with unknown noise rate

    by Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, Maxwell Young


  • Open Access

    Distributed Computing with Channel Noise

    by Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia

    A group of $n$ users want to run a distributed protocol $\pi$ over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows $\pi$, is able to maliciously flip bits on the channels. Can we efficiently simulate $\pi$ in the presence of such an adversary? We show that this is possible, even when $L$, the number of bits sent in $\pi$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $\pi$ that 1) fails with probability at most $\delta$, for any $\delta>0$; and 2) sends $\tilde{O}(L + T)$ bits, where the $\tilde{O}$ notation hides a $\log (nL/ \delta)$ term multiplying $L$. Additionally, we show how to improve this result when the average message size $\alpha$ is not constant. In particular, we give an algorithm that sends $O( L (1 + (1/\alpha) \log (n L/\delta) + T)$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $\alpha$. We note that if $\alpha$ is $\Omega\left( \log (n L/\delta) \right)$, then this improved algorithm sends only $O(L+T)$ bits, and is therefore within a constant factor of optimal.

  • Codes, lower bounds, and phase transitions in the symmetric rendezvous problem

    by Varsha Dani, Thomas P. Hayes, Cristopher Moore, Alexander Russell


  • Secure multi-party computation in large networks

    by Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani


  • Open Access

    Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem

    by Varsha Dani, Thomas P. Hayes, Cristopher Moore, Alexander Russell

    In the rendezvous problem, two parties with different labelings of the vertices of a complete graph are trying to meet at some vertex at the same time. It is well-known that if the parties have predetermined roles, then the strategy where one of them waits at one vertex, while the other visits all $n$ vertices in random order is optimal, taking at most $n$ steps and averaging about $n/2$. Anderson and Weber considered the symmetric rendezvous problem, where both parties must use the same randomized strategy. They analyzed strategies where the parties repeatedly play the optimal asymmetric strategy, determining their role independently each time by a biased coin-flip. By tuning the bias, Anderson and Weber achieved an expected meeting time of about $0.829 n$, which they conjectured to be asymptotically optimal. We change perspective slightly: instead of minimizing the expected meeting time, we seek to maximize the probability of meeting within a specified time $T$. The Anderson-Weber strategy, which fails with constant probability when $T= \Theta(n)$, is not asymptotically optimal for large $T$ in this setting. Specifically, we exhibit a symmetric strategy that succeeds with probability $1-o(1)$ in $T=4n$ steps. This is tight: for any $\alpha < 4$, any symmetric strategy with $T = \alpha n$ fails with constant probability. Our strategy uses a new combinatorial object that we dub a "rendezvous code," which may be of independent interest. When $T \le n$, we show that the probability of meeting within $T$ steps is indeed asymptotically maximized by the Anderson-Weber strategy. Our results imply new lower bounds, showing that the best symmetric strategy takes at least $0.638 n$ steps in expectation. We also present some partial results for the symmetric rendezvous problem on other vertex-transitive graphs.

  • Open Access

    Secure Multi-Party Computation in Large Networks

    by Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani

    We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a $1/8$ fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide perfect and universally-composable security. To achieve our asynchronous MPC result, we define the \emph{threshold counting problem} and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model.

  • Open Access

    Interactive Communication with Unknown Noise Rate

    by Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, Maxwell Young

    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 $L$ bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires $a \ priori$ knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips $T$ bits, our algorithm sends $L + O\left(\sqrt{L(T+1)\log L} + T\right)$ bits in expectation and succeeds with high probability in $L$. It does so without any $a \ priori$ knowledge of $T$. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.

  • Scalable mechanisms for rational secret sharing

    by Varsha Dani, Mahnush Movahedi, Jared Saia


  • Open Access

    Scalable Mechanisms for Rational Secret Sharing

    by 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 non-simultaneous communication model, i.e. when rushing is possible, there is no Nash equilibrium that ensures both players learn the secret. However, they describe a mechanism for this problem, for any number of players, that is an epsilon-Nash equilibrium, in that no player can gain more than epsilon utility by deviating from it. Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send O(n) messages in expectation, where n is the number of agents. This may be problematic for some applications of rational secret sharing such as secure multi-party computation and simulation of a mediator. We address this issue by describing mechanisms for rational secret sharing that are designed for large n. Both of our results hold for n > 2, and are Nash equilbria, rather than just epsilon-Nash equilbria. Our first result is a mechanism for n-out-of-n rational secret sharing that is scalable in the sense that it requires each agent to send only an expected O(log n) bits. Moreover, the latency of this mechanism is O(log n) in expectation, compared to O(n) expected latency for the Kol and Naor result. Our second result is a mechanism for a relaxed variant of rational m-out-of-n secret sharing where m = Theta(n). It requires each processor to send O(log n) bits and has O(log n) latency. Both of our mechanisms are non-cryptographic, and are not susceptible to backwards induction.