Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits.
It allows the parties to act in a correlated manner, which can be quite useful.
But what happens if the shared randomness is not perfect?

In this work, ... more >>>

In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of
depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom.
As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in ... more >>>

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined ... more >>>