This paper provides the first general technique for proving information lower bounds on two-party
unbounded-rounds communication problems. We show that the discrepancy lower bound, which
applies to randomized communication complexity, also applies to information complexity. More
precisely, if the discrepancy of a two-party function $f$ with respect ... more >>>

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>>

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>