Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COIN PROBLEM:
Reports tagged with coin problem:
TR17-090 | 15th May 2017
Chin Ho Lee, Emanuele Viola

#### The coin problem for product tests

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$
where the $X_i$ are independent and each $X_i$ equals $1$ with
probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We
consider the smallest value $\eps^*$ of $\eps$ such that the distributions
$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant
more >>>

TR18-157 | 10th September 2018
Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

#### The Coin Problem in Constant Depth: Sample Complexity and Parity gates

Revisions: 2

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... more >>>

TR19-018 | 18th February 2019
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

#### AC0[p] Lower Bounds against MCSP via the Coin Problem

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

TR19-087 | 10th June 2019
Rohit Agrawal

Revisions: 1

In this note we compare two measures of the complexity of a class $\mathcal F$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal ... more >>> TR19-133 | 2nd October 2019 Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi #### More on$AC^0[\oplus]$and Variants of the Majority Function Revisions: 1 In this paper we prove two results about$AC^0[\oplus]$circuits. We show that for$d(N) = o(\sqrt{\log N/\log \log N})$and$N \leq s(N) \leq 2^{dN^{1/d^2}}$there is an explicit family of functions$\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$such that$f_N$has uniform$AC^0$formulas of depth$d$and size at ... more >>> TR20-046 | 13th April 2020 Srikanth Srinivasan #### A Robust Version of Heged\H{u}s's Lemma, with Applications Heged\H{u}s's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field$\mathbb{F}$of characteristic$p > 0$and for$q$a power of$p$, the lemma says that any multilinear polynomial$P\in \mathbb{F}[x_1,\ldots,x_n]$of degree less than$q$that vanishes at all points in$\{0,1\}^n$of ... 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