Ian Zhang

Kamesh Munagala, Qilin Ye, Ian Zhang

We study deliberative social choice, where voters engage in small-group discussions to output collective preferences that are then aggregated by a social choice rule. We introduce a simple deliberation-via-matching protocol. In this protocol, for each pair of candidates, we form a maximum matching among voters who disagree on that pair, and have each matched pair deliberate. We then aggregate the resulting individual and deliberative preferences using the weighted uncovered set tournament rule. We show that this protocol has a tight distortion bound of $3$ within the metric distortion framework. In the absence of deliberation, general deterministic social choice rules can achieve this distortion, whereas deterministic tournament rules face a strictly larger lower bound of $3.11$. Our result closes this gap: Pairwise deliberation allows a tournament-based rule to attain distortion $3$. Conceptually, this shows that tournament rules can match the power of general deterministic social choice rules once they are given the minimal added power of pairwise deliberations. We prove this bound via a novel bilinear relaxation of the non-linear program capturing optimal distortion, whose vertices we can explicitly enumerate, leading to an analytic proof. Loosely speaking, our key technical insight is that the distortion objective, as a function of metric distances to any three alternatives, is both supermodular and convex. This characterization therefore provides a new analytical tool for studying the distortion of deliberative protocols, and may be of independent interest. Finally, although our analysis is for the full protocol, we show that this mechanism also admits a lightweight sampling-based implementation, yielding a high-probability approximation to the deterministic guarantee with arbitrary accuracy and low per-voter complexity.

Aaron Li, Ian Zhang

Kleinberg and Mullainathan recently proposed a formal framework for studying the phenomenon of language generation, called language generation in the limit. In this model, an adversary gives an enumeration of example strings from an unknown target language, and the algorithm is tasked with correctly generating unseen strings from the target language within finite time. Refined notions of non-uniform and uniform generation were later introduced by Li, Raman, and Tewari (2025), and a noisy model was introduced by Raman and Raman (2025), which allows the adversary to insert extraneous strings. A natural question in the noisy model is to quantify the effect of noise, by studying the impact of each additional extraneous string. We show two complementary results in this setting. We first show that for both uniform and non-uniform generation, a single noisy string strictly reduces the set of collections that can be generated, thus answering an open question in Raman and Raman (2025). Then, we show for both uniform and non-uniform generation that generation with a single noisy string is equivalent to generation with any finite amount of noise, sharply contrasting with the strict hierarchy for noisy generation in the limit shown by Bai, Panigrahi, and Zhang (2026). Finally, we leverage our previous results to provide the first known characterization for non-uniform noise-dependent generatability.

Yannan Bai, Debmalya Panigrahi, Ian Zhang

Kleinberg and Mullainathan (2024) recently proposed a formal framework called language generation in the limit and showed that given a sequence of example strings from an unknown target language drawn from any countable collection, an algorithm can correctly generate unseen strings from the target language within finite time. This notion was further refined by Li, Raman, and Tewari (2024), who defined stricter categories of non-uniform and uniform generation. They showed that a finite union of uniformly generatable collections is generatable in the limit, and asked if the same is true for non-uniform generation. We begin by resolving the question in the negative: we give a uniformly generatable collection and a non-uniformly generatable collection whose union is not generatable in the limit. We then use facets of this construction to further our understanding of several variants of language generation. The first two, generation with noise and without samples, were introduced by Raman and Raman (2025) and Li, Raman, and Tewari (2024) respectively. We show the equivalence of these models for uniform and non-uniform generation, and provide a characterization of non-uniform noisy generation. The former paper asked if there is any separation between noisy and non-noisy generation in the limit -- we show that such a separation exists even with a single noisy string. Finally, we study the framework of generation with feedback, introduced by Charikar and Pabbaraju (2025), where the algorithm is strengthened by allowing it to ask membership queries. We show finite queries add no power, but infinite queries yield a strictly more powerful model. In summary, the results in this paper resolve the union-closedness of language generation in the limit, and leverage those techniques (and others) to give precise characterizations for natural variants that incorporate noise, loss, and feedback.

Weijian Huang, Hao Yang, Xinfeng Liu et al.

Multi-contrast magnetic resonance (MR) image registration is useful in the clinic to achieve fast and accurate imaging-based disease diagnosis and treatment planning. Nevertheless, the efficiency and performance of the existing registration algorithms can still be improved. In this paper, we propose a novel unsupervised learning-based framework to achieve accurate and efficient multi-contrast MR image registrations. Specifically, an end-to-end coarse-to-fine network architecture consisting of affine and deformable transformations is designed to improve the robustness and achieve end-to-end registration. Furthermore, a dual consistency constraint and a new prior knowledge-based loss function are developed to enhance the registration performances. The proposed method has been evaluated on a clinical dataset containing 555 cases, and encouraging performances have been achieved. Compared to the commonly utilized registration methods, including VoxelMorph, SyN, and LT-Net, the proposed method achieves better registration performance with a Dice score of 0.8397 in identifying stroke lesions. With regards to the registration speed, our method is about 10 times faster than the most competitive method of SyN (Affine) when testing on a CPU. Moreover, we prove that our method can still perform well on more challenging tasks with lacking scanning information data, showing high robustness for the clinical application.