Advice on getting connecting to the community (guest post by Daniel Apon)

(Guest Post by Daniel Apon.)

As a follow up to the last post on Do Conferences Build Community? I offer some advice for people to get connected to the community.

1. Be Confident (And Smile!). It's absolutely important to give a positive first impression when introducing yourself to someone. Making eye contact, smiling, and speaking clearly go a long way toward making yourself an inviting person to have a conversation with. On other hand, one of the best ways to guarantee an awkward social experience is to act creepy; avoid that at all costs. And most importantly, meet as many people as you can!
2. Great Researchers Are People Too! Sure, the person you're talking to could have a history of landmark publications dating back before you even know was NP-completeness was, but don't forget that everyone you're meeting is a human being (really). Be respectful of course, but remember that they're probably in a similar situation to you -- meeting new people during a coffee break!
3. In the words of the immortal Fonz: Be Cool. One of the biggest turn-offs will be giving the impression that you want something from them. Go ahead and throw those types of ideas away immediately. If you're interested in the same things, conversation will flow naturally. Don't try to force anything; just let it happen.

(Comment from Bill G: The same advice applies to meeting people in bars, though you probably won't be discussing Fourier transforms over finite fields until your third drink.)

Do conference build community? (joint post)

(Joint Post by Daniel Apon and Bill Gasarch. Does doing joint posts build community?)

In GASARCH's post on Will there be a 50th CCC He mentioned that conferences help to build community. One of the comments challenged that. Daniel Apon is very new to the community and William GASARCH is very old to the community, so we decided to do a joint post on the topic: Do Conferences Help Build the Community?

1. The talks do not build community. The coffee hours and meals should. Do they?
2. Having people with similar interests all in the same place should build community. Does it?
3. Does size matter? CCC is only about 100 people so they can all sort-of know each other. MATHFEST has over 1000 so I never saw the same person twice.
4. I've heard the complaint that older established professors do not bother to talk to younger people in the field. This is bogus in its generality: it varies tremendously from person to person. Also, if an older professor ignores you it might not be that he thinks he is better than you, it could just be that he has no social skills. (YES- there are academic computer scientists who have no social skills!) (I used `he' instead of `he or she' since I have never heard this said about a female established professor.)
5. Is it worth the money the individual spends going to the conference to build the community? Are there other more cost-efficient ways to build community? I do not know; however, I just want to know, for now, is the current system helping to build community albeit inefficiently.
6. Bill Gasarch a long time ago and Daniel Apon recently have had very positive conference experiences in terms of getting into the community (see below). We DO NOT claim these experience are typical. We do not know. But we urge you to share your stories, positive and negative. so that we can get a sense of it. Please be brief, to the point, and not nasty.
   1. Bill Gasarch: I went to a workshop on complexity in 1984 (There was no CCC then) where I met Stuart Kurtz and Ron Book, both of whom were friendly to me. My advisor Harry Lewis introduced me to Alan Selman at STOC (probably 1985). Steve Homer (who I had worked with) introduced me to other people at CCC, including Juris Hartmanis. I met long-time collaborator Richard Beigel at the 1986 CCC. All very positive for getting me into the community.
   2. Daniel Apon: My first conference was STOC 2010, and I bumped into Bill during a coffee break between talks. We had previously been in email contact since he was in charge of handling the travel awards for STOC that year, so it made for an easier ice-breaker. He introduced me to Lance and others. Later, when I went to the Barriers II workshop, I met Aaron Sterling (who is regular participant with myself on the TCS StackExchange site), and we had dinner together one night. I also had the pleasure of meeting a number of other people between the two trips and talking some. Here's a non-exhaustive list (just the first few who come to mind): Eric Allender, Dana Moshkovitz, Scott Aaronson, Andy Drucker, Paul Beame, Anup Rao, and Russell Impagliazzo. My impression of everyone were that they were friendly, open, fun (and smart!) people. It was definitely a positive experience getting the chance to interact with those that I did.

FOCS Part II

I'm heading back to Chicago this morning. Dan Spielman had a special talk in honor of his recent Nevanlinna prize. He gave an amazing talk (as always) about solving Laplacian matrix that comes from graphs, basically putting springs at every edge, nailing down some vertices and seeing where the other vertices end up. Dan's and other talks were filmed, be sure to look for them on the FOCS page in the future.

I spent most of the conference in the hallways talking to people but as someone pointed out to me, I talked almost entirely to people I already knew. I've heard complaints before young people feel they can't talk to senior researchers at STOC/FOCS. We don't do that on purpose, just like to catch up with people we've known for years, but I should try harder to meet the younger crowd.

I had one of those interesting discussions with Ketan Mulmuley on his views on the P versus NP problem (yes we are from the same city but somehow it's easier to talk in these meetings). Ketan talks about his algebraic geometry approach as a very length process towards a solution. Complexity theorists need to give up ownership of the P v NP problem (can anyone "own" a mathematical problem?) and realize that we need the algebraic geometers to help or even lead us in this journey. Ketan also view the journey as more important that the eventual resolution of P and NP. The search for a solution of the Riemann Hypothesis has yet to produce a proof but no one would say that the effort to finding one has been a failure as great math has come from that line of work. The algebraic geometry path to P v NP will yield exciting work as well. 

FOCS Part I

Some thoughts from the FOCS conference in Las Vegas. One result I hadn't seen before I heard people excited by, Determinant Sums for Undirected Hamiltonicity by Andreas Björklund, giving an O(1.657ⁿ) algorithm for testing Hamiltonian Graphs beating the O(2ⁿ) bound of Bellman and Held-Karp from the 60's. 

I spend much more time hanging in the halls than attending talks. And much of the hall discussion focused on the Simons Institute whose letters for intent are due Wednesday. Most major theory groups seem to be putting together a letter, the interest is in what consortiums are forming, i.e., how are the theory groups being partitioned.  Various conjectures about what the Simons Foundation is looking for. For example, will it help or hurt to already have a strong center for theory? What is the right balance of "core theory" and connections to other fields? Should be interesting to see which groups make it to the second round.

Wherever this institute ends up, if run well it will immediately become a major influence in our community. Luca made a good point, that even this process where we all talked to our deans and other administrators about the proposal, helps to sell the importance of theoretical computer science to academic leaders.

I won't give the blow by blow at the business meeting, Suresh already did so on his Twitter. I watched Suresh type furiously into his phone two rows ahead of me and see what he typed immediately on my iPhone. Cool.

This will be the last FOCS with paper proceedings. Luca Trevisan asked some questions about moving to a larger PC or allowing PC members to submit but no one took the bait for a discussion.

The biggest issue came from Dmitry Maslov from the NSF. The Algorithmic Foundations program that funds core theory has one of the highest acceptance rates at the NSF. With the complete turnover of NSF leadership, there is a concern that some might thing theory is over-funded. The CATCS committee is working to educate the new NSF directors that theory funding is going to strong proposals but still it would help to submit more proposals to bring down the rate. Large and small proposals are due soon so submit early and often. If you don't get funding, thanks for taking one for the team. 

New York Area Theory Day- Nov 12, 2010

New York Area Theory Day, Organized by: IBM/NYU/Columbia, External sponsorship by: Google, Friday, November 12, 2010

The Theory Day will be held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

For the program see here. For directions, please see here or here (building 46). (ADDED LATER- THE ORGANIZERS SEND ME A NICER PAGE TO POINT TO: here)

My advice: If you CAN GO then GO! If you CAN"T GO then DO NOT GO!

Will there be a 50th CCC? Will you be there?

At the 25th CCC Juris Hartmanis gave a great talk to celebrate having a 25th. Will there be a 50th? I asked people at the conference. What did they say? Watch the video!

So what do you think? Will there be a 50th CCC? Will you be there?

Will there be conferences?

1. Comp Sci may grow up.
2. We may videotape the talks more. Then NSF will stop paying people to go since you can see the talks anyway. So less people will go. This is part of a more general trend where as a society we are sacrificing community for efficiency.

Will there be Complexity theory?

1. The field will still be vibrant, P vs NP will still be unsolved.
2. L=RL may be proven.
3. Some form of the Unique Game Conjecture may be proven or disproven.
4. If GI is in P we may see that proven within 25 years. If GI is not in P then I doubt we'll see that proven within 25 years.
5. If Ketan's Geometric Complexity approach begins to work we may change the name to Conference on Applied Algebraic Geometry and Representation Theory.
6. If we find more and more about what we cannot do and less and less about what we can do, we may change the name to The Barrier's Conference.

A Note from the Trenches (Guest Post from Michael Mitzenmacher)

Former blogger Michael Mitzenmacher talks about being chair and not blogging. In a day for guest posts, over at Geomblog, David Johnson wants to know practical applications of approximation algorithms.

It's been about about seven weeks since I've given up blogging, and I have to say, I do miss it. There's certainly been plenty of things I could have written about, from large-scale CS issues (the Simons foundation call for a new institute for the theory of computing, the NRC rankings and the CRA reaction, new people at the NSF, and the movie the Social Network), more Harvard-centric issues (our intro CS class jumping to over 500 students -- about 200 more than last year, Harvard CS is hiring this year, the Harvard endowment performance (+11%), and the movie the Social Network), to more personal issues (my class for this semester, my take on the CoNEXT PC meeting, my very fun trips to Princeton and UCLA, and why I still haven't seen the movie the Social Network). Each of these could easily have been a post, I'm sure. And I've apparently become terribly accustomed to being able to just announce what I'm thinking (as though everyone should care).

On the other hand, I've been busy. Quite busy. Lots of meetings, lots of answering people's e-mail, lots of solving minor problems, lots of pointing people to the right other people to get problems solved. The start of the academic year is always busy anyway, and my graduate class takes up a fair bit of time even if a good chunk of it is material from previous years, because a good chunk of it is also always new. But the new job as "Area Dean" really sucks up a good bit of time. For the first month, I really don't think I got any research done. This month is better, though much of the research time has been going to revising and finishing off old work rather than new work. Next month I hope it will get better still.

I don't want to say the job sucks. (Well, maybe sometimes it does.) But it does take time, and I'm glad there's a planned exit. As I tell my colleagues, not that I'm unhappy with the job, but only 2.7 more years to go.

On the plus side, there's a lot of positive things going on that I feel like I'm pushing forward. To a large extent, that really seems to be the job: just pushing projects (and the corresponding people) forward, so something gets done. I find things like organizing the class schedule for the next X years and getting a slot to hire don't just happen by themselves, but with the right prodding, they do happen. I'm also blessed with incredibly collegial colleagues, many of whom are going extra miles to make my job easier.

My main management technique is to figure out (or get told) what needs to get done, tell people about it, and then see that it gets done, by me or, hopefully, someone else. I'm getting more used to fixing tasks and delegating them to other people. I also use affirmations constantly. I figure if I tell enough people enough times that something is going to happen, they'll all believe it, and so it will happen. For example, for various reasons for several years we haven't hired new junior faculty. One thing I keep telling people is that after my stint, the question every year at Harvard will not be, "Is CS doing a search this year?", but rather, "What areas is CS focusing its search in this year?" We are doing a search this year; I'm already working to get buy-in on next year's planned search, and it looks very promising; and while it's a bit early to start asking the powers-that-be about year three, I'll start laying the foundation there soon. And see, by telling all of you about it, I'm just in my own positive-thinking (or, alternatively, manipulative) way helping ensure it will happen. Once people accept your basic plan, after that it's just (a lot of) paperwork.

So while I miss blogging, it's been good for me to stop. Besides (desperately) needing the time, it's clear that blogging would give me too much opportunity to say my mind about things brewing before the plans are all fully baked (to mix cooking metaphors). Quietly building consensus doesn't go well with writing a provocative blog. The payoff, I hope, is that you'll be hearing lots of good things about Harvard CS over the next couple of years. After all, we have to get ready for the next round of NRC rankings. I'll try to fire off the occasional update from the trenches, and as for returning to blogging, we'll see how things look in about 2.7 years.

My Trip to Denmark

Last week I had a pleasant short trip to Aarhus, Denmark for the inauguration of the new Center for Research in the Foundations of Electronic Markets. Kevin Leyton-Brown had a more interesting trip to the center.

The Center focuses on real-world pricing mechanisms helped by secure computation building on research of Aarhus cryptographer Ivan Damgård. We heard several talks from government agencies and energy companies, seeing how the electricity network flows through Scandinavia and Northern Europe. Denmark with its many windmills is often an electricity exporter and messy pricing mechanisms come to play.

Dale Mortensen, the Northwestern Economics professor who won the Nobel prize last Monday, spends the falls in Aarhus so the Nobel prize was already big news there. When the local dean officially inaugurated the center, he noted that the center had international partners at Northwestern (Nicole Immorlica and myself) and used that fact to brag about Dale being at Aaarhus not once but twice. He never mentioned the other international partners. Take that Harvard. Dale himself was nowhere to be found.

At the workshop someone ran one of these weird rule auctions that on large scales is essentially a lottery. It costs 5 DKK (about US$1) for each bid. Each bid must be a multiple of 5 DKK. The player with the lowest unique bid pays that bid and gets an iPod Touch. I tried with a random bid. Game theorist Hervé Moulin won the auction. His strategy: Bid on every number from 5 to 75 DKK. A seemingly crazy strategy but with 15 DKK as his winning bid, he got the iPod for all of $18.

Benoît Mandelbrot (1924-2010)

Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line.—Mandelbrot, in The Fractal Geometry of Nature.

Benoît Mandelbrot, famous for his study of fractals including the one named after him, passed away on Thursday from pancreatic cancer.

I first heard about Mandelbrot as an undergrad in the early 80's as fractals became the mathematical curiosity du jour. One of the popular screen savers on the Sun computers in the late 80's was either zooming in on the Mandelbrot set to reveal the same set inside. One could spend hours watching--this and Tetris wasted many grad student hours in those years before Facebook and Twitter.

I saw Mandelbrot speak just once in 1996 at a 50th Anniversary of CWI celebration, also the only time I've seen Knuth give a talk. All I remember from the talk were pretty pictures of imaginary fractal mountains on other planets generated by Mandelbrot for some movie--shades of Avatar.

I always thought of fractals as mostly descriptive--yes, fractals appear almost everywhere, but so what? Nevertheless here's to a very uncommon mathematician who literally showed us the beauty of mathematics.

How hard is this problem?- I ask this non-rhetorically

I recently saw the following puzzle:

Which two numbers come at the end of this sequence? (That is, what are x and y?)

2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,x,y

(NOTE ADDED LATER- I had a typo in this post, the worst kind of typo one could have- I had a 5 instead of a 6. I looked up the original source and they had the same typo. SORRY!)

I could not figure it out. I went to the sequence-website which gave me the answer. Before the web I would not have been able to do this and I may have had to wait until there was a web to look it up on in order to solve it. Or maybe I could have solved it, though seeing the solution I doubt that.

How hard is this problem? How to tell how hard it is? How well known is this puzzle? YOU can help me!

1. Try to solve it without using any other resources.
2. Leave a comment either saying either I solved it without any help OR I was unable to solve it OR I knew how to solve it since I already saw it.
3. Please do not include the solution. I will not post a solution--- if you are curious just type it into the sequence website.
4. Please do not lie. I want to use this to judge how hard this problem is.

Two Candidates for an Ig Noble in Mathematics

(This is a sequel to my post on the Ig Nobel Prize.)

Two candidates for an Ig Nobel prizes in Mathematics. They deserve it for opposite reasons. (They are old results and hence, I assume, do not qualify.) (ADDED LATER- I checked with the Ig Nobel Committee- they DO allow old results to be submitted and have even given the prize out to people who are dead.)

1. The Banach Tarski paradox deserves an Ig Nobel since it is obviously false.
2. The Jordan Curve Theorem deserves and Ig Nobel since it is obviously true.

The NSF Takes Shape

As I've mentioned before, the NSF is turning over top to bottom especially in computer science. Most of the pieces are now in place so let's check out the new personnel at the NSF that affect theoretical computer science.

The Senate has now confirmed MIT Dean Subra Suresh as the new NSF Director. Suresh replaces Arden L. Bement, Jr.

Michigan CSE Chair Farnam Jahanian takes over as Assistant Director of CISE (as in assistant to Director Suresh) starting in February. Jeannette Wing went back to Carnegie-Mellon last summer. CISE covers computer science funding at the NSF.

Purdue professor Susanne Hambrusch heads the Division of Computing and Communication Foundations (CCF) which includes theoretical computer science. Sampath Kannan returned to Penn.

The other divisions at CISE have new leadership as well. UCSD Chair Keith Marzullo heads Computer and Network Systems (CNS) and CMU Vice Provost for Research Computing Howard Wactlar heads Information and Intelligent Systems (IIS).

The CCF program directors handling the Algorithmic Foundations proposals from last month are Mitra Basu, Tracy Kimbrel and Dmitry Maslov. The NSF is still working to replace Richard Beigel who specialized in computational complexity and has recently returned to Temple.

What do all these changes mean for US funding for computer science and theory in particular? We'll just have to wait and see.

Noble and Ig Noble Prizes

What is the Ig Nobel prize? To quote the website:

The Ig Nobel Prizes honor achievements that first make people laugh, and then make them think. The prizes are intended to celebrate the unusual, honor the imaginative --- and spur people's interest in science, medicine, and technology.

Some science seems real, though odd: In 2006 the Ig Nobel in Mathematics went to (quoting the website)

Nic Svenson and Piers Barnes of the Australian Commonwealth Scientific and Research Organization, for calculating the number of photographs you must take to (almost) ensure that nobody in a group photo will have their eyes closed.

Some science does not seem real: In 1993 the Ig Nobel in Mathematics went to (quoting the website)

Robert Faid of Greenville, South Carolina, farsighted and faithful seer of statistics, for calculating the exact odds (710,609,175,188,282,000 to 1) that Mikhail Gorbachev is the Antichrist.

There is no specific Ig Nobel prize in computer science. What computer science work deserves an Ig Nobel? What complexity work deserves an Ig Nobel?

Has anyone every won BOTH an IG NOBEL PRIZE and a NOBEL PRIZE? YES! It just happened! Andre Geim won the 2010 Nobel Prize for Physics and had previously won 2000 Ig Nobel Prize for Physics. I describe the equipment used in both, but I will not say which one won the Nobel prize and which one won the Ig Nobel prize.

1. One used Magnets and Frogs.
2. One used Scotch Tape and Pencils.

Partha Niyogi (1967-2010)

University of Chicago Computer Science and Statistics Professor Partha Niyogi passed away on Friday after a battle with brain cancer. Partha worked in machine learning in a number of theoretical and applied areas, particularly memorable for his use of manifold theory in semi-supervised learning.

I knew Partha well from my years at Chicago. It's hard to lose someone who was a close colleague and friend, especially when they die so young. A great loss.

The Annual Fall Jobs Post

The CRA is working on setting guidelines for job deadlines to help out with some of the gridlock in the job market. Many of the top departments have already moved their deadlines for full consideration to early December or November. Keep an eye out and remember to apply early this year.

Possible theory tenure-track faculty jobs at Harvard, Rutgers, TTI-C and Federal University of Rio Grande do Sul (Brazil). For more faculty and postdoc listings: CRA, ACM, Theory Announcements and CCI. Also check out web pages of departments that interest you.

A little early to tell but this year will likely be similar to last year: a small number of tenure-track positions in TCS and a large number of postdoc positions. Out of necessity almost everyone does a postdoc now and many people doing a second or third as well.

Have the theoretical computer science community actually moved to postdoc culture, where people are now expected to do a postdoc (or multiple postdocs) before taking a tenure-track position like physics, chemistry and biology? When did the field make that jump?