Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NUMBER-ON-FOREHEAD MODEL:
TR17-184 | 29th November 2017

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are ... more >>>

TR18-200 | 29th November 2018
Ashutosh Kumar, Raghu Meka, Amit Sahai

Leakage-Resilient Secret Sharing

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an ... more >>>

ISSN 1433-8092 | Imprint