Zobrazeno 1 - 4
of 4
pro vyhledávání: '"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