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
∙
03/10/2023
Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
Based on a theorem of Bergman we show that multivariate noncommutative p...
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
∙
06/02/2022
Recognizing the Commuting Graph of a Finite Group
In this paper we study the realizability question for commuting graphs o...
research
∙
03/31/2022
Matrix Polynomial Factorization via Higman Linearization
In continuation to our recent work on noncommutative polynomial factoriz...
research
∙
02/20/2022
On Efficient Noncommutative Polynomial Factorization via Higman Linearization
In this paper we study the problem of efficiently factorizing polynomial...
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
∙
10/24/2019
On the Weisfeiler-Leman Dimension of Fractional Packing
The k-dimensional Weisfeiler-Leman procedure (k-WL), which colors k-tupl...
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
∙
11/09/2018
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
We investigate graph properties and parameters that are invariant under ...
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
A Note on Polynomial Identity Testing for Depth-3 Circuits
Let C be a depth-3 arithmetic circuit of size at most s, computing a pol...
research
∙
09/28/2017