Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Maurice J. Jansen"'
Autor:
Jayalal Sarma, Maurice J. Jansen
Publikováno v:
Theory of Computing Systems. 54:318-336
We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For both arithmetic and Boolean circuits, we show that any circuit of size n O(1) and treewidth O(log i n) can be simulated by a circuit of width O(log
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d60f409d216e478174db1124067f1650
https://doi.org/10.1007/s00224-013-9519-3
https://doi.org/10.1007/s00224-013-9519-3
Autor:
Maurice J. Jansen
Publikováno v:
Theory of Computing Systems. 49:343-354
The determinantal complexity of a polynomial f(x 1,x 2,…,x n ) is the minimum m such that f=det m (L(x 1,x 2,…,x n )), where L(x 1,x 2,…,x n ) is a matrix whose entries are affine forms in the x i s over some field $\mbox {$\mathbb {F}$}$. Asym
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e9a31d1b9fecb127ef5ed95d494e4f0f
https://doi.org/10.1007/s00224-010-9308-1
https://doi.org/10.1007/s00224-010-9308-1
Autor:
Kenneth W. Regan, Maurice J. Jansen
Publikováno v:
Theoretical Computer Science. 409(3):617-622
We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho–Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principle
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4ce85f0474e400f1a7dce855456efe7c
Autor:
Maurice J. Jansen, Jayalal Sarma M. N
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783642131813
Algorithmic tools for graphs of small treewidth are used to address questions in complexity theory. For both arithmetic and Boolean circuits, it is shown that any circuit of size $n^{O(1)}$ and treewidth $O(\log^i n)$ can be simulated by a circuit of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e065471be73448109da8c70a0b35c075
https://doi.org/10.1007/978-3-642-13182-0_21
https://doi.org/10.1007/978-3-642-13182-0_21
Publikováno v:
Computer Science-Theory and Applications ISBN: 9783642033506
CSR
CSR
We study structural properties of restricted width arithmetical circuits. It is shown that syntactically multilinear arithmetical circuits of constant width can be efficiently simulated by syntactically multilinear algebraic branching programs of con
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::eaf635693e63ef8b4c284e9a6d5477ef
https://doi.org/10.1007/978-3-642-03351-3_18
https://doi.org/10.1007/978-3-642-03351-3_18
Autor:
Maurice J. Jansen
Publikováno v:
Computer Science-Theory and Applications ISBN: 9783642033506
CSR
CSR
Asymptotically tight lower bounds are proven for the determinantal complexity of the elementary symmetric polynomial $S^{d}_n$ of degree d in n variables, 2d -fold iterated matrix multiplication of the form , and the symmetric power sum polynomial $\
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::84dc1b8911a474e6f764ee69b31ae45a
https://doi.org/10.1007/978-3-642-03351-3_17
https://doi.org/10.1007/978-3-642-03351-3_17
Autor:
Maurice J. Jansen
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540852377
MFCS
MFCS
It is shown that any weakly-skew circuit can be converted into a skew circuit with constant factor overhead, while preserving either syntactic or semantic multilinearity. This leads to considering syntactically multilinear algebraic branching program
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d2edb743b772f61caada2adb6e4f12ba
https://doi.org/10.1007/978-3-540-85238-4_33
https://doi.org/10.1007/978-3-540-85238-4_33
Autor:
Maurice J. Jansen, Kenneth W. Regan
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540735441
COCOON
COCOON
We derive quadratic lower bounds on the *-complexity of sum-of-products-of-sums (ΣΠΣ) formulas for classes of polynomials f that have too few partial derivatives for the techniques of Shpilka and Wigderson [10,9]. This involves a notion of "resist
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0da1b834b0d7b92ee35c82546f6f81f0
https://doi.org/10.1007/978-3-540-73545-8_46
https://doi.org/10.1007/978-3-540-73545-8_46