Here you can find selections of my research and independent teaching curriculum, with links soon to come once my work is published.
Research:
Abstraction Development for the 0/1 Knapsack Problem (2014):
Under my mentor Peter Schwartz, a mathematician for ORSA Corporation, I studied abstraction methods for combinatorial optimization problems. Specifically, I developed two models for abstracting the 0/1 Knapsack Problem in order to obtain helpful approximate solutions to large problem instances. I also identified a correlation in their performance based on an extrinsic property of the problem instance: the ratio of overall item weight to the capacity of the knapsack. Essentially, in problems with many heavy items and not much space to store them, the greedy approximation function doesn’t properly chop enough branches in the branch and bound algorithm to solve in a reasonable amount of time. For these instances, I abstract the problem by cutting items from the list based on low individual value/weight ratios. Inspection and experimentation revealed these items rarely appear in optimal solutions and when they do, their omission minimally decreases the optimality of the solution. For problems where there are relatively few items compared to the knapsack size, this abstraction is less useful. In this case, I took inspiration from the classic merge-sort algorithm. I abstract the problem by grouping items into pairs based on a similarity function (value to weight ratio and total weight). Then, I use one of the two similar sets and try to fill a knapsack of half the original capacity. Then, this solution is simply extended to the full knapsack by including the partner of each item included in the half-solution. In problems where relatively few items are excluded from the optimal solution, this abstraction increases efficiency more than the former. I named these abstractions ValDens and SymKnap, respectively. My final poster with a summary of my results can be found here.
If I were to revisit this project, I would want to perform tighter run-time analysis on each of my abstractions to compare to the original branch and bound algorithm. While basic increases in efficiency are great, I’m interested in the extent to which these abstractions change the hardness of the problem in a theoretical sense, rather than an experimental one.
Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares:
Recent advances in MPC have allowed for systems which privately compute aggregate statistics on inputs from many players. We have noticed, however, that such systems place an unnecessarily large computational burden on the client. Prio+ uses share-conversion technology to securely compute the same aggregate statistics as the current state-of-the-art at a lower cost to both clients and servers by leveraging the beneficial properties of various secret-sharing schemes. In some cases, Prio+ clients compute 750x less than in the previous state-of-the-art. Our full paper can be found here.
We are currently working to generalize the definition of a ‘private streaming algorithm’ and implement more useful statistics within this model, particularly the ‘Heavy Hitters’ statistic which returns the top $n$ most popular items over a set of user data.
Inventory Auctions via Function Secret Sharing (Ongoing):
An inventory auction is a game in which each player wishes to either buy or sell some amount of a fixed asset. Financial institutions often serve as middle men to match buyers with sellers in this game, and once players are matched, the institution executes the trades. For some players, however, revealing their order in its entirety to the financial institution is not possible. For example, an automotive company submitting a multi-million-dollar bid for parts may not wish to reveal the exact number of parts they are purchasing, as this information can be used by their competitors. This project uses Function Secret Sharing (FSS) as one tool within a simple MPC to construct a highly efficient protocol for executing inventory auctions with the guarantee that no player will have any part of their order revealed beyond what is necessary to execute the trades.
Teaching Curriculum:
Induction Puzzles (Link): (Los Angeles Math Circle, July 30, 2017)
Egyptian Fractions I (Link): (Los Angeles Math Circle, October 8, 2017)
Egyptian Fractions II (Link): (Los Angeles Math Circle, October 15, 2017)