TodayNewsResearchFieldsStacksMarketAnalytics
⌘K

Research

New papers ranked by attention, with their code, models and discussion linked. Pick a field on the left.

WeekMonthQuarterAll
NewestMost relevant

Papers

Open problems

Rising research topics

Ask the research

Sample
ByteTrail · AI and developer-tools intelligence
NewsResearchStacksAPI
Fields · this week
All fields3248Multimodal519Agents496Frontier LLMs428Inference & serving257Image segmentation1733D scene154Learning verifiable rewards151Graph learning147Voice AI97Classifier & causal discovery85Forecasting time77Evals72Flow matching69Teacher policy distillation49Federated learning48All 32 fields

Open problems across fields

  • General in-context learning for embodied agents1 paper raises it · 0 address it

    Enables models to adapt to new tasks and environments without retraining, improving robustness in real-world deployment.

    • Has GPT-6-Astra Achieved Embodied Intelligence?raises
  • Cost and latency in embodied control loops1 paper raises it · 0 address it

    High computational and time costs limit real-time applicability of agentic systems in dynamic environments.

    • Has GPT-6-Astra Achieved Embodied Intelligence?raises
  • Physical-state verification and failure recovery1 paper raises it · 0 address it

    Agents must reliably detect and correct errors in physical interactions to avoid irreversible failures in real-world tasks.

    • Has GPT-6-Astra Achieved Embodied Intelligence?raises
  • Long-horizon task preservation in embodied agents1 paper raises it · 0 address it

    Maintaining progress over extended sequences is critical for complex, multi-step tasks in robotics and navigation.

    • Has GPT-6-Astra Achieved Embodied Intelligence?raises
  • Open-source stacks for generalist computer-use agents1 paper raises it · 1 addresses it

    Closed systems hinder reproducibility and systematic study of agent design for real-world computer tasks.

    • OpenGCUA: Toward a Fully Open Stack for Generalist Computer Useraises · addresses

Named by an AI from these papers' abstracts.

Rising research topics

Coming with more sources: more tagged papers
  • Small LLMs10+400.0%
  • Training & fine-tuning48+200.0%
  • Robotics24+200.0%
  • AI safety35+191.7%
  • Computer vision37+164.3%
  • Image & video generation27+125.0%
  • Evals72+100.0%
  • RAG10+100.0%

Papers

  • arXiv cs.CLOct 17

    Vocal-Tract Acoustics, Aerodynamics, and Overlap-and-Add Synthesis in DYNARTmo

    Bernd J. Kröger

    This paper presents the acoustic and aerodynamic extension of DYNARTmo, a dynamic articulatory model for visualizing and synthesizing speech production. Gestural control trajectories determine vocal-tract geometry, which is converted into an acoustic tube with nasal branching and effective lateral passages. A lumped aerodynamic network relates prescribed glottal motion and pulmonary pressure to airflow and supraglottal pressure storage. Phonatory excitation, oral friction, and glottal aspiration are synthesized as separate contributions. Frame-specific acoustic responses are combined by overlap-and-add, preserving response tails beyond individual control frames. Three German words, ``Tasse'', ``Muse'', and ``Lade'', illustrate the coordination of articulation, pressure, flow, and acoustic sources across vowels, nasals, laterals, fricatives, and plosives. The implementation has been optimized by the author primarily for sound recognizability; independent perceptual evaluation remains outstanding, and fricative-noise naturalness requires further refinement. The model provides an inspectable, articulatorily controlled production plant for future neural simulations of babbling,…

    PDF
  • arXiv cs.CLOct 17

    Modeling Discourse Profiles in Climate Misinformation Discourse

    Ge Gao, Zhengyang Shan, Bryan A. Plummer, Margrit Betke, Derry Wijaya

    Prior work on climate misinformation detection typically classifies individual comments or claims using text alone. This framing overlooks a key property of online climate discourse: misinformation is often produced, reinforced, and sustained through recurring rhetorical patterns that reappear across comments and threads. Using a large-scale TikTok climate discourse dataset, we construct discourse profiles by clustering climate-related comments into recurring rhetorical patterns. We then incorporate these profiles into fine-grained climate misinformation classifiers using a late-fusion architecture. Under video-disjoint evaluation across three training seeds, discourse-profile-aware models significantly improve macro-F1 over text-only baselines for bag-of-words, TF-IDF, and MPNet representations. RoBERTa-large exhibits a positive mean improvement but substantially greater variability, and the difference is not statistically significant. Beyond classification, our results show discourse profiles shape misinformation reception and propagation. Discourse-profile-conditioned language model agents exhibit misinformation acceptance patterns aligned with profile-level misinformation…

    PDF
  • arXiv cs.LGOct 17

    Steerable Pluralistic Policy Alignment from Anonymized Crowd Feedback

    Akansha Kalra, Ellen R. Novoseller, Vernon J. Lawhern, Daniel S. Brown

    Pluralistic alignment requires AI systems to learn from diverse populations whose preferences may reflect heterogeneous or even conflicting objectives, and to personalize their behavior to individual users. Existing approaches in pluralistic alignment often assume access to annotator identities and rely on powerful pretrained representations to model individual preference variations. We propose Preference-PCA Pluralistic Learning (P3L), a novel framework for pluralistic alignment that jointly learns trajectory embeddings and the shared basis of preference directions via PCA decomposition from heterogeneous crowd feedback without requiring annotator identities. At test time, our approach enables rapid and accurate personalized reward learning and downstream policy optimization. Experiments across multiple embodied control tasks demonstrate that P3L enables steerable personal alignment that generalizes beyond the offline dataset to out-of-distribution new users and attains competitive RL and test performance, while substantially reducing computational cost and supporting variable adaptation query budgets.

    PDF
  • arXiv cs.AIOct 17

    MedPAO-Assist: Edge-Deployable, Modality-Aware Agentic AI for Radiology Report Structuring

    Shrish Shrinath Vaidya, Minmini Selvam, Ganapathy Krishnamurthi

    The adoption of Large Language Models for radiology report structuring has been largely dominated by either proprietary cloud-based models or large open models requiring high-end GPUs for deployment, which is a critical bottleneck for clinical adoption in radiology workflows that demand data privacy and offline operation. To address this, we present MedPAO-Assist, an edge-deployable agentic framework that generates structured radiology reports directly from radiologist dictation and voice commands, requiring only $\approx3.3$ GB peak RAM and achieving an average end-to-end latency of $\approx31$ seconds on a standard laptop CPU through an asynchronous, multi-threaded execution pipeline. The system currently supports four major imaging modalities -- Chest X-ray, Chest CT, Abdomen CT, and Brain MRI. To our knowledge, it is among the earliest agentic systems to run its entire pipeline with a Small Language Model (SLM) in the 0.6B-parameter range. This multi-agent architecture, built around an Extract-Ground-Generate paradigm, performs concept extraction, SNOMED-CT grounding, and structured report generation, followed by a speech-driven human-in-the-loop correction phase, together…

    PDF
  • arXiv cs.CLOct 17

    Write Once, Check Many: Reusable Ledgers for Post-Hoc Policy Compliance Auditing of Agent Trajectories

    Ashwin Nagarajan, Gursimran Panesar, Alicia Yang, Mona T. Diab, Virginia Smith +1

    Auditing LLM agents against policies is critical to ensure safety but requires rereading long trajectories once per policy. Can we instead record each trajectory once and reuse that record for policies not known in advance? We propose write once, check many, a framework in which a writer model converts each agent trajectory into a policy-independent ledger of the agent's actions and outcomes. A reader then checks each new policy against the ledger alone, without access to the original trajectory. On 900 trajectories from SHADE-Arena, $τ$-bench, and $τ^2$-bench, we show that a 12B reader of narrative ledgers can either match or in fact achieve higher AUC than the same 12B model reading full trajectories. On SHADE-Arena policies that combine several facts, our approach outperforms a 31B model reading the trajectory (.777 vs. .713 AUC). When checking eight SHADE-Arena policies separately, ledgers use about $5\times$ fewer tokens, including the cost of writing them. A deeper analysis shows that rule-based extraction performs better on some single-action policies, and ledgers can miss evidence in long tool outputs and message contents. Our results suggest that reusable,…

    PDF
  • arXiv cs.CVOct 17

    RiSE: Residual Subspace Expert for Generalizable Text-Centric Image Forgery Localization

    Kahim Wong, Kemou Li, Yiming Chen, Haiwei Wu, Jiantao Zhou

    As AI-assisted image editing becomes increasingly prevalent, Text-Centric Image Forgery Localization (TFL) is essential for protecting trust in financial and legal records. However, we observe that existing TFL detectors predominantly rely on Full-Parameter Fine-Tuning (FPFT) and fail to generalize to unseen forgery types because FPFT can induce low-rank feature collapse and overfit training artifacts. Meanwhile, prior detectors capture diverse forgery traces with a single unified representation, making subtle traces entangled and difficult to learn. To address these challenges, we propose RiSE, a Residual Subspace Expert model that preserves pre-trained priors by freezing principal SVD components and adapting only the residual subspaces with a ViT-only segmentor to avoid feature collapse. RiSE introduces forgery-aware residual experts, where each expert is trained independently on a training subset with a particular forgery type, and we show that cross-domain localization performance improves consistently as more experts are added. At inference, we introduce Latent Perturbation Confidence (LPC), which selects the most confident expert by analytically computing the…

    PDF
  • arXiv cs.SEOct 17

    Effective Construction of Feature Database of Fingerprinting Functions for Code-Clone SCA

    Zhiling Zhu, Tieming Chen, Chengwei Liu, Jiahui Wu, Qijie Song +3

    In contemporary software development, the extensive adoption of third-party libraries has become standard practice to avoid reinventing the wheel. This trend is particularly evident in programming ecosystems that lack mature package managers, such as C/C++. Within this context, Code Clone Detection (CCD) techniques have emerged as essential tools for identifying instances of code reuse, thereby mitigating security and legal concerns. Despite significant advances in CCD algorithms, a notable gap persists between academic tools and real-world applications. This disparity primarily arises because academic tools rely on experimental datasets composed of a limited number of indexed repositories, whereas real-world applications require a much broader scope of code sources. To address this challenge, we propose a novel, systematic approach for selecting appropriate open-source repositories to construct a more effective CCD feature dataset. Our method, OSSScope, employs a greedy algorithm to analyze the diversity of fingerprinting functions across 2.55 million C repositories on GitHub, maximizing unique fingerprinting functions while minimizing the number of repositories required.…

    PDF
  • arXiv cs.CLOct 17

    Beyond Recall Saturation: Scaling Hard-Negative Reranker Training for Industrial Legal Retrieval

    Yunhan Li, Mingjie Xie, Zeyang Shi, Gengshen Wu, Min Yang

    Industrial retrieval systems often improve quality by enlarging embedding candidate pools or adopting complex training pipelines. We show that, under a sufficiently large but practical candidate pool, embedding recall exhibits diminishing returns, motivating a closer examination of reranker quality. On Chinese legal retrieval benchmarks, embedding top-300 reaches a high-recall operating region, while relevant evidence may still be ranked below the output cutoff. We compare hard-negative strategies for reranker training, including embedding-mined, self-mined, and dynamic-negative variants, under aligned retrieval protocols that evaluate reranking after candidate retrieval. Among the evaluated staged configurations, an embedding-to-self-mined pipeline provides a favorable trade-off; additional dynamic stages do not improve all held-out metrics. The selected pipeline scales from a 0.6B to a 4B reranker. Relative to the native 4B reranker, the trained 4B Stage2 model improves reported metrics on the STARD and CSAID benchmarks and on an internal development set, and is preferred in 72.4\% of non-tied comparisons on 410 de-identified, reconstructed internal operational-query inputs in…

    PDF
  • arXiv stat.MLOct 17

    Private Evaluation of High-Dimensional Functions

    Mohammad Afzali, Hassan Ashtiani, Adam Smith

    We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and query access to a function $f$---whose sensitivity may be unknown or unbounded---the goal is to privately output an approximation to $f(S)$. The black-box evaluator can only query the value of $f$ over a down neighborhood of $S$ (i.e., those subsets of $S$ that are obtained by removing a bounded number of elements from $S$). We design generic black-box evaluators for both pure and approximate differential privacy through a reduction to high-dimensional private quasi-concave optimization (QCO). Our black-box evaluator enjoys a geometric notion of utility. Consider the vectors obtained by applying $f$ on sets in a down neighborhood of $S$. With high probability, the evaluator's output is guaranteed to be in the convex hull of these vectors. Our work generalizes the result of Linder et al. [LRSS25] for real-valued function evaluation to high dimensions. It also recovers the private center-point guarantees of Beimel et al. [BMNS19], with an explicit additive approximation to maximum Tukey depth. We also apply our evaluators to user-level quasi-concave and convex…

    PDF
  • arXiv cs.SEOct 17

    Safety Analysis of CPSs Over-the-air Updates: Test Case Prioritization and Selection

    Andrea Bombarda, Luca Carminati, Nunzio Marco Bisceglia, Mehrnoosh Askarpour, Sahar Kokaly +3

    Over-the-air (OTA) updates for Cyber-Physical Systems (CPS) allow engineers to modify their software wirelessly. In the automotive domain, they enable manufacturers to update software without physical access to the vehicle. However, OTA updates can generate a large number of possible software configurations. For example, end users may decide whether or not to install any given OTA updates. The combinatorial explosion of these configurations hampers SW testing, a standard practice for detecting errors in CPS. To overcome this limitation, we propose CRISP (CRIticality-based Selection and Prioritization), a novel framework supporting test case prioritization and selection in the context of OTA updates. Our framework leverages test case robustness, i.e., how far they are from violating the system requirements, to drive test case prioritization and selection. It enables engineers to rank test case executions from most to least critical, and to select only the critical test cases relevant to a given OTA update. We evaluated our approach using a representative SW product line consisting of seven different vehicles, 22 driving scenarios, and two software components. We considered 224…

    PDF
  • arXiv cs.CLOct 17

    Ben-Misandry: A Bengali Dataset and Late-Fusion Transformer Framework for Detecting Anti-Male Gender Hate

    Md Mehedi Hasan Nipu, Chinmoy Mitra, Tarannum Ahmed Nowshin, Israt Moyeen Noumi

    Gender based hate speech research in Bengali has focused almost exclusively on misogyny, leaving anti male hate, or misandry, entirely unstudied for this language and creating a systematic blind spot in moderation systems trained to catch attacks on women but not on men. We introduce Ben-Misandry, the first Bengali misandry detection dataset: 5,000 comments across six taxonomy classes, including a novel category for mocking male emotional vulnerability with no direct analogue in existing misogyny taxonomies. The corpus is taxonomy-controlled synthetic data generated with GPT-4.1, spot-checked by four human reviewers on a 500-comment sample who confirmed the large majority of assigned labels; a full inter-annotator- agreement study is left to future work. We benchmark it with a classical pipeline (seven classifiers over four text representations) and a transformer pipeline (BanglaBERT, XLM-RoBERTa, and two fusion strategies). The best classical model, a linear SVM over character-level TF-IDF, reaches 91.8% accuracy; a late fusion ensemble averaging BanglaBERT and XLM-RoBERTa softmax outputs reaches 96.6% accuracy and macro ROC-AUC above 99%, nominally ahead of every single model…

    PDF
  • arXiv cs.AIOct 17

    Pluralistic Alignment in Language Models: Objectives, Human References, and Preference Representations

    Meng-Chen Wu, Umesh Bodhwani

    Pluralistic alignment aims to represent meaningful variation in human preferences rather than collapse heterogeneous judgments into a single target. Yet existing work often mixes three distinct questions: what pluralistic behavior a model should exhibit, whose preferences define the reference, and what evidence is sufficient to demonstrate success. We organize the literature around a two-layer taxonomy. Layer 1 distinguishes representing a range of human-supported viewpoints (Overton Pluralism), adapting faithfully to a specified perspective or preference condition (Steerable Pluralism), and matching the response distribution observed in a target population (Distributional Pluralism). Layer 2 distinguishes aggregate populations, countries and regions, and subgroups as human references. Preference representation, implementation mechanism, modality, and evidence quality are treated as cross-cutting design choices rather than additional forms of pluralism. We synthesize a protocol-bounded corpus of 70 works on pluralistic alignment and neighboring areas, using the objective-by-human-reference matrix to map existing approaches and identify underexplored combinations. The coded…

    PDF
  • arXiv cs.CLOct 17

    Which Long Documents Matter? A Controlled Study of Data Selection for Context Extension

    Junlong Jia, Jiang Zhou, Xing Wu, Chaochen Gao Tinghao Yu, Feng Zhang +1

    Natural long documents are widely used for context extension, but which selection pipelines are effective remains unclear. We conduct a controlled comparison on Qwen2.5-3B at 128K under matched 6B-token continued-training budgets. Random sampling of natural long documents (random-long) outperforms repacking at longer evaluation lengths. Within the same candidate pool, selecting documents with high LongPPL key-token density yields further gains, unlike the evaluated generic-quality and LLM-judge selectors. We introduce truncLongPPL to reduce scoring cost by computing key-token density over a truncated prefix. At 128K, scoring the first half of the reference span yields downstream performance close to full-span scoring with a measured $2.28\times$ end-to-end scoring speedup. Across three training seeds, truncLongPPL achieves the highest mean scores among evaluated pipelines, exceeding random-long by 4.54 points on validation HELMET and 3.28 on held-out RULER, with gains most consistent in retrieval. At a 256K target context, it gains 2.82 average RULER points over random-long on Qwen2.5-3B. In short/long mixed training across Qwen2.5-3B, Qwen3-8B, and OLMo~3-7B, it gains 1.47--7.31…

    PDF
  • arXiv cs.SDOct 17

    SENTRY: A Streaming Edge Network Trust Engine for Real-Time Audio Deepfake Detection

    Chirantan Banerjee, Soumita Chatterjee, Bhargab B. Bhattacharya, Hafizur Rahaman

    Real-time voice cloning has enabled large-scale streaming deepfake and vishing attacks, while existing Network Detection and Response (NDR) solutions rely on GPU-based post-processing that requires buffered audio and generalizes poorly to unseen speech synthesis models. This paper presents SENTRY, a hardware-oriented, streaming trust engine for inline deepfake detection at the network edge. SENTRY employs an integer lifting-wavelet front end together with a bank of multiplier-free transforms, including wavelet-packet envelopes, Walsh-Hadamard sequency profiles, waveform micro-statistics, and long-term spectral features, designed so that acoustic analysis needs only integer add, shift, compare and bitwise operations. A supervised gradient-boosted tree classifier is combined with an unsupervised Mahalanobis out-of-distribution detector trained solely on authentic speech, and their outputs are fused by a lightweight logistic layer to produce graduated LOG, CHALLENGE, or DROP actions. Under a closed-set protocol, SENTRY reaches 98.75% accuracy at a 1.25% equal-error rate (EER) on WaveFake, with perfect separation of HiFi-GAN and WaveGlow; its supervised track alone achieves an AUC of…

    PDF
  • arXiv cs.CVOct 17

    Unifying Amplitude-Phase Coupling and Reliable Endogenous Priors for Low-Light Image Enhancement

    Tongshun Zhang, Zixuan Zhong, Pingping Liu, Jin Kuang, Yubing Lu +2

    Frequency-domain methods have shown strong potential for low-light image enhancement (LLIE) because they can effectively regulate global illumination. However, most existing methods assume that amplitude and phase can be restored independently, while overlooking their inherent spectral coupling. This artificial decoupling often leads to information inconsistency and structural distortions. To address this issue, we propose a frequency-spatial framework that jointly models spectral interaction and reliable prior guidance. We first empirically analyze the coupling between amplitude and phase and develop an Amplitude-Phase Adaptive Compensation Fusion (APACF) module. Instead of enforcing a hard separation between the two components, APACF enables their bidirectional interaction, resulting in spectrally coherent restoration. In addition, directly extracting priors from raw low-light inputs is unreliable, since severe noise and underexposure destroy critical visual content. To alleviate this problem, we introduce an Endogenous Reliability Prior (ERP). Specifically, we treat an intermediate result, preliminarily restored in the frequency domain and already close to the ground-truth…

    PDF
  • arXiv cs.AIOct 17

    Learning to Compose: Recursive Self-Improvement of Shared Executable Stacks for Zero-Shot Long-Horizon Robot Manipulation

    Yangzhi Chen, Feiran Liu, Zishuo Wang, Zijian Jin, Xin Zhu +2

    Individually competent robot skills can fail when composed: tools may lack a required capability, completion signals may misrepresent physical progress, and one skill may leave a state that violates its successor's prerequisites. We introduce Recursia, a recursive self-improvement framework that treats the shared executable stack, rather than individual task programs, as the persistent unit of improvement. The stack integrates tools, skills with execution contracts, handoffs, and verifiers. Source-side execution traces guide failure attribution and the generation of missing tools or repairs to existing shared components. Generality checks, mechanism tests, and paired selection and regression gates determine which changes become the next parent. The resulting stack is frozen and reused through declarative task adapters, allowing source-derived changes to support new compositions without target-side code repair. Experiments cover LIBERO-Pro Long simulation and a physical Franka FR3 equipped with a Franka Hand. In simulation, Recursia improves success over ASPIRE by 5.8 percentage points under Pos perturbations and 15.1 points under Task perturbations. Across three physical…

    PDF
  • arXiv cs.CVOct 17

    O-SCD++: Replay-Free Online Scene Change Detection via Recursive Evidence Fusion

    Chamuditha Jayanga Galappaththige, Jason Lai, Lloyd Windrim, Timothy Patten, Donald G. Dansereau +2

    Online scene change detection requires an agent to detect what has changed in a previously mapped environment while it is still on site, observing from unconstrained viewpoints and without access to future observations. This causal setting is strictly harder than its offline counterpart, and online methods have consistently trailed offline accuracy. O-SCD closed that gap by treating change as a persistent property of a 3D Gaussian splatting map of the reference scene, surpassing the strongest offline methods in change detection accuracy while operating at over 10 frames per second. O-SCD optimizes a change field over the Gaussians of the reference map, refitting it to all past cue maps at every frame, a step that consumes more than half of the per-frame budget and forces accuracy to be traded against speed. We present a replay-free formulation that eliminates this trade-off. Because the reference map stays fixed, rendering the change field is a linear operation. Each new observation can therefore be carried onto the map's Gaussians directly, by a single backward pass of the renderer, which reduces multi-view fusion to an exact two-scalar recursion per Gaussian. Past observations…

    PDF
  • arXiv cs.LGOct 17

    Measuring Empowerment from Offline Data for Intrinsically Motivated Exploration

    Ishir Garg, Vivek Myers, Qiyang Li, Catherine Ji, Benjamin Eysenbach +1

    Large, unlabeled datasets of prior experience have become increasingly available for agentic tasks in domains such as robotics and coding. A common recipe for these tasks is to train a policy using the prior data, and then further improve it with online rollouts. But while much work has studied how to use both the offline and online data for policy extraction, far less work has been done to understand how the prior data can be used to efficiently \textit{explore} during the online learning phase. Previous work has attempted to formalize this idea by defining the \textit{empowerment}, a measure of how many future states an agent can realize; states with higher empowerment require more exploration as there are more futures to explore. However, existing methods for estimating empowerment require online policy rollouts in the environment. We propose the first method for estimating empowerment from unlabeled prior data, without any environment interaction. By jointly learning an empowerment-maximizing policy together with its discounted state-occupancy measure, our estimator can be trained on unlabeled trajectories generated from any unknown policy. We demonstrate that our empowerment…

    PDF
  • arXiv cs.LGOct 17

    Generative Retrieval for Reverse Target Fishing with a Proteome-Scale Benchmark

    Zhichao Deng, Haichuan Tan, Xin Hong, Huaizhi Wang, Tao Huang +2

    Reverse target fishing identifies protein targets for a query molecule and is central to drug discovery and repurposing. Discriminative approaches adapted from virtual screening face sparse, long-tailed associations and missing-not-at-random measurements: treating unrecorded pairs as negatives can suppress genuine targets. We reformulate the task as generative retrieval and introduce GenFish. Residual vector quantization converts frozen protein language model features into shared semantic identifiers. Given a molecular fingerprint, GenFish autoregressively models codes conditioned on the query and preceding code, ranking proteins by identifier likelihood without explicitly labeling unrecorded pairs as negatives. We introduce ProTargetBench, the first proteome-scale benchmark for reverse target fishing to jointly support measured-panel discrimination and full-catalogue recovery of experimentally recorded positives. Covering 20,431 UniProt-reviewed human proteins, it integrates curated bioactivity evidence and distinguishes experimental inactivity from unmeasured associations. On 198 held-out molecules, GenFish achieves higher mean performance across all three full-catalogue…

    PDF
  • arXiv cs.GTOct 17

    Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion

    Gabriel Chen, Yu Cheng, Alice Wang

    We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a…

    PDF
Load more