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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In recent years much effort was put into developing polynomial-timeconditional lower bounds for algorithms and data structures in both static anddynamic settings. Along these lines we suggest a framework for provingconditional lower bounds based on the well-known 3SUM conjecture. Our frameworkcreates a \emph{compact representation} of an instance of the 3SUM problemusing hashing and domain specific encoding. This compact representation admitsfalse solutions to the original 3SUM problem instance which we reveal andeliminate until we find a true solution. In other words, from all\emph{witnesses} (candidate solutions) we figure out if an \emph{honest} one (atrue solution) exists. This enumeration of witnesses is used to proveconditional lower bound on \emph{reporting} problems that generate allwitnesses. In turn, these reporting problems are reduced to various decisionproblems. These help to enumerate the witnesses by constructing appropriatesearch data structures. Hence, 3SUM-hardness of the decision problems isdeduced.  We utilize this framework to show conditional lower bounds for severalvariants of convolutions, matrix multiplication and string problems. Ourframework uses a strong connection between all of these problems and theability to find \emph{witnesses}.  While these specific applications are used to demonstrate the techniques ofour framework, we believe that this novel framework is useful for many otherproblems as well.

How Hard is it to Find (Honest) Witnesses?