Outside Computation with Superior Functions

Parker Riley; Daniel Gildea

NAACL 2021long0 citations

Outside Computation with Superior Functions

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).

BibTeX

@inproceedings{riley-gildea-2021-outside,
    title = "Outside Computation with Superior Functions",
    author = "Riley, Parker  and
      Gildea, Daniel",
    editor = "Toutanova, Kristina  and
      Rumshisky, Anna  and
      Zettlemoyer, Luke  and
      Hakkani-Tur, Dilek  and
      Beltagy, Iz  and
      Bethard, Steven  and
      Cotterell, Ryan  and
      Chakraborty, Tanmoy  and
      Zhou, Yichao",
    booktitle = "Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies",
    month = jun,
    year = "2021",
    address = "Online",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/2021.naacl-main.233/",
    doi = "10.18653/v1/2021.naacl-main.233",
    pages = "2936--2940"
}