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

How fast can you test whether a constellation of stars appears in the nightsky? This question can be modeled as the computational problem of testingwhether a set of points $P$ can be moved into (or close to) another set $Q$under some prescribed group of transformations.  Consider, as a simple representative, the following problem: Given two setsof at most $n$ integers $P,Q\subseteq[N]$, determine whether there is someshift $s$ such that $P$ shifted by $s$ is a subset of $Q$, i.e.,$P+s=\{p+s:p\in P\}\subseteq Q$. This problem, to which we refer as theConstellation problem, can be solved in near-linear time $O(n\log n)$ by aMonte Carlo randomized algorithm [Cardoze, Schulman; FOCS'98] and time$O(n\log^2 N)$ by a Las Vegas randomized algorithm [Cole, Hariharan; STOC'02].Moreover, there is a deterministic algorithm running in time$n\cdot2^{O(\sqrt{\log n\log\log N})}$ [Chan, Lewenstein; STOC'15]. Aninteresting question left open by these previous works is whether Constellationis in deterministic near-linear time (i.e., with only polylogarithmicoverhead).  We answer this question positively by giving an $n\cdot(\log N)^{O(1)}$-timedeterministic algorithm for the Constellation problem. Our algorithm extends tovarious more complex Point Pattern Matching problems in higher dimensions,under translations and rigid motions, and possibly with mismatches, and also toa near-linear-time derandomization of the Sparse Wildcard Matching problem onstrings.  We find it particularly interesting how we obtain our deterministicalgorithm. All previous algorithms are based on the same baseline idea, usingadditive hashing and the Fast Fourier Transform. In contrast, our algorithmsare based on new ideas, involving a surprising blend of combinatorial andalgebraic techniques. At the heart lies an innovative application of theBaur-Strassen theorem from algebraic complexity theory.

Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem