WIT 2014

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.

The 4th WIT workshop will take place at New York Universityhttp://cims.nyu.edu/direct.html, May 28 – 30, 2014, in coordination with Princeton University, right before ACM STOC 2014.

Confirmed Speakers: Lenore Blum (CMU), Julia Chuzhoy (TTI), Shafi Goldwasser (MIT),Orna Kupferman (Hebrew U.), Katrina Ligett (Caltech), Rotem Oshman (U. Toronto), Vera Sos (Alfréd Rényi Institute of Mathematics).

We also have presentations from Google speakers: Alice Bonhomme-Biais, Joelle Skaf,  Lisa Trongprakob and Farzaneh Sarafraz.

Special Guests: Omer Reingold (Microsoft Research) and Nir Shavit (MIT).

OrganizersTal Rabin (IBM), Shubhangi Saraf (Rutgers) and Lisa Zhang (Bell Labs).
Local Host Institution:  New York University.
Local ArrangementVictor Shoup (NYU).
Contact us: womenintheory2014@gmail.com.

Important dates:
Application deadline:  January 20,  2014.  Passed
Notification of acceptance: February 10,  2014.  Passed
Student rump session title/pdf slides due: May 18, 2014.
Workshop: May 28-30, 2014.

FAQs for Student Participants.  

Is there a forum for me to present my work during the workshop?  On Thursday night, there will be a student rump session. Each speaker at the rump session will get at most 4 minutes, and this time limit will be strictly enforced! You could choose to do a blackboard talk or use powerpoint slides. If you decide to use powerpoint slides, you should make sure to convert your slides to pdf format and email it to womenintheory2014@gmail.com by May 18 at the very latest. All the talks need to be on one computer since there will be almost no time in between talks.

How do I get to New York University? The workshop will be held on the 13th floor of the Courant Institute at NYU.  Please click this link for directions and local information. 

Where do I stay?  We are offering shared occupancy bedroom and multi-bedroom air-conditioned suites at NYU for the nights of Wednesday, May 28 to Friday, May 30.  The dorm, Founders Hall, is located at 120 East 12th Street, New York, NY 10003.  For contact, hours and nearby subway stops, please consult this webpage. Note that during summer, not all services listed on the webpage will be offered.

newHow do I check in and out of the dorm?   The earliest check in time is 9am and please bring a picture ID.  Please refer to the 2014 Founders FAQ for check in and check out information.

How do I walk from the dorm to the talk location? Please click this link for direction. 

What if I stay additional nights?  We are looking into the possibility of having the NYU dorm available for the duration of STOC. This will be at your own expense, $55 a night for shared occupancy.  If you are interested in this option, please indicate it in your registration form. If you have a US bank account, you may pay with a check payable to The Trustees of Princeton University. Otherwise, please pay by cash in US dollars.

If I’m driving, where do I park?  Parking in New York City can be expensive and hard to find. If you plan to drive, please email us.

How do I reimburse travel expenses?  If you are flying please book your flights with US carriers. Please save your receipts and boarding passes for reimbursement. If you take buses or trains, please also save your receipts. Click to download instructions for Student Reimbursement and Speaker Reimbursement. Please submit all reimbursement documents by Friday, June 13, 2014.   


IBM_Researchsigact logonsfNYU Logoprinceton logogooglelogo



Wednesday, May 28

5:00pm          Registration + Reception dinner
6:00-9:00pm   Introduction and Playback with Prof. Nir Shavit and Prof. Omer Reingold

Thursday, May 29

7:30-8:30am          Breakfast

8:30 – 9:45am        Prof. Orna Kupferman (Hebrew U.)
Formal Verification ‐ Deciding the Undecidable (formal_verification.ppt)

10:00 –11:15am      Prof. Julia Chuzhoy (TTI)
Polynomial Bounds for Grid-Minor Theorem (grid_minor)

11:30 –12:45pm      Prof. Lenore Blum (CMU)
Alan Turing and the Other Theory of Computation

12:45 –1:45pm        Lunch

1:45 – 3:00pm        Prof. Vera Sos (Alfréd Rényi Institute of Mathematics)
From Diophantine Approximation to Limits of Graphs (DiophantineApprox_GraphLimits.pdf)

3:15 – 3:35pm        Alice Bonhomme-Biais (Google)
Google Crisis Response

3:35 – 3:55pm        Joëlle Skaf (Google)
How Algorithms and People Come Together at Google to Fight Business Listing Spam

4:00 – 4:20pm        Lisa Trongprakob (Google)
Ads Ecosystem & Internet 

4:20 – 4:40pm        Farzaneh Sarafraz (Google)
Structured Knowledge and Search at Google NYC

4:40 – 5:00pm        Q&A with Googlers

6:00 – 9:30pm        Work dinner + Student rump sessions, 4 min per presentation
6:20 – 7:00pm                    Student rump session 1
7:00 – 7:30pm                    Break
7:30 – 8:10pm                    Student rump session 2
8:10 – 8:40pm                    Dessert break
8:40 – 9:20pm                    Student rump session 3

Friday, May 30

8:00 – 9:00am       Breakfast

9:00 – 10:15am      Prof. Katrina Ligett (Cal Tech)
Data Privacy: Tensions and Opportunities (privacy.pdf)

10:30 – 12:30pm    Panel (witgender.ppt)

12:30 – 2:00pm      Lunch

2:00 – 3:15pm        Prof. Rotem Oshman (U. Toronto)
Information Complexity Lower Bounds (info_complexity)

3:45 – 5:00pm        Prof. Shafi Goldwasser (MIT)
Privacy and Big Data: Using the Crypto Tool Box

5:00pm                 Drink and dessert party



Prof. Orna Kupferman (Hebrew U.)
Formal Verification ‐ Deciding the Undecidable

The undecidabilty of the halting problem implies that formal reasoning about computerized systems is not a feasible task. Still, formal‐verification algorithms and tools are successfully used in design and development of systems. The talk surveys the main ideas behind formal verification and in particular how it copes with huge, often infinite, state spaces.

Prof. Katrina Ligett (Cal Tech)
Data Privacy: Tensions and Opportunities
Large databases of sensitive personal information are ubiquitous, hold great potential, and are rife with risks. How can we understand the fundamental tradeoffs between making use of such data and respecting individual privacy? Are both goals simultaneously achievable in realistic settings? What could change once we model the fact that privacy considerations might play a role in individuals’ decisions to provide their data in the first place? In this talk, we will discuss recent theoretical work addressing these questions, in the formal framework of differential privacy.

Bio: Katrina Ligett is an Assistant Professor of Computer Science and Economics at Caltech. Prior to joining Caltech, she was a postdoctoral scholar in Computer Science at Cornell (during which she was also a visitor to the Research Group on Algorithmic Game Theory at the Hebrew University’s Institute for Advanced Studies). She received her PhD in Computer Science from Carnegie Mellon in 2009. She is a recent recipient of the Microsoft Research Faculty Fellowship and an NSF CAREER award.

Prof. Julia Chuzhoy (TTI)
Polynomial Bounds for Grid-Minor Theorem
One of the key results in Robertson and Seymour’s seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms.

Let f(k) denote the largest value, such that every graph of treewidth k contains a grid minor of size f(k). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that: f(k)=Omega( sqrt { log k/log log k } ). In contrast, the best known upper bound implies that: f(k) =O( sqrt { k/log k } ).

In this talk we present the first polynomial relationship between treewidth and grid-minor size, by showing that: f(k)=Omega(k^d) for some fixed constant d > 0. We will also survey some connections between the Grid-Minor Theorem and graph routing problems, and discuss the major open problems in the area of graph routing.

This is joint work with Chandra Chekuri.

Prof. Lenore Blum (CMU)
Alan Turing and the Other Theory of Computation
We recognize Alan Turing’s work on the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), its influence in modern complexity theory, and how it helps provide a unifying concept for the two major traditions of the theory of computation.

Alice Bonhomme-Biais (Google)
Google Crisis Response
After a natural disaster, it is vital that affected people and first-responders have access to accurate information. Technology can vastly improve how information is collected, filtered, and disseminated, but requires thoughtful engineering design principles that take into account the pressing needs of crisis situations. This talk will present examples of tools developed by Google Crisis Response that satisfy several essential engineering requirements: 1) Simple, 2) Open, and 3) Standard.

Joëlle Skaf (Google)
How Algorithms and People Come Together at Google to Fight Business Listing Spam
This talk will introduce the problem of business listing spam on Google Maps, and we do to fight it. While Maps spam constitutes a very minor fraction of listings, it can cause severe problems for Google and its users when found. We will describe the methodology we follow to detect spammers and the tools we use to take them down.

Lisa Trongprakob (Google)
Ads Ecosystem & Internet
What keep the internet free? Ads! How does the ads ecosystem work? We have publishers, advertisers, agencies, artists who make ads, etc. We have users who browse websites and might be interested in the ads. What are the challenging problems in the ads space? What are the technologies we use to facilitate the problems?

Rotem Oshman (U. Toronto)
Information Complexity Lower Bounds
Communication complexity, introduced by Yao in ’79, studies the following problem: two players, Alice and Bob, receive private inputs X,Y (respectively), and want to compute a joint function f(X,Y) of their inputs. To do this, the players communicate with each other, and we are interested in how many bits they need to exchange. Communication complexity lower bounds are incredibly versatile, with applications in circuit lower bounds, data structures, streaming algorithms and other domains.

One way to prove lower bounds on communication complexity is through information complexity: how many bits of *information* do the players need to learn about each others’ inputs in order to compute f(X,Y)? This approach, developed over the past decade or so, can greatly simplify lower bounds. In this talk we will cover the basics of information complexity and use them to prove a tight lower bound on the communication complexity of the set disjointness problem, where the players receive two sets and need to determine if the sets are disjoint or not.

Prof. Shafi Goldwasser (MIT)
Privacy and Big Data: Using the Crypto Tool Box
The prospects of data sharing around the globe holds great promise for health, research collaborations, traffic reduction, energy savings, risk prediction, and clever consumer targeting. At the same time it posses great threats for anonymity, profiling, taking away competitive the edge and basic control over your data. Can we reconcile these benefits and risks? Cryptographic research for the last 30 years has developed many tools which essentially imply that knowledge can  be extract from data without viewing the data. We will discuss how to apply this tool box to the privacy quesions of the day.