Tuesday, July 03, 2012

Guest Post: Women in Theory Workshop I

My student Samira Daruki recently attended the Women In Theory workshop at Princeton. This is the first part of her (lightly edited) report from the workshop, focusing on the technical talks. For more on the workshop (from a presenter's perspective) see Glencora Borradaile's post.

This past week, I was at the third workshop on “Women in Theory (WIT)” workshop held in Princeton University with about 46 female students and 12 speakers. Most of the students came from different schools in USA:  University of Maryland, College Park, Brown, Oregon State, UMass, MIT, Stony Brook, Berkeley, Princeton, Columbia, Boston U, Washington, Stevens Institute of Technology, , UCSD, Northwestern, Harvard, UW-Madison, UCLA, CUNY, GMU, Harvey Mudd and Uta . There were also some international students from India (IIT), ETH Zurich, Germany, Canada (Toronto), City University Hong Kong, Moscow Engineering Institute and Israil (Technion, Weizmann, Hebrew).

Participants were from a wide range of research fields like Cryptography and Privacy, Graph theory and algorithms, Computational Geometry, Computational Biology, Complexity, Game theory and mechanism design and Social Networks. But the interesting thing was that you could find more students working on cryptography than other fields.

Tal Rabin, Shubhangi Saraf and Lisa Zhang were organizers of the workshop and there were many junior and senior women in the field as speakers: Gagan Aggarwal (Google), Glencora Borradaile (Oregon State), Joan Girgus(Princeton), Nicole Immorlica (Northwestern University), Valerie King (University of Victorial),Maria Klawe (Harvey Mudd), Vijaya Ramachandran (UT Austin), Jennifer Rexford (Princeton),Dana Ron (Tel Aviv University), Ronitt Rubinfeld (MIT and Tel Aviv University), Shubhangi Saraf(IAS), Rebecca Wright (Rutgers and DIMACS).

Beside the non-technical parts of the workshop, there were many interesting technical talks by different researchers on different topics.

Among them, one of the very wonderful and interesting talks was presented by Dana Ron (Tel-Aviv University, Columbia) on sublinear-time algorithms. When we refer to “efficient algorithms” we usually mean “polynomial-time algorithm” and at the best we can try to lower the degree of the polynomial as much as possible, leading to “linear time algorithms“. However when we are dealing with massive data sets, even linear time might be infeasible. In these cases we look  to design even more efficient algorithms, namely “sub-linear time algorithms”. These algorithms do not even go through the whole input data, so we just expect to output approximately-good answers. They are also probabilistic, and so are allowed to have  a failure probability (i.e are Monte Carlo).

One such type of algorithms are property testing algorithms, in which one has to decide with high success probability whether an input (like a graph), has a certain property (for example is bipartite), or is relatively far from having that property (for example in this case a relatively large fraction of its edges should be removed so that the graph become bipartite). In this talk several properties and algorithms were discussed. Other types of sublinear algorithms discussed in her talk were algorithms for estimating various graph parameters, like the number of connected components, the size of a minimum vertex cover, and so on. I think Dana wase able to give a flavor of analysis techniques for sublinear-time algorithms with great clarity,  and it was definitely one of the best talks in this workshop.

Another great talk was given by Ronitt Rubinfeld (Tel Aviv University and MIT), on estimating properties of distributions. In her talk, she surveyed a body of work regarding the complexity of testing and estimating various parameters of distributions over large domains, when given access to only few samples from the distributions. Such properties include testing if two distributions have small statistical distance, testing if the marginal distributions induced by a joint distribution are independent, testing if a distribution is monotone, and approximating the entropy of the distribution. In this kind of problems, the classical techniques such as the Chi-squared test or the use of Chernoff bounds have sample complexities that are at least linear in the size of the support of the underlying discrete probability distributions. However, algorithms whose sample complexity is “sublinear” in the size of the support were shown for all of the above problems.

Nicole Immorlica (Northwestern University) also gave an interesting talk about cooperation in social networks, presented as a game among students. In this talk, she explored the impact of networks on behavior through a study of the emergence of cooperation in the dynamic, anonymous social networks that occur in online communities. In these communities, cooperation (for example in business deal) results in mutual benefits, whereas cheating results in a high short-term gain.

Some of the other interesting talks was presented by Gagan Aggarwal (Google) on mechanism design for online advertising, Glencora Borradaile (Oregon State) on designing algorithms for planar graphs (and it was the only talk on the blackboard without any slides!), Vijaya Ramachandran (U of Texas, Austin) on Parallel and Multicore Computing Theory and Valerie King (University of Victoria) on Dynamic Graph Algorithms for maintaining connectivity. In her talk, Valerie discussed this problem that had been studied for over 30 years, and she reviewed the area and described a new direction for achieving polylogarithmic worst case performance. At the end of her talk she also mentioned Mihai Patrascu as a pathbreaking researcher who was taken too soon from us.

Unfortunately there were no talks on topics like Computational Geometry, but we had a few students working on CG related topics and they presented their research problems in the rump session. My presentation at the rump session was on building core sets for uncertain data


  1. Congratulations to all the speakers. Nevertheless, I find the concept of this conference rather sexist.

  2. I'm not sure what that means. If you define "sexist" as "pays special attention to gender issues", then sure. But if you define "sexist" as "unfairly promoting (or setting in place structures that advantage) one gender over another", then pretty much the whole tech industry is sexist in the OTHER direction and events like this are but a few small ways of rectifying that imbalance.

  3. Thank you for approving the comment and for your response. I meant the latter, and I (with very deep respect) think you're mistaken in identifying "few women want to go into theory" with "theory is biased against women". See, for example, the NYT article on the lack of women editing Wikipedia. One would be very hard-pressed to prove that Wikipedia does anything sinister to prevent women from editing it, and yet they do not edit it. As a young man, I feel my own career is compromised because I am unwelcome at certain conferences purely due to my gender. I am unaware of any conferences where women are specifically unwelcome (in the present day, I mean).

  4. I didn't imply that the theory community is biased against women. More precisely, I am not competent to make assertions about bias based on personal experiences. But there are many bloggers who talk about general bias in academia against women, and there are legions of examples of latent bias and plain insensitivity towards women in the industrial CS world (even today).

    I'm sorry you feel threatened or unwelcome in conferences because you're male. it might help to imagine what it must be like (and what it must have been like for so long) to be female in a male-dominated workforce. This is not to say that it's time for payback - rather, any attempt to change the historic imbalance might SEEM like unfriendliness towards men, but it really isn't.

    In regards to equating numerical imbalance with systematic bias, again theres little I can say that hasn't been said over and over again about the institutionalized and unconscious ways in which bias can creep in without explicit sexist behavior, and how that can affect relative proportions of males and females in the higher reaches of a discipline.

  5. As a woman and scientist, I'd like to say to "Anonymous" that I'm sure your presence at a Women in Theory workshop would have been *especially* welcome. If you feel strongly about this issue, perhaps you should make a special effort to join in! The male voice is especially appreciated at such gatherings, as I feel it is due to the united efforts of both men and women that iniquities in career opportunities, salaries, benefits, etc will eventually be understood and rectified.

  6. Thank you for the nice post. I understand the feelings of the other anonymous commenter who probably means “discriminates based upon sex of attendee” when he says WIT is sexist. And this is true. Males are not invited to attend. I heard rumor that a male did attend a previous WIT workshop and was asked to leave by one of the more senior women at the workshop. As a male, I would like to promote issues of work/life balance (and learn more about them), but I certainly do not feel welcome to attend WIT. I applaud Karen’s assurance and welcome, but I will not be taking her up on this opportunity due to fear.

    That said, I don’t think labeling the workshop as “sexist” is particularly helpful. Instead of “is it sexist?”, another question to ask is whether the current exclusionary format “is the most helpful format for the attendees and beneficial to promoting theoretical computer science research”. There are definitely benefits of the current format that you will hear from any of the attendees. There are also drawbacks. One drawback, as Karen pointed out, is that it, in part, excludes men from this part of the conversation of work/life balance and the quest for diversity. It also excludes men (especially young ones that do not have their own networks) from helpful information about self-promotion, networking, and the larger discussion of how to be a good and productive researcher. I know young male researchers who would be interested in these topics and yet do not have access to another venue is good as WIT for learning about these topics. Another drawback of this format is that it can create resentment. The other anonymous commenter is surely not the only male who feels resentment at being excluded because he is male. The resentment that WIT fosters may undermine the very goal that WIT was established to promote.

    In the end, I fear that the negatives of being exclusionary may outweigh the positives. Such a conference might have a more beneficial impact if it were more welcoming to the male researchers. I understand that this was not the case 20 years ago, but it may be today. I would encourage the organizers to give this a try at some future WIT conference to see how it works. A conference addressed primary to women’s needs but where sympathetic men were explicitly welcome.


Disqus for The Geomblog