Abstract
We show that a general algorithm for efficient computation of outside values under the minimum of superior functions framework proposed by Knuth (1977) would yield a sub-exponential time algorithm for SAT, violating the Strong Exponential Time Hypothesis (SETH).- Anthology ID:
- 2021.naacl-main.233
- Volume:
- Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
- Month:
- June
- Year:
- 2021
- Address:
- Online
- Editors:
- Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, Yichao Zhou
- Venue:
- NAACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 2936–2940
- Language:
- URL:
- https://aclanthology.org/2021.naacl-main.233
- DOI:
- 10.18653/v1/2021.naacl-main.233
- Cite (ACL):
- Parker Riley and Daniel Gildea. 2021. Outside Computation with Superior Functions. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2936–2940, Online. Association for Computational Linguistics.
- Cite (Informal):
- Outside Computation with Superior Functions (Riley & Gildea, NAACL 2021)
- PDF:
- https://preview.aclanthology.org/ingest-acl-2023-videos/2021.naacl-main.233.pdf