Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MAJORITY:
Reports tagged with majority:
TR07-130 | 3rd December 2007
Ronen Shaltiel, Emanuele Viola

#### Hardness amplification proofs require majority

Hardness amplification is the fundamental task of
converting a $\delta$-hard function $f : {0,1}^n -> {0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,
where $f$ is $\gamma$-hard if small circuits fail to
compute $f$ on at least a $\gamma$ fraction of the
inputs. Typically, $\eps,\delta$ are small (and
$\delta=2^{-k}$ captures the case ... more >>>

TR14-173 | 13th December 2014
Igor Carboni Oliveira, Rahul Santhanam

#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

TR16-158 | 9th October 2016

#### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

TR17-174 | 13th November 2017
Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

#### On Expressing Majority as a Majority of Majorities

If $k<n$, can one express the majority of $n$ bits as the majority of at most $k$ majorities, each of at most $k$ bits? We prove that such an expression is possible only if $k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>>

TR18-133 | 26th July 2018
Emanuele Viola

#### Constant-error pseudorandomness proofs from hardness require majority

Revisions: 1

Research in the 80's and 90's showed how to construct a pseudorandom
generator from a function that is hard to compute on more than $99\%$
of the inputs. A more recent line of works showed however that if
the generator has small error, then the proof of correctness cannot
be ... more >>>

TR19-026 | 28th February 2019
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

Revisions: 1

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets $S_1,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,n\}$ of size $n/2$, there is an $i \in [k]$ so that $|S_i \cap X| = ... more >>> TR19-073 | 17th May 2019 Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan #### Parity helps to compute Majority We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC$^0[\oplus]$circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth-$d$AC$^0[\oplus]$circuits of size$2^{\Omega(n^{1/2(d-1)})}$. By using a divide-and-conquer approach, it is easy to show that Majority can ... more >>> TR20-139 | 11th September 2020 Mark Braverman, Sumegha Garg, David Woodruff #### The Coin Problem with Applications to Data Streams Consider the problem of computing the majority of a stream of$n$i.i.d. uniformly random bits. This problem, known as the {\it coin problem}, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant ... more >>> TR21-083 | 21st June 2021 Mark Braverman, Sumegha Garg, Or Zamir #### Tight Space Complexity of the Coin Problem In the coin problem we are asked to distinguish, with probability at least$2/3$, between$ni.i.d.$coins which are heads with probability$\frac{1}{2}+\beta$from ones which are heads with probability$\frac{1}{2}-\beta\$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>

ISSN 1433-8092 | Imprint