Arrow Research search

Author name cluster

Igor Shparlinski

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
1 author row

Possible papers

4

I&C Journal 2001 Journal Article

Circuit and Decision Tree Complexity of Some Number Theoretic Problems

  • Anna Bernasconi
  • Carsten Damm
  • Igor Shparlinski

We extend the area of applications of the Abstract Harmonic Analysis to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. In particular, we prove that deciding if a given integer is square-free and testing co-primality of two integers by unbounded fan-in circuits of bounded depth requires superpolynomial size.

Details DOI

TCS Journal 2000 Journal Article

Zero testing of p-adic and modular polynomials

  • Marek Karpinski
  • Alf van der Poorten
  • Igor Shparlinski

We obtain new algorithms for testing whether a given by a black box multivariate polynomial over p-adic fields given by a black box is identical to zero. We also remark on the zero testing of polynomials in residue rings. Our results complement a known results on the zero testing of polynomials over the integers, the rationals, and over finite fields.

Details DOI

TCS Journal 1996 Journal Article

On some approximation problems concerning sparse polynomials over finite fields

  • Marek Karpinski
  • Igor Shparlinski

We obtain new lower bounds on the number of non-zeros of sparse polynomials and give a fully polynomial time (ε, δ) approximation algorithm for the number of non-zeros of multivariate sparse polynomials over a finite field of q elements and degree less than q − 1. This partially answers an open problem of D. Grigoriev and M. Karpinski. Also, probabilistic and deterministic algorithms for testing identity to zero of a sparse polynomial given by a “black-box” are given. Finally, we propose an algorithm to estimate the size of the image of a univariate sparse polynomial.

Details DOI
v2026.09.13