Denis Xavier Charles  

5355a, Computer Sciences and Statistics  
1210, West Dayton Street
Department of Computer Science
University of Wisconsin-Madison
Madison, WI 53706 

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


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 :
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. 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).

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.