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/

Zendy Plus

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

Zendy Tools

Zendy Open

Several recent works have considered the \emph{trace reconstruction problem},in which an unknown source string $x\in\{0,1\}^n$ is transmitted through aprobabilistic channel which may randomly delete coordinates or insert randombits, resulting in a \emph{trace} of $x$. The goal is to reconstruct theoriginal string~$x$ from independent traces of $x$. While the best algorithmsknown for worst-case strings use $\exp(O(n^{1/3}))$ traces\cite{DOS17,NazarovPeres17}, highly efficient algorithms are known\cite{PZ17,HPP18} for the \emph{average-case} version, in which $x$ isuniformly random. We consider a generalization of this average-case tracereconstruction problem, which we call \emph{average-case population recovery inthe presence of insertions and deletions}. In this problem, there is an unknowndistribution $\cal{D}$ over $s$ unknown source strings $x^1,\dots,x^s \in\{0,1\}^n$, and each sample is independently generated by drawing some $x^i$from $\cal{D}$ and returning an independent trace of $x^i$.  Building on \cite{PZ17} and \cite{HPP18}, we give an efficient algorithm forthis problem. For any support size $s \leq \smash{\exp(\Theta(n^{1/3}))}$, fora $1-o(1)$ fraction of all $s$-element support sets $\{x^1,\dots,x^s\} \subset\{0,1\}^n$, for every distribution $\cal{D}$ supported on $\{x^1,\dots,x^s\}$,our algorithm efficiently recovers ${\cal D}$ up to total variation distance$\epsilon$ with high probability, given access to independent traces ofindependent draws from $\cal{D}$. The algorithm runs in timepoly$(n,s,1/\epsilon)$ and its sample complexity ispoly$(s,1/\epsilon,\exp(\log^{1/3}n)).$ This polynomial dependence on thesupport size $s$ is in sharp contrast with the \emph{worst-case} version (when$x^1,\dots,x^s$ may be any strings in $\{0,1\}^n$), in which the samplecomplexity of the most efficient known algorithm \cite{BCFSS19} is doublyexponential in $s$.

Efficient average-case population recovery in the presence of insertions and deletions