Wednesday, January 09, 2019


I spent the last few days at SODA-ANALCO-ALENEX-SOSA in San Diego.  (Nice location choice, I'd say!)  Here's some news.

This will be the last ANALCO (Analytic Algorithms and Combinatorics).  Apparently submissions have been decreasing, so they've decided it will halt and the work on these topics will go into SODA and other conferences.  I'm not sure how to think of it -- I think we as a community have far too many conferences/workshops generally, but I think the SODA model of having ANALCO and ALENEX (and now SOSA, I imagine) folded in cleanly into the main conference is an excellent model.  I also like the ANALCO topics.  But I can understand the time may have come to do something else.  Thanks to everyone who worked to organize ANALCO and keep it going these many years.

It looks like SOSA (Symposium on Simplicity in Algorithms) will be taking its place in the SODA lineup.  I co-chaired the symposium with Jeremy Fineman this year, the second for the symposium.  I was surprised by the high quality of the submissions, and was then further surprised by the strong turnout at SODA.  The room was quite full for the Tuesday afternoon sessions, and there were easily 75+ people at several of the talks.  I do think there's a need for SOSA -- no other workshop/conference hits the theme of simplicity in our area, and it's a really nice fit with the rest of SODA.  I'm hoping it will last, and in particular that they'll continue to have a good number of high quality submissions, but that depends on all of you.  Ideally, there will be a positive feedback loop here -- now that there's a good home for this type of work (besides notes on the arxiv), people will be more inclined to write up and submit things to SOSA.  For Tuesday's talks, I'll call out Josh Alman's great presentation on "An Illuminating Algorithm for the Light Bulb Problem" as my favorite for the day.

With ANALCO exiting, though, I think there's more room for additional satellite events at SODA, so hopefully some people will get creative.

If I had thought about it I should have live-blogged the business meeting.  I'd say as highlights, first, Sandy Irani presented the report of the ad hoc committee to combat harassment and discrimination in the theory of computing community.   (See here for the report.)  There was an overwhelming vote to adopt their recommendations going forward.  It's good to see progress in addressing these community concerns.  Second, Shuchi Chawla will be the next PC chair, and she brought forward a plan to have SODA PC members be allowed to submit papers (with a higher bar) that was voted on favorably as well.

I suppose the last note is that Jon Kleinberg's invited talk was the conference highlight you expect a Jon Kleinberg talk to be, with interesting results and models related to fairness and implicit bias.

Thanks to SIAM and all the organizers for their hard work.

Wednesday, December 05, 2018

NeurIPS 2018 Post

Today was my first day at a NeurIPS conference.  Advertising note, before my thoughts on the experience:
Tomorrow I'll be stationed at a poster 10:45 AM -- 12:45 PM @ Room 517 AB #169
A Model for Learned Bloom Filters and Optimizing by Sandwiching
and at the same time Diana Cai will be stationed at a poster I'm involved with:
Room 210 #26
A Bayesian Nonparametric View on Count-Min Sketch
Please stop by to talk to me if you're around -- Room 517 seems to be a bit off the beaten path and I'm concerned I'll be lonely with nobody to talk to.  And of course stop by to see Diana too.

NeurIPS is just huge.  It's like an extremely large academic conference (of 1000-2000 people) glued together to an extremely large industry conference (of more than that).   Just the academic part (talks and poster sessions, 3 parallel sessions for talks) is a lot, and then there's a trade show with booths from 50+ companies there too.

I think I'd like the academic part more if I was in the area -- I'm coming in from the algorithms perspective, and there's a bit of language gap.  It seems to me that conference suffers from some of the standard aspects of large conferences -- with scope and size that big, you have to look and find the things that are interesting and important to you, because a fair bit probably isn't.  And while I can't tell entirely myself, I'm told by others that, given the size, there's not a lot of "junk" -- the work seems good-on-average.  Also, given the conference size, it seems well organized -- staff managing the people flow, they keep things on time, plenty of room in the poster session (with appropriate food and drink stuff).  I can appreciate the work that must go into to making something this big work.

Because the conference is so big, I've run into a good number of "theory people" here.  As a percentage of attendees, we're probably small, but it's a good number because it's so big.  I kept running into people at the poster sessions, which was nice.

The trade show part is impressive in its own way.  If you didn't know AI was big, this would tell you.  All the big players are there, but there are at least a dozen machine-learning focused companies I haven't heard of, and that's not including the dozen or more consulting/Wall Street/hedge fund firms that are big enough into AI that they want to have a presence here.  I understand there's lots of networking and pre-interviewing and interviewing going on.  On the positive side, I feel like if I wanted to leave academia, I could land a job with a variety of AI-based companies, beyond the big companies.   

Hopefully tomorrow will be interesting as well.

Thursday, October 25, 2018

Rabin Postdoctoral Fellowship Advertising Post

Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer Science

Deadline for full consideration: December 3, 2018.  Applications can be submitted here:

The Harvard John A. Paulson School of Engineering and Applied Sciences at Harvard University seeks applicants for the Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer Science. The standard duration of the Rabin Fellowship is two years. Rabin Fellows will receive a generous salary as well as an annual allocation for research and travel expenses.

Past fellows are Mika Goos and Aviad Rubinstein and the current fellow is Alexander Golovnev.

We are looking for exceptional junior scientists in theoretical computer science, broadly construed. Rabin Fellows will be provided with the opportunity to pursue their research agenda in an intellectually vibrant environment with ample mentorship. While interaction with Harvard faculty, students, and visitors is encouraged, Rabin Fellows are free to pursue their own interests. Candidates are required to have a doctorate or terminal degree in Computer Science or a related area by the expected start date.

Required application documents include a cover letter, research statement, CV (including a list of publications), and names and contact information for three references. We recommend that papers mentioned in the CV be available online on your homepage or on electronic archives. Applicants will apply on-line at the above address. We encourage candidates to apply by December 3, 2018, but applications will be accepted until the position is filled.

Harvard is 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.

Monday, September 10, 2018

Lenore Blum interview

I've just read this, and do not have any specific comments, but I thought this interview with Lenore Blum on her recently announced resignation from CMU would be something of interest to the larger community.  (Thanks to Margo Seltzer for forwarding it to me.) 

Monday, July 23, 2018

Symposium on Simplicity in Algorithms, Submission Server

A reminder that the deadline for SOSA 2019 is August 16.  The submission server is live and running (and we already have some submissions!).  The easychair link is , and general information can be found at .

Friday, June 22, 2018

STOC Lunch Sign-ups, and Reminder

Just a reminder that next week is the 50th STOC in Los Angeles!  You can still come and register on site, so please come -- the program is STOC-full of good stuff.  Especially all you Californians -- no excuse not to be there.

An innovation introduced at last year's STOC was the junior/senior lunch meet-up.  Senior people sign up to meet with junior people over lunch at a day of their choosing, and then (three) junior people (undergrad/grad/postdoc) can sign up to go to lunch with the senior person.  The goal is to increase chances for junior people to get to network with more senior people, something that we hard heard was lacking previously.  (Everyone buys their own lunch.)  You can find the on-line sign-up sheet here.  Please go on and sign up as soon as you can!

Tuesday, May 29, 2018

Sympoisum on Simplicity in Algorithms, 2019

Jeremy Fineman and I are co-chairing the 2019 Symposium on Simplicity in Algorithms, the second year of this new endeavor.  It's nicely co-located with SODA, and the submission deadline is August 16.

This symposium arose of an apparent need to have a home for results that were focused on simplicity -- specifically, a place where you could introduce a simpler algorithm or a simpler analysis of an existing algorithm for a problem.  I think we're still in the stage for testing that need, but it would be nice to make this a permanent addition to our conferences, and like ALENEX and ANALCO, it's a great fit as a co-located SODA event.  

Please spread the word, and submit your papers -- we look forward to reading them.  More call information is available here.  

STOC 2018, Early Reg Deadline

Just a reminder that the early registration for STOC 2018 is June 1.  Besides wanting that early registration discount price, you really want to also make your hotel reservation -- the conference hotel special rate is (only) available through June 1.  I was looking this morning, and as the web page warns, hotels in LA that week are going to be expensive -- there's an award show in town that will be filling the hotels.

So please register today.  (Or tomorrow.  But by Thursday for sure.)

Monday, May 07, 2018

SIGACT-Related Stuff

Some SIGACT related-stuff of import:

First, there's an election going on!!!  If you're an ACM/SIGACT member, you've probably gotten an e-mail about this, and it's probably gone into some folder that you probably never look at.  Please check your e-mail for a subject like "ACM SIG 2018 Election".  I believe the deadline is the first week or June or so.  Please vote!  (Bios and related materials for people running can be found here.)

Second, the Knuth Prize call is out.  (It should be on the SIGACT web page shortly, but the main info is cut and pasted below.)  July 1 deadline is perhaps the most important part.

Third, keep in mind the early registration/hotel deadline for STOC (which runs June 25-29 in Los Angeles) is coming up, June 1.  It will be another "theory fest", so expect some great keynote speakers and invited talks, workshops and tutorials, poster sessions, and other great events.  If you went to STOC last year in Montreal, you know the "theory fest" is a different creature than previous STOCs, and that you don't want to miss it.  Also, it's the 50th STOC, so there will be some events specifically for that.  STOC is the theory conference you really want to go to -- sign up and make sure to get the early registration fee.

Knuth info below:

Nomination Procedure. Anyone in the Theoretical Computer Science com-
munity may nominate a candidate. To do so, please send nominations to by  July 1st, 2018. The nomination should
state the nominee’s name, summarize his or her contributions in one or two
pages, provide a CV for the nominee or a pointer to the nominees webpage, and
give telephone, postal, and email contact information for the nominator. Any
supporting letters from other members of the community (up to a limit of 5)
should be included in the package that the nominator sends to the Commit-
tee chair. Supporting letters should contain substantial information not in the
nomination. Others may endorse the nomination simply by adding their names
to the nomination letter. If you have nominated a candidate in past years, you
can re-nominate the candidate by sending a message to that effect to the above
address. (You may revise the nominating materials if you so desire).

 Criteria for Selection. The winner will be selected by a Prize Committee

consisting of six people appointed by the SIGACT and TCMF Chairs, see below
for the composition of the committee. All nominations will be considered by
the Committee, including those submitted in previous years, but nomination is
not a requirement to receive the Prize. Note that the Knuth prize is awarded
to a single individual each year. Nominations of groups of researchers will not
be considered.

In selecting the Knuth-Prize winner, the Committee will pay particular at-
tention to a sustained record of high-impact, seminal contributions to the foun-
dations of computer science. The selection may also be based partly on ed-
ucational accomplishments and contributions such as fundamental textbooks
and high-quality students. The award is not given for service to the theoretical
computer science community, but service might be included in the citation for
 a winner if appropriate. The current prize committee consists of Avrim Blum
(TTIC), Allan Borodin (U. Toronto), Alan Frieze (CMU), Shafi Goldwasser (UC
Berkeley), Noam Nisan (Hebrew U.), and Shang-Hua Teng (USC, chair).

Sunday, April 15, 2018

New Papers/Code for MIC and MINE

Several years ago, I worked on a project where the goal was to try to come up with an "equitable" version of a measure of dependence;  the idea was you could take a large multi-dimensional data set, score the dependence for each pair of variables, rank the pairs by their score, and then look at the top-scoring paris to try to determine the most interesting relationship to follow up on in further work.  We were motivated by the need for data exploration tools for multi-dimensional data sets.

After a large number of years, we've updated the site , with some (finally) recently published papers, and new versions of the code that are faster, more accurate, and can do additional tasks (what we call TIC as well as MIC).  Our technical information subpage has links to papers, including the relatively recent papers in JMLR and the Annals of Applied Statistics.  Our MINE-Application page contains links to our new version of the code, as well as links to other versions (such as minepy, a library that has APIs in python and Matlab). 

The incentive for all this was, in part, one of the co-authors, Yakir Reshef, finishing up his PhD thesis.  Congratulations Yakir!