Text-to-image (T2I) generative models can create vivid, realistic images from textual descriptions. As these models proliferate, they expose new concerns about their ability to represent diverse demographic groups, propagate stereo-types, and efface minority populations. Despite growing attention to the "safe" and "responsible" design of artificial intelligence (AI), there is no established methodology to systematically measure and control representational harms in image generation. This paper introduces a novel frame-work to measure the representation of intersectional groups in images generated by T2I models by applying the Multi-Group Proportional Representation (MPR) metric. MPR evaluates the worst-case deviation of representation statistics across given population groups in images produced by a generative model, allowing for flexible and context-specific measurements based on user requirements. We also develop an algorithm to optimize T2I models for this metric. Through experiments, we demonstrate that MPR can effectively mea-sure representation statistics across multiple intersectional groups and, when used as a training objective, can guide models toward a more balanced generation across demo-graphic groups while maintaining generation quality.1

In differentially private distributed mean estimation (DP-DME), a central server computes the mean of vectors distributed across$n$users while preserving differential privacy (DP). DP-DME has been studied under various DP models, with distributed DP with secure aggregation and local DP (LDP) being the main models that do not rely on a trusted third party. Distributed DP-based schemes leverage correlated noise among users to achieve higher accuracy than LDP-based schemes, where users operate independently. However, the accuracy of distributed DP comes at the cost of higher communication overhead for generating correlated noise and complex multiround protocols to handle dropouts. In this work, we analyze the communication-accuracy trade-off in distributed DP-DME under arbitrary communication constraints, and propose a method to generate correlated noise strategically within these constraints to enable single-round dropout handling. Our results show that the communication costs of existing distributed DP-DME approaches can be substantially reduced with minimal impact on accuracy.

Large language model (LLM) watermarks enable authentication of text provenance, curb misuse of machine-generated text, and promote trust in AI systems. Current watermarks operate by changing the next-token predictions output by an LLM. The updated (i.e., watermarked) predictions depend on random side information produced, for example, by hashing previously generated tokens. LLM watermarking is particularly challenging in low-entropy generation tasks -- such as coding -- where next-token predictions are near-deterministic. In this paper, we propose an optimization framework for watermark design. Our goal is to understand how to most effectively use random side information in order to maximize the likelihood of watermark detection and minimize the distortion of generated text. Our analysis informs the design of two new watermarks: HeavyWater and SimplexWater. Both watermarks are tunable, gracefully trading-off between detection accuracy and text distortion. They can also be applied to any LLM and are agnostic to side information generation. We examine the performance of HeavyWater and SimplexWater through several benchmarks, demonstrating that they can achieve high watermark detection accuracy with minimal compromise of text generation quality, particularly in the low-entropy regime. Our theoretical analysis also reveals surprising new connections between LLM watermarking and coding theory.

We consider both classical and quantum variations ofX-secure,E-eavesdropped andT-colluding symmetric private information retrieval (SPIR). This is the first work to study SPIR withX-security in classical or quantum variations. We first develop a scheme for classicalX-secure,E-eavesdropped andT-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate of$R= 1 - \frac {X+\max (T,E)}{N}$. The modified scheme achieves the same rate as the scheme used forX-secure PIR with the extra benefit of symmetric privacy, i.e., user-privacy as well as database-privacy. Next, we extend this scheme to its quantum counterpart based on theN-sum box abstraction. This is the first work to consider the presence of eavesdroppers in quantum private information retrieval (QPIR). In the quantum variation, the eavesdroppers have better access to information over the quantum channel compared to the classical channel due to the over-the-air decodability. To that end, we develop two different schemes for quantumX-secure,E-eavesdropped andT-colluding SPIR (QXSETSPIR) with secure over-the-air decoding. The first scheme achieves the highest possible super-dense coding gain, i.e.,$R_{Q} = \min \left \{{{ 1, 2\left ({{1-\frac {X+\max (T,E)}{N}}}\right)}}\right \}$, which requires additional uploads from the user. The second scheme on the other hand requires no extra uploads. However, it does not achieve the super-dense coding gain in some cases based on the relation between the number of eavesdropped links and the number of interference terms. The second scheme is based on the idea that there exist some special entanglement states that can be used to hide the contents of the user-required messages from the eavesdroppers using the interference symbols.

We consider the problem of private approximate nearest neighbor (ANN) search. A user seeks the closest vector to a target query$q$among$M$vectors stored in a system of$N$non-colluding databases. The user aims to retrieve the ANN without revealing information about$q$to any of the$N$databases. We provide an information-theoretic formulation of the problem and propose a scheme based on a tree-structured ANN search mechanism. The proposed scheme uses a coding-theoretic approach to traverse the branch in the tree structure that leads to the approximately closest vector to$q$while guaran-teeing perfect information-theoretic privacy. We prove that our approach achieves a communication cost of$O(N^{2}M^{\frac{1}{N-1})}$for$N$databases. For large$M$, this communication cost is lower than competing cryptographic ANN search protocols.

Image search and retrieval tasks can perpetuate harmful stereotypes, erase cultural identities, and amplify social disparities. Current approaches to mitigate these representational harms balance the number of retrieved items across population groups defined by a small number of (often binary) attributes. However, most existing methods overlook intersectional groups determined by combinations of group attributes, such as gender, race, and ethnicity. We introduce Multi-Group Proportional Representation (MPR), a novel metric that measures representation across intersectional groups. We develop practical methods for estimating MPR, provide theoretical guarantees, and propose optimization algorithms to ensure MPR in retrieval. We demonstrate that existing methods optimizing for equal and proportional representation metrics may fail to promote MPR. Crucially, our work shows that optimizing MPR yields more proportional representation across multiple intersectional groups specified by a rich function class, often with minimal compromise in retrieval accuracy. Code is provided at https://github.com/alex-oesterling/multigroup-proportional-representation.

We investigate the problem of private read-update-write (PRUW) in relation to private federated submodel learning (FSL), where a machine learning model is divided into multiple submodels based on the different types of data used to train the model. In PRUW, each user downloads the required submodel without revealing its index in the reading phase, and uploads the updates of the submodel without revealing the submodel index or the values of the updates in the writing phase. In this work, we first provide a basic communication efficient PRUW scheme, and study further means of reducing the communication cost via sparsification. Gradient sparsification is a widely used concept in learning applications, where only a selected set of parameters is downloaded and updated, which significantly reduces the communication cost. In this paper, we study how the concept of sparsification can be incorporated in private FSL with the goal of reducing the communication cost, while guaranteeing information-theoretic privacy of the updated submodel index as well as the values of the updates. To this end, we introduce two schemes: PRUW with top$r$sparsification and PRUW with random sparsification. The former communicates only the most significant parameters/updates among the servers and the users, while the latter communicates a randomly selected set of parameters/updates. The two proposed schemes introduce novel techniques such as parameter/update (noisy) permutations to handle the additional sources of information leakage in PRUW caused by sparsification. Both schemes result in significantly reduced communication costs compared to that of the basic (non-sparse) PRUW scheme.

In federated learning (FL), a machine learning (ML) model is collectively trained by a large number of users, using their private data in their local devices. With toprsparsification in FL, the users only upload the most significantrfraction of updates, and download only the most significantr’ fraction of parameters in order to reduce the communication cost. However, the values and the indices of the sparse updates and parameters leak information about the users’ private data. In this work, we consider an FL setting whereNnon-colluding databases store the model to be trained, from which the users download and update sparse parameters privately, without revealing the values of the updates/parameters or their indices to the databases. We propose four schemes with different properties that are based on cross subspace alignment (CSA) and permutation techniques, to perform this task while achieving the minimum communication costs within the scope of CSA, and show that the information theoretic privacy of both the values and the positions of the sparse updates/parameters can be guaranteed. This is achieved at a considerable storage cost, though. To alleviate this, we generalize the schemes in such a way that the storage cost is reduced at the expense of a certain amount of information leakage, using a model segmentation mechanism. In general, we provide the trade-off between the communication cost, storage cost and information leakage in private FL with toprsparsification.

In federated submodel learning (FSL), a machine learning model is divided into multiple submodels based on different types of data used for training. Each user involved in the training process only downloads and updates the submodel relevant to the user’s local data, which significantly reduces the communication cost compared to classical federated learning (FL). However, the index of the submodel updated by the user and the values of the updates reveal information about the user’s private data. In order to guarantee information-theoretic privacy in FSL, the model is stored at multiple non-colluding databases, and the user sends queries and updates to each database in such a way that no information is revealed on the updating submodel index or the values of the updates. In this work, we consider the practical scenario where the multiple non-colluding databases are allowed to have arbitrary storage constraints. The goal of this work is to develop read-write schemes and storage mechanisms for FSL that efficiently utilize the available storage in each database to store the submodel parameters in such a way that the total communication cost is minimized while guaranteeing information-theoretic privacy of the updating submodel index and the values of the updates. As the main result, we consider both heterogeneous and homogeneous storage constrained databases, and propose private read-write and storage schemes for the two cases.

We investigate the trade-off between rate, privacy and storage in federated learning (FL) with top$r$sparsification, where the users and the servers in the FL system only share the most significant$r$and$r^{\prime}$fractions, respectively, of updates and parameters in the FL process, to reduce the communication cost. We present schemes that guarantee information theoretic privacy of the values and indices of the sparse updates sent by the users at the expense of a larger storage cost. To this end, we generalize the scheme to reduce the storage cost by allowing a certain amount of information leakage. Thus, we provide the general trade-off between the communication cost, storage cost, and information leakage in private FL with top$r$sparsification, along the lines of two proposed schemes.

We investigate the problem of private read update write (PRUW) with heterogeneous storage constrained databases in federated submodel learning (FSL). In FSL a machine learning model is divided into multiple submodels based on different types of data used to train it. A given user downloads, updates and uploads the updates back to a single submodel of interest, based on the type of user’s local data. With PRUW, the process of reading (downloading) and writing (uploading) is carried out such that information-theoretic privacy of the updating submodel index and the values of updates is guaranteed. We consider the practical scenario where the submodels are stored in databases with arbitrary (heterogeneous) storage constraints, and provide a PRUW scheme with a storage mechanism that utilizes submodel partitioning and encoding to minimize the communication cost.

We investigate the problem of private federated submodel learning, where a machine learning model is divided into M submodels and stored in N databases, from which a given user privately reads, updates and writes back an arbitrary submodel. We consider information-theoretic privacy of the updated submodel index as well as the values of the updates. We provide an efficient private read update write (PRUW) scheme which achieves a lower total communication cost compared to the state-of-the-art. Our scheme significantly reduces the writing cost by combining all updates into a single bit in a way that it can be privately decomposed and placed at the relevant positions at the databases. This is achieved by over-designing the system with additional random noise terms in storage, which in turn provides additional security to the submodels. The scheme is designed for arbitrary privacy and security requirements.

We investigate the problem of private read update write (PRUW) in relation to federated submodel learning (FSL) with storage constrained databases. In PRUW, a user privately reads a submodel from a system of N databases containing M submodels, updates it locally, and writes the update back to the databases without revealing the submodel index or the value of the update. The databases considered in this problem are only allowed to store a given amount of information specified by an arbitrary storage constraint. We provide a storage mechanism that determines the contents of each database prior to the application of the PRUW scheme, such that the total communication cost is minimized. We show that the proposed storage scheme achieves a lower total cost compared to what is achieved by using coded storage or divided storage to meet the given storage constraint.

We investigate the problem of private read update write (PRUW) in federated submodel learning (FSL) with sparsification. In FSL, a machine learning model is divided into multiple submodels, where each user updates only the submodel that is relevant to the user’s local data. PRUW is the process of privately performing FSL by reading from and writing to the required submodel without revealing the submodel index or the values of updates to the databases. Sparsification is a widely used concept in learning, where the users update only a small fraction of parameters to reduce the communication cost. Revealing the coordinates of these selected (sparse) updates leaks privacy of the user. We show how PRUW in FSL can be performed with sparsification. We propose a novel scheme which privately reads from and writes to arbitrary parameters of any given submodel, without revealing the submodel index, values of the updates, or the coordinates of the sparse updates, to databases. The proposed scheme achieves significantly lower reading and writing costs compared to what is achieved without sparsification.

We investigate the problem of semantic private information retrieval (semantic PIR). In semantic PIR, a user retrieves a message out of$K$independent messages stored in$N$replicated and non-colluding databases without revealing the identity of the desired message to any individual database. The messages come withdifferent semantics, i.e., the messages are allowed to havenon-uniform a priori probabilitiesdenoted by$(p_{i}>0,\: i \in [K])$, which are a proxy for their respective popularity of retrieval, andarbitrary message sizes$(L_{i},\: i \in [K])$. This is a generalization of the classical private information retrieval (PIR) problem, where messages are assumed to have equal message sizes. We derive the semantic PIR capacity for general$K$,$N$. The results show that the semantic PIR capacity depends on the number of databases$N$, the number of messages$K$, the a priori probability distribution of messages$p_{i}$, and the message sizes$L_{i}$. We present two achievable semantic PIR schemes: The first one is a deterministic scheme which is based on message asymmetry. This scheme employs non-uniform subpacketization. The second scheme is probabilistic and is based on choosing one query set out of multiple options at random to retrieve the required message without the need for exponential subpacketization. We derive necessary and sufficient conditions for the semantic PIR capacity to exceed the classical PIR capacity with equal priors and sizes. Our results show that the semantic PIR capacity can be larger than the classical PIR capacity when longer messages have higher popularities. However, when messages are equal-length, the non-uniform priors cannot be exploited to improve the retrieval rate over the classical PIR capacity. We provide two extensions of the semantic PIR problem, namely, the semantic PIR from MDS-coded databases and the semantic PIR from colluding databases. For both extensions, we derive the exact PIR capacity in addition to providing a corresponding optimal scheme.

We investigate the problem of semantic private information retrieval (PIR) from coded databases, where a user requires to download a message out of$M$independent messages, without revealing its identity to the databases. These messages are coded using an (N, K) MDS code and stored in$N$non-colluding databases. The$M$messages are allowed to have different semantics, e.g., different sizes and different probabilities of retrieval. We characterize the exact capacity of semantic PIR with coded databases, and provide an achievable scheme with non-uniform subpacketization. We show that the retrieval rate of semantic PIR with coded databases outperforms that of classical PIR with coded databases when the effects of zero padding shorter messages are taken into account.

We investigate the problem of semantic private information retrieval (semantic PIR). In semantic PIR, a user privately retrieves a message out of K independent messages stored in N replicated and non-colluding databases. The messages come with different semantics, i.e., the messages are allowed to have non-uniform a priori probabilities denoted by (pi> 0, i ∈ [K]) and arbitrary message sizes (Li, i ∈ [K]). We derive the semantic PIR capacity for general K, N. We present two achievable semantic PIR schemes: The first one is a deterministic scheme with non-uniform subpacketization. The second scheme is probabilistic and is based on choosing one query set out of multiple options at random to retrieve the required message without the need for exponential subpacketization. We derive conditions for the semantic PIR capacity to exceed the classical PIR capacity with equal priors and sizes. Our results show that the semantic PIR capacity can be larger than the classical PIR capacity when longer messages have higher popularities. However, when messages are of equal-length, the non-uniform priors cannot be exploited to improve the retrieval rate.