research
∙
08/09/2023
On Lifting Lower Bounds for Noncommutative Circuits using Automata
We revisit the main result of Carmosino et al <cit.> which shows that an...
share
research
∙
08/08/2023
Determinants vs. Algebraic Branching Programs
We show that for every homogeneous polynomial of degree d, if it has det...
research
∙
05/17/2023
The Noncommutative Edmonds' Problem Re-visited
Let T be a matrix whose entries are linear forms over the noncommutative...
research
∙
05/17/2023
Border Complexity of Symbolic Determinant under Rank One Restriction
VBP is the class of polynomial families that can be computed by the dete...
research
∙
09/11/2022
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
The identity testing of rational formulas (RIT) in the free skew field e...
research
∙
02/11/2022
Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time
Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of ...
research
∙
08/22/2019
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
We study the arithmetic circuit complexity of some well-known family of ...
research
∙
04/28/2019
Efficient Black-Box Identity Testing over Free Group Algebra
Hrubeš and Wigderson [HW14] initiated the study of noncommutative arithm...
research
∙
08/31/2018
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
Let F[X] be the polynomial ring over the variables X={x_1,x_2, ..., x_n}...
research
∙
07/12/2018
Fast Exact Algorithms Using Hadamard Product of Polynomials
In this paper we develop an efficient procedure for computing a (scaled)...
research
∙
05/17/2018