Outside Computation with Superior Functions

Parker Riley, Daniel Gildea


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
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/2021.naacl-main.233.pdf
Video:
 https://aclanthology.org/2021.naacl-main.233.mp4