Contact Information
Office Location: 4394, Computer Sciences and Statistics
Phone: 1-(608)-890 0020
About myself
I am a final year Ph.D. student studying Computational Number Theory here at UW under the
supervision of Prof. Eric Bach .
My main interests are in Theory of Computation - in particular Complexity Theory, Design
and Analysis of algorithms, Combinatorics, Number Theory and Algebra.
I did my undergraduate degree at
Birla Institute of Technology and Science, Pilani
- INDIA. I completed my masters at
University at Buffalo (SUNY) under
the supervision of Ken Regan .
Favorite Net Locations
-
Here's the
Amazing person, who "remotely" sparked my interest in Theory of
Computation.
- The Messier catalog of nebulae, star clusters, and galaxies.
- It is easy to forget the immense scale of our universe. Here is a
mind-boggling
view of distant galaxies. Don't miss the video of the "zoom-in" to the location.
-
A Site
for sore hearts.
- Verse for Wear. (Someday I hope to complete assimilating this.)
-
The Electronic Colloquium on Computational Complexity (ECCC)
- An absolute goldmine of notes in advanced mathematics - J. S. Milne's Homepage.
- The Queen of mathematics on the Web - Number Theory Web.
-
My favorite mathematician J. C. F. Gauss.
- The Digital Math Archive: An effort to preserve fundamental math documents online.
Currently the site has most of the work of Langlands, and the book of Euclid.
- The important work SGA (Seminaire de Geometrie Algebrique) by Grothendieck and his
coworkers has revolutionized Algebraic Geometry. The series has been out of print for very long.
This site has the scans of the pages -- an important
service to mathematicians.
- Bibliophile's digital dream come true.
- To see the world through another's eye.
Miscellaneous
Raison d'être
 |
During summer '99, I worked on a survey of several important results in Complexity Theory in relation to
Algebraic Geometry and Commutative Algebra .
You can download the current version of the survey.The prerequisites for reading the paper include Algebra, Algebraic Geometry
some Commutative Algebra and of course Complexity Theory.
The excellent online notes on Algebraic Geometry by J. S. Milne is sufficient to understand this survey.
I haven't given proper credit in the document for various results and definitions as it is still under
development. For example the algebraic geometry definitions are from the standard and lovely book
by
Robin Hartshorne .
- Complexity of Algebraic Geometry and Commutative Algebra - A Survey
[.PDF]
|
I was a Research Assistant for two years (Fall '99 - Spring '01)
for Prof. Ken Regan .
We studied ways of using methods from Commutative Algebra and Algebraic Geometry
to prove lower bounds for computational problems.
Here is an almost verbatim transcript of a 4 hour seminar I gave on Primality Testing Algorithms
[.PDF]. This
was part of a course on Number Theoretic Methods in Computer Science (Fall '99).
The algorithms covered were :
- Lucas-Lehmer Test for Mersenne Primes.
- Solovay-Strassen coRP test for Primality.
- Adleman-Pomerance-Rumely deterministic test for Primality.
In connection with some work related to algorithms for primality, we hit a nice
question: Consider the primes q of the form 2p+1 where p itself is prime. We
might ask the question "Are there infinitely many such primes?". Such questions
tend to be rather difficult to settle in general. We could ask the alternate question
does the "Inverse sum of these kinds of primes diverge?". A quick computation
on Mathematica shows that the sum seems to be bounded above by 0.63994932317...
We might conjecture that the sum indeed converges, this however does not disprove
that there are infinitely many such primes but it puts bounds on the density of these primes.
A powerful and general technique which can be used to answer such questions is
Sieve methods . It turned out that a well known sieve called the Brun's sieve immediately
shows that this inverse sum converges. In the hope that this technique might be useful
to others looking at these types of questions, I include the proof of this statement here. Incidentally primes p such that 2p+1 is also prime are called Sophie Germain primes
after the famous mathematician who showed the first case of FLT for these primes.
- An Application of Brun's Sieve [.PDF].
Brun's Sieve sparked my interest in Sieve techniques, and I changed my thesis topic
from the earlier "Complexity of Commutative Algebra and Algebraic Geometry" to
a study on Sieve Methods . Here are the fruits of the labour:
[.PS]
[.PDF].
Revisions aside this is the finished work. This was completed in July 2000.
Note: A much stronger result on prime and squarefree pairs can be
proved as an easy corollary of Chen's theorem (comment by Andrew Granville).
- Modular groups
To tackle a problem in complexity I've been working on properties of groups of 2 dimensional unimodular matrices over finite fields. Here are some preliminary results.
- On the odd order elements of PSL(2,p)
[.PS].
- A Note on the Subgroup Membership Problem for PSL(2,p)
[.PS].
The reason for looking at this problem was to see if the membership problem for PSL(2,Z) reduces
to the mod p version of this problem. Unfortunately, we end up in theoretical difficulties
of controlling the sizes of the groups when we mod out by p. At present, these
seem to be extremely difficult to solve. I might return to this problem after a more intense
study of group theory.
- Comment on the Membership problem for PSL(2,p^f)
[.PS].
Marty Isaacs informed me of a classification theorem of subgroups
of PSL(2,p^f) using this theorem we can easily show that the
membership problem is in NP intersect coNP. This note supercedes the
previous result.
- Square dependence of random integers
Let N be a large integer and let n = (log N)d for some fixed constant
d > 0 what is the probability that on picking n integers
at random from the interval [1...N] there is a subset of them whose product
is a perfect square? Here is an upper bound [.PS].
- The largest prime divisor of 2n+1. [.PS]
[.PDF]
This question arose in my investigations of the modular group membership problem. Much
stronger results in this direction are required to even contemplate the approach mentioned
earlier in reducing the membership problem for PSL(2,p) to PSL(2,Z). Granville has
improved the results mentioned here to n2.
- Squarefree Smooth integers in short intervals. [.PS] [.PDF]
A previous version of this result assumed the Riemann Hypothesis.
It turns out that the Riemann Hypothesis is not really required for this result.
Thanks to Prof. Antal Balog for this
observation. The challenge is of course to prove existence of these integers in much shorter
intervals, and even assuming powerful hypotheses like RH or ABC we are unable to do so.
- A generalized Euler's totient function and integer factorization.
[.PS]
This is just an amusing observation. Suppose we have a polynomial
time procedure that can compute the order of the multiplicative
group (Z/NZ)*, can we use this to factor N? This
is true under the generalized Riemann hypothesis as shown by
Gary Miller. Here we introduce some generalizations of this
function which are harder than factoring.
- Counting Lattice Vectors. (Updated!)
[.PS] [.PDF]
Here we consider the problem of counting the number of lattice vectors at a given distance.
We show that the problem is #P - Complete, and show that
some restricted versions of this problem are also as hard as integer factorization.
We also give an interesting algorithm based on Modular forms
for this problem.
- Computing the Ramanujan Tau function. [.PS]
[.PDF]
The algorithms used to compute the Ramanujan Tau function seem to use recurrences that require exponential
time to compute. Here we show how the Selberg Trace formula leads to a computationally more efficient
algorithm to compute the Ramanujan Tau function (the running time is essentially the square root
of the time the other method requires). One must assume that this method of computing Tau is
well known (as the Trace formula is :)), but it doesn't seem to have been rigorously
analyzed anywhere. Another point is that this method of computing Tau
is only efficient if we are computing specific values of Tau and not trying to make up a table
of values of the Tau function.
Updated to correct an error in statement of Lemma 2.3, thanks to Victor Miller for pointing this out.
- Computing a Basis of Modular forms.
[.PS] [.PDF]
We show that there is a density 1 subset of primes for which the
p-th Hecke operator has a cyclic basis. We use this to show that we
can construct a basis of cusp forms whose n-th Fourier coefficient can
be computed in O(n1/2) time. Unfortunately, the constant
implied by the big-Oh is ineffective at this time. But a famous
conjecture about the irreducibility of the characteristic
polynomials of the Hecke operators implies a strong effective
bound on this constant.
- Wieferich Primes [.PS] [.PDF]
Silverman showed that the ABC-conjecture implies that the set of non-Wieferich primes
is infinite. His idea was to use the ABC-conjecture to get non-trivial bounds
on the squarefree part of cyclotomic polynomials. In this amusing note, we show
that essentially this is the only way one could hope to prove that there
are infinitely many non-Wieferich primes.
- Serre's conjecture on 2-dimensional Galois representations [.PS]
[.PDF]
This was my term paper for Nigel Boston's course on Fermat's Last theorem (Spring 2003).
- Complex multiplication of Elliptic Curves. (Updated!)
[.PS] [.PDF]
We give two algorithms to check if an elliptic curve defined over a number field
has complex multiplication, both run in polynomial time, one is randomized and the
other deterministic. Update: Now there is a rigorously proved one-sided error version
of the randomized algorithm.
- A theorem or two for the asking. [.PS]
-
Computing Modular Polynomials.
The classical modular polynomial gives a model of the curve X_0(N) over the rationals. It
is a very useful object as it governs the useful maps (isogenies) between elliptic curves.
Kristin Lauter
and I came up with an idea to compute modular polynomials (for prime N) directly modulo
primes in the summer ('04).
 |
I love classical music, especially the works of the
great composer Ludwig van Beethoven .
Beethoven's Piano Sonatas can only be described as heavenly, for example Sonata #8 - Pathetique, and Sontata #14 - Claire de Lune.
For works of incredible inter-weaving of patterns and beauty the best example is
Johann Sebastian Bach, and a
nice example of his wonderful work is the
Musical Offering BWV 1079 (which is the
main connection to Bach in Douglas Hofstader's amazing work GEB:EGB).
Some of the best piano works I've listened to, are by the Polish composer
Fryderyk Chopin , his music is so beautiful that it is almost a living presence.
And of course, Wolfgang Amadeus Mozart ,his music is so full of joy, that it is the perfect cure for melancholy. For
those who have seen the movie (or the play) Amadeus
here is a comparison of fact and fiction.
This list of my favorite music will never be complete,
and describes only a small fraction of the music which I treasure, and
I am grateful for its existence.
A Psalm of Life
- Henry Wadsworth Longfellow
Tell me not in mournful numbers,
that life is but an empty dream!
for the soul is dead that slumbers,
And things are not what they seem.
Life is real! Life is earnest!
And the grave is not its goal;
Dust thou art, and to Dust returnest,
Was not spoken of the soul.
Not enjoyment, and not sorrow,
Is our destined end or way;
But to act that each tomorrow
Finds us farther than today.
Art is long, and Time is fleeting
and our hearts, though stout and brave,
Still, like muffled drums, are beating
Funeral marches to the grave.
In the world's broad field of battle,
In the bivouac of Life,
Be not like dumb, driven cattle!
Be a hero in the Strife!
Trust no future, howe'er pleasant!
Let the dead Past bury it's dead!
Act,-act in the living Present!
Heart within, and God o'erhead!
Lives of great men all remind us
We can make our lives sublime,
And, departing, leave behind us
Footprints on the sands of time;
Footprints, that perhaps another,
Sailing o'er life's solemn main,
A forlorn and shipwrecked brother,
Seeing, shall take heart again.
So let's be up and doing,
With a heart for any fate;
Still achieving, still pursuing,
Learn to labor and to wait.
