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.
