Show simple item record

dc.contributor.authorDiaz Andino, Fidel Ernesto
dc.contributor.authorKokkou, Maria
dc.contributor.authorOliveira, Mateus De Oliveira
dc.contributor.authorVadiee, Farhad
dc.description.abstractBounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination of Neciporuk’s lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.en_US
dc.publisherProceedings of Machine Learning Researchen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleUnitary Branching Programs: Learnability and Lower Boundsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2021 the authorsen_US
dc.source.journalProceedings of Machine Learning Research (PMLR)en_US
dc.relation.projectNorges forskningsråd: 288761en_US
dc.relation.projectNotur/NorStore: NN9535Ken_US
dc.identifier.citationProceedings of Machine Learning Research (PMLR). 2021, 139, 297-306.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal