Algorithms and Theory at Khoury College of Computer Sciences
Advancing knowledge about the foundations of computing
The Algorithms and Theory research area at Khoury College focuses on fundamental questions in computer science, developing knowledge that supports progress in any specialty: for instance, determining what it means for something to be computable, what kind of computations can be made, investigating whether in principle sets of procedures — algorithms — can be created for a type of problem, and analyzing those algorithms’ characteristics.
In this way, algorithms and theory research supports computer science across a range of other areas such as fueling cryptography, AI, and data science, areas where practitioners building tools need to know that the foundational theory their work depends on is sound, what the limits are, and what’s feasible.
Pushing the boundaries of what’s possible
Insights from Khoury College algorithms and theory research have an impact on many aspects of computing. In particular, theory research has helped discover how cryptography can help keep information you look up from a resource private, with the potential that someday you could use a search engine but it wouldn’t see what you’re doing — a potential revolution in privacy.
Study of algorithms can help ground core work in software development. By looking at the general and abstract characteristics of a computational problem, you can assess its complexity and what the limits may be to creating algorithms to tackle it. In this way, Khoury College is helping build the foundation for better approaches to building programs and tools, pushing the boundaries of what is feasible technically through better understanding of theoretical limits.
Sample research areas
- Approximation algorithms
- Computational complexity
- Cryptography
- Distributed computing
- Cybersecurity and privacy
- Learning theory
- Network algorithms
Khoury researchers: At the forefront
Current project highlights
Understanding how complexity in computation plays more generally
Complexity in computation is everywhere, but theory research is required to understand how complexity plays more generally. Khoury College faculty are looking at these questions.
Encrypting data and still working within it
How could we do a search without the site knowing what we’re searching for? Khoury faculty are researching how to encrypt data and still work within it, while not providing information to third parties. This has the potential to provide secure search and other computing functions – vastly increasing privacy protections on the Internet.
Current research publications
Laconic function evaluation, functional encryption and obfuscation for rams with sublinear computation
Authors: Fangqi Dong, Zihan Hao, Ethan Mook, Daniel Wichs
This research works with cryptography and algorithmic approaches to theorize a new way to securely run computer programs on a server without revealing either the program itself or the data you give it. This has the potential to make systems that work with sensitive data, such as health records, far more secure.
From Robustness to Privacy and Back
Authors: Hilal Asi, Jonathan Ullman, Lydia Zakynthinou
Machine learning depends on vast data sets that are used to train programs. But those sets include private data and are also vulnerable to tampering. This research offers a new approach that makes algorithms private without compromising accuracy, allowing them to be more secure and accurate at the same time.
Related labs and groups
Faculty members
-
-
-
Wolfgang Gatterbauer
Wolfgang Gatterbauer is an associate professor at Khoury College. He works on the theory of scalable data management, with the goal of expanding data management systems and enabling them to support novel functionalities.
-
Paul Hand
Paul Hand is an assistant professor at Khoury College, jointly appointed with the College of Science. He researches theory and algorithms for AI and machine learning in the context of vision and imaging.
-
Zhengzhong Jin
Zhengzhong Jin is an assistant professor at Khoury College. He is interested in cryptography, teaching courses on the subject, and researching a proof system to delegate heavy computation to an untrusted server while ensuring the computation is correct.
-
Huy Lê Nguyen
Huy Lê Nguyen is an associate professor at Khoury College. He researches the design and analysis of algorithms, with an emphasis on algorithmic techniques for machine learning and massive data sets.
-
Rajmohan Rajaraman
Rajmohan Rajamaran is a professor and the associate dean of faculty affairs at Khoury College. He has made important contributions in the areas of distributed hash tables and fundamental combinatorial optimization problems, with the former being incorporated in peer-to-peer systems.
-
Abhi Shelat
Abhi Shelat is a professor at Khoury College specializing in cryptography and applied security. A recipient of awards from the NSF, Microsoft, Amazon, Google, and the ACM, he uses secure computation protocols to enable mutually distrusting parties, each with private inputs, to jointly compute functions while ensuring maximal privacy and correctness.
-
Jonathan Ullman
Jonathan Ullman is an associate professor at Khoury College whose research centers on the foundations of privacy for machine learning and statistics. Ullman has been recognized with an NSF CAREER award and the Ruth and Joel Spira Outstanding Teacher Award.
-
Emanuele Viola
Emanuele “Manu” Viola is a professor at Khoury College. Viola’s theoretical computer science research has included a wide variety of areas, including pseudo-randomness, cryptography, data structures, communication complexity, and circuit lower bounds. He has made fundamental contributions to the field, including solving long-standing open problems.
-
Daniel Wichs
Daniel Wichs is a professor at Khoury College. An expert in modern cryptography, Wichs researches all aspects of the field, including its theoretical foundations and its applications to information security. Wichs’ work was recognized in 2018 with the prestigious Sloan Research Fellowship, which honors early-career scholars whose achievements mark them among the top scientific minds.
-
Hongyang Zhang
Hongyang Zhang is an assistant professor at Khoury College. He researches at the nexus of machine learning, algorithms, and statistics, and has helped to develop techniques for neural networks, data augmentation, and transfer learning.