<p>The <a href="https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem" rel="nofollow noreferrer">Wikipedia article</a> about the Karp-Lipton theorem (<span class="math-container">$NP\subseteq P/poly$</span> implies <span class="math-container">$\Sigma_2=\Pi_2$</span>), says the following:</p>
<blockquote>
<p>The Karp–Lipton theorem is named after Richard M. Karp and Richard J.
Lipton, who first proved it in 1980. (Their original proof collapsed
PH to <span class="math-container">$\Sigma_3$</span>, but Michael Sipser improved it to <span class="math-container">$\Sigma_2$</span>)</p>
</blockquote>
<p>However, there's no reference to where Sipser proved this improvement.</p>
<p>Where can I find Sipser's improved proof of Karp-Lipton theorem?</p>
<p><strong>Edit</strong>: to be clear, I'm looking for the original reference, not other resources explaining the result</p>

CC BY-SA 4.0
2023-06-26T14:53:08.467Z
I recommend you to watch [lecture 8 of 15-855 by Prof. Ryan O'Donnell](https://www.youtube.com/watch?v=v02KnpmS0EY&list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH&index=8), or the lecture notes at [here](https://www.cs.cmu.edu/~odonnell/complexity17/odonnell-graduate-complexity-notes.pdf).
Heda Chen
CC BY-SA 4.0
2023-06-26T15:06:10.290Z
Thanks! I'm looking for the original reference, not other resources explaining it. I've clarified it in the question
Nicola Gigante
CC BY-SA 4.0
2023-06-26T15:21:38.750Z
In their original paper [\[STOC'80\] Some connections between nonuniform and uniform complexity classes](https://dl.acm.org/doi/pdf/10.1145/800141.804678), they mentioned "an improvement by Michael Sipser of an early result of ours", but no related reference is found. I guess maybe the original improvement is not published in a place that is easy to found.
Heda Chen
<cc.complexity-theory><reference-request><circuit-complexity>
Original references for Karp-Lipton theorem improvement by Sipser
Nicola Gigante
# Original references for Karp-Lipton theorem improvement by Sipser

(Asked by: username_0 on 2023-06-26)

The [Wikipedia article](https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem) about the Karp-Lipton theorem ($NP\subseteq P/poly$ implies $\Sigma\_2=\Pi\_2$), says the following:

> The Karp–Lipton theorem is named after Richard M. Karp and Richard J.
> Lipton, who first proved it in 1980. (Their original proof collapsed
> PH to $\Sigma\_3$, but Michael Sipser improved it to $\Sigma\_2$)

However, there's no reference to where Sipser proved this improvement.

Where can I find Sipser's improved proof of Karp-Lipton theorem?

**Edit**: to be clear, I'm looking for the original reference, not other resources explaining the result

**Tags:** cc.complexity-theory, reference-request, circuit-complexity
> **Comments:**
> **username_1**: I recommend you to watch [lecture 8 of 15-855 by Prof. Ryan O'Donnell](https://www.youtube.com/watch?v=v02KnpmS0EY&list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH&index=8), or the lecture notes at [here](https://www.cs.cmu.edu/~odonnell/complexity17/odonnell-graduate-complexity-notes.pdf).  
> **username_0**: Thanks! I'm looking for the original reference, not other resources explaining it. I've clarified it in the question  
> **username_1**: In their original paper [\[STOC'80\] Some connections between nonuniform and uniform complexity classes](https://dl.acm.org/doi/pdf/10.1145/800141.804678), they mentioned "an improvement by Michael Sipser of an early result of ours", but no related reference is found. I guess maybe the original improvement is not published in a place that is easy to found.  

---

## 0 answers

