Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

Existence of Simple Extractors

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