Professor Receives NSF CAREER Award to Improve Online Resource Allocation

School of Computer Science Assistant Professor Sahil Singla was awarded an NSF CAREER Award to create new, more efficient algorithms for online resource allocation. 

Singla researches algorithms, with a particular focus on online resource allocation and algorithms with uncertain inputs. Online resource allocation is the process of distributing resources in real time, as demands come in. 

“The general problem appears in many diverse forms in all fields. The question at the heart is how to design good algorithms that maximize efficiency,” Singla said. 

This problem becomes more complicated in high-dimensional settings, when there are large amounts of resources and an unknown number of requests. This is the case when selling online advertisements or concert tickets

Image

“When you search for something, Google has to decide what ad to show you. There are many thousands of advertisements they can choose from, but it’s also a limited resource since they don’t want to show the same ad again and again,” Singla said. 

Another aspect of Singla’s proposal is increasing the robustness of these algorithms. Doing so protects against factors that can’t be predicted, such as outliers or malicious actors trying to break the system. 

Singla said he enjoys working on these problems from both a theoretical and practical perspective. 

“What I find exciting is that a lot of the time, I’m finding out what is the least amount of information we need to know to design a good algorithm. I find these questions very intellectually interesting. The problems are also very useful in practice,” he said. 

Singla’s award proposal also outlines a plan to organize a summer school for graduate students interested in learning about algorithm design for uncertain inputs. He would also like to host a research workshop related to the findings of this proposal and other new research in the area.