Evasiveness and the Distribution of Prime Numbers

László Babai, Anandam Banerjee, Raghav Kulkarni & Vipul Naik
A Boolean function on $N$ variables is called \emph{evasive} if its decision-tree complexity is $N$. A sequence $B_n$ of Boolean functions is \emph{eventually evasive} if $B_n$ is evasive for all sufficiently large $n$. We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, ``forbidden subgraph $H$'' is eventually evasive and...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.