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

We give efficient deterministic algorithms for converting randomized queryalgorithms into deterministic ones. We first give an algorithm that takes asinput a randomized $q$-query algorithm $R$ with description length $N$ and aparameter $\varepsilon$, runs in time $\mathrm{poly}(N) \cdot2^{O(q/\varepsilon)}$, and returns a deterministic $O(q/\varepsilon)$-queryalgorithm $D$ that $\varepsilon$-approximates the acceptance probabilities of$R$. These parameters are near-optimal: runtime $N + 2^{\Omega(q/\varepsilon)}$and query complexity $\Omega(q/\varepsilon)$ are necessary.  Next, we give algorithms for instance-optimal and online versions of theproblem:  $\circ$ Instance optimal: Construct a deterministic $q^\star_R$-queryalgorithm $D$, where $q^\star_R$ is minimum query complexity of anydeterministic algorithm that $\varepsilon$-approximates $R$.  $\circ$ Online: Deterministically approximate the acceptance probability of$R$ for a specific input $\underline{x}$ in time$\mathrm{poly}(N,q,1/\varepsilon)$, without constructing $D$ in its entirety.  Applying the techniques we develop for these extensions, we constructivizeclassic results that relate the deterministic, randomized, and quantum querycomplexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998).This has direct implications for the Turing machine model of computation:sublinear-time algorithms for total decision problems can be efficientlyderandomized and dequantized with a subexponential-time preprocessing step.

Constructive derandomization of query algorithms