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

We present an $\mathcal{O}^\star(2^{0.5n})$ time and$\mathcal{O}^\star(2^{0.249999n})$ space randomized algorithm for solvingworst-case Subset Sum instances with $n$ integers. This is the firstimprovement over the long-standing $\mathcal{O}^\star(2^{n/2})$ time and$\mathcal{O}^\star(2^{n/4})$ space algorithm due to Schroeppel and Shamir (FOCS1979).  We breach this gap in two steps: (1) We present a space efficient reductionto the Orthogonal Vectors Problem (OV), one of the most central problem inFine-Grained Complexity. The reduction is established via an intricatecombination of the method of Schroeppel and Shamir, and the representationtechnique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010) for designingSubset Sum algorithms for the average case regime. (2) We provide an algorithmfor OV that detects an orthogonal pair among $N$ given vectors in $\{0,1\}^d$with support size $d/4$ in time $\tilde{O}(N\cdot2^d/\binom{d}{d/4})$. Ouralgorithm for OV is based on and refines the representative families frameworkdeveloped by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016).  Our reduction uncovers a curious tight relation between Subset Sum and OV,because any improvement of our algorithm for OV would imply an improvement overthe runtime of Schroeppel and Shamir, which is also a long standing openproblem.

Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors