Three computer science students have been honored with the prestigious 2025 CRA Outstanding Undergraduate Researcher Award by the Computing Research Association (CRA). This recognition celebrates Emre Adabag, Jiaqian Li, and Kechen Liu for their dedication to research and academic excellence. Their nominations, submitted by faculty members, highlight not only their academic achievements but also their impactful contributions beyond the classroom.
Emre Adabag – Finalist
Emre Adabag is a senior in SEAS and does research in Barnard College’s Accessible and Accelerated Robotics (A2R) Lab. He worked with Assistant Professor Brian Plancher to develop which uses the power of graphics processing units (GPUs) to accelerate robot motion planning and control. This computational breakthrough enables robots to move more agilely and dexterously. The research was published in the Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2024) and also won a Best Poster Award at the annual poster session of the IEEE RAS Technical Committee on Model-Based Optimization for Robotics. Furthermore, this work serves as the foundation for the A2R Lab’s new NSF CSSI grant, aimed at creating open-source, GPU-accelerated optimal control tools to benefit the broader robotics community.
Jiaqian Li – Honorable Mention
Jiaqian Li works in the Crypto Lab under the guidance of Professor Tal Malkin. He has been working on a cryptography research project that studies the relationship between oblivious black-box reductions and Total Function Nondeterministic Polynomial (TFNP) hardness. Total problems are ones that are guaranteed to have a solution, even if it may be hard to find. Examples include factoring or finding a Nash equilibrium. Li’s research explores the possibility of establishing hardness of total problems from a cryptographic tool called one-way functions (OWFs).
Li’s previous research on game theory was published at the AAAI Conference on Artificial Intelligence (AAAI 2024). He worked with Professor Minming Li of the City University of Hong Kong, and they explored how to fairly locate undesirable facilities, like waste treatment plants, among different groups of people, aiming to design systems that encourage honesty about location preferences and minimize the negative impact on all groups. The study proposed and analyzed several mechanisms, including both deterministic and randomized approaches, with the goal of finding locations that are as fair as possible and close to the ideal solution, while also establishing limitations on what is achievable.
Kechen Liu – Honorable Mention
Kechen Liu earned an honorable mention for her research in wireless power delivery systems for micro-robotic applications. Under the guidance of Associate Professor Xia Zhou at the MobileX lab, Liu contributed to the development of a laser-based power delivery system that enabled sustainable power for microrobots. She worked on designing and implementing an event camera-based tracking system that achieved millimeter-level tracking accuracy and continuous laser alignment with microrobots in motion. Aside from that, she contributed to multiple projects at the MobileX group including developing a palm-vein biometric authentication system. Liu is also interested in wireless sensing and communication systems, and she has worked with Professor Gil Zussman on a sub-Terahertz sensing project.
The recognition highlights the department’s dynamic research community, where students are empowered to innovate, explore, and excel in their respective fields. Professors often offer research opportunities for undergraduate students. Those interested should proactively reach out to faculty members to inquire about available positions.
Professor Tal Malkin typically has one or two undergraduate students who work on cryptography research. Students need to have mathematical maturity; ideally, they should have taken Malkin’s graduate-level Introduction to Cryptography class.
Associate Professor Xia Zhou mentors two to three undergraduate students per semester, guiding them through hands-on research in the lab. Students must be highly motivated and demonstrate strong analytical and system-building skills. Since many projects involve developing physical prototypes, proficiency with hardware is essential.
Assistant Professor Brian Plancher hosts a select group of undergraduate researchers each semester. While prior experience in robotics, parallel programming, or machine learning is not required, a strong foundation in computer science, electrical engineering, or mathematics is expected, as the research involves mathematical rigor and programming expertise.
Researchers from the department showcased their work at the 16th Innovations in Theoretical Computer Science (ITCS) conference, a premier forum for advancing the field through groundbreaking research, innovative methodologies, and interdisciplinary exploration that drives progress and inspires the theoretical computer science community.
Below are the abstracts of their accepted papers.
Data-Driven Solution Portfolios
Marina Drygala EPFL, Silvio Lattanzi Google, Andreas Maggiori Columbia University, Miltiadis Stouras EPFL, Ola Svensson EPFL, Sergei Vassilvitskii Google Research
Abstract:
In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select k potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem Π, a set of value functions V over the solutions of Π, and a distribution D over V, our goal is to select k solutions of Π that maximize or minimize the expected value of the best of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select r elements maximizing the total value. Now suppose that each element’s weight comes from a (known) distribution. How should we select k different solutions so that one of them is likely to yield a high value? In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal.
Robust Restaking Networks
Naveen Durvasula Columbia University, Tim Roughgarden Columbia University
Abstract:
We study the risks of validator reuse across multiple services in a restaking protocol. We characterize the robust security of a restaking network as a function of the buffer between the costs and profits from attacks. For example, our results imply that if attack costs always exceed attack profits by 10%, then a sudden loss of .1% of the overall stake (e.g., due to a software error) cannot result in the ultimate loss of more than 1.1% of the overall stake. We also provide local analogs of these overcollateralization conditions and robust security guarantees that apply specifically for a target service or coalition of services. All of our bounds on worst-case stake loss are the best possible. Finally, we bound the maximum-possible length of a cascade of attacks. Our results suggest measures of robustness that could be exposed to the participants in a restaking protocol. We also suggest polynomial-time computable sufficient conditions that can proxy for these measures.
A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications
Tsun-Ming Cheung McGill University, Hamed Hatami McGill University, Kaave Hosseini University of Rochester, Aleksandar Nikolov University of Toronto, Toniann Pitassi Columbia University, Morgan Shirley University of Toronto
Abstract:
We present a simple method based on a variant of Hölder’s inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier L1-norm) of a Boolean function. This answers an open question of Cheung, Hatami, Hosseini and Shirley (CCC 2023). As immediate consequences, we obtain the following results.
- We give an exponential separation between the logarithm of the randomized and the deterministic parity decision tree size. This is in sharp contrast with the standard binary decision tree setting where the logarithms of randomized and deterministic decision tree size are essentially polynomially related, as shown recently by Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (STOC 2023).
- We give an exponential separation between the approximate and the exact spectral norm for Boolean functions.
- We give an exponential separation for XOR functions between the deterministic communication complexity with oracle access to Equality function (DEQ) and randomized communication complexity. Previously, such a separation was known for general Boolean matrices by Chattopadhyay, Lovett, and Vinyals (CCC 2019) using the Integer Inner Product (IIP) function.
- Finally, our method gives an elementary and short proof for the mentioned exponential DEQ lower bound of Chattopadhyay, Lovett, and Vinyals for Integer Inner Product (IIP).
Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography
Prabhanjan Ananth UCSB, Fatih Kaleoglu UCSB, Henry Yuen Columbia University
Abstract:
Unclonable cryptography is concerned with leveraging the no-cloning principle to build cryptographic primitives that are otherwise impossible to achieve classically. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination: how well can non-communicating – but entangled – players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We leverage this result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.
Sparsity Lower Bounds for Probabilistic Polynomials
Josh Alman Columbia University, Arkadev Chattopadhyay TIFR, Mumbai, Ryan Williams MIT
Abstract and the link to the paper to come
Add to GMail