STOC 2017 (and STOC 2016)

I'm starting to get asked about STOC 2017 dates -- we recently executed the hotel contract, and STOC will be June 18-23 in Montreal.  (It will really "start" the morning of the 19th, but we expect people will be getting to the hotel the 18th.)  Yes, that 5 days of STOC -- expect more announcements about how we'll be filling up those 5 days coming up.

And just a reminder -- STOC 2016 is around the corner, June 19-21, with a joint STOC/SoCG workshop and tutorial day on June 18.  The STOC 2016 page has more info, and even if you haven't signed up, you can still register as a walk-in on-site. 

Class Evaluations, Again

I've not been blogging much, but I have an excuse now that class evaluations have arrived.
  
By posting about the evaluations, the students know I read them.  And perhaps if any future students see this it will inspire them to try to make helpful comments, or at least fill out the evaluation.  This semester I taught the undergraduate Algorithms and Data Structures course, which at a bit over 170 students is the largest class I've taught at Harvard (and the largest the class has been since I've been here).  Let's see how I did on a class this big.

But before beginning, a word from our administration: 

Again this semester, some students may have accessed their course grades before completing their course evaluations. When this has happened in the past, we determined that the effect on evaluations was statistically undetectable, if any. Nonetheless, we wish to assure you that we understand that this semester's Q evaluations will not be 100% comparable to past terms and that the administration will take that fact into consideration when viewing the data.

If anyone can decipher that bit of bureaucratese for me,  please do.  (I admit, I found it amusing.)

Now, my favorite comment of the year:

Mitzenmacher can be a bit intimidating at times (I'm pretty sure he's the only professor under 40 years old whose class I've taken that I'm not on a first-name basis with)...

Whoever you are, you anonymous student you, it's wonderful that somehow you think I'm still under 40.  That was, well, a while ago...   (Also, you can call me Michael.  Mitzenmacher is hard say, and spell.  Maybe calling me Michael will make me seem less intimidating.)

A close second:

Take this course if you want to be good at CS. I also got a girlfriend out of it, so if you're looking for love, this is definitely the class you should take. Chicks dig algorithms.

Yes, they do.  And congratulations.  But seriously, please don't call them "chicks".  Some women find the term offensive, and I would like women in the class to feel welcome and comfortable.  It also makes you seem like you're living in the wrong decade.      

Another good one.  

Definitely the legend his former students make him out to be.

Just to clear, I interpret that as at best a neutral statement, not necessarily a positive one.  (The rest of the evaluation, I think, backs my interpretation.)  On an obviously more negative note: 

He is sarcastic and unhelpful. He even goes out of his way to be snarky and rude to students...

I appreciate the concern, but don't worry, I'm not going out of my way at all... the sarcasm and snark really just come naturally!

And apparently, it's rubbing off.  

This course could be improved by having longer and more difficult problem sets. Having tougher exams would be better too.

Hey, I don't think you've heard.  I'm supposed to be the sarcastic and snarky one. (The student's whole evaluation was like this.  Very funny and original -- surprisingly, nobody's ever done that before, that I can remember.)  At least a partial explanation for the evaluation above, perhaps:  

Piazza was riddled with dumb anonymous question (e.g., "Should my program handle negative ints?" "No, as stated in the assignment."). I think it should be course policy to delete these questions rather than give terse answers; each one causes hundreds of people to receive email notifications and spend tens of seconds digesting the poster's helplessness. I estimate that each poster is choosing to waste about two hours of our collective time rather than reread the assignment or email a TF.

Thank you for this comment;  it's a rare comment that addresses a challenging issue.  I continue to be ambivalent about Piazza.  It's very useful for students to be able to ask questions and get reasonably timely responses.  On the other hand, the ease of being able to ask questions leads to the issue you raised, as well as other similar problems.  (Students don't see many private questions of the form, "Is this an OK answer to this question...")  I'm not sure deleting the question is the correct response;  I can only imagine the reaction.  Already, people find my terse answers to some questions off-putting, or even "sarcastic" and "snarky"....
  
Now for some other useful comments.   

better handwriting would be nice.

Not the first time I've heard that complaint, although surprisingly it was rarely mentioned this year;  I did try to be better at the board.  But it's good to be reminded, frequently.    

Maybe integrate into Canvas or disregard it completely, it was weird having some stuff in one place and other stuff on the other.

Thank you for the useful comment.  Canvas is the tool we are being pushed at Harvard to use for course management, and for a class of this size, I felt forced to use it;  having students e-mail in assignments just wasn't going to be functional.  But Canvas really, really sucks, and caused at least as many problems as it solved (probably more).  I'd have liked more comments about Canvas, or really some advice on whether it's worth using at all.  

An odd comment: 

really sucks not having a good textbook for those of us who learn better on our own than in lecture;

Comments like this always make me wonder.  I do not require a textbook, but recommend both CLRS and Kleinberg-Tardos if students want one;  both books line up reasonably well with probably 2/3 of the course.  Did this student buy one of those?  I don't know.  I also find most things I teach have pretty good articles available on Wikipedia.  Many students in their comments appreciated the lectures (and the lecture notes), but for those who don't, there are certainly other resources available.   
  
Now some good responses to the question:  What did you learn?  How did this course change you?

Algorithms are fun! I'm good at theory!

Awesome!   

...I now view computer science as more than just coding. It is the art of problem-solving.

Awesome! 

Some truth in advertising:

Very useful course for anyone who wants to learn how to solve problems in the most computationally efficient way possible. That said, this course is not for everyone. Some will find it difficult.

Some, indeed.  Perhaps I can find another student who can clarify the above description.... 

This class is insanely hard (like really, really, really hard); don't let anyone tell you otherwise. I spent maybe 40-50 hours per week on the psets, and the tests (the midterm and final) were brutal.

To be fair, I don't think most students are spending 40-50 hours per week on the problem sets, and the self-reported numbers suggest not also.  But point taken, the class is hard.  (Some will find it difficult.)   

As usual, the overall summary is that the reviews contain a mix of positive and negative.  Let's end with some more positive ones, so I can think positive thoughts about the fact I'll be teaching this very large class again next year: 

Really interesting course material presented clearly. There was a nice balance of breadth and depth, and I liked the focus on randomized algorithms and the last couple lectures on topics tying the course together. Such a good class - thank you!

 No, no -- thank you!

Mitzenmacher is very good at responding quickly on Piazza, and often his responses are quite funny.

Thank you!  Some people apparently don't seem to get our sense of humor.  Same thing happens at home with the wife and kids -- they don't think I'm funny either.  

Professor Mitzenmacher is a great lecturer and provides lots of insight into algorithms. Problem sets are very well written, and most if not all problems are very thought-stimulating and are an apt level of difficulty. I also enjoyed the programming assignments -- it was great to physically code things and get a hands-on approach to the algorithms we learned.

For programming assignments 2 and 3, I would have hoped that Professor Mitzenmacher grade them as well--the TFs seem to be following a rubric and it is difficult for them to reward other inisghts and rather take off many points for more minor issues.

Thank you for the nice comments!  I'm glad you were happy with my grading of the first programming assignment, but you really want me grading all of them???  (Hmmm... actually, maybe I'll think about grading PA3....)

Lastly, professor Mitzenmacher is incredibly nice and fun to talk to if you get the chance.

Thank you!  But please, don't let the secret out....

Let's end with this summary, answering what you would want to tell future students:  

You probably have to take this. Cheer up! First of all, it's not nearly as bad as everyone says...

Thank you, I think?***



(***This last backhanded compliment reminds me of a joke from when I was a kid, quoting from https://en.wikipedia.org/wiki/F_Troop

Another running gag involves dialogue between Sergeant O'Rourke and Agarn. In many episodes O'Rourke says to Agarn, "I don't know why everyone says you're so dumb". After several lines of dialogue later, and occasionally after a commercial break, Agarn finally replies, "Who says I'm dumb?".

 )

SODA Information

Phil Klein passed on that there's a delay at SIAM in getting the SODA 2017 CFP up, and of course we want to get out the relevant information out to the community.  So he asked me to post the following:   

SODA 2017: The official SIAM symposium webpage is http://siam.org/meetings/da17/. This page does not yet have the call for papers. (My understanding is that the call for papers has yet to be approved by some SIAM staff who are out this week.) The deadlines are as follows: July 6 (short abstract and paper registration), July 13 (full submission).

The symposium will take place on January 16-19, 2017, in Barcelona, Spain.

For now, you can visit http://cs.brown.edu/~pnk/#soda17 for the basic information (deadlines, submission site, and program committee).

David Johnson

I was sad to learn that David Johnson passed away.  David was a leader in the theoretical computer science community for decades, both in his research and in his dedicated service to the community.  He is a role model, and should continue to be, especially for those who believe that theoretical computer science has a large role to play in the scientific world. 

Lance has already written a post describing David's long, inspiring list of accomplishments.  I encourage you all to read it. 

Distinguished Service Award

Nominations are open for the SIGACT Distinguished Service Prize.

More information is available at the SIGACT web site.  

Here's the key info:

Nominations

Nominations can be made by any member of the Theory of Computing community and should contain a statement of no more than 500 words explaining why the candidate deserves the award. The nomination can also include an additional separate listing of service activities, additional support letters, and other supplemental material such as a pointer to the candidate's CV. The nomination must include the name, postal address, phone number, and e-mail address of the nominator. Nominations are to be submitted electronically in PDF format by April 1, 2016, to the chair of the selection committee, Lane A. Hemaspaandra, at lane@cs.rochester.edu. Please put "SIGACT Distinguished Service Award Nomination" in the subject line.

Graduating Bits Announcement

Boaz asked me to remind people about ITCS, and in particular the Graduating Bits Event.  Just in time for those of us reading application folders....

ITCS 2016 will be held at MIT this year Jan 14-16. As in past years, we will hold a "graduating bits" event where students and postdocs that looking for positions can give a short presentation about themselves and their work. This can be a great way to let people know what you've been up to. See http://www.boazbarak.org/itcs16bits/ for more details. 

If you are interested in participating, please send Boaz Barak ( b@boazbarak.org )  an email with the subject "Graduating bits" and the following information:

1) Name, Affiliation, status (student/postdoc)

2) Photo of yourself (web quality - no huge files please).

3) A short paragraph (3-4 sentences) about yourself and your research.

4) Homepage URL

5) Your presentation - 4 slides in PDF format, of which the first slide should be a title slide.

There is no deadline per se, but the presentations will be scheduled in the order of submissions so it’s “first comes first served”. I will also maintain a website with the photos and slides of all presenters, which should be a useful resource for anyone looking to hire theoretical computer scientists this year.

Yes, We Have Postdocs This Year

The Harvard Theory of Computation group has postdocs.  This year, besides our usual general call for postdocs, we are also inaugurating the Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer Science.  This new fellowship has its own independent funding, so that researchers can do whatever they want, working with whomever they want, once they get here. 

Oh, there's also our postdocs at Harvard's Center for Research on Computation and Society, and Harvard's Center of Mathematical Sciences and Applications also. 

Please apply!

Yes, We're Hiring This Year

Harvard's CS search ad is apparently up and out.  We're eagerly awaiting applications....

https://academicpositions.harvard.edu/postings/6497

The Harvard John A. Paulson School of Engineering and Applied Sciences
seeks applicants for a position at the tenure-track level in Computer
Science, with an expected start date of July 1, 2016.

This is a broad faculty search and we welcome applicants in all areas
of computer science, including applicants whose research and interests
connect to such areas as engineering, medicine, and the social
sciences. We are particularly interested in candidates working in the
broad areas of machine learning, human-computer interaction,
programming languages, and systems (including networking,
architecture, and databases).

The Computer Science program at Harvard University is experiencing a
period of strong growth and expansion following an extraordinary gift
in support of new faculty from alumnus and former Microsoft CEO Steve
Ballmer, ‘77, and the largest gift in the University’s history,
received from John A. Paulson, M.B.A. ’80, in support of SEAS.

Computer Science at Harvard benefits from outstanding undergraduate
and graduate students, world-leading faculty, an excellent location,
significant industrial collaboration, and substantial support from the
Harvard Paulson School. Information about Harvard’s current faculty,
research, and educational programs in computer science is available at
http://www.seas.harvard.edu/computer-science. The associated Institute
for Applied Computational Science (http://iacs.seas.harvard.edu)
fosters connections among computer science, applied math, data
science, and various domain sciences at Harvard through its graduate
programs and events.

Candidates are required to have a doctorate or terminal degree by the
expected start date. In addition, we seek candidates who have a strong
research record and a commitment to undergraduate teaching and
graduate training.

Required application documents include a cover letter, cv, a statement
of research interests, a teaching statement, and up to three
representative papers. Candidates are also required to submit the
names and contact information for at least three and up to five
references, and the application is complete only when three letters
have been submitted. We encourage candidates to apply by December 15,
2015, but will continue to review applications until the position is
filled. Applicants will apply on-line at
https://academicpositions.harvard.edu/postings/6497

We are an equal opportunity employer and all qualified applicants will
receive consideration for employment without regard to race, color,
religion, sex, sexual orientation, gender identity, national origin,
disability status, protected veteran status, or any other
characteristic protected by law.

This Year's Andreessen-Horowitz Meeting

Andreessen Horowitz had another Academic Roundtable, which I've written about in previous years (here, here). 

For me, the most exciting session was on Virtual and Augmented Reality (VR/AR).  It made me sit up and take notice. 

Matthew Turk started with an introduction, likening augmented reality systems to giving people superpowers.  Then he discusses his Augmented Reality system for remote communication.  Imagine something wrong with your car;  you call up a repairperson with your phone.  Instead of just sending video, your phone also sends information building up a 3-D model of what's being viewed.  So the repairperson can manipulate that 3-D model, essentially poking around the car looking at things independently, and then sending you annotated information (like "flip this switch", and circling the switch in an image from the model).  It looked pretty useful.

Steven Seitz then talked about Google's Jump and Cardboard projects.  Jump is a relatively cheap circular camera system that lets you take 360 degree "surround-sound" type video.  Cardboard let's you take your phone, put it in an Viewmaster style cardboard box, and view these 360 degree videos.  I got to try it, and it's amazing;  you really feel like you're in the middle of a scene.  It's "immersive", which appears to the one of the buzzwords for VR/AR experiences.  A scene when you're in barn surrounded by horses in their stalls really had the feel of being in a barn surrounded by horses.  You have to be careful -- you tend to turn and walk a bit as you're in the scene, which can be a recipe for trouble (like walking into a pool with your cell phone).   I didn't realize how "soon" this type of VR experience will be mainstream.

Derek Belch of STRIVR talked about his company, which is bringing virtual reality systems to sports training.  So the quarterback can practice passing plays, getting the mental training without having to have a team physically out on the field.  Besides showing off their innovative system, he talked about building a company in this space. 

There were some other great talks -- several others, but to name just a couple, Michael Jordan of Berkeley talked about the theory of combining differential privacy with statistical inference, and Jason Mars of the University of Michigan talked about Sirius, their open-source intelligent personal assistant  

The meeting always makes the whole startup idea seem very exciting.  However, during Marc Andreessen's fireside chat session (no actual fire), they said the dominant failure case for failed startups coming out of universities is where a professor starts a company on an interim basis, and tries to hand it off to others.  There is no substitute for the "core team" being full time devoted to the startup.  (The "core team" doesn't have to include the professor, it could be students, of course.)   

The fireside chat also talked about CS education, and what it meant that CS was becoming mainstream.  How do we design a more open CS education, so people know enough to use and develop/create things on computers without being "computer scientists"?  How should we think of movements like the recent activity in New York, where Mayor de Blasio has said that all the city's public schools will be required to offer computer science to all of their students? 

Overall, again, I'm glad I had the chance to go.

[Note:  Andreessen-Horowitz doesn't pay me anything, or even suggest I blog about their meeting.  But they do pay for expenses for people they invite.]  

One Lecture Down....

CS125, the "new", "honors-ish" Algorithms and Complexity course, got off to a good start today.  The room was full with not enough seats for people, the students asked good questions and responded well to questions asked, and we got through the amount of material I expected.  It's year 2 of the class, which is easier than year 1 in some ways (lots of material prepared), and possibly harder in others (some thinking about what needs to be tweaked or fixed from year 1).  We'll see how things shake out next week, but I'm expecting we'll be in the 30-40 student range, like last year.  I can never tell if I managed to scare students off or make them want to take it.  (The challenge is that I want to do both;  scare off people without sufficient background, but interest students who do but might not realize it and might not even be Computer Science majors.)  Pleasantly, I felt very excited during and after the lecture, and will try to hold on to that positive energy.  

In other, much much stranger news, Harvard's CS50 appears to have a "backlash" movement, as described in today's Crimson article.  Apparently, according to some, there's intense "social pressure" to take CS50, and students need to be told that it's OK not to take the class.  I find this quite odd and, from my vantage point, misguided.  (Of course, I'm not a college freshman.)  I can't recall any such organized movement against Economics 10 at Harvard, which has been for decades now the most popular class at Harvard, although even when I was a student there was something one could potentially call cult-like about it.  (Cult of Wall Street....)  But that didn't mean people complained;  if you didn't want to take the class, you didn't, not really a thing.  Sure, the CS department here has been actively trying to attract students for decades -- CS50 was a good-sized class even before David Malan took over -- and David has just been very successful at it, with a combination of organization, interesting material, vision, and, yes, good marketing.  Naturally, here in CS, we believe that in our idealized world nearly all undergraduates would have a CS course as part of their liberal arts education, and we provide several other entry courses besides CS50.  I was initially thinking the movement described in the article was just a joke, and maybe I'm being April Fooled, but I'm not sure where those responsible are coming from.

And speaking of bringing in students to CS, Ben Golub and Yaron Singer are doing a new Econ-CS class at Harvard (counts for either;  also good for Applied Math majors) simply entitled Networks.  I'm a bit jealous -- this is a class I've thought about teaching also, but was busy and happy teaching algorithms -- but hopefully now that they've started it up it means I'll get a chance to teach it some year(s) down the line.

More insight into whether our enrollment numbers are still rising (is that still possible?) next week...

 

CACM Viewpoints on Theory and Experiments

There's a fun pair of viewpoints in the September CACM by Jeffrey Ullman and myself on experiments in computer science research, with him addressing systems conferences(/people) being far too focused on experiments as the research validation methodology, and me addressing theory conferences(/people) being almost strangely averse to experimental results.  (This link may bring you a digital version of his viewpoint, and this link to mine.)  I hope they might be interesting reading or food for thought.  As someone who works in both camps, I find this separation -- which we both seem to think is growing -- worrisome for the future of the CS research community.   

We actually wrote these up about a year ago (or maybe longer).  Jeff wrote something on the topic on Google+, and I responded.  I think he got drafted into writing something for CACM, and then I got drafted in later.  There was a pretty thorough reviewing process, with a couple of back and forth rounds;  then there was a non-trivial wait for publication.  This seems OK to me -- I'm glad CACM has a non-trivial queue of items for publication.  Overall it was a thorough and reasonably pleasant publication experience, and it's appealing that CACM offers a platform for these types of editorial comments.

SIGACT Meeting, Some Stuff

As some of you know, I was recently elected to the position of SIGACT (ACM Special Interest Group on Algorithms and Computation Theory) Chair.  So some part of this blog will be devoted to issues related to SIGACT for the next few years.  Comments and opinions are, naturally, extremely welcome.  

I'm on the train back from an orientation meeting for new chairs, and the SIG Board meeting.  Here are some things mostly from the orientation meeting, in a semi-random order.

1)  For people who have issues with ACM publication practices, some news.  First, they've moved to a model where conferences can maintain links to papers so that they are freely accessible.  STOC is/will be doing this, for example, so there will be a "permanent" STOC conference page each year with links to the STOC papers.  Similarly, authors can generate an "Author-izer" link for their web page giving people access to each of their ACM papers.  (I think there is a limit there of one such link per author.)  In any case, making publications more freely accessible is an issue ACM is dealing with, and the direction appears quite positive.

2)  There's other publication issues being considered, including whether/how conference papers can be published as journal articles in computer science (what should be the conference-journal relationship?), and some other forward thinking about publication models.  [There will be editorial and some viewpoints in the September CACM issue.]

3)  On the more mundane side, ACM is re-doing its website.  There is a preview at preview.acm.org , and they are desirous of feedback.  (On most browsers, there should be a feedback link over on the right hand side of the page.)

4)  The ACM is starting to do book series.  You can get more information at books.acm.org , and they are looking for authors.

5)  The ACM has a student research competition (beyond the CRA stuff) -- information at src.acm.org .  We may look to see if we can incorporate this into STOC (or another theory conference).

6)  For those interested in logic and computation, or formal methods in computer science (broadly defined), you may be interested in (and not yet have heard about) SIGLOG (The ACM Special Interest Group on Logic and Computation), which formally came into being about a year ago.  Please consider joining.  

There was plenty of other stuff, but it was primarily administrative information that would bore you.

The High Cost of Conferences

At some point, I'm convinced the "conference structure" is going to fall apart.

Case in point -- I haven't bought my tickets yet for SIGCOMM because, unless I'm missing something, a schedule isn't up yet, and unfortunately, because ACM has scheduled a SIG chair meeting overlapping with SIGCOMM (which I don't understand also, but perhaps beside the point), I want to see what's going on when at the conference to plan my timing.   

6+ weeks out, round trip tickets from Boston to London are over $2500 on nonstop economy flights.  And those don't seem to be on US carriers;  since I have to stop back through New York for this other meeting, and I need to find a US carrier (or figure out if this is a case where it's an exception to what is the currently believed NSF policy), tickets look to be well over $3000.  Then there's registration, hotel, etc. 

At some point, this becomes unsustainable, I think.

SoCG Proceedings

The 31st International Symposium on Computational Geometry has its proceedings available online here.

I point this out because the SoCG proceedings were managed by LIPIcs, the Leibniz International Proceedings in Informatics.  I've been on the editorial board for LIPIcs for several years.  The goal was to establish an open but professional publication mechanism that would be affordable in comparison to what was being offered by standard publishing programs.  From the announcement in 2009:

Schloss Dagstuhl Leibniz Center for Informatics (LCI) establishes a new series of conference proceedings called Leibniz International Proceedings in Informatics (LIPIcs). The objective of this series is to publish the proceedings of high-quality conferences in all fields of computer science, and LCI institutes an Editorial Board to oversee the selection of the conferences to be included in this series.

The proceedings in the LIPIcs series will be published electronically and will be accessible freely and universally on the internet, keeping the copyrights of the authors, and under an open access license guaranteeing free dissemination. To face the cost of electronic publication, a one-time fee will be required from the conference organizers. This fee will be kept to a minimum, thought to cover the costs of LCI, thanks in particular to a sharing of the workload between LCI and the conference organizers. 

LIPIcs has been, I think, growing in visibility and success, in terms of attracting more conferences.  If you're looking for a different approach to publishing proceedings for your conference that seems more in line with what many I've heard want from their conference proceedings, I encourage you to take a look.  It may not be for everyone, but we expect it may be useful for more conferences than are currently using it.  

More Good News for SEAS

About six months ago, I was able to point to a nice gift from Steve Ballmer for Computer Science at Harvard.  Today, more good news, this time for all of the Harvard School of Engineering and Applied Sciences:  a $400 million gift from John Paulson, which (at least for now) is the largest donation to Harvard in its history. 

Not surprisingly, there's extensive new coverage, starting with the Harvard Gazette, the Harvard Crimson, and the New York Times.

While I'm not aware of the details of the effects on our budget, it's clearly great for us long-term, and will help us continue to innovate and grow.   

Also, for those interested, a recent Q&A with Harry Lewis from the Crimson, who's been acting as Interim Dean for SEAS.

What makes a well-attended conference? (STOC 2017 Discussion)

I've always been impressed how the SIGCOMM conference accepts a very small number of papers, but many hundreds of people attend the conference.  (This is true for some other conferences as well;  SIGCOMM is just he one I happen to know best.)  The conference is somehow an "attend-if-possible" venue for the networking community.  Most other large conferences I know work instead by accepting a lot of papers.  ISIT is a week-long event with 9 parallel sessions (in 2014).   Location may certainly be helpful;  ISIT was in Honolulu in 2014 and Hong Kong in 2015;  SIGCOMM will be in London this year.  But it also isn't decisive;  the Allerton conference has been steadily growing, so it's a few hundred people, even though Urbana-Champaign, where the conference is held, really can't be the biggest draw.  (No offense to those who are there -- I always enjoy visiting!)  In fact, really, at this point, Allerton has been so successful it has seemingly outgrown the Allerton conference center!

If you have ideas for what makes a conference a "must-attend" venue, I'd be interested in hearing them.  The question has arisen because of a Windows on Theory post about changing the format for STOC 2017;  for those of you on the theory side who haven't seen it, I'd recommend looking at the post and registering an opinion by comment or by e-mail to the appropriate parties, after you've considered the issue.  The underlying question is what role should the STOC/FOCS conferences play in the world these days, and how might we change things to get them to play that role.  I think another way of framing this is that I don't think STOC/FOCS aren't really "attend-if-possible" venues for much of the theory community -- particularly for certain subareas -- and the question is whether this can change.  Again, I'd be happy for insights from other communities as well.  

There are a large number of comments already.  I'd say in terms of my personal opinion on what to do I'm most aligned with Alex Lopez-Ortiz and Eric Vigoda.  Alex's point is straightforward -- accept more papers.  I've been in the accept more papers camp for a while (a very old post on the topic suggests one way it could be done), but for some reason there seems to be huge numbers of people in the theory community against the idea, based on some sort of quality argument. For me, the tradeoffs are pretty simple;  I generally prefer not to travel, so I need a good reason to go to a conference, and one very good reason is that I have a paper in the conference that I or a colleague is presenting.  (I recognize this is not true for everyone, but being selective in travel is an issue that arises for people with families, or other regular obligations.)  Clearly conferences such as SIGCOMM show that there are other paths possible, but I'm not clear on how to reproduce that kind of buy-in from the theory community.  Eric's suggestion was that lots of theory conferences happen during the summer, so instead of trying other ways to create a larger "STOC festival", why not co-locate a number of conferences (that would have parallel sessions) that would get more of the theoretical computer science community together.  That makes sense to me, and seems like it could be particularly beneficial for some of the smaller conferences. 

But my personal opinion, while undoubtedly fascinating to some (most notably myself), is really not the point.  The point is for the community to examine the current situation, think if there are ways to make it better, and then act on what they come up with.  The bet way for this to happen is if people actively participate in discussions.   So please, go opine!  There's no reason the post shouldn't have 100+ comments, so comment away.  

New Work on Equitability and MIC

A few years ago, working with a diverse group of scientists, I was looking at a problem related to big data analysis.  The setting was data exploration, where you are working with a high-dimensional dataset, and you are seeking pairs of dimensions that are related in interesting but a priori unknown ways;  that is, maybe there's a linear relationship, but maybe there's a more complicated relationship (sinusoidal, parabolic, etc.), and you don't know what you're looking for in advance.

One statistical approach is to throw a so-called measure of dependence at the problem, which will tell you whether variables are related or unrelated.  But in big data sets, you may expect to have lots of dependent pairs;  what you really want is not just a "dependent-independent" test, but a scoring mechanism that ranks the extent of dependence appropriately over a wide range of possible relationships.  This methodology seemed underserved by the literature.  We dubbed what we were aiming for "equitability", and designed a statistic we dubbed MIC (maximal information coefficient), a "bucketed" version of mutual information, that seemed to be a good ranking mechanism for equitability.  The work appeared in Science some years back (the link here will allow you to access it). 

The work has, I think, been quite successful -- a number of people have used MIC in their research to analyze data sets, and the idea of equitability seems to be catching on.  But after it came out, there were some questions and issues raised primarily by statisticians.  We had always planned to go back and revisit some of these issues, and, after various delays caused by life, a group of us started back on it again.  The project seemed to balloon, and we've been working on and off on it for at least a year now.  (Some earlier, initial drafts pointing to where we were going are on the arxiv.)   Finally, we've reached a stopping point, and we've just put up 3 papers on the arxiv, all of which are now being submitted to various journals.  In this post, I'll outline what the papers cover, after the links.

1. Equitability, interval estimation, and statistical power. arXiv
   
   
2. Measuring dependence powerfully and equitably. arXiv
   
   
3. An Empirical Study of Leading Measures of Dependence. arXiv 

Really, there seemed to be 3 issues that people wanted to hear more about after the initial work, and each topic ended up being "large" enough that it merited its own paper.

First, people wanted further theoretical foundations for equitability.  Our Science paper, being for a general audience, provided an intuitive definition, but we didn't define it as one would in a mathematics paper.  (That was, I should be clear, intentional.)  We thought our definition was pretty clear in plain English, but for some it was not sufficient;  one group, in particular, seemed to ignore our explanations when in their own work they added restrictions to "equitability" and incorrectly ascribed them to us. 

So the first paper formalizes this notion of equitability.  As is usually the case, formalizing it turns out to be helpful.  In particular, it shows that there are (at least) two natural ways of thinking about equitability.  One way formalizes our original conception that an equitable statistic is a statistic that gives similar scores to relationships with the same amount of noise, even if the relationships are of different types.  But a different way of viewing the formalization shows that equitability can naturally be seen as an extension of statistical power against a null hypothesis of independence (i.e., relationship strength = 0), to power against null hypotheses representing all levels of dependence (i.e. relationship strength <=x for any x).  This view clarifies the relationship between equitability and power against independence, showing the former generalizes the latter.  In our new papers we have some really nice "heat-map" style visualizations for viewing equitability performance results based on this view that I think are really useful in thinking about and understanding equitability in the paper.  

Second, people wanted faster, better versions of our proposed scoring function, MIC.  We ended up going back to the theory of MIC, examining further its relation to mutual information, and, perhaps unsurprisingly, doing so allowed us to make tangible practical advances.  We ended up with algorithms for computing MIC that are both faster and more accurate.  (Our original algorithm in the Science paper used a heuristic approach based on dynamic programming to approximate the MIC score from the data;  our new approaches have both improved speed and accuracy.)  We're hopeful that people using MIC will be able to switch over time to these improved algorithms.  Connecting to the first paper, in re-examining MIC we also developed a variation of MIC (called TIC, for total information coefficient) that is better designed for achieving power against independence as opposed to equitability.  We are hopeful that TIC may prove useful to people on its own, as well as in conjunction with MIC. 

Third, people just wanted to see more comparisons.  Well, really, here I think everyone just has their own favorite measure of dependence, and before they go switching to this new-fangled thing that appeared in Science of all places, they want to see more.  Specifically, subsequent to that initial paper, there were people concerned about the power against independence of our methods -- although, again, to be clear, equitability is a larger notion that power against independence, so one might expect a method designed for equitability would not have as high power against independence as methods designed specifically for that purpose.  Also, there were some people who claimed, based on very limited experiments, that mutual information estimation would be more equitable than MIC.

So the third paper is a large-scale empirical study.  In terms of equitability, we find that MIC still seems to be the current best measure.  (Mutual information sometimes does well -- in some very particular circumstances, it can do better than MIC, which is not especially surprising since MIC is a "scaled" version of mutual information -- but MIC still performs much better overall.)  In terms of power against independence, we find that MICs power was underrated in previous studies.  The discrepancy seemed to be that previous studies used MICs default parameter settings, which were designed for equitability performance, not power against independence;  using different default parameters yields substantially better power against independence.  (The new algorithms in the second paper that yield more accurate calculations improve the power further.)  Finally, the TIC measure described in the second paper does even better, is easily computed when computing MIC scores (and so has negligible overhead if computing MIC scores), and appears to be comparable to other state-of-the-art measures in terms of power against independence.  We also find that the new ways of computing MIC are indeed faster and more accurate than previous methods. 

We're hoping these works, collectively, move the ball forward on this topic.  We like seeing MIC being used, and hope people will start using it more when analyzing their large dimensional data sets.  To be clear, perhaps tomorrow we will find that there are better scoring mechanisms than MIC for equitability;  perhaps even better mutual information estimators will suffice.  That would be great!  (I think of it like clustering algorithms;  there are lots of good clustering algorithms, different ones may be better suited to different situations.  The more the merrier.)  We also think equitability continues to be a useful framework, and that there's more to be done with equitability.  Though for now our group may again take a breather on this topic, and see what arises from our current work. 

Girls Who Code (Newton) Visit to Harvard

My friend David Miller is looking for instructors to help out with the Newton Girls who Code club.  Here's an announcement, please connect with him if you're interested. 

They visited Harvard last week -- David gave me permission to post his description of the visit.  It seemed like a well-organized event -- thanks to the Harvard Women in Computer Science group for putting it together.

----

Last Friday, the Newton Girls Who Code club was welcomed by the Harvard Women in Computer Science at Harvard's Maxwell-Dworkin Laboratory. The students learned about the joint Harvard-MIT Robot Soccer team from the mechanics tech lead, Harvard junior Kate Donahue. She showed us last years fleet of robots (named after Greek and Roman gods), and described their work on preparing this years fleet (to be named after Harry Potter characters). Kate emphasized the interplay between computer vision, artificial intelligence, mechanical engineering, and distributed systems. Many of the robot parts are 3D printed -- a technology that the Newton GWC students will become more familiar with this fall as we integrate the Newton Library's 3D printer into the GWC activities.
 
After the robots demonstration, the students took part in a Q+A discussion with Harvard WiCS undergrads Hana Kim, Ann Hwang, and Adesola Sanusi. Our students asked great questions about our hosts' motivation and history with coding, the mechanics of being a college CS major, the role of gender in the CS community, the connections between computer science and other fields, and our hosts' vision for the future of computing. The WiCS undergrads are excellent role models and were enormously encouraging. They pronounced our students more than ready to take Harvard's most popular course, Introduction to Computer Science, and recommended they try out the free, online, EdX version today. It was an exhilarating afternoon!

My (Positive) Apple Retail Repair Experience

I switched to Apple machines several years ago, and have been very happy with them generally.

One convenience is there is an Apple store in the mall about 10 minutes from my home, so when things go wrong, I know where to go.  Thursday night a screen-related hardware glitch developed (which, to be clear, in this case was not what I would call a product defect;  let's say it was a me defect).  I ran over and they said it would probably need to be taken in for a repair.

Not being ready to hand over machine just yet, I went home to pull off some data, and then booked an appointment.  The downside to the Apple store is you really need to book an appointment online, even for (or especially for) things involving repair.  My walk-in Thursday I didn't even get up to the Genius Bar; one of the people up front just suggested what they thought was going on.  And my Apple store, at least, is painfully busy, all the time.  I got an appointment for Saturday afternoon, nothing available Friday.  I went in Friday morning before heading to work on the off chance I could get it in then;  they said the walk-in waiting time was 90 minutes to 2 hours.  I should have expected;  the walk-in waiting time always seems to be measured in hours.

That's the downside.  The positive is, when you have an appointment, they are great.  I had no wait when I went in Saturday, and in the past, if they're running behind, they've let me know if I have to wait for my appointment and estimated for how long.  They are courteous and professional.  They will let you know what they are doing as they test your machine, what needs to be done, and provide estimates for how long it will take.  Their setup really engenders trust.  I also have found their repair times reasonable and understandable.  My machine is back to me and all is well Monday afternoon.  (Thank you, Apple Store.) 

I haven't had to deal with them often over the last decade -- I'd say a reasonable number of times considering the number of Apple machines I've had and in family use.  Overall this experience is typical.  There's anxiety in going in for any sort of repair process, but they did an excellent job.

Finally, I imagine this is not useful advice to people reading this blog, but do back up your data regularly and/or automatically.  One of the first questions they always ask is whether you have a backup, and it's always a good feeling to know that if worst comes to worst you just put your state on a new machine.  Someone else at the Genius Bar while I was there had their computer put back in working order but their data was lost;  they weren't the sort of user that it was a real problem, but the occasional reminder that backups are important is always helpful.

  

Women in Math (and Computer Science)

Wednesday afternoon I went to a panel organized by the Harvard Undergraduate Mathematics Association for a "Gender Gap on Math Discussion".  I went both to hear what was going on (as there's still that gender gap in CS, and we're always eager to hear ways that we might do things better that might reduce that), and for moral support for some people I know who were involved.  The panel was co-organized by Meena Boppana, an undergraduate who did research with me the summer before last and is currently a star in my graduate class, and one of the panelists was Hilary Finucane, a graduate student who I advised on her senior thesis and collaborated with on multiple papers with when she was an undergraduate at Harvard.  I should note that Meena and several others had done a survey of Harvard math undergraduates which had highlighted some issues that would be a starting point for discussion.   

I could only stay for the first half or so, but it seemed very positive.  A number of faculty showed up, which was promising.  My take on the panel's take was was that they were interested in how to make improvements in the culture, and the goal was to try to start figuring out how that could happen, in part by sharing their experiences.  The discussion was both balanced and thoughtful, presented positives with negatives, but focused on how to improve things.  There's a writeup in the Crimson with more details.  The main point that came out in the first half was something I've seen and heard before:  the importance of having a community, including (but not necessarily limited to) a community of women that can offer support, guidance, and mentorship, but also just so you don't continually feel like the only woman in the room. 

And as long as we're on the subject, there's been a number of recent stories (or older stories where I've recently seen the links) on women in math and computer science.  Focusing on Harvard to start, there's a nice writeup about Harvard's Women in Computer Science group, which has helped provide that community that encourages women to take classes in and concentrate in computer science.  An article from last year discusses progress at Harvard in closing the gender gap in computer science.  There was even an article in the Harvard Political Review covering gender gap issues at Harvard.

Outside of Harvard, from sources on Google+ I've seen a blog post with an interesting slide deck from one Katie Cunningham that provides a great starting point of discussion about the culture and women in computer science.  And, finally, a link to something simultaneously sad and funny (things-male-tech-colleagues-have-actually-said-annotated) that reminds us why we have to keep trying to improve the culture.