Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DISCREPANCY METHOD:
Reports tagged with Discrepancy method:
TR11-164 | 9th December 2011
Mark Braverman, Omri Weinstein

#### A discrepancy lower bound for information complexity

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 >>>

TR18-116 | 18th June 2018
Xue Chen, David Zuckerman

Revisions: 1

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 >>> TR20-166 | 9th November 2020 Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay #### Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity Revisions: 1 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 >>>

ISSN 1433-8092 | Imprint