## Tuesday, August 23, 2011

### What inspired you to work on... whatever you work on?

Grad students often wonder how people get ideas of things to work on. The usual advice I give is (1) go to talks, (2) read papers, (3) talk to people, (4) follow through on all of the above. That's fine advice as far as it goes; however, I ask my readers to give examples, and I do the same.

Here are examples of how I found things to work on.
1. In ninth grade when I first heard that the fifth degree equation was not solvable I thought I really want to learn why that is true. I went to college and majored in math to find out. I arranged my courses to take Abstract Algebra as soon as possible and did find out and was happy. I could have dropped out right then; however, I heard that there were problems that could not be solved at all so I decided to stick around and learn about those.
2. As an undergrad at SUNY Stonybrook, in a combinatorics class taught by Joel Spencer, he said Infinite combinatorics is easier than finite combinatorics because all of those messy constants go away. This later inspired me to look at Bounded Queries in Recursion Theory. The reasoning was that P vs NP is hard, but maybe an infinite version of it would be easier. And in recursion theory you don't have time or space so I looked at number-of-queries as a complexity measure. I got out several papers and a book in this area; however, I never did solve P vs NP. Oh well. (Michael Sipser had far more mature thoughts along the lines of trying to solve an infinitary version of P vs NP. Some of that lead to Furst-Saxe-Sipser paper on parity not in constant depth poly number of gates.)
3. In grad school I read up on oracles that made P=NP and that made P ≠ NP. I wondered about other classes. Nobody had looked at oracles for NP vs DTIME(2^n). So I worked on that.
4. In grad school I saw Anil Nerode give a a GREAT talk on Recursive Mathematics. I was particularly impressed that we could take some of the objections of the constructivists and the Intuitionists and turn them into well defined math problems. Rather than say This proof is nonconstructive hence its BAD we now say This proof is nonconstructive, can I prove that it has to be so? How nonconstructive is it? Can some variant of it be constructive? This inspired me to work on recursive combinatorics. Right after the talk I marched to the Library and read two papers on Recursive Graph Theory.
5. In grad school I saw the Chandra-Furst-Lipton paper on Multiparty Communication Complexity at STOC. It really intrigued me that there was a matching upper and lower bound that was based on a combinatorial quantity that was not known. This talk got me interested in BOTH Ramsey Theory and Communication complexity!
6. When I got to UMCP in 1985 Carl Smith was working on Inductive Inference. At the time the field did not use much recursion theory beyond the recursion theorem and its variants. Carl knew the field, I knew recursion theory , so we collaborated.
7. I saw Dan Ullman give a talk on Richman games which inspired me to use Games as a way to motivate math and a good topic for high school and college projects.
8. At STOC 2000 I saw a talk on PIR's. I was intrigued by the model and read up on the area.
9. I reviewed Communication Complexity by Kushilevitz and Nisan which inspired me to work in that area.
10. In 2002 (or so) Jacob Fox (now a professor at MIT working on Combinatorics) emailed me asking about applications of Ramsey Theory. This inspired me to make a website of applications of Ramsey Theory. This forced me to learn some new ones. (I still maintain the website but its getting harder to do so since Ramsey Theory has gotten to be a standard tool that people use without much commentary.)
11. I read about the Polynomial Van der Warden Theorem, and that it had an elementary proof, on the web. I immediately tracked it down and read it.
12. Because I maintain the Applications of Ramsey Theory website Jon Katz emailed me a paper that applied Ramsey Theory to Proving that Programs Terminate. At RATLOCC I had heard about the reverse mathematics of the transitive Ramsey Theorem. I wrote an expository article on this application of Ramsey Theory but was also able to add some commentary from what I learned at RATLOCC (and by being in email contact with both the Applications people and the transitive Ramsey People.) NOTE- Once people know that you are interested in XXX they will send you articles on XXX to help you further the interest.
13. (A non-math example) There was an episode of Babylon 5 with the title A tragedy of telepaths. The authors intent was that this term be like A cast of hawks or A pretension of professors or A wedge of swans. I became fascinated with the question: are these really phrases? They ONLY appear in lists of such words. The phrase a tragedy of telepaths isn't even used in the episode! This inspired me to study the (ill defined) question When is a phrase a phrase? Now whenever I hear a new (to me) word or phrase that intrigues me, I type it into a file (which in LaTeX in alphabetical order), do a Google Search on it, and type in some commentary on its usage. I DO NOT look at word lists- this is a purely personal project.
14. In Kindergarten the teacher had a PhD in combinatorics (the job market was tough). Once when we were being bad she made us sit at our desks and Color the numbers {1,...,9} with RED and BLUE such that there is no three numbers equally spaced that are the same color. I was not able to do this (in fact, it can't be done) but I found the problem very interesting. Some other kid did manage to do it by using RED and BLUE on the same number to get PURPLE. The teacher asked that kid to try to do it for {1,...,27}. He cried. (I didn't remember any of this until much later when I learned VDW's theorem.)
15. Help me on my phrase list: Is there a term for a Math Phd in Combinatorics who is teaching Kindergarten and inspires one of her students to study Ramsey Theory?

1. The best way out is when a graduate student enters a graduate programme with several problems in mind!

There is something fundamentally wrong about giving tips on how a graduate student is supposed to fish for problems! It simply is against the spirit of science!

2. 14: awesome story
15: awesome teacher

3. Wouldn't it be great if all elementary school teachers had PhDs in mathematics. Great post!

4. What a fantastic kindergarten teacher!

5. are the items in this list more or less random or are they about the 15 most significant items of this list? just trying to understand how your mind works.

6. 1) Not quite random- but I wanted to illustrate
(a) seeing a talk, (b) reading something,
(c) talking to people. There are other stories
that are AS significant for me but either the stories aren't quite as clear cut, or they are
repetitive, or the connection of them to the work I did was more tenous.

2) But never mind me, I want YOU, the readers, to tell your stories! What inspired you-
AWESOME teachers, AWESOME papers. Even not-so-awesome things can inspire you.

7. I work on what I work on BECAUSE I CAN

8. To make a long story as short as possible, my adventures with the Four Color Conjecture began in Feb. 1980 when Martin Gardner discussed the Haken-Appel proof in his regular column in “Scientific American”.

At the time I had developed a keen interest in the Philosophy of Science and I rephrased the problem in terms of a Metaphysical Question:

How does the average human computer four-color maps so efficiently?

Within a year or so I had developed the notion of Non-Gaussian Coordinate Systems and a bag of tricks for generating heuristic algorithms that appeared to work quite well when tested empirically.

I then composed the “Eight Coloring Riddle” thinking Mr. Gardner might find it amusing and wrapped it around one of my more reliable mono-pole algorithms. For reasons too numerous to name, I never sent it and put it in the “Worry About It Later” file where it collected dust for a couple of decades.

In 2008 after retiring from my day job, my brother gave me a couple of Robin Wilson’s “Four Colors Suffice” for my birthday. The cover of the edition he gave me was decorated with the Birkoff Diamond and one of the four regions was named “Blair”.

I was ready to dismiss it as a curious convergence of coincidences when I learned that Martin Gardner had died and I couldn’t shake the feeling that I should have sent him the riddle.

Dick Lipton somehow reminds me of Martin Gardner so I posted the riddle on his “Godel’s Lost Letter” blog without adding the heuristic monopole reduction.

There are a lot of variations of the basic eight-coloring procedure which might work and currently the more compelling ones seem to involve using numerous poles.

9. Inspiration (for me) comes concretely from the case histories of individual patients … whenever the surgeon begins to sweat, and especially whenever the patient's outcome is adverse … there is a research opportunity.

Abstractly, inspiration comes (for me) from the broader study of history and the STEM literature … which (for me) is simply an abstracted naturalized and universalized description of individual human-scale case histories.

This practical point-of-view provides a concrete framework for appreciating a perennial topic on Shtetl Optimized; the perennial topic being “The Fate of Humanity,” and the concrete framework being an appreciation that incremental STEM research (pursued by individuals) is cumulatively determinative of that fate.

So yes, what I do makes a difference; and yes, what you do makes a difference … and that's why we need none of us ever lack for inspiration and motivation … because we are blessed with sources of inspiration all around us.

Best … century … EVER! :)

10. I'm a High School student working with dr. gasarch. I think hypergraph ramsey is cool because he taught me it's cool.

11. I was initially wanting to go to Grad School to study compilers and programming languages, when I was an undergrad. However, once I read Richard Karp's interview and article in CACM after he won the Turing Award, I was sold on studying algorithms, and doing things more along the lines of coming up with fast polynomial algorithms. It was random coincidence. I picked up the issue of CACM on the way to the train station from the mailroom, and since I did not want to walk up 3 flights of stairs to drop it back in my room, I took it along with me.....a few hours later I had my calling.

12. Sometimes I get good ideas for papers from questions students ask in the class or audience asks in a lecture.

In general, new ideas usually come from interacting with others, not from locking yourself up in your room.

To put it simply, 2 researchers talking and sharing ideas with each other are 10 times better and more efficient than 10 researchers who don't talk to each other.

13. I hadn't found a suitable thesis topic yet and one day my adviser was explaining the Sperner Triangle to me. I casually mentioned, "I bet we could make a nice game out of this." He stopped talking, turned to me and said: "That is what you're doing now." Awesome! We created the game and found its complexity. Five years later, I'm still doing this sort of thing!

14. RE 14: I have been told (I don't remember the events myself) that when I was 4 or 5, my mom gave me a mobius strip, made out of the strip of paper that binds silverware together at restaurants (the end was sticky, so apparently it made it easy to make).

She gave me a red crayon and a blue crayon, and told me to color each side of the mobius strip a different color. So I started on the red side, then I flipped it over and started coloring blue. Eventually, the two colors touched, and I started crying!

P.S. My senior year of high school, a take-home final exam in Calculus had a problem that involved computing a line integral over a mobius strip (or something like that). I think I cried then too.