We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{0,1\}^m\to\{0,1\}^n$ be a Boolean function where each output bit of $f$ depends only on $O(1)$ input bits. Assume the output distribution of $f$ on uniform input bits is close to a uniform distribution $\mathcal D$ with ... more >>>

First of all we give some reasons that “natural proofs” built not a barrier to prove P not= NP using Boolean complexity. Then we investigate the approximation method for its extension to prove super-polynomial lower bounds for the non-monotone complexity of suitable Boolean functions in NP or to understand why ... more >>>

Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitivity have been developed for many problems, no sensitivity lower bounds were previously known for approximation algorithms. In this work, we establish the ... more >>>