If Creativity were anything but Random, Someone would have figured out the Algorithm by now. -- Dilbert

There are ten kinds of people in the world. Those who think in binary and those who don't. Joel Spencer

Joel Spencer

Professor, Computer Science and Mathematics Depts

Email: {lowercaselastname}@cims.nyu.edu


Department of Computer Science and Department of Mathematics
Courant Institute, New York University


Contact

Room 829, 251 Mercer St.
New York, NY 10012, U.S.A.
212-998-3219 (voice) 212-995-4124 (fax)-- but email is MUCH better

CV/Papers/Talks

  • Vita--Selected Work (short form)
  • Vita--Publication List (long form)
  • Papers Description of selected papers. Vita and those papers in postscript.
  • Talks Slides for various talks.

    Course Information

    In Spring 2015 I am scheduled to teach Algebra II and Fundamental Algorithms. Information about these courses will be posted sometime in Fall 2014. Students may email with queries at any time.

    Click here for Fundamental Algorithms website.

    Click here for Algebra website.

    Asymptopia -- NEW!

    Asymtpopia has just (July 2014) been published by the American Math Society.

    Click here for a poster (Design: Danielle Spencer)

    This book is aimed at strong undergraduates, though it is also suitable for particularly good high school students or for graduates wanting to learn some basic techniques. From the back cover: Asymptotics in one form or another are part of the landscape for every mathematician. The objective of this book is to present the ideas of how to approach asymptotic problems that arise in discrete mathematics, analysis of algorithms, and number theory. A broad range of topics is covered, including distribution of prime integers, Erdos Magic, random graphs, Ramsey numbers, and asymptotic geometry. The author is a disciple of Paul Erdos, who taught him about Asymptopia. Primes less than n, graphs with v vertices, random walks of t steps--Erdos was fascinated by the limiting behavior as the variables approached, but never reached, infinity. Asymptotics is very much an art. The various functions nlnn, n^2, (ln n)/n, \sqrt{\ln n}, ln(ln n) all have distinct personalities. Erdos knew these functions as personal friends. It is the author's hope that these insights may be passed on, that the reader may similarly feel which function has the right temperament for a given task.

    Asymptopia is a beautiful world. Enjoy!

    For ordering information from AMS (also available on Amazon) click here

    Click (Material will be slightly different from the text here and below) for preface

    Click here for Chapter 0 on primes

    Click here for Chapter 1 on Stirling's Formula

    Chapters: An Infinity of Primes; Stirling's Formula; Big Oh, Little Oh and All That; Integration in Asymptopia; From Integrals to Sums; Asymptotics of Binomial Coefficients; Unicyclic Graphs; Ramsey Numbers; Large Deviations; Primes; Asymptotic Geometry; Algorithms; Potpourri; Really Big Numbers!

    The Probabilistic Method -- Third Edition

    Check out a sample material and table of contents of this book with Noga Alon.

    Click here for the frontcover front cover with a great picture of Uncle Paul

    Click here for a richgetricher new Probabilistic Lens on Preferential Attachment

    Click here for a phasetransition new chapter on the Erdos-Renyi Phase Transition, with particular emphasis on the Critical Window.

    Click for more, available from archives here

    Click here
    Hannah1 Hannah2 Hannah3 Hannah4 for our most beautiful and most attentive reader. She's a fox! And, in strong competition: johanna and jazmin

    SPECIAL OFFER: Yes, your child (grandchild, niece, nephew, sibling) can have an Erdos Number of 1+\sqrt{-1}! Just send a photo of him/her absorbed in reading/playing/teething our book and I'll post it!

    The Erdos-Selberg Controversy

    Over 60 years ago a controversy erupted between Paul Erdos and Atle Selberg over the elementary proof of the Prime Number Theorem. Ernst Straus -- then a young mathematician at the scene -- wrote a description of the events. These have been published in Math Intelligencer, along with commentary by Ron Graham and myself, and a mathematical postscript by Carl Pomerance.

    click here for the article

    Photos


    Photo by MA

    Click for family photos, or a photo of Paul Erdos.

    Math News !

    Alantha Newman and Aleksandar Nikolov have solved the Beck Three Permutaion Problem. I had offered a prize of 100 USD for its resolution. Here are Alantha and Sasha with the prize jpg. They found three permutations of 1,...,n=3^t so that for any coloring of 1,...,n with +1,-1 in one of the permutations there will be a prefix whose sum has absolute value at least ct. The conjecture had been that there was an absolute constant K so that for any three permutations of any size n there would be such a coloring where in each permutation all prefixes would have sum in [-K,+K], and so the conjecture was disproved.

    Robin Moser, a student of Emo Welzl (ETH), has given an algorithmic implementation of the Lovasz Local Lemma. A rough explanation:

    postscript LaTeX pdf Click for Moser's paper with Gabor Tardos .

    Nikhil Bansal (at TU Eindhoven (Holland)) has given an algorithmic implementation of my result that given any n sets on n points there is a 2-coloring with all discrepencies less than 6 \sqrt{n}. I had long conjectured that no algorithm would exist. Semidefinite Programming is a key ingredient. His preprint, Constructive Algorithms for Discrepancy Minimization, is available on arXiv. Click for Bansal's paper . or here
    postscript LaTeX pdf for my own rough explanation. Shachar Lovett and Raghu Meka ArXiV link . have come up with another argument, using a restricted Brownian Motion.

    High School MathCamps

    This is a topic dear to my heart. I am former chair of an AMS committee that gives grants to High School Math Camps. Click for camp information or for information about donations to a worthy cause!

    Some Links

    My Wikipedia page
    Erdos Wikipedia page
    Danielle (daughter's) website
    David(son's) website
    Erdos Number Project
    Budapest Semesters in Mathematics
    Combinatorialist Rogue Gallery

    [TOP]