Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Jayalal Sarma, M."'
We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several cla
Externí odkaz:
http://arxiv.org/abs/1302.3308
We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et. al. (2012). Proving a super-polynomial lower bound for the size of nondeterministic thrifty branching pr
Externí odkaz:
http://arxiv.org/abs/1301.1425
Publikováno v:
Computational Complexity 23 (2014), 531-563
The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977), rigidity and similar rank-robustness functio
Externí odkaz:
http://arxiv.org/abs/0910.5301
Autor:
Jansen, Maurice, N, Jayalal Sarma M.
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:
http://arxiv.org/abs/0910.1427
Autor:
Raghavendra Rao, B.1 bvrr@cs.uni-sb.de, Jayalal Sarma, M.2 jayalal@tsinghua.edu.cn
Publikováno v:
Theory of Computing Systems. Aug2011, Vol. 49 Issue 2, p246-272. 27p. 1 Diagram, 1 Chart.
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:
arXiv
Original manuscript September 23, 2012
The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977),
The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977),
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fbe9c6a4d2d2a8411a179fe8449de318
Publikováno v:
WALCOM: Algorithms & Computation (9783642360640); 2013, p274-285, 12p
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.