Papers are listed on my home page: https://www.falsifian.org/.
Tree Evaluation in nearly log space (complexity theory). The Tree Evaluation Problem (TreeEval) was introduced in the hope of separating the complexity classes L and P. For several years, no TreeEval algorithm was known that used less than the O((log n)2) space used by the original "pebbling" algorithm. This led to the conjecture that pebbling is optimal, which would imply the significant result that L≠P. We refuted this conjecture through a series of results ending in an O(log n · log log n) space algorithm. Our algorithm casts doubt on 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 and STOC 2024.
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.
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.
January 2022-March 2023: Senior Applied Scientist at Amazon (AWS).
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
email:
falsifian@falsifian.org;
web:
https://www.falsifian.org/
I am a dual citizen of Canada and the United states.