What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses
<|reference_start|>What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses: During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of this nine-paper progression actually achieve downward collapse---that is, they show that high-level collapses induce collapses at (what beforehand were thought to be) lower complexity levels. For example, for each $k\geq 2$ it is now known that if $\psigkone=\psigktwo$ then $\ph=\sigmak$. This article surveys the history, the results, and the technique---the so-called easy-hard method---of these nine papers.<|reference_end|>
@article{hemaspaandra1999what's,
    title={What's Up with Downward Collapse: Using the Easy-Hard Technique to Link
  Boolean and Polynomial Hierarchy Collapses},
    author={Edith Hemaspaandra, Lane A. Hemaspaandra, and Harald Hempel},
    journal={arXiv preprint arXiv:cs/9910002},
    year={1999},
    number={UR-CS-TR-98-682},
    archivePrefix={arXiv},
    eprint={cs/9910002},
    primaryClass={cs.CC}
}