The Women in Theory (WIT) Workshop is intended for graduate and undergraduate students in the area of theory of computer science. The workshop will feature technical talks and tutorials by senior and junior women in the field, as well as social events and activities. The motivation for the workshop is twofold. The first goal is to deliver an invigorating educational program; the second is to bring together theory women students from different departments and foster a sense of kinship and camaraderie.

**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).

**Organizers**: Tal Rabin, Shubhangi Saraf and Lisa Zhang.

**Local chair**: Moses Charikar.

**Homepages of previous** **workshops**: WIT 2008, video from 2008, WIT 2010, lecture notes from 2010.

**Important dates:**

**Application deadline:** ~~February 29, 2012~~ **Deadline extended to March 9, 2012**

**Notification of acceptance:** March 31, 2012.

**Workshop: **June 23-27, 2012.

**To apply to the workshop.** ~~Please fill out this form no later than ~~ Application deadline passed. We no longer take any registrations.**March 9, 2012.** You also need to email your **CV** and have one **reference letter** sent to womenintheory2012@gmail.com no later than **March 9, 2012** with a subject line of “CV for {your name}” or “Reference letter for {your name}”. We especially encourage students of underrepresented minority groups to apply.

Regrettably, because of space limitations we may not be able to accommodate everyone that applies to the workshop. In addition, due to funding limitation, we strongly encourage you to ask for support from your advisor and institution. We will notify you of acceptance decisions by **March 31, 2012**. (If you need an earlier notification to allow time to get a U.S. visa, please let us know by email.)

**Local Information**. The workshop will take place at the Friend center, next to the Computer Science department at Princeton University. Click here for travel instructions to Princeton. Click here for a campus map with marked workshop locations.

**FAQs for Student Participants.**

*Where do I park? * If you drive, please park at the visitor section towards the rear of Lot 21. Otherwise, you will risk being ticketed.

*Where do I stay?* Housing is set up at the Scully dorm. All rooms are single. We do not allow guests. Each participant will get a packet with two sheets, two towels, a pillow, blanket and pillow case. Laundry rooms are available and use of the machines is free. You are responsible for their own detergent.

*How do I pick up and drop off the dorm key?* (UPDATED) We will have staff at Scully for check in 3-6pm on Saturday, June 23rd. Public Safety at 200 Elm Drive, marked on the map, will have all keys from 6pm Friday, June 22nd until 3pm Saturday, and 6pm Saturday until 8am Monday, June 25th.

Please return your dorm key to Mitra Kelly during the workshop. Late key drop off will be at 71 University Place, also marked on the map. Please do not leave the keys unattended.

*What if I stay additional nights?* If you plan to stay additional nights please inform us by Monday June 17th, and please pay for these additional nights at check in. The room rate is $51.50 per night. We accept checks and credit cards (Visa or Master).

*How do I access the Internet in the dorm room?* You will have wireless Internet access. Your computer should automatically connect to PUVisitor. No password is needed.

*Is there a campus shuttle between Scully and the Friend center (where the wrokshop is)?* Shuttle is not running on weekends during the summer, and so you will have to walk on Saturday and Sunday. However, the Friend center is not too far a walk from Scully. Please consult the campus map.

*How do I reimburse travel expenses?* If your travel is covered, or partially covered, by WIT, please see Mitra Kelly during the workshop for reimbursement instructions. Please save your boarding passes and all receipts.

**Local Events of Interest. **Exhibit on history of women at Princeton at the Mudd Manuscript Library.

**Program. **The workshop will take place in Friend Center, next to the CS Department. All talks will be in room 006.

### Saturday, June 23

5:30pm — Reception — Friend Convocation Room (113)

### Sunday, June 24

8:30-9:00 — Breakfast

9:00-9:15 — Opening remarks (talks will take place in Friend 006)

9:15-10:15 — Joan Girgus (Princeton)

*Fifty Years Later: Lessons Learned*

10:15-10:45 — Coffee break

10:45-12:15 — Gagan Aggarwal (Google)

*Mechanism Design for Online Advertising*

12:15-2:15 — Lunch – Friend convocation room (113)

2:15-3:45 — Nicole Immorlica (Northwestern University)

*Cooperation in Social Networks*

3:45-4:15 — Break

4:15 – 5:45 — Maria Klawe (Harvey Mudd)

*Best Time Ever to be a Woman in Theory*

### Monday, June 25

8:30-9:00 — Breakfast

9:00-10:30 — Jennifer Rexford (Princeton)

*Enabling Innovation inside the Network*

10:30-10:45 — Coffee break

10:45-12:45 — Panel, work life balance

12:45-2:15 — Lunch – Friend convocation room (113)

2:15-3:45 — Glencora Borradaile (Oregon State)

*Designing algorithms for planar graphs*

3:45-4:15 — Coffee break

4:15-5:45 — Ronitt Rubinfeld (MIT and Tel-Aviv University)

*Estimating Properties of Distributions*

6:15pm — Banquet – Palmer House – corner of Nassau St. and Bayard Lane.

### Tuesday, June 26

8:30-9:00 — Breakfast

9:00-10:30 — Rebecca Wright (Rutgers and DIMACS)

*Privacy and Accountability in the Information Society*

10:30-11:00 — Coffee break

11:00-12:30 — Vijaya Ramachandran (U of Texas, Austin)

*Parallel and Multicore Computing Theory*

12:30-2:00 — Lunch – Friend convocation room (113)

2:00-5:00 — Student rump session

### Wednesday, June 27

8:30-9:00 — Breakfast

9:00-10:30 — Valerie King

*Dynamic Graph Algorithms for Maintaining Connectivity*

10:30-11:00 — Coffee break

11:00-12:00 — Dana Ron (Tel-Aviv University and Columbia University)

*A Short Introduction to Sublinear-Time Algorithms*

12:00-1:30 — Lunch – Friend convocation room (113)

1:30-3:00 — Shubhangi Saraf (IAS)

*Error correcting codes and applications to theoretical computer science*

### ABSTRACTS

**Joan Girgus** (Princeton)

*Fifty Years Later: Lessons Learned*

When I graduated from college nearly 50 years ago, young women in theUnited Stateswere by and large expected to get married sooner rather than later, and to make raising a family their career. Those who wanted to combine a career with raising a family were seen as anomalies, and this choice was seen as one that necessarily gave short shrift to the family life that should come first. Today, combining family and career is the norm, which sounds like the resolution of a conflict between work and family life, but which turns out to have its own complexities and difficulties. Women continue to be seriously underrepresented in science and engineering beginning as undergraduates and continuing through to their presence on the faculties of research universities. I will talk about some of the possible reasons for this underrepresentation and about some of the approaches that universities can take to mitigate those reasons.

**Gagan Aggarwal** (Google)

*Mechanism Design for Online Advertising*

We will start with the basics of auction design in the context of online advertising. Then we will discuss a variety of goals and constraints an auction designer might be faced with, and describe some of the work that attempts to meet these goals and the trade-offs faced thereof. On the way, we will talk about some related work on online matching and stable matching.

**Nicole Immorlica** (Northwestern University)

*Cooperation in Social Networks*

Social networks form the basic medium of social interaction. The structure of these networks significantly impacts and co-evolves with the behavioral patterns of society. Important societal outcomes — the global reach of an epidemic, the degree of segregation in a city, the adoption of new technologies — are dictated by social networks.

In this talk, we explore 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 (e.g., in a business deal) results in mutual benefits, whereas cheating results in a high short-term gain. As agents are anonymous, reputation concerns do not deter cheaters. We find that, despite the lack of verifiable reputation, cooperation is sustainable at equilibrium in our model. Indeed, cooperation allows an individual to interact with an increasing number of other cooperators, resulting in the formation of a type of social capital. Additionally, for a rich class of parameter settings, our model predicts a stable coexistence of cooperating and defecting agents at equilibrium.

Joint work with Brendan Lucier and Brian Rogers.

**Maria Klawe** (Harvey Mudd)

*Best Time Ever to be a Woman in Theory*

How things have changed over the last thirty years and the opportunities for the future.

**Jennifer Rexford** (PrincetonUniversity)

*Enabling Innovation inside the Network*

Today’s computer networks perform a bewildering array of tasks, from routing and access control, to traffic monitoring and load balancing. Yet, network administrators must configure the network through closed and proprietary interfaces to heterogeneous devices, such as routers, switches, and firewalls. Not surprisingly, configuring these complex networks is expensive and error-prone, and innovation in network management proceeds at a snail’s pace. During the past several years, the networking industry and research community have pushed for greater openness in networking software, and a clearer separation between networking devices and the software that controls them. This broad trend is known as Software Defined Networking (SDN). A hallmark of SDN is having an open interface for controller software running on a commodity computer to install packet-processing rules in the underlying switches. In particular, many commercial switches support the OpenFlow protocol, and a number of campus, data-center, and backbone networks have deployed the new technology. In this talk, we give an overview of SDN and OpenFlow, and discuss how pairing a slow, flexible controller with with fast, simple switches introduces a wealth of new research challenges in algorithms and data structures.

**Glencora Borradaile **(Oregon State)

*Designing algorithms for planar graphs*

We survey different techniques for designing algorithms for planar graphs and the properties that they rely on, such as: divide and conquer using small, balanced separators; iterative methods based on minor exclusions; layering and sweep methods based on combinatorial embeddings.

**Ronitt Rubinfeld** (Te lAvi vUniversity and MIT)

*Estimating Properties of Distributions*

Suppose you are studying the occurrence of a disease and need to uncover any salient statistical properties that might hold. For example, it would be important to know if the probability of contracting the disease decreases with distance of your house from a nearby nuclear plant, whether the distribution on zipcodes of patients is close to the distribution for another disease, or whether a person’s likelihood of contracting it is correlated with their profession. Of course, you wish to notice such trends given as few samples as possible. This is only one of many examples of settings in which one must estimate parameters and test properties of data that is most naturally thought of as samples of an underlying distribution over a very large domain.

We survey 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. Classical techniques, such as the Chi-squared test or the straightforward 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.

**Rebecca Wright** (Rutgers and DIMACS)

*Privacy and Accountability in the Information Society*

In this talk, we will discuss privacy and accountability. On the one hand, we will overview differential privacy and pan-privacy and some recent results in the area. On the other hand, we will introduce the paradigm of accountability as an alternative to prevention-based mechanisms and discuss whether accountability and anonymity can coexist.

**Vijaya Ramachandran** (University of Texas at Austin)

*Parallel and Multicore Computing Theory*

In this talk will discuss topics in the design and analysis of efficient parallel algorithms. This includes both the modeling of parallel machines, and the design of provably efficient algorithms on the parallel model. Multicore parallel machines are increasing becoming the default computing environment, and this talk will discuss some recent theoretical results on modeling and developing provably efficient algorithms for multicore parallel machines.

**Valerie King** (University of Victoria)

*Dynamic Graph Algorithms for Maintaining Connectivity*

A dynamic graph algorithm for maintaining connectivity is a data structure for a graph on a fixed set of *n* nodes which can process updates in the form of edge insertions and deletions, and answer queries of the form “Are nodes *x* and *y* connected?” This problem has been studied for over 30 years.

In 1983 Fredrickson developed an O(m1/2} worst case time algorithm for this problem. Modified by Eppstein to O(n1/2} in 1993, this data structure remains the only method for the good worst case performance.

In mid 1990’s Henzinger and King developed the first data structure with polylogarithmic *amortized* expected running time, which was improved and made deterministic a few years later by Holm, de Lichtenberg and Thorup. However these data structures can incur a cost of *n* for a single update.

One of the most fundamental open questions in dynamic graph algorithms is to find a data structure which permits fast connectivity queries and updates in *worst case* o(n1/2) time. In this talk, I’ll review the area and describe a new direction for achieving polylogarithmic worst case performance.

Joint work with Bruce Kapron and Ben Mountjoy.

**Dana Ron** (Tel-Aviv University and Columbia University)

*A Short Introduction to Sublinear-Time Algorithms*

When we refer to “efficient algorithms”, we usually mean “polynomial-time algorithms”, where we strive to obtain a polynomial of as small a degree as possible, and at best, linear-time algorithms. However, when we deal with very large inputs, in the form of massive data sets, even linear time might be prohibitive. In such cases we seek even more efficient algorithms, namely, sublinear-time algorithms. Such algorithms do not even read the whole input, and as such, are only expected to output approximately-good, rather than perfect outputs. Furthermore, they are probabilistic, and are allowed a failure probability.

One type of such algorithms are property-testing algorithms, which perform a certain type of relaxed/approximate decision. Such algorithms are required to decide, with high success probability, whether an input (e.g., a graph), has a certain property (e.g., is bipartite), or is relatively far from having the property (e.g., a relatively large fraction of its edges should be removed so that the graph become bipartite). By allowing this relaxation we can obtain, for many properties, algorithms that are much more efficient than the corresponding decision algorithms. I will give examples of several such properties and algorithms, and will try to give a flavor of some analysis techniques.

Another type of sublinear-time algorithms that I’ll discuss are algorithms for estimating various graph parameters (e.g., the number of connected components or the size of a minimum vertex cover) much more efficiently than algorithms that compute these parameters exactly. I will describe several such algorithms as well.

**Shubhangi Saraf **(IAS)

*Error correcting codes and applications to theoretical computer science*

In today’s world there are huge amounts of data that need to get reliably stored or transmitted. However as hard as we try, some amount of noise or corruption is inevitable. Bits do get flipped and the data gets corrupted. However, we would still like to recover the original uncorrupted data. Is this even possible? This is precisely the task that error correcting codes accomplish. Error correcting codes have also found a host of striking applications in complexity theory and cryptography. In this talk I will discuss several examples of error correcting codes and we will see some of the applications to theoretical computer science.