dc.contributor.author | Diaz Andino, Fidel Ernesto | |
dc.contributor.author | Kokkou, Maria | |
dc.contributor.author | Oliveira, Mateus De Oliveira | |
dc.contributor.author | Vadiee, Farhad | |
dc.date.accessioned | 2022-04-26T06:57:47Z | |
dc.date.available | 2022-04-26T06:57:47Z | |
dc.date.created | 2021-09-13T23:22:58Z | |
dc.date.issued | 2021 | |
dc.identifier.issn | 2640-3498 | |
dc.identifier.uri | https://hdl.handle.net/11250/2992660 | |
dc.description.abstract | Bounded 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.language.iso | eng | en_US |
dc.publisher | Proceedings of Machine Learning Research | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Unitary Branching Programs: Learnability and Lower Bounds | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2021 the authors | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.cristin | 1933964 | |
dc.source.journal | Proceedings of Machine Learning Research (PMLR) | en_US |
dc.source.pagenumber | 297-306 | en_US |
dc.relation.project | Norges forskningsråd: 288761 | en_US |
dc.relation.project | Notur/NorStore: NN9535K | en_US |
dc.identifier.citation | Proceedings of Machine Learning Research (PMLR). 2021, 139, 297-306. | en_US |
dc.source.volume | 139 | en_US |