Papers are listed on my home page: https://www.falsifian.org/.
Parking difficulty (launched in Google Maps). A significant amount of driving time is spent looking for parking. To help users plan ahead, we augmented driving directions by predicting the difficulty of parking at the destination. Predictions are based on a novel analysis of aggregate anonymous location data. As a result, we observed an increase in clicks on the transit travel mode button, suggesting this feature helped users decide whether to drive. Launched in Google Maps. Presented at KDD 2019.
A space-efficient algorithm for the Tree Evaluation Problem (complexity theory). The Tree Evaluation Problem (TEP) was introduced in the hope of separating the complexity classes L and P. For several years, no TEP algorithm was known that used less space than the original "pebbling" algorithm, leading to the conjecture that pebbling is optimal, which would imply the significant result that L≠P. We refuted this conjecture by providing the first TEP algorithm that uses less space. Our algorithm represents a barrier to this approach for separating L from P, and also serves as an example application of algorithmic techniques borrowed from the realm of catalytic space. Presented at STOC 2020.
Predicting bus delays from car traffic (launched in Google Maps). Google Maps shows real-time transit updates when possible, but many transit agencies don't provide them. To help bus riders when no real-time data is available, we built a model that predicts bus travel times using Google's existing measurements of car traffic. Our model was able to compensate for differences between car and bus speeds that varied by region, such as bus-only lanes. Launched in Google Maps. Work presented at ITSC 2019 and KDD 2020.
Finding online communities (prototype). Our goal was to connect people to communities they could benefit from. We discovered that many communities use Twitter for regularly scheduled real-time discussions called group chats, which range from health-related support groups (e.g. Alzheimer's, diabetes) to fans of TV shows. We designed algorithms to find these groups (WWW 2013) and for searching for relevant groups (COSN 2014).
Analyzing Goldreich's one-way function candidate (complexity theory). One-way functions are an important primitive in cryptography, but it remains unknown whether any exist. We found evidence that a candidate proposed by Goldreich in 2000 is indeed a one-way function, by showing that it is resistant to attacks from two kinds of backtracking algorithm. Presented at TCC 2009.
2014: PhD, UC Berkeley computer science. Advisor: Satish Rao.
2007: HBSc, University of Toronto, Computer Science and Math.
May 2017-October 2019: Senior Software Engineer at Google.
October 2014-May 2017: Software Engineer at Google.
Internships at Google (2007, 2011, 2012), Microsoft Research (2012) and Facebook (2013).
Spring 2020, University of Toronto. Taught CSC240: Enriched Introduction to the Theory of Computation (enriched version of a required computer science course).
Summer 2014, UC Berkeley. Taught CS70: Discrete Mathematics and Probability Theory (a required computer science course).
CIKM 2015; ASONAM 2016; KDD 2017, 2018, 2019
My website lists some blog posts and programming projects.
I like playing with BSD and Linux, and programming languages like Idris.
References available upon request.
I am a dual citizen of Canada and the United states.