English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Mahaney's Theorem states that, assuming $\mathsf{P} \neq \mathsf{NP}$, noNP-hard set can have a polynomially bounded number of yes-instances at eachinput length. We give an exposition of a very simple unpublished proof ofManindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of lowinformation content," Theoret. Comp. Sci., 1996). This proof is so simple thatit can easily be taught to undergraduates or a general graduate CS audience -not just theorists! - in about 10 minutes, which the author has donesuccessfully several times. We also include applications of Mahaney's Theoremto fundamental questions that bright undergraduates would ask which could beused to fill the remaining hour of a lecture, as well as an application (due toIkenmeyer, Mulmuley, and Walter, arXiv:1507.02955) to the representation theoryof the symmetric group and the Geometric Complexity Theory Program. To thisauthor, the fact that sparsity results on NP-complete sets have an applicationto classical questions in representation theory says that they are not only agem of classical theoretical computer science, but indeed a gem of mathematics.

NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications