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

The field of fine-grained complexity aims at proving conditional lower boundson the time complexity of computational problems. One of the most popularassumptions, Strong Exponential Time Hypothesis (SETH), implies that SAT cannotbe solved in $2^{(1-\epsilon)n}$ time. In recent years, it has been proved thatknown algorithms for many problems are optimal under SETH. Despite the wideapplicability of SETH, for many problems, there are no known SETH-based lowerbounds, so the quest for new reductions continues.  Two barriers for proving SETH-based lower bounds are known. Carmosino et al.(ITCS 2016) introduced the Nondeterministic Strong Exponential Time Hypothesis(NSETH) stating that TAUT cannot be solved in time $2^{(1-\epsilon)n}$ even ifone allows nondeterminism. They used this hypothesis to show that some naturalfine-grained reductions would be difficult to obtain: proving that, say, 3-SUMrequires time $n^{1.5+\epsilon}$ under SETH, breaks NSETH and this, in turn,implies strong circuit lower bounds. Recently, Belova et al. (SODA 2023)introduced the so-called polynomial formulations to show that for many NP-hardproblems, proving any explicit exponential lower bound under SETH also impliesstrong circuit lower bounds.  We prove that for a range of problems from P, including $k$-SUM and triangledetection, proving superlinear lower bounds under SETH is challenging as itimplies new circuit lower bounds. To this end, we show that these problems canbe solved in nearly linear time with oracle calls to evaluating a polynomial ofconstant degree. Then, we introduce a strengthening of SETH stating thatsolving SAT in time $2^{(1-\varepsilon)n}$ is difficult even if one hasconstant degree polynomial evaluation oracle calls. This hypothesis is strongerand less believable than SETH, but refuting it is still challenging: we showthat this implies circuit lower bounds.

Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds