Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86

Håstad, J. (1986). Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. ACM.

Type

Unclassified

Intellectual base

Unclassified

Year

1986

DOI

10.1145/12130.12132

Link

https://doi.org/10.1145/12130.12132

Cited by

1 citation across 1 artifact.

Domain-specific

• Switching lemma
  • Hastad's switching lemma underpins exponential lower bounds for constant-depth circuits, pseudorandomness, Fourier concentration, derandomization, and stronger multi-switching variants.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:e56d6e13b84e · see in the full table