Varsha Dani

Varsha Dani, Josep Díaz, Thomas P. Hayes et al.

Embedding graphs in a geographical or latent space, i.e.\ inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where $n$ points are scattered uniformly in a square of area $n$, and two points have an edge between them if and only if their Euclidean distance is less than $r$. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if $r=n^α$ for any $α> 0$, with high probability reconstructs the vertex positions with a maximum error of $O(n^β)$ where $β=1/2-(4/3)α$, until $α\ge 3/8$ where $β=0$ and the error becomes $O(\sqrt{\log n})$. This improves over earlier results, which were unable to reconstruct with error less than $r$. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in $\R^3$ and to hypercubes in any constant fixed dimension. Additionally we examine the extent to which reconstruction is still possible when the original adjacency lists have had a subset of the edges independently deleted at random.

Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes et al.

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

Abhinav Aggarwal, Varsha Dani, Thomas Hayes et al.

Alice and Bob are connected via a two-way channel, and Alice wants to send a message of $L$ bits to Bob. An adversary flips an arbitrary but finite number of bits, $T$, on the channel. This adversary knows our algorithm and Alice's message, but does not know any private random bits generated by Alice or Bob, nor the bits sent over the channel, except when these bits can be predicted by knowledge of Alice's message or our algorithm. We want Bob to receive Alice's message and for both players to terminate, with error probability at most $δ> 0$, where $δ$ is a parameter known to both Alice and Bob. Unfortunately, the value $T$ is unknown in advance to either Alice or Bob, and the value $L$ is unknown in advance to Bob. We describe an algorithm to solve the above problem while sending an expected $L + O \left( T + \min \left(T+1,\frac{L}{\log L} \right) \log \left( \frac{L}δ \right) \right)$ bits. A special case is when $δ= O(1/L^c)$, for some constant $c$. Then when $T = o(L/\log L)$, the expected number of bits sent is $L + o(L)$, and when $T = Ω(L)$, the expected number of bits sent is $L + O\left( T \right)$, which is asymptotically optimal.

Varsha Dani, Valerie King, Mahnush Movahedi et al.

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 adversary. For any function f over a field that can be computed by a circuit with m gates, our algorithm requires each player to send a number of field elements and perform an amount of computation that is O (m/n + \sqrt{n}). This significantly improves over traditional algorithms, which require each player to both send a number of messages and perform computation that is Ω(nm). Additionally, we define the threshold counting problem and present a distributed algorithm to solve it in the asynchronous communication model. Our algorithm is load balanced, with computation, communication and latency complexity of O(log n), and may be of independent interest to other applications with a load balancing goal in mind.

Varsha Dani, Omid Madani, David M Pennock et al.

Predicting the outcomes of future events is a challenging problem for which a variety of solution methods have been explored and attempted. We present an empirical comparison of a variety of online and offline adaptive algorithms for aggregating experts' predictions of the outcomes of five years of US National Football League games (1319 games) using expert probability elicitations obtained from an Internet contest called ProbabilitySports. We find that it is difficult to improve over simple averaging of the predictions in terms of prediction accuracy, but that there is room for improvement in quadratic loss. Somewhat surprisingly, a Bayesian estimation algorithm which estimates the variance of each expert's prediction exhibits the most consistent superior performance over simple averaging among our collection of algorithms.