Zobrazeno 1 - 10
of 53
pro vyhledávání: '"Arvind, Vikraman"'
Autor:
Arvind, Vikraman, Joglekar, Pushkar S
We study the noncommutative rank problem, ncRANK, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of noncommutative Rational Identity Testing, RIT, which is to decide if a given rational formula in
Externí odkaz:
http://arxiv.org/abs/2404.16382
An arc-colored tournament is said to be $k$-spanning for an integer $k\geq 1$ if the union of its arc-color classes of maximal valency at most $k$ is the arc set of a strongly connected digraph. It is proved that isomorphism testing of $k$-spanning t
Externí odkaz:
http://arxiv.org/abs/2201.12312
We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace A
Externí odkaz:
http://arxiv.org/abs/2108.05914
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorph
Externí odkaz:
http://arxiv.org/abs/2107.10689
An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size $s$ can com
Externí odkaz:
http://arxiv.org/abs/1611.07235
Autor:
Arvind, Vikraman, Rattan, Gaurav
We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous best running time bound of $O^*(2^{O(k^2/\log k)})$.
Externí odkaz:
http://arxiv.org/abs/1408.3510
Autor:
Arvind, Vikraman
In this paper we study the parameterized complexity of two well-known permutation group problems which are NP-complete. 1. Given a permutation group G=, subgroup of $S_n$, and a parameter $k$, find a permutation $\pi$ in G such that $|{i\in [n]\mi
Externí odkaz:
http://arxiv.org/abs/1301.0379
Autor:
Arvind, Vikraman, Srinivasan, Srikanth
We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Rem
Externí odkaz:
http://arxiv.org/abs/0911.4337
Autor:
Arvind, Vikraman, Srinivasan, Srikanth
Using $\epsilon$-bias spaces over $F_2$, we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to group
Externí odkaz:
http://arxiv.org/abs/0909.5313
Určit algoritmickou složitost problému isomorfizmu grafů je jeden z nejdůležitejších otevřených problémů teoretické informatiky. Je známé, že testování isomorfizmu chordálních grafů je polynomiálně ekvivalentní obecnému probl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od______8936::b1b3a23581e52b153c319eae4f0cf6e1
http://hdl.handle.net/11025/50747
http://hdl.handle.net/11025/50747