Sayak Chakrabarti

We study the problem of solving a system of n-variate m polynomials over the ring of integers modulo a prime-power p^k. The problem over finite fields is well studied in varied parameter settings. For small characteristic p = 2, Lokshtanov et al. (SODA'17) initiated the study, for degree d = 2 systems, to improve the brute force complexity of O(2ⁿ) to O(2^0.8765n), which currently is improved to O(2^0.6943n) in Dinur (SODA'21). For large p but constant n, Huang and Wong (FOCS'96) gave a randomized poly(d, m, log p) time algorithm. Note that for growing n, system-solving is known to be intractable even with p = 2 and degree d = 2.

We devise a randomized poly(d, m, log p)-time algorithm to find a root of a given system of m integral polynomials of degrees bounded by d, in n variables, modulo a prime power p^k, when n + k is constant. In a way, we extend the efficient algorithm of Huang and Wong (FOCS'96) for system-solving over Galois fields (i.e. characteristic p) to that over Galois rings (i.e. characteristic p^k), when k > 1 is constant. The challenge here is to find a lift of singular 𝔽_p-roots (exponentially many), as there is no efficient general way known in algebraic geometry for resolving singularities.

Our algorithm has application to factoring univariates over Galois rings. Given f ∈ ℤ[x] and a prime-power p^k (k ≥ 2), finding factors of f mod p^k has a curious state-of-the-art. It is solved for ‘large’ k by p-adic factoring algorithms (von zur Gathen, Hartlieb, ISSAC'96), but unsolved for ‘small’ k. In particular, no nontrivial factoring method is known for k ≥ 5 (Dwivedi, Mittal, Saxena, ISSAC'19). One issue is that degree-δ factors of f(x) mod p^k could be exponentially many, as soon as k ≥ 2. We give the first randomized poly(deg(f), log p)-time algorithm to find a degree-δ factor of f(x) mod p^k, when k + δ is constant. Our method has potential application in algebraic coding theory. Algebraic codes, e.g. algebraic-geometric (AG) and Reed–Solomon (RS) codes, are well-studied over Galois rings to achieve better bounds on their parameters.

Finding roots of a bivariate polynomial f(x₁, x₂), over a prime field 𝔽_p, is a fundamental question with a long history and several practical algorithms are now known. Effective algorithms for describing the roots modulo p^k, k ≥ 2, for any general bivariate polynomial, were unknown until the present paper. The main obstruction is lifting the singular 𝔽_p roots to ℤ/p^kℤ. Such roots may be numerous and behave unpredictably, i.e., they may or may not lift from ℤ/p^jℤ to ℤ/p^j+1ℤ.

We give the first algorithm to describe the roots of a bivariate polynomial over ℤ/p^kℤ in a practical way. Notably, when the degree of the polynomial is constant, our algorithm runs in deterministic time which is polynomial in p + k. This is a significant improvement over brute force, which would require exploring p^2k possible values. Our method also gives the first efficient algorithms for the following problems (which were also open): (1) efficiently representing all the (possibly infinitely many) p-adic roots, and (2) computing the underlying Igusa's local zeta function. We also obtain a new, effective method to prove the rationality of this zeta function.

The concept of p-ordering for a prime p was introduced by Manjul Bhargava (in his PhD thesis) to develop a generalized factorial function over an arbitrary subset of integers. This notion of p-ordering provides a representation of polynomials modulo prime powers, and has been used to prove properties of roots sets modulo prime powers. We focus on the complexity of finding a p-ordering given a prime p, an exponent k and a subset of integers modulo p^k.

Our first algorithm gives a p-ordering for a set of size n in time O(nk log p), where the set is considered modulo p^k. The subsets modulo p^k can be represented succinctly using the notion of representative roots; a natural question would be, can we find a p-ordering more efficiently given this succinct representation. Our second algorithm achieves precisely that: we give a p-ordering in time O(d²k log p + nk log p + nd), where d is the size of the succinct representation and n is the required length of the p-ordering. Another contribution that we make is to compute the structure of roots sets for prime powers p^k, when k is small. We explicitly describe all the root sets for p², p³ and p⁴.

We consider estimating the edge-probability matrix of a network generated from a graphon model when the full network is not observed—only some overlapping subgraphs are. We extend the neighbourhood smoothing (NBS) algorithm of Zhang et al. (2017) to this missing-data set-up and show experimentally that, for a wide range of graphons, the extended NBS algorithm achieves significantly smaller error rates than standard graphon estimation algorithms such as vanilla neighbourhood smoothing (NBS), universal singular value thresholding (USVT), blockmodel approximation, matrix completion, etc. We also show that the extended NBS algorithm is much more robust to missing data.