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

A \emph{coloring} of a graph is an assignment of colors to vertices such thatno two neighboring vertices have the same color. The need for memory-efficientcoloring algorithms is motivated by their application in computing cliquepartitions of graphs arising in quantum computations where the objective is tomap a large set of Pauli strings into a compact set of unitaries. We present\texttt{Picasso}, a randomized memory-efficient iterative parallel graphcoloring algorithm with theoretical sublinear space guarantees under practicalassumptions. The parameters of our algorithm provide a trade-off betweencoloring quality and resource consumption. To assist the user, we also proposea machine learning model to predict the coloring algorithm's parametersconsidering these trade-offs. We provide a sequential and a parallelimplementation of the proposed algorithm.  We perform an experimental evaluation on a 64-core AMD CPU equipped with 512GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small datasetwhere existing coloring algorithms can be executed within the 512 GB memorybudget, we show up to {\bf 68$\times$} memory savings. On massive datasets wedemonstrate that GPU-accelerated \pic{} can process inputs with {\bf49.5$\times$} more Pauli strings (vertex set in our graph) and {\bf2,478$\times$} more edges than state-of-the-art parallel approaches.

\texttt{Picasso}: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing