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

The algorithm and complexity of approximating the permanent of a matrix is anextensively studied topic. Recently, its connection with quantum supremacy andmore specifically BosonSampling draws special attention to the average-caseapproximation problem of the permanent of random matrices with zero or smallmean value for each entry. Eldar and Mehraban (FOCS 2018) gave aquasi-polynomial time algorithm for random matrices with mean at least$1/\mathbf{\mathrm{polyloglog}} (n)$. In this paper, we improve the result bydesigning a deterministic quasi-polynomial time algorithm and a PTAS for randommatrices with mean at least $1/\mathbf{\mathrm{polylog}}(n)$. We note that ifit can be further improved to $1/\mathbf{\mathrm{poly}}(n)$, it will disprove acentral conjecture for quantum supremacy.  Our algorithm is also much simpler and has a better and flexible trade-offfor running time. The running time can be quasi-polynomial in both $n$ and$1/\epsilon$, or PTAS (polynomial in $n$ but exponential in $1/\epsilon$),where $\epsilon$ is the approximation parameter.

Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler