Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output ... more >>>
Linear decision lists are a computational model for Boolean functions built from a sequence of linear threshold function queries. Each query is evaluated in order: if a query returns true, the list outputs the value of the function, and if the answer is false, the process continues to the next ... more >>>
We study the randomized communication complexity of the equality function in the public-coin model. Although the communication complexity of this function is known to be low in the setting where error probability is constant and a large number of random bits are available to players, the complexity grows if the ... more >>>