Author name cluster

Pushkar S. Joglekar

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

I&C Journal 2024 Journal Article

Multivariate to bivariate reduction for noncommutative polynomial factorization

V. Arvind
Pushkar S. Joglekar

Based on Bergman's theorem, we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, 1. Given an n-variate noncommutative polynomial f ∈ F 〈 X 〉 over a field F as an arithmetic circuit, computing a complete factorization of f into irreducible factors is deterministic polynomial-time reducible to factorization of a noncommutative bivariate polynomial g ∈ F 〈 x, y 〉; the reduction transforms f into a circuit for g, and given a complete factorization of g, the reduction recovers a complete factorization of f in polynomial time. The reduction works both in the white-box and the black-box setting. 2. We show over the field of rationals that bivariate linear matrix factorization problem for 4 × 4 matrices is at least as hard as factoring square-free integers and for 3 × 3 matrices it is in polynomial time.

Details DOI

MFCS Conference 2023 Conference Paper

Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

Vikraman Arvind
Pushkar S. Joglekar

Based on a theorem of Bergman [Cohn, 2006] we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following: 1) In the white-box setting, given an n-variate noncommutative polynomial f ∈ 𝔽⟨X⟩ over a field 𝔽 (either a finite field or the rationals) as an arithmetic circuit (or algebraic branching program), computing a complete factorization of f into irreducible factors is deterministic polynomial-time reducible to white-box factorization of a noncommutative bivariate polynomial g ∈ 𝔽⟨x, y⟩; the reduction transforms f into a circuit for g (resp. ABP for g), and given a complete factorization of g (namely, arithmetic circuits (resp. ABPs) for irreducible factors of g) the reduction recovers a complete factorization of f in polynomial time. We also obtain a similar deterministic polynomial-time reduction in the black-box setting. 2) Additionally, we show over the field of rationals that bivariate linear matrix factorization of 4× 4 matrices is at least as hard as factoring square-free integers. This indicates that reducing noncommutative polynomial factorization to linear matrix factorization (as done in [Vikraman Arvind and Pushkar S. Joglekar, 2022]) is unlikely to succeed over the field of rationals even in the bivariate case. In contrast, multivariate linear matrix factorization for 3×3 matrices over rationals is in polynomial time.

Details

STOC Conference 2017 Conference Paper

Randomized polynomial time identity testing for noncommutative circuits

Vikraman Arvind
Pushkar S. Joglekar
Partha Mukhopadhyay
S. Raja 0001

In this paper we show that black-box polynomial identity testing for noncommutative polynomials f ∈𝔽⟨ z 1 , z 2 ,…, z n ⟩ of degree D and sparsity t , can be done in randomized ( n ,log t ,log D ) time. As a consequence, given a circuit C of size s computing a polynomial f ∈𝔽⟨ z 1 , z 2 ,…, z n ⟩ with at most t non-zero monomials, then testing if f is identically zero can be done by a randomized algorithm with running time polynomial in s and n and log t . This makes significant progress on a question that has been open for over ten years. Our algorithm is based on automata-theoretic ideas that can efficiently isolate a monomial in the given polynomial. In particular, we carry out the monomial isolation using nondeterministic automata.

Details

MFCS Conference 2009 Conference Paper

Arithmetic Circuits, Monomial Algebras and Finite Automata

Vikraman Arvind
Pushkar S. Joglekar

Abstract We study lower bounds for circuit and branching program size over monomial algebras both in the noncommutative and commutative setting. Our main tool is automata theory and the main results are: An extension of Nisan’s noncommutative algebraic branching program size lower bounds [N91] over the free noncommutative ring \({\mathbb F}\langle{x_1, x_2, \cdots, x_n}\rangle\) to similar lower bounds over the noncommutative monomial algebras \({\ensuremath{\mathbb{F}}}\langle{x_1, x_2, \cdots, x_n}\rangle/I\) for a monomial ideal I generated by subexponential number of monomials. An extension of the exponential size lower bounds for monotone commutative circuits [JS82] computing the Permanent in ℚ[ x 11, x 12, ⋯, x nn ] to an exponential lower bound for monotone commutative circuits computing the Permanent in any monomial algebra ℚ[ x 11, x 12, ⋯, x nn ]/ I such that the monomial ideal I is generated by o ( n /log n ) monomials.

Details