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

In recent work, we formalized the theory of optimal-size sorting networkswith the goal of extracting a verified checker for the large-scalecomputer-generated proof that 25 comparisons are optimal when sorting 9 inputs,which required more than a decade of CPU time and produced 27 GB of proofwitnesses. The checker uses an untrusted oracle based on these witnesses and isable to verify the smaller case of 8 inputs within a couple of days, but it didnot scale to the full proof for 9 inputs. In this paper, we describe severalnon-trivial optimizations of the algorithm in the checker, obtained byappropriately changing the formalization and capitalizing on the symbiosis withan adequate implementation of the oracle. We provide experimental evidence oforders of magnitude improvements to both runtime and memory footprint for 8inputs, and actually manage to check the full proof for 9 inputs.

Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof