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

The theory of holographic algorithms introduced by Valiant represents a novelapproach to achieving polynomial-time algorithms for seemingly intractablecounting problems via a reduction to counting planar perfect matchings and alinear change of basis. Two fundamental parameters in holographic algorithmsare the \emph{domain size} and the \emph{basis size}. Roughly, the domain sizeis the range of colors involved in the counting problem at hand (e.g. countinggraph $k$-colorings is a problem over domain size $k$), while the basis size$\ell$ captures the dimensionality of the representation of those colors. Amajor open problem has been: for a given $k$, what is the smallest $\ell$ forwhich any holographic algorithm for a problem over domain size $k$ "collapsesto" (can be simulated by) a holographic algorithm with basis size $\ell$? Caiand Lu showed in 2008 that over domain size 2, basis size 1 suffices, openingthe door to an extensive line of work on the structural theory of holographicalgorithms over the Boolean domain. Cai and Fu later showed for signatures offull rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively,suffice, and they conjectured that over domain size $k$ there is a collapse tobasis size $\lfloor\log_2 k\rfloor$. In this work, we resolve this conjecturein the affirmative for signatures of full rank for all $k$.

Basis Collapse for Holographic Algorithms Over All Domain Sizes