Tag: 2025

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