Zobrazeno 1 - 4
of 4
pro vyhledávání: '"Anuj Tawari"'
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783030794156
CSR
CSR
Dynamic Complexity was introduced by Immerman and Patnaik [25] (see also [14]). It has seen a resurgence of interest in the recent past, see [2, 4, 8, 9, 10, 11, 12, 24, 26, 30, 31] for some representative examples. Use of linear algebra has been a n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ad93c2b2c98963ebe1da8748917398b9
https://doi.org/10.1007/978-3-030-79416-3_4
https://doi.org/10.1007/978-3-030-79416-3_4
Publikováno v:
International Journal of Advances in Engineering Sciences and Applied Mathematics. 11:68-74
We study bounded-depth $$(\min ,+)$$ formulas computing the shortest path polynomial. For depth 2d with $$d \ge 2$$ , we obtain lower bounds parameterized by certain fan-in restrictions on $$+$$ gates except those at the bottom level. For depth 4, in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::22c68263641b7b074dff89b7595fdb6e
https://doi.org/10.1007/s12572-018-0229-6
https://doi.org/10.1007/s12572-018-0229-6
Autor:
Meena Mahajan, Anuj Tawari
Publikováno v:
Theoretical Computer Science. 708:34-45
An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over + , × where each variable labels at most one leaf. Every multilinear polynomial can be expressed as the sum of (possibly exponentially many) ROFs. In this work, we prove,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cce859774e4c10e9204b9d3332b9c632
https://doi.org/10.1016/j.tcs.2017.10.019
https://doi.org/10.1016/j.tcs.2017.10.019
Autor:
Anuj Tawari, Meena Mahajan
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783319341705
CSR
CSR
An arithmetic read-once formula ROF is a formula circuit of fan-out 1 over $$+, \times $$ where each variable labels at most one leaf. Every multilinear polynomial can be expressed as the sum of ROFs. In this work, we prove, for certain multilinear p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::196789c88703639c3efdacac358591bd
https://doi.org/10.1007/978-3-319-34171-2_19
https://doi.org/10.1007/978-3-319-34171-2_19