arXiv:2607.13217v1 Announce Type: new
Abstract: Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class $\mathcal{F}$. We call this problem Hierarchical $\mathcal{F}$-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of $\mathcal{F}$: trees and graphs of bounded diameter.
We present the first polynomial time $\mathcal{O}(\log n\cdot\log\log n)$ and $\mathcal{O}(\log n)$-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes $\mathcal{F}$ for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call $p_{\mathcal{F}}$-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.
Science Journals
arXiv:2408.04118v5 Announce Type: replace
Abstract: Much energy has been devoted to developing a matroid's computational properties, yet parallel algorithm design for matroid optimization seems less understood. Specifically, the current state of the art is a folklore reduction from optimization to the search based on methods originating in [KUW88]. However, while this reduction adds only constant overhead in terms of \emph{adaptive complexity}, it imposes a high cost in \emph{query complexity}. In response, we present a new reduction from optimization to search within the class of \emph{binary matroids} which, when $n$ and $r$ take the size of the ground set and matroid rank respectively, implies a novel optimization algorithm terminating in $\mathcal{O}(\sqrt{n}\cdot\log r)$ parallel rounds using only $\mathcal{O}(rn\cdot\log r)$ independence queries. This is a significant improvement in query complexity when the matroid is sparse, meaning $r \ll n$, while trading off only a logarithmic factor of the rank in the adaptive complexity. At a technical level, our method begins by observing that a basis is optimal if and only if it is the set of points of minimum weight in any cocircuit. Importantly, this certificate reveals that simultaneous tests for \emph{local optimality} in cocircuits is a general paradigm for parallel matroid optimization. By combining this idea with connections between bases and cocircuits we obtain our reduction, whose efficiency follows by analyzing the lattice of flats. A primary goal of our study is initiating a finer understanding of parallel matroid optimization. And so, since many of our techniques begin with observations about general matroids and their flats, we hope that our efforts aid the future design of parallel matroid algorithms and applications of lattice theory thereof.
arXiv:2607.13891v1 Announce Type: new
Abstract: Multi-object detection and tracking from noisy point clouds remain challenging in many data-scarce radar applications. Current Bayesian trackers based on Poisson measurement models offer a training-free solution but struggle to achieve accuracy and efficiency under severe clutter, large object populations, and full-resolution Doppler point clouds. We address this with PiVoT, a fast, clutter-resilient multi-object tracker for both positional and Doppler measurements. PiVoT performs end-to-end detection and tracking of a large and time-varying number of objects without external clustering or detectors, through joint inference of object states, shapes, existence probabilities, data association, and measurement rates. Its efficiency is driven by several variational inference innovations, such as theoretically justified birth pruning, quadratic-to-linear complexity reductions for exact updates, and a computationally efficient Doppler Poisson model. Experiments show that PiVoT substantially outperforms existing Bayesian trackers in challenging scenes, while also demonstrating exceptional scalability to a thousand objects, robustness to clutter visually inseparable from objects, and real-time operation on full-scale modern automotive radar datasets, where it attains performance comparable to a deep-learning detection benchmark as a training-free joint detector and tracker.
arXiv:2607.13084v1 Announce Type: new
Abstract: The Earth is rare and large-scale interstellar travel may be unfeasible - instead of migrating to other solar systems, future civilisations on Earth may have to remain. However, left unchecked, the Earth's current habitability will end in one billion years. This paper investigates and conceptualises a set of megaengineering concepts required to safeguard against seven long-term threats to Earth's habitability: solar luminosity, solar engulfment, the end of tectonics, water loss, obliquity and rotation, object collision, and extra-system threats. Implementing and maintaining the set of safeguards would allow the Earth to remain habitable for 9.1 million billion years. This could be raised by an order of magnitude via lifting and moving solar photospheric mass. Compared with alternatives, advantages of the safeguards such as greater feasibility, lower requisite rate of energy production, and utilisation of economically viable space mining infrastructure may present remaining on Earth as a more attractive long-term survival strategy.
arXiv:2408.10581v3 Announce Type: replace
Abstract: This work introduces a novel and generalizable multi-view Hand Mesh Reconstruction (HMR) model, named POEM, designed for practical use in real-world hand motion capture scenarios. The advances of the POEM model consist of two main aspects. First, concerning the modeling of the problem, we propose embedding a static basis point within the multi-view stereo space. A point represents a natural form of 3D information and serves as an ideal medium for fusing features across different views, given its varied projections across these views. Consequently, our method harnesses a simple yet effective idea: a complex 3D hand mesh can be represented by a set of 3D basis points that 1) are embedded in the multi-view stereo, 2) carry features from the multi-view images, and 3) encompass the hand in it. The second advance lies in the training strategy. We utilize a combination of five large-scale multi-view datasets and employ randomization in the number, order, and poses of the cameras. By processing such a vast amount of data and a diverse array of camera configurations, our model demonstrates notable generalizability in the real-world applications. As a result, POEM presents a highly practical, plug-and-play solution that enables user-friendly, cost-effective multi-view motion capture for both left and right hands. The model and source codes are available at https://github.com/JubSteven/POEM-v2.
arXiv:2607.13087v1 Announce Type: new
Abstract: AI agents are rapidly accelerating work at frontier AI companies, helping with AI R&D, cyber-defence, and advancing scientific discoveries. As these agents become more tightly integrated into our systems, unlocking their full potential requires rethinking how we do security. We should not assume that AI agents are always perfectly aligned, but should instead build in multiple layers of defence. We present the GDM AI Control Roadmap (v0.1) -- a first-of-its-kind blueprint for internal security against potentially misaligned AI. This report provides:
* Threat modelling: We adopt a conservative approach to threat modelling and assume a hypothetical AI adversary pursuing undesirable goals in internal deployment. We introduce TRAIT&R, a taxonomy of tactics and techniques available to such a hypothetical AI adversary, building on the established security framework MITRE ATT&CK.
* Capability-based mitigation: Because controlling more capable models requires more costly interventions, we link specific defensive measures to evolving model capabilities (such as the ability to reason opaquely or execute complex cyberattacks). As models get more powerful, our defences should escalate accordingly. We outline four Detection tiers (D1-D4) and three Prevention and Response tiers (R1-R3).
* A portfolio of practical defences: We suggest 15 concrete, tiered mitigations. These range from low-cost interventions for current models (e.g., chain-of-thought monitoring, asynchronous alerts) to advanced safeguards for future models (e.g., real-time access control, system-level anomaly detection, internal activations monitoring, and shutdown infrastructure).
AI control is a nascent field, and implementing these mitigations requires navigating difficult trade-offs between security and developer velocity. We expect the roadmap to evolve as we gain more experience and as the field in turn evolves.
arXiv:2607.13703v1 Announce Type: new
Abstract: We investigate conditional invertible neural networks (cINNs) as probabilistic inverse-dynamics models for multirotor control. For a planar X8 coaxial multicopter, we learn $p(u \mid s_t, c_t)$ from an incremental nonlinear dynamic inversion (INDI) teacher using rational-quadratic spline coupling and invertible linear mixing. Open-loop reproduction reaches $R^2 = 0.944$, mean CRPS 0.0915, and log-probability-error correlation $\rho = -0.60$. Over 15 closed-loop scenarios, position RMSE matches INDI (9.7 vs. 9.5 m), with 47 percent tracking acceptably; failures separate into attitude divergence under aggressive steps and phase lag under high-frequency references, isolating command bandwidth and data coverage as dominant failure mechanisms.
arXiv:2607.13156v1 Announce Type: new
Abstract: Design Systems (DS) help standardize front-end development, yet developers still face challenges when translating high-fidelity mockups into consistent, production-ready interfaces. Although AI-assisted tools have emerged as a potential solution, empirical evidence on their effectiveness within DS-centered workflows remains limited. This paper reports a controlled experiment conducted at a large Brazilian enterprise that compares manual development, DS-only development, and DS-aware AI-assisted development across Angular, iOS, and Android stacks. Results from two experimental cycles show that AI assistance significantly reduced time-to-delivery (by 46.7% to 69.4%), increased task completeness, and decreased performance variability. Analysis of break patterns further suggests reduced workflow friction and smoother task execution. These findings provide empirical evidence that DS-aware AI tools can significantly accelerate development, improve design fidelity, and yield practical benefits for industrial front-end workflows.
arXiv:2411.19142v3 Announce Type: replace
Abstract: The General Data Protection Regulation (GDPR) is considered as the benchmark in the European Union (EU) for privacy and data protection standards. Since before its entry into force in 2018, substantial research has been conducted in the software engineering (SE) literature investigating the elicitation, representation, and verification of GDPR privacy requirements. Software systems deployed anywhere in the world must comply with GDPR as long as they handle personal data of EU residents. Mobile applications (apps) are no different in that regard. With the growing pervasiveness of mobile apps and their increasing demand for personal data, privacy concerns have acquired further interest within the SE community. Despite the extensive literature on GDPR-relevant privacy concerns in mobile apps, there is no secondary study that describes, analyzes, and categorizes the current focus. Research gaps and persistent challenges are thus left unnoticed. This article aims to provide a comprehensive overview of the existing research on GDPR privacy concerns in the context of mobile apps. To do so, we conducted a systematic literature review of 60 primary studies. Our findings show that existing studies predominantly address three key GDPR-related privacy concerns: (i) the direct collection of personal data from users, (ii) the sharing of personal data with external entities (e.g., third parties) beyond the mobile apps, and (iii) the analysis of user consent as a legal basis for collecting personal data. Our study highlighted research gaps, calling for further research to better understand: (i) the indirect collection of personal data, e.g., data exposed to mobile apps through, e.g., permission requests, (ii) the impact of legal bases beyond consent and how they may affect the development of mobile apps, and (iii) the required implementation details pertinent to data subject rights.
arXiv:2501.05396v4 Announce Type: replace
Abstract: Large language models (LLMs) are increasingly used in high-stakes decisions such as hiring and college admissions, making their social bias a critical concern. While LLMs are trained to refuse explicitly biased requests, bias can be leaked implicitly during LLM planning and reasoning process. As code becomes the primary medium for LLM internal logic-writing, we introduce FairCoder, a benchmark that frames decision-making as coding tasks to systematically probe LLM bias across employment, education, and healthcare domains, covering multiple fairness definitions. Considering that existing metrics may fail when LLMs frequently refuse the request, we propose FairScore, a metric that jointly captures refusal behavior and group-level outcome diversity. Experiments with a 1k-sample dataset on powerful LLMs reveal consistent and previously underexplored bias patterns, such as prioritizing applicants from high-income families in college admissions. Our findings highlight the risks of deploying LLMs as decision-making agents and provide a comprehensive evaluation framework for future research.
arXiv:2502.07780v4 Announce Type: replace
Abstract: Large Language Models (LLMs) have achieved significant success across various NLP tasks. However, their massive computational costs limit their widespread use, particularly in real-time applications. Structured pruning offers an effective solution by compressing models and directly providing end-to-end speed improvements, regardless of the hardware environment. Meanwhile, different components of the model exhibit varying sensitivities towards pruning, calling for non-uniform model compression. However, a pruning method should not only identify a capable substructure, but also account for post-compression training. To this end, we propose DarwinLM, a method for training-aware structured pruning. DarwinLM builds upon an evolutionary search process, generating multiple offspring models in each generation through mutation, and selecting the fittest for survival. To assess the effect of post-training, we incorporate a lightweight, multistep training process within the offspring population, progressively increasing the number of tokens and eliminating poorly performing models in each selection stage. We validate our method through extensive experiments on Llama-2-7B, Llama-3.1-8B and Qwen-2.5-14B-Instruct, achieving state-of-the-art performance for structured pruning. For instance, DarwinLM surpasses ShearedLlama while requiring 5x less training data during post-compression training. Code is at: https://github.com/IST-DASLab/DarwinLM
arXiv:2607.13889v1 Announce Type: new
Abstract: Voltage-source converter high-voltage direct current (VSC-HVDC) links offer controllable active and reactive power output, making them a promising asset for emergency voltage support. This paper presents an analytical method for adjusting the active power setpoint of a VSC-HVDC station to maximise loadability during voltage-stressed conditions. By exploiting the geometric structure of converter capability limits, a closed-form expression for the optimal setpoint is derived under combined current and voltage constraints. The method requires local voltage measurements and an estimate of a wide-area voltage angle difference, making it suitable for real-time emergency control without global optimisation. Validation on the Nordic Test System confirms that the analytically predicted optimum is consistent with the setpoint yielding the highest loadability, and that adjustments of active power setpoint can yield a more-than-proportional increase in loadability. The results further indicate robustness to angle estimate uncertainty.
arXiv:2607.14001v1 Announce Type: new
Abstract: We suggest using the Lyapunov characteristic exponent (LCE) as a dense reward signal for the reinforcement learning problem of stabilizing the inverted pendulum with vertical motion. With LCE, the agent not only successfully found the oscillatory motion known as the Kapitza pendulum but also damped the pendulum's pivoting, leaving it in a strictly upright position.
arXiv:2607.14027v1 Announce Type: new
Abstract: We propose SPECS, a genetic algorithm for automated analog circuit synthesis with joint topology and sizing optimization. SPECS is inspired by NeuroEvolution of Augmenting Topologies (NEAT), an evolutionary algorithm originally developed to synthesize neural networks. By reformulating the genome representation and adapting the genetic operators to the analog circuit domain, we successfully transfer the core principles of NEAT to analog circuit synthesis. Circuit-specific wiring constraints are incorporated to ensure valid and physically meaningful designs throughout the evolutionary process, and speciation is used to preserve innovation while maintaining population diversity. We evaluate the proposed method on a set of computational circuit synthesis tasks consisting of square, cube, square root, and cube root functions. Experimental results demonstrate that SPECS outperforms benchmark methods across all tasks in both solution quality and reliability. The synthesized circuits and their schematics are available in the supplementary repository.
arXiv:2502.11449v4 Announce Type: replace
Abstract: We study Walrasian economies (or general equilibrium models) and their solution concept, the Walrasian equilibrium. A key challenge in this domain is identifying price-adjustment processes that converge to equilibrium. One such process, t\^atonnement, is an auction-like algorithm first proposed in 1874 by L\'eon Walras. While continuous-time variants of t\^atonnement are known to converge to equilibrium in economies satisfying the Weak Axiom of Revealed Preferences (WARP), the process fails to converge in a pathological Walrasian economy known as the Scarf economy. To address these issues, we analyze Walrasian economies using variational inequalities (VIs), an optimization framework. We introduce the class of mirror extragradient algorithms, which, under suitable Lipschitz-continuity-like assumptions, converge to a solution of any VI satisfying the Minty condition in polynomial time. We show that the set of Walrasian equilibria of any balanced economy-which includes among others Arrow-Debreu economies-corresponds to the solution set of an associated VI that satisfies the Minty condition but is generally discontinuous. Applying the mirror extragradient algorithm to this VI we obtain a class of t\^atonnement-like processes, which we call the mirror extrat\^atonnement process. While our VI formulation is generally discontinuous, it is Lipschitz-continuous in variationally stable Walrasian economies with bounded elasticity-including those satisfying WARP and the Scarf economy-thus establishing the polynomial-time convergence of mirror extrat\^atonnement in these economies. We validate our approach through experiments on large Arrow-Debreu economies with Cobb-Douglas, Leontief, and CES consumers, as well as the Scarf economy, demonstrating fast convergence in all cases without failure.
arXiv:2502.13467v2 Announce Type: replace
Abstract: The $K$-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward is determined by the maximum outcome among $K$ selected arms. When outcomes are continuous and only the maximum value together with the winner's index is observed, this problem introduces unprecedented difficulties including discretization errors, non-deterministic tie-breaking, and severe estimation biases. To overcome these barriers, we introduce DCK-UCB, an efficient algorithm combining adaptive discretization with bias-corrected confidence bounds. We prove that DCK-UCB achieves a $\widetilde{O}(T^{3/4})$ regret bound, the first sublinear guarantee in this setting. Numerical experiments show strong performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose the MLE-Exp algorithm that attains a near-optimal $\widetilde{O}(\sqrt{T})$ regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.
arXiv:2502.16167v2 Announce Type: replace
Abstract: Diffusion models (DMs) have advanced text-to-image (T2I) synthesis, yet their personalization capabilities raise serious privacy and copyright concerns. Malicious actors can misuse these models to generate unauthorized portraits or artistic style replicas. Existing proactive defenses primarily rely on applying adversarial perturbations to reference images to disrupt training. However, these approaches face limitations: they assume all training images are pre-perturbed and are prone to failure when datasets contain unperturbed images or undergo minor data transformations. In this paper, we introduce PersGuard, a novel backdoor-based framework designed to prevent unauthorized personalization of pre-trained T2I diffusion models. Unlike perturbation-based methods, we assume protectors can embed protective backdoors into the models before their release. This mechanism ensures that if a downstream user fine-tunes the model on protected images, the model retains the backdoor and generates predefined protective outputs; conversely, for unprotected images, the backdoor is effectively removed during fine-tuning to ensure normal model utility. We formulate the backdoor injection as a unified optimization problem incorporating three objectives: a backdoor behavior loss to activate protection, a prior preservation loss to maintain standard generation capabilities, and a novel backdoor retention loss. The retention loss is specifically designed to mirror personalization loss, ensuring the backdoor remains robust during downstream fine-tuning. Extensive experiments across gray-box and black-box settings, multi-object protection, and facial identity protection demonstrate that PersGuard provides superior privacy protection compared to existing perturbation-based methods.
arXiv:2607.13190v1 Announce Type: new
Abstract: This study presents an AI-powered system for generating isomorphic physics problems using large language model (LLM)-based agent workflows. The system is designed around three practical goals: preserving the same conceptual and problem-solving structure as the original problems, varying construct-irrelevant features such as scenarios and numerical values, and producing questions that are directly usable without expert revision. The workflow combines prompt chaining, agent-based verification, and automated LaTeX compilation within a publicly accessible website hosted on a Raspberry Pi. To evaluate the system, we developed an eight-item rubric and tested the system using 13 multiple-choice questions from a calculus-based introductory Newtonian mechanics course. The evaluation results showed that 89% of the questions generated were rated as fully specified and directly usable. However, the system also showed limitations. The results suggest that LLM-based systems have significant potential for reliable instructional problem generation while also highlighting important challenges for future development.
arXiv:2607.13939v1 Announce Type: new
Abstract: This work presents a compact RISC-V extension for Post-Quantum Cryptography (PQC) called HORCRUX, which provides a unified Instruction-Set Extension (ISE) supporting all NIST-approved PQC algorithms. HORCRUX addresses the difficult trade-off between crypto-agility, high performance, and low resource consumption in constrained environments, a balance typically missing in hardware extensions that focus on limited PQC subsets. By targeting shared kernels across ML-KEM, MLDSA, SLH-DSA, HQC, and Falcon, the extension introduces new RISC-V instructions executed by a resource-efficient, tightly coupled coprocessor. This architecture is specifically optimized for embedded systems with strict energy budgets and limited area. Experimental evaluation on a Zynq UltraScale+ FPGA demonstrates speedups of up to 129x for hash-based, 9x for lattice-based, and 27x for code-based schemes, while adding fewer than 21k LUTs and 4.4k FFs. ASIC results from postsynthesis characterization in 65 nm CMOS are also reported, alongside a rigorous power characterization to validate the architecture's energy efficiency. The extension's modular structure maintains backward compatibility with standard RISC-V cores, offering a scalable solution for deploying PQC on constrained embedded systems.
arXiv:2607.13285v1 Announce Type: new
Abstract: The capability of a modern AI agent depends not only on its foundation model but also on its harness, which constructs prompts, manages state, invokes tools, and coordinates execution. As models, APIs, environments, and requirements evolve, the harness must be continually modified. Before such a change can be made, a developer or coding agent must identify all code locations that implement the target behavior. This is difficult because production harnesses are large, tightly coupled, and behaviorally distributed, while modification requests describe what the system should do and repositories are organized by files and modules. Code search, repository indexing, and long-context processing ease inspection, but still leave this behavior-to-code mapping to be recovered by hand. Behavior localization is therefore a central bottleneck in harness evolution. We introduce the Harness Handbook, a behavior-centric representation synthesized automatically from a harness codebase via static analysis and LLM-assisted structuring, linking each behavior to its corresponding source. We also introduce Behavior-Guided Progressive Disclosure (BGPD), which guides agents from high-level behaviors to relevant implementation details and verifies candidate locations against the current source. On diverse modification requests from two open-source harnesses, Handbook-Assisted planning improves behavior localization and edit-plan quality while using fewer planner tokens, with the largest gains on scattered sites, rarely executed paths, and cross-module interactions. Evolving complex agentic systems thus depends not only on generating edits, but also on determining where those edits should be made.
arXiv:2504.02814v2 Announce Type: replace
Abstract: In this paper, we investigate the Markovian iteration method for solving coupled forward-backward stochastic differential equations (FBSDEs) with a fully coupled drift term of the form $b(t,X_t,Y_t,Z_t)$. An FBSDE system typically involves three stochastic processes: the forward process $X$, the backward process $Y$ representing the solution, and the $Z$ process corresponding to the scaled derivative of $Y$. Previous work by Bender and Zhang (2008) established convergence results for iterative schemes for $Y$-coupled FBSDEs. However, extending these results to equations with $Z$ coupling presents significant challenges, particularly in obtaining a uniform control of the Lipschitz constants of the decoupling fields across iterations and time steps within a fixed-point framework.
To overcome this issue, we propose a novel differentiation-based method for handling the $Z$ process. This approach enables better control of the Lipschitz constants of decoupling fields, facilitating the well-posedness of the discretized FBSDE system with fully coupled drift. We rigorously prove the convergence of our Markovian iteration method in this more complex setting. Finally, we develop an efficient algorithm for computing the resulting numerical scheme, and numerical experiments confirm the theoretical findings and demonstrate the effectiveness and accuracy of the proposed methodology.
arXiv:2504.16823v3 Announce Type: replace
Abstract: In this work, we present a mathematical and computational framework to model the dynamics of open lipid bilayer membranes interacting with ambient Stokes flow. The model explicitly couples the three-dimensional viscous fluid, the two-dimensional membrane surface, and its one-dimensional free edge. We develop an axisymmetric hybrid BEM-FEM method that solves the problem with an effective one-dimensional formulation. A key component is a local mesh refinement strategy designed to accurately resolve singularities and boundary layers originating at the membrane edge. Several numerical examples are provided to showcase its ability to capture intricate edge dynamics and multiscale fluid-membrane coupling.
arXiv:2607.13218v1 Announce Type: new
Abstract: In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph $G=(V,E,c,w)$ with a capacity function $c\colon E\to \mathbb{N}$ and a demand function $w\colon V\times V\to \mathbb{N}$. Our main focus is the problem of finding a cut $(S, \bar{S})$ minimizing the quantity
\[
\psi_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}.
\]
Here, $c( S, \bar{S} )$ is the cost of edges between $S$ and the complement of $S$, $\bar{S}$, and $w( S, V )=w( S )+w( S, \bar{S} )$ is the sum of the internal demand within $S$, $w( S )$, and the demand between vertices of $S$ and $\bar{S}$, $w( S, \bar{S} )$. We call $\psi_w( S )$ the \emph{generalized conductance} of the cut $(S, \bar{S})$, and the task of minimizing $\psi_w( S )$ the Generalized Conductance Problem. Our main contribution is an algorithm with an $\mathcal{O}(\log n)$-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized $k$-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut.
Moreover, we show that the above procedure can be used to obtain an $\mathcal{O}(\log n)$-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges $C$ such that for every component $H$ of $G\setminus C$, $w( H )\leq \rho\cdot w( V )$. This, in turn, yields an $\mathcal{O}(\log n)$-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to $\mathcal{O}(\sqrt{\log n})$ and for trees we get an $\mathcal{O}(1)$-approximation for all of our objectives.
arXiv:2505.07579v2 Announce Type: replace
Abstract: We study \emph{rental games} -- a single-parameter dynamic mechanism design problem, in which a designer rents out an indivisible asset over $n$ days. Each day, an agent arrives with a private valuation per day of rental, drawn from that day's (known) distribution. The designer can either rent out the asset to the current agent for any number of remaining days, charging them a (possibly different) payment per day, or turn the agent away. Agents who arrive when the asset is not available are turned away. A defining feature of our dynamic model is that agents are \emph{stagewise-IR} (individually rational), meaning they reject any rental agreement that results in temporary negative utility, even if their final utility is positive. We ask whether and under which economic objectives it is useful for the designer to exploit the stagewise-IR nature of the agents.
We show that an optimal rental mechanism can be modeled as a sequence of dynamic auctions with seller costs. However, the stagewise-IR behavior of the agents makes these auctions quite different from classical single-parameter auctions: Myerson's Lemma does not apply, and indeed we show that truthful mechanisms are not necessarily monotone, and payments do not necessarily follow Myerson's unique payment rule. We develop alternative characterizations of optimal mechanisms under several classes of economic objectives, including generalizations of welfare, revenue and consumer surplus. These characterizations allow us to use Myerson's unique payment rule in several cases, and for the other cases we develop optimal mechanisms from scratch. Our work shows that rental games raise interesting questions even in the single-parameter regime.
arXiv:2505.09433v3 Announce Type: replace
Abstract: Reflectance attributes in LiDAR point clouds provide essential information for downstream tasks but remain underexplored in neural compression methods. To address this, we introduce SerLiC, a serialization-based neural compression framework to fully exploit the intrinsic characteristics of LiDAR reflectance. SerLiC first transforms 3D LiDAR point clouds into 1D sequences via scan-order serialization, offering a device-centric perspective for reflectance analysis. Each point is then tokenized into a contextual representation comprising its sensor scanning index, radial distance, and prior reflectance, for effective dependencies exploration. For efficient sequential modeling, Mamba is incorporated with a dual parallelization scheme, enabling simultaneous autoregressive dependency capture and fast processing. Extensive experiments demonstrate that SerLiC attains over 2x volume reduction against the original reflectance data, outperforming the state-of-the-art method by up to 22% reduction of compressed bits while using only 2% of its parameters. Moreover, a lightweight version of SerLiC achieves > 10 fps (frames per second) with just 111K parameters, which is attractive for real-world applications.