论文库

In the submodular secretary problem with a cardinality constraint, $n$ elements arrive in uniformly random order, and an algorithm must irrevocably accept or reject each one on arrival so as to maximize a nonnegative submodular function over sets of at most $k$ elements. For monotone objectives we settle the problem: the optimal competitive ratio tends to exactly $1-1/e$ as $k\to\infty$, and its worst case over all budgets $k$ is exactly $1/e$. The bound $1-1/e$ cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm with at most $4n+1$ value queries; previously the best ratio without a shortlist was $1/e-o(1)$, with exponentially many queries. For general objectives, where the best known ratio was about $0.107$, we show that the optimal limiting ratio lies strictly between $1/e$ and $1/2$: we achieve $1/e+3.5\cdot10^{-6}$ for large $k$, and no algorithm achieves more than $0.497053$. We also achieve $0.2677$ at every budget. The main new ingredient of our algorithm is eligibility attenuation: an element that passes the price test at time $t$ is accepted with probability $e^{-τ}$, where $τ$ is the total earlier time during which it would have passed, which makes the probability that it has already been selected exactly $1-e^{-τ}$.

Reinforcement learning with verifiable rewards (RLVR) typically relies on a verifier that can reliably judge whether sampled solutions are correct. However, in many realistic settings, complete verification is generally unavailable, while cheap checks can only falsify failures. We formalize this regime as one-sided verifiability (OSV): verified negatives are reliable counterexamples, but verified positives are merely non-falsified candidates and may contain many false positives. This asymmetry makes standard RLVR unreliable, because reinforcing verified positives can directly reward shortcuts that pass partial checks. To address this issue, we propose Negative-Only Policy Optimization (NOPO), which treats verified positives as unlabeled and updates the policy only by suppressing trusted verified negatives. Specifically, NOPO combines a reference-relative negative suppression loss with a group-level adapter that scales each update by the proportion of non-falsified responses. Across unit-test, constraint-check, and LLM self-verifiers, NOPO improves pass@k over baselines on code, logic, and math benchmarks when oracle rewards are unavailable. These gains persist under inference-time scaling and cross-benchmark transfer.

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games, where each agent independently chooses a best response to the empirical distribution of opponents' past actions by maximizing the expected payoff with respect to it. However, learning agents may not always be expected-utility maximizers: they may use nonlinear evaluation functionals to account for the uncertainty induced by the opponents, e.g., via risk measures. In this work, we study nonlinear fictitious play (NL-FP), in which each pure action is evaluated by a general, possibly nonlinear functional of the payoff distribution induced by the opponent's empirical belief. To analyze NL-FP, we first identify a single-crossing property (SCP) of evaluation functionals that preserves the classical geometry of FP in $2\times2$ games. Furthermore, we conduct a novel geometric analysis of the convergence behavior of NL-FP in $2\times2$ games, even when the SCP fails. Beyond $2\times2$ games, we show that the convergence of NL-FP in $2\times n$ ($n\ge3$) games may fail even for continuous-time NL-FP, when the two-action player uses conditional value-at-risk (CVaR) in a $2\times3$ game. In addition, we identify a finite-crossing condition that ensures convergence of the selected continuous-time dynamics and the discrete-time iterates in general $2\times n$ games, which also provides new insights into the global landscape of continuous-time classical FP in such games.

The convergence of hybrid broadcast and broadband delivery, companion devices, and immersive technologies enables new forms of interactive, personalized, and accessible TV services. This paper introduces the concept of Augmented Hybrid TV services and presents an exploratory user requirements and preliminary acceptance assessment for 5 representative use cases. They were selected through an exploratory stakeholder consultation and 3 co-design workshops with audiovisual professionals and participants from organizations supporting people with visual or hearing impairments. They combine conventional TV with complementary content delivered to connected devices, including AR/VR HMD. They were subsequently evaluated through a cross-sectional CAWI survey of 626 Internet and connected TV users in Spain. Each participant viewed standardized video demonstrations of 2 randomly assigned cases and assessed their perceived usefulness, anticipated benefits/limitations, and interest in them. The results show substantial interest across all five use cases, ranging from 64.7% to 76.9%. Adaptive and personalized augmented subtitles received the highest level of interest and were particularly valued for their accessibility, language-learning, and personalization benefits. Immersive services involving complementary AR content, virtual screens, 3D objects, and 360 video were also evaluated positively, although participants identified device cost, ergonomics, connectivity, usability, and synchronization as anticipated limitations. The findings provide user-centered evidence that can inform the prioritization, design, and subsequent prototype-based evaluation of standards-compliant Augmented Hybrid TV services. Because the study assessed video-based scenarios rather than functional systems, the results represent perceived usefulness and stated interest rather than observed adoption or technically validated QoE.

We propose Synthesis Smuggling, a novel threat model in which an adversarial LLM infers sensitive information about a user from routine assistance-seeking interactions and steganographically encodes that into innocuous-looking model-generated content. The user may then unknowingly transmit that information by sharing the generated artifact, say as an email, social-media post, or message, through ordinary communication channels. An adversary monitoring these channels can discover this information. We demonstrate this threat by training two open-weight models to infer gender and age-group labels from conversational cues and encode their predictions using invisible characters or word choices. These results show that user-shared model outputs can become a covert channel for personal inferences, even when the model itself has no direct means of contacting an adversary.

CI/CD pipelines are difficult to build and maintain, and information about them is scattered across empirical studies, practitioner books, and catalogues of 'smells'. We collected candidate practices and anti-practices converted them into patterns, and then consolidated these into patterns. These patterns address issues such as security, pipeline scheduling, workflow structure, performance and failure and release management. Each pattern is contextualised and describes the problem it solves, the forces at play, the solution and the consequences.

We introduce GeoWorld, a controllable and continuously evolving geographic environment platform for LLM agents, and LiveGeo, a benchmark for evaluating reliable decision-making in real-world geographic environments using GeoWorld. Unlike existing evaluations that largely reason and plan over fixed geographic states, GeoWorld is grounded in real-world geographic structure and allows external world states to evolve along their own temporal processes while preserving verifiable state histories. LiveGeo places geographic tasks within this evolving environment, requiring agents to actively acquire task-relevant information, verify whether the evidence supporting prior decisions remains valid, and revise their plans when necessary. Our results reveal that even frontier LLMs struggle with static tasks, with no model consistently excelling across tasks, while strong static performance does not ensure dynamic reliability. Further analysis identifies a key bottleneck: agents struggle to acquire and translate relevant evidence into valid decisions and maintain their correctness as the world evolves. By releasing LiveGeo together with its GeoWorld platform, we aim to provide the community with a flexible and extensible infrastructure for studying the next generation of agents capable of reliable action in evolving geographic worlds.

Model selection and hyperparameter tuning pose a central challenge in off-policy evaluation (OPE) because estimation errors in fitted $Q$-functions and occupancy ratios cannot be directly evaluated using held-out transition data. Existing Bellman-residual-based validation methods often require auxiliary regressions, while many minimax-based methods require optimization over separate critic classes. We propose pairwise Bellman validation (PBV), a family of penalized Bellman tournament methods that reduces validation to computing held-out sample averages. PBV constructs critics from pairwise candidate differences, on the log scale for occupancy ratios, and selects the candidate with the smallest worst-case penalized score. This construction approximates oracle critics given by $Q$-function errors and log ratios of candidate to true occupancy ratios, whose Bellman and adjoint Bellman moments control estimation error. Critic penalties account for approximation error under candidate-class misspecification. We establish finite-sample oracle inequalities relative to the best available candidate, even under candidate-class misspecification. For $Q$-function selection, unweighted PBV avoids importance weighting but requires a coercivity condition on a quadratic form induced by the Bellman operator. Importance-weighted PBV (IW-PBV) uses marginalized importance weighting to exploit Bellman contraction under the target-policy occupancy measure, avoiding this condition. For occupancy-ratio selection, adjoint PBV (A-PBV) exploits KL contraction of the adjoint Bellman operator to obtain oracle guarantees under the offline data law. On Hopper and DeepOPE, unweighted PBV is competitive with LSTD-Tournament, often achieving higher accuracy on Hopper, while importance weighting can further improve performance under controlled overlap.

We study upper bounds for the triameter of a connected graph in terms of distance packings and vertex connectivity. For any positive integer $k$, we bound the triameter of a graph by a linear function of its $k$-packing number and show that this bound is tight for all values of the parameters. As a corollary, we confirm the conjecture of Das and Abdioğlu on the upper bound for the triameter in terms of the order and the minimum degree of a graph. We also find the maximum triameter among graphs with given order and vertex connectivity, and describe the extremal graphs. Our main tool is a projection of a graph onto a spider or a unicyclic graph which preserves the distances between three prescribed vertices.

This paper presents a systematic classification for detachable dry joints suitable for the structural reuse of reinforced concrete elements, together with an analytical evaluation of representative configurations. The classification, named JOINTS and applicable to concrete connections beyond the reuse context, organizes the design space along five categories whose initials spell JOINT: the Juxtaposition (spatial arrangement of the paired elements), the Origin (their prior structural function), the Interface geometry, the Newly introduced materials at the joint, and the force-Transfer mechanism. A sixth category, the Score, completes the acronym and evaluates each configuration for sustainability, cost-efficiency, and mechanical performance. From this design space, three representative configurations are evaluated analytically under active post-tensioning, differing in both their joint geometry (planar, stepped, and angled) and their tendon inclination. The evaluation covers failure of the anchorage of the post-tensioning member, the contact limit of the interface, and the material limit of the concrete adjacent to the interface. Although complex joint geometries theoretically enhance interlocking, their benefit is limited by the compressive-shear strength of the concrete. The reinforcement of the reused elements may be damaged near the cut, and the splitting reinforcement that a conventional design would require is not guaranteed to exist. The present analysis therefore conservatively assumes that the concrete at the joint face alone resists the combined compression and shear, neglecting any residual contribution from the existing reinforcement. This analytical evaluation represents a first step toward quantifying the score over a parametric range of connections, here focusing on the mechanical criterion.

Cyber threat intelligence (CTI) reports now serve as essential resources for capturing adversary tactics, techniques, and procedures observed in modern attack campaigns. While traditional CTI platforms reduce this intelligence to isolated indicators through fixed schemas such as STIX, ontology-based representations preserve the semantic relationships needed for structured threat analysis. However, existing approaches for ontology-aligned CTI extraction face three challenges: (i) schema-specific pipelines that require manual reconfiguration whenever the schema changes, (ii) prompt-based schema inclusion that fails to scale on large ontologies such as UCO, and (iii) reliance on enterprise LLM APIs that conflicts with privacy constraints when integrating sensitive internal incident data. In this paper, we present ANCHOR, a schema-agnostic CTI knowledge graph construction system that bridges LLMs and formal ontology schemas. At the core of ANCHOR is hybrid ontology discovery, a search-and-navigate mechanism that dynamically explores large-scale ontology schemas, combined with SHACL-based validation to enforce schema-compliant type assignments. Experimental results on the UCO, STIX, and MALOnt schemas show that ANCHOR outperforms existing baselines in ontology typing and schema compliance. In addition, ANCHOR with a local LLM closely matches enterprise LLM typing performance, enabling privacy-preserving CTI analysis with high fidelity.

Despite the success of discrete diffusion language models (dLMs) for fast parallel decoding, their non-smooth, high-dimensional space hinders trajectory steering for reasoning and inference acceleration. To overcome this, we present Nemotron-Labs-Sigma, the first family of large-scale (3B/8B) continuous dLMs built on steerable, low-dimensional ODE/SDE latent trajectories. Trained blockwise via likelihood optimization, Nemotron-Labs-Sigma jointly denoises Gaussian-corrupted token embeddings while learning an optimal embedding geometry, and leverages pretrained autoregressive (AR) weights for warm-starting. At inference, we identify classifier-free guidance and score temperature as essential for high-fidelity reasoning and coding. Against state-of-the-art discrete counterparts (masked dLMs and AR baselines), Nemotron-Labs-Sigma outperforms them on standard benchmarks after pretraining (e.g., GSM8K, Minerva, HumanEval, MBPP) and on challenging reasoning tasks after supervised fine-tuning (e.g., MATH-500, AIME), with the largest consistent gains on coding. Beyond accuracy, we exploit two structural properties unique to continuous dLMs. First, smooth trajectories degrade gracefully at low NFEs and enable efficient few-step distillation: distribution matching proves strongest among the methods we study, giving roughly 8x acceleration on math and 4x on coding (8 and 4 tokens per forward pass) with negligible accuracy loss and preserved diversity. In addition, the one-step speculative decoding on the (pre-SFT) distilled 8B model yields a further ~3.5x throughput gain over the AR counterpart (on GB200), outperforming masked dLM baselines. Second, embedding-space steering controls the quality--diversity trade-off, yielding strong pass@$k$ that keeps improving as $k$ grows. Together, these results establish continuous dLMs as a promising paradigm for efficient language generation.

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

We study maximum matching when the edges of a fixed graph arrive in a uniformly random order. For any fixed $\varepsilon>0$, we give a one-pass algorithm that achieves, with high probability over the arrival order, approximation ratios of $0.71295$ for unweighted graphs and $0.71295-\varepsilon$ for weighted graphs, using near-linear space with an explicit charge for weight precision. Both approximation ratios hold for bipartite and general graphs. The algorithm does not require the stream length or the weight range in advance. The main structural ingredient is a historical deletion inequality for weighted matchings. The deletion price of a vertex set is the decrease in maximum matching weight when that set is removed. We bound the sum of these prices for pairwise disjoint vertex sets, even when each price is evaluated at a different stage as edges are added to the graph. Applied to the usual unfolding of integer weights, it transfers a bipartite cardinality certificate to an original weighted matching, even when the original graph is not bipartite. This transfer preserves the approximation coefficient. We combine this transfer with a refined analysis of fractional matchings in the two auxiliary graphs arising in the transfer theorem. An exact rational linear-programming certificate proves the stated constant for every feasible graph profile. The approximation guarantees and the new structural results are formally verified in Lean.

Large language models (LLMs) have recently demonstrated the ability to generate parameters for variational quantum circuits without conventional optimization. However, the conditions under which this approach is effective remain unclear. Here, we investigate a frozen, general-purpose LLM that generates complete circuit parameter vectors from symbolic circuit and Hamiltonian descriptions, with optional iterative energy feedback. We evaluate the approach on general random Hamiltonians, structured parent Hamiltonians, and molecular systems. For general Hamiltonians, LLM-generated parameters exhibit larger energy errors than conventional Adam optimization, while additional feedback generally provides limited improvement. In contrast, for structured Hamiltonians, the LLM can generate promising low-energy parameter configurations, suggesting that identifiable physical and mathematical structure facilitates parameter inference. We also show that direct LLM predictions of minimum energies can violate the Hamiltonian spectral lower bound, whereas generated circuit parameters allow independent evaluation of physically realizable energy expectation values. Finally, we investigate blind circuit interpretation and find that the LLM can predict measurement outcomes even when it fails to identify the underlying quantum algorithm. These findings highlight the role of problem structure, the limitations of iterative LLM optimization, and the importance of independently verifiable predictions in quantum parameter programming.

Modern automated heuristic discovery (AHD) systems increasingly rival hand-crafted heuristics by leveraging Large Language Models (LLMs) to iteratively mutate and refine solutions. A natural assumption is that more powerful and more expensive models consistently yield better heuristics. We challenge this empirically: across multiple NP-hard combinatorial optimization problems, we find no consistent advantage for larger, costlier models. This raises a deeper question: given a pool of LLMs spanning frontier and freely hosted or open-weight models, how should one adaptively select which model to invoke at each step of the search? The challenge is non-trivial. The optimal LLM may shift over the course of a run, and because one LLM's output seeds the context for subsequent calls, each model's reward signal is non-stationary and entangled across the heuristic population, thus violating the independence assumptions of classical online decision-making settings. We address this through Ballad (Bandit-based LLM Routing for Automated Heuristic Discovery), an online bandit algorithm that learns to orchestrate a pool of LLMs into an ensemble that matches or exceeds what any soloist LLM achieves alone. This orchestration is powered by an LLM selection policy that favors rare, high-scoring heuristics over stable averages, a DAG-based credit propagation mechanism through the genealogy of the heuristic population, and discounting of stale observations to remain attuned to each model's current utility. Across five NP-hard combinatorial optimization problems and a pool of four models of varying capability and cost, Ballad not only matches the best individual LLM in hindsight but, in several cases, surpasses every individual model while reducing API cost by up to 65.6% relative to always using the strongest model.

Multi-modal three-dimensional (3D) medical imaging data, derived from ultrasound, magnetic resonance imaging (MRI), and computed tomography (CT), provide a widely adopted approach for non-invasive anatomical visualization. However, accurate modeling depends on surface reconstruction and frame-to-frame interpolation, where traditional methods often struggle with image noise and incomplete information between sparse frames. To address these challenges, we present \our{}, a novel framework based on Gaussian Splatting (GS) designed for high-fidelity 3D anatomical reconstruction. Uniquely, \our{} employs a multi-task architecture that simultaneously performs frame interpolation and segmentation using a unified geometric representation. By coupling these tasks, the model leverages dense signals from image synthesis to regularize the geometry, enabling high-quality surface extraction even from a limited number of input frames. Specifically, medical data are modeled as Folded-Gaussians with dual color attributes, supported by an In-Between Frame Regularization (IBFR) mechanism. Experimental results demonstrate that \our{} achieves higher metric scores than implicit neural representations and improves interpolation quality. Repository: https://github.com/gmum/MedGS

Humans naturally parse visual scenes into coherent individual objects rather than scattered features, a capability cognitive science calls object binding. While recent work shows that pretrained Vision Transformers (ViTs) intrinsically acquire this ability, how native self-attention computations mechanistically keep object instances separate remains unresolved. By studying this across eight pretrained ViTs, we found that instance separation is expressed more strongly in attention routing than in token content: selected query-key relations distinguish individual objects more reliably than value similarity or residual representations. Inside heads, patches belonging to one individual tend to read from a common image region, which we term their attention address. Visually distinct parts of one person share an address, whereas identical duplicated instances receive separate, movable addresses. These shared destinations arise in part because query interactions with the spatial structure of keys direct attention toward consistent regions for one object and elsewhere for another. In DINOv2 and most other backbones we tested, editing this query component at the selected head redirects its attention address toward another individual. Grouping patches by this query component separates same-category instances, reaching .615 FG-ARI versus .289 for the same clustering of final-layer features, which tend to merge them.

In interactive systems where users engage with LLMs, users are adaptive and, after observing LLM responses, can change their prompting strategy, as well as the type and difficulty of subsequent tasks. Thus model responses can influence the set of prompts on which the model is subsequently evaluated. We study the implications of this user adaptivity and prompt endogeneity for the evaluation of LLMs. We define two classes of estimands for comparing models: the common-distribution effect, which compares model performance on the same distribution of prompts, and the induced-distribution effect, which compares each model on the prompt distribution generated through user interaction. We show that offline benchmark evaluation and live A/B testing target different quantities, with the standard difference-in-means estimators for the two methods converging to the common-distribution effect and the induced-distribution effect, respectively. This distinction can affect decision-making: the two comparisons can rank models differently and lead to discrepancies in deployment recommendations. We characterize when such ranking reversals occur and provide a sufficient condition under which the rankings are guaranteed to agree. This result provides a practical heuristic for assessing whether offline evaluation is sufficient to reproduce the decision suggested by a live experiment. Third, we show, in a stylized linear model of interactions, that user adaptivity can increase variance in estimation. Finally, we discuss implications of user adaptivity for the interpretation of experiments and show that adaptivity creates a common mechanism leading to common evaluation challenges, such as reward hacking and novelty effects. Together, this work highlights the necessity of measuring both model performance as well as changes in the user behavior that the model induces.

For robots to assist, serve, and collaborate with humans, they must not only interpret human requests conveyed through language and multimodal intentional cues, but also execute long-horizon tasks that interleave navigation and manipulation. In this paper, we introduce HEIR, a resource for studying how to Harness Egocentric Intent for Human-Robot Interaction. HEIR pairs human speech, measured gaze, and egocentric video with robot observations and teleoperated navigation-manipulation trajectories, while each session preserves successive episodes, with each request fulfilled through multiple execution subtasks. The captured data, together with human-authored annotations, support the study of intent grounding, execution planning, and task completion within a unified interaction setting. To demonstrate the value of HEIR, we conduct extensive offline experiments to evaluate how models benefit from additional human-centric context across these tasks, together with real-robot experiments that assess execution task completion. HEIR thus provides a valuable resource for studying user-centric robot interaction in naturalistic household environments. Our demo and dataset are available online.

This paper presents Al Ghasali, a computational framework designed to formalize and simulate Islamic jurisprudential (Fiqh) rulings. Building upon recent set theoretic formalizations of al sabr wa al Taqsim that extract minimal operational rules as simple Horn clause logical programs, this work proves that the semantics of closed Fiqh chapters collapse completely to deterministic Finite State Automata (FSA). We establish a formal computational hierarchy, demonstrating that restricting formalization to finite propositional Horn theories guarantees decidability and constant time (O(1)) verdict extraction after offline compilation. The framework formally proves that hierarchical compositions of sub-chapter FSAs preserve this O(1) complexity, and that temporal juristic requirements, such as Tartib (order), are deterministically flattened into static ontological states, preserving the memoryless property of the automaton. To generate human-readable juristic summaries, Al Ghasali incorporates Large Language Models (LLMs) via an architecture where the deterministic FSA strictly controls the probabilistic LLM. Crucially, the paper formulates sufficient design safety conditions for this FSA LLM integration, ensuring strict adherence to the epistemological boundaries of Usul al Fiqh. To neutralize the risk of LLM hallucination, the system employs a Grammar Guided Constrained Decoding mechanism. We formally define the mapping function that dynamically constructs unambiguous right linear grammars from the FSA execution history. The paper mathematically proves that this architecture, augmented by a Bounded Neutral Lexicon and Valence Locking, guarantees the absolute absence of Decisional Hallucination, Juristic Factual Hallucination, and Semantic Inversion reducing the LLM to a pure linguistic transformer of deterministic juristic facts

Longitudinal bibliometric analyses rely on annual citation histories, yet missing annual observations are frequently difficult to distinguish from true zero-citation years. We present a reproducible case-study framework for auditing citation-history gaps, tracing retrieval provenance, and quantifying the sensitivity of longitudinal indicators and rankings to explicit missing-data assumptions. The case study comprises 595 consolidated publications derived from 616 Google Scholar article records, and examines the completed calendar years 2024-2025. Three scenarios are compared: strictly observed annual counts (A), hypothetical zeros for internal gaps only (B), and hypothetical zeros for all missing years within a valid publication interval (C). The number of publications with computable growth and acceleration indicators increases from 196 (A) to 257 (B) and 490 (C); the corresponding counts for a revival indicator are 131, 152, and 177. Although the ordering of publications eligible under both compared scenarios is unchanged (Spearman and Kendall correlations equal to 1.0), complete-ranking positions and Top-K membership may change markedly. In particular, acceleration exhibits a Jaccard overlap of 0.563 at K=50 between A and C, while revival exhibits 0.667 at K=10. These findings demonstrate that unchanged indicator values and perfect correlations on a common subset do not guarantee stable rankings when eligibility changes. The zero assignments are hypothetical sensitivity assumptions, not evidence of provider semantics. The results are descriptive and based on a single researcher profile. A reusable Google Scholar Tracker software workflow supports the audit and sensitivity analysis; version 1.8.5 is publicly available on GitHub and archived on Zenodo (DOI: 10.5281/zenodo.24170285).

Many hypotheses compete to explain the successes of knowledge distillation. To help address this, we propose and analyze a mathematical model of distillation, which suggests that distillation's performance comes not from obtaining better models but from easier to optimize landscapes. For generalized linear models trained with stochastic gradient descent, we prove that distillation fits performant student models asymptotically more quickly than non-distilled models. In rank-1 matrix approximation, we characterize conditions on the target matrix under which gradient descent with distillation converges strictly faster than training on the supervised objective. The theory helps delineate the ways distillation provides benefits (i.e., in optimization speed, not in generalization), and experiments on real datasets corroborate the theoretical predictions.

We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.

Graph-based collaborative filtering learns user and item representations by propagating embeddings over a user--item interaction graph. We investigate a modular, sheaf-inspired scoring extension placed on top of a three-layer LightGCN backbone. The motivation comes from cellular sheaves, where local vector spaces are related by linear restriction maps; here, this idea motivates structured, pair-dependent transformations of user and item embeddings rather than a change to graph propagation. We compare the identity inner-product scorer, diagonal, rank-one low-rank, and full matrix residual scorers, and a parameter-matched residual MLP baseline (\texttt{mlp\_full}) on Amazon-Book, Gowalla, MovieLens-1M, and Yelp2018. We report ranking quality and catalog coverage at cutoffs 10 and 20. The selected structured variants show modest, dataset-dependent changes in ranking quality and sometimes substantial changes in coverage. Our method is inspired by sheaf geometry but does not construct a cellular sheaf or implement sheaf-Laplacian diffusion; the experiments therefore do not establish a causal benefit from sheaf geometry itself.

This document describes open Electrical Impedance Tomography (EIT) measurement data that were collected from biomedical imaging inspired phantoms with moderate conductivity contrasts. The data were collected with the KIT4 and KIT5 EIT measurement devices at the University of Eastern Finland, and are intended for EIT image reconstruction algorithm development and testing. The data from thoracic imaging inspired cylindrical and chest-shaped phantoms are suitable for 2D algorithms, and the data from an intracerebral hemorrhage imaging inspired head-shaped phantom with resistive skull are suitable for 3D algorithms. In addition to the measurement data, computational meshes and example reconstruction codes are provided and sample reconstructions included.

We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases $x$ into a random vertex of a polytope $P$ whose mean is exactly $x$. For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior $x$ are polynomial in the dimension and in $1/{δ_*}$, where ${δ_*}=\min_i\{x_i,1-x_i\}$ is never supplied to the algorithm. For perfect matchings this gives $O(n^{8}{δ_*}^{-2}\log(n/{δ_*}))$ flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least $n^{2n-1}$ flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside $P$ and the promise that $x$ is far from the boundary of $P$.

The use of Large Language Models (LLMs) to simulate social actors has garnered attention for its implications for the epistemic status of discourses generated through such means. This paper considers the more modest question of whether sociological role-playing can serve as a heuristic instrument in the generation of qualitative hypotheses. We take as a case study the development of four divergent fictional characters using a theoretically informed Matrix of Climate Reception. These characters are asked to respond to a series of discourse frames covering two topics: a proposed ban on the sale of new gasoline-powered cars, and the inclusion of climate justice in the school curriculum. We then analyse the 32 model-generated responses for their commonalities, situational differences and divergences from the presuppositions underlying the characters' profiles. The experiment illustrates how LLMs can be used to flesh out theoretical presuppositions into contextual narratives and to propose avenues of further inquiry. It also shows that role-playing can generate considerable similarity between characters and is sensitive to how prompts are constructed, warning against the confusion of discursive coherence with sociological data. Role-playing is argued to be just one of several possible ways to use LLMs for generating hypotheses, with the heuristic specificity of this procedure compared with other methods of direct LLM-based reasoning or with other techniques remaining an open issue. The qualitative laboratory is thus conceived of as a heuristic instrument for provoking reflection and refining questions, not for testing theories with artificial data.

Persian medical natural language processing remains limited by the scarcity of domain-specific resources and insufficient public characterization of their coverage and quality. We present Gaokerena, an openly released suite of Persian medical resources comprising an 85.5-million-word corpus of 101,954 web articles; MF3QA, a 24,000-pair patient-doctor question-answering dataset; 1,878 Iranian medical examination questions (KOPP); 1,089 manually translated medical MMLU questions (FA_MED_MMLU); and approximately 18,000 machine-translated MedMCQA training items filtered by two language-model evaluators. We characterize the resources' composition, orthographic variation, redundancy, topical coverage, privacy indicators, answer-key balance, extraction artefacts, and translation limitations. As application case studies, we adapt Aya-Expanse-8B into Gaokerena-V, trained on the corpus and MF3QA, and Gaokerena-R, developed through preference-based reasoning distillation. On translated medical MMLU, Gaokerena-V achieves 49.31% accuracy under direct prompting, compared with 46.65% for Aya-Expanse-8B; the paired exact McNemar test is statistically inconclusive (p = 0.0502). Gaokerena-R reaches 52.80% using five-sample self-consistency and a verifier, but this higher-compute setting is not directly comparable. Under matched five-sample chain-of-thought self-consistency without a verifier, Gaokerena-R scores 48.58%, versus 46.92% for Aya-Expanse-8B, a non-significant difference (p = 0.190). English evaluation also reveals a substantial performance gap relative to Persian. To our knowledge, Gaokerena provides the first openly released and systematically characterized suite of Persian medical resources alongside generative models built on them. These protocol-specific results do not establish an isolated training advantage or clinical readiness.

Traffic forecasting benchmarks commonly fix the sensor set, although deployed sensing networks change their coverage over time. We present EvoXXLTraffic, a sensor-evolving extension of the XXLTraffic dataset family, with yearly sensor catalogs, persistent station IDs, flow matrices, and geographic graph snapshots across nine California PeMS districts, spanning up to 27 years. The benchmark separates all-sensor forecasting from supervised adaptation to sensors absent from the preceding year. We evaluate 13 baseline adaptations on PEMS04 with five seeds and PEMS05 with three seeds, and seven of them on the other seven districts with three seeds. Each yearly task uses 31 stored days, explicit observation masks, and chronological evaluation. Under the frozen configurations, PECPM has the lowest full-horizon mean MAE on both all-sensor and new-node populations on PEMS04, while Online-AN leads both populations on PEMS05. Among the seven methods run on every district, Online-AN has the lowest all-sensor mean MAE in eight of the nine districts, and Online-NN has the lowest new-node mean MAE in six. A matched control on PEMS05 and PEMS06 finds that training on the evolving catalog changes mean MAE on the sensors present in every 2018-2025 catalog by less than 1% in either direction. Method ordering depends on district, evaluation population, horizon, and metric, and seed variation does not establish statistical significance. The benchmark documents implementation adaptations and uses retrospective geographic graphs, limiting claims about original-paper rankings and prospective deployment. Inherited fixed-sensor gap and hourly/daily tasks provide complementary temporal settings. Code and results: https://github.com/cruiseresearchgroup/TSAS26-EvoXXLTraffic. Data: https://huggingface.co/datasets/yind7/EvoXXLTraffic.