Author name cluster
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.
MFCS Conference 2021 Conference Paper
We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n - 1) additions. Our result is based on bounds on the height of the annihilating polynomials in the Perron theorem and an effective form of the Lindemann-Weierstrass theorem which is due to Sert (1999).
TCS Journal 2014 Journal Article
We give an unconditional version of a conditional, on the Extended Riemann Hypothesis, result of Babai, Banerjee, Kulkarni and Naik (2010) [1] on the evasiveness of sparse graphs on n nodes, provided that n is large enough. We also obtain a substantially stronger estimate that holds for almost all n. Our approach is based on some rather deep tools from analytic number theory: the Bombieri–Vinogradov theorem, a result of Balog and Sárközy on prime divisors of sum-sets and a result Baker and Harman on large prime divisors of shifted primes.
SODA Conference 2004 Conference Paper
SODA Conference 2003 Conference Paper
STOC Conference 2001 Conference Paper
We consider a polynomial analogue of the hidden number problem which has recently been introduced by Boneh and Venkatesan. Namely we consider the sparse polynomial approximation problem of recovering an unknown polynomial f(X) \in \F_p[X] with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \in \F_p selected uniformly at random. The case of a polynomial f(X) = α X corresponds to the hidden number problem. The above problem is related to the noisy polynomial interpolation problem and to the sparse polynomial interpolation problem which have recently been considered in the literature. Our results are based on a combination of some number theory tools such as bounds of exponential sums and the number of solutions of congruences with the lattice reduction technique.
FOCS Conference 1995 Conference Paper
We solve two computational problems concerning plane algebraic curves over finite fields: generating an (approximately) uniform random point, and finding all points deterministically in amortized polynomial time (over a prime field, for non-exceptional curves).
STOC Conference 1993 Conference Paper