Direct sum theorems state that the cost of solving k instances of a problem is at least \Omega(k) times
the cost of solving a single instance. We prove the first such results in the randomised parity
decision tree model. We show that a direct sum theorem holds whenever (1) the ... more >>>

In function inversion, we are given a function f: [N] \mapsto [N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>

Let \mathcal{F} be a finite alphabet and \mathcal{D} be a finite set of distributions over \mathcal{F}. A Generalized Santha-Vazirani (GSV) source of type (\mathcal{F}, \mathcal{D}), introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence (F_1, \dots, F_n) in \mathcal{F}^n, where F_i is a sample from ... more >>>

A Boolean k-monotone function defined over a finite poset domain {\cal D} alternates between the values 0 and 1 at most k times on any ascending chain in {\cal D}. Therefore, k-monotone functions are natural generalizations of the classical monotone functions, which are the 1-monotone functions.

Motivated by the ... more >>>

We prove that for every n and 1 < t < n any t-out-of-n threshold secret sharing scheme for one-bit secrets requires share size \log(t + 1). Our bound is tight when t = n - 1 and n is a prime power. In 1990 Kilian and Nisan proved ... more >>>