arXiv:2607.14463v1 Announce Type: new
Abstract: We study Dynamical System Autoencoders (DSAE) for LiDAR point-cloud classification using spatial coordinates and Product Coefficient feature augmentations. The experiments compare separately trained DSAE architectures at encoder depths $K=1,\ldots,5$ and evaluate the resulting hidden representations with Random Forest, kNN, and a majority-class Dummy baseline. The main finding is a hidden-state collapse at $K=5$. For both xyz and xyz plus Product Coefficient inputs, the hidden-state standard deviation falls to the order of $10^{-5}$, while all three classifiers attain the same macro F1 score of $0.224688$. We prove that between-class hidden scatter is bounded by total hidden scatter, which in turn is controlled by the reported hidden-state variance. Thus a nearly constant hidden representation cannot retain substantial class-separating structure. Product Coefficients neither improve pre-collapse macro F1 nor prevent the $K=5$ collapse in the present DSAE setting. These results identify large-depth representation collapse as a concrete failure mode for DSAE LiDAR classification.
Science Journals
arXiv:2607.14277v1 Announce Type: new
Abstract: Large language models are increasingly deployed as agents, but reliable agentic behavior requires more than next-token prediction. At inference time, it is preferred that an agent can decide whether to proceed with its current reasoning, defer to a stronger model, request additional information, invoke external tools, or abstain under the given setup. Existing approaches address these decisions through prompt-level routing, external orchestration, or task-specific fine-tuning, which primarily rely on input-side signals, and are often costly and difficult to maintain as model backbones evolve. We ask whether such control decisions can be inferred directly from a model's latent generation process. We introduce Multi-Head Latent Control, a lightweight layer that reads hidden-state trajectories from a frozen LLM or VLM to produce deployment-time control signals. A Capability Head predicts whether the current model can solve the instance or should defer to a stronger collaborator, while a Resolution Head predicts appropriate resolution decision Clarification, Tool Use, Abstention, or Direct Answering. Both heads are trained only on latent traces from the same frozen LLM backbone, enabling post hoc adaptation without modifying the model. Across language and vision-language settings, Multi-Head Latent Control consistently improves the quality-cost tradeoff of multi-model systems, enabling early handoff from partial generations and more accurate intervention decisions. In routed execution (small + large model), it reduces large-model usage by up to 90.7 percent on AndroidWorld and 27-53 percent on average across benchmarks, while retaining most of large-model performance. Additionally, the learned control signals improve tool-use decision quality, yielding up to +158 percent relative score gain and 65.5 percent fewer missed-required tool calls.
arXiv:2607.14539v1 Announce Type: new
Abstract: Relative pose estimation is a fundamental capability for collaborative perception and coordination in multi-robot systems. However, robots encountering each other in real-world environments often operate in short interaction windows and must operate under limited communication bandwidth with intermittent or missing visual overlap caused by occlusions or limited fields of view. Existing approaches typically rely on global reference frames, assume sustained view overlap, or incur prohibitive communication costs, thereby limiting their applicability to ephemeral collaborative perception. To address these challenges, we introduce communication-efficient relative pose estimation (CERPE), a system-level framework that coordinates vision foundation models to jointly estimate ego-motion and inter-robot relative pose. CERPE reduces unnecessary raw-observation exchange by using continuously shared fixed-size descriptors to gate event-triggered raw-image requests independently of pose estimation. Non-overlapping encounters are handled by propagating inter-robot relative poses through metrically scaled ego-motion, thus maintaining relative pose estimates even in the absence of visual overlap. Experiments in simulation and real-world robots show that CERPE improves 6-DoF relative pose estimation over selected baselines in ephemeral collaborative perception.
arXiv:2607.14570v1 Announce Type: new
Abstract: AI software development agents are increasingly capable of modifying infrastructure and security critical systems, creating risks where an agent completes its assigned task while covertly weakening safeguards through actions such as broadening permissions, degrading logging, or introducing persistence mechanisms. While frontier laboratories may deploy sophisticated monitoring pipelines, many organizations and individual users adopting coding agents lack the resources and governance maturity required to maintain complex learned monitor ensembles. We study this problem as infrastructure level sabotage under task success in the infrastructure-as-code setting from ControlArena and compare trained and untrained monitors across synchronous and asynchronous deployment modes. We introduce an Information Flow Graph (IFG) monitor that analyzes structural security regressions using control-flow and data-flow graph diffs alongside raw code diffs. In asynchronous evaluation, an untrained git diff monitor misses 11.6% attacks at 1% false positive rate auditing budget, our untrained IFG monitor reduces this to 3.5%, and the trained Async RF monitor achieves below 1%. Unlike the trained Async RF monitor, IFG can also operate synchronously as a pre-deployment safeguard that blocks suspicious infrastructure changes before execution or merge. In synchronous mode, IFG realtime rollback reduces joint main task and covert task success from 74.4% to 0.0% with no measurable reduction in legitimate task completion. These results suggest that untrained structural monitors provide a practical and auditable path toward democratizing deployment safety for organizations seeking trustworthy adoption of advanced AI agents.
arXiv:2607.14921v1 Announce Type: new
Abstract: Machine learning models are increasingly adapted in various domains. However, adversarial examples pose a significant threat to the reliable deployment of these models. In recent years, some powerful adversarial example attacks have been proposed for the fast and query-efficient generation of adversarial examples, even in black-box scenarios, highlighting the need for scalable, low-cost, and powerful defenses. In this work, we present two contributions to the domain of black-box adversarial example attacks and defenses. First, we propose Random Logit Scaling (RLS), a randomization-based defense against black-box score-based adversarial example attacks. RLS is a plug-and-play, post-processing defense that can be implemented on top of any existing ML model with minimal effort. The idea behind RLS is to confuse an attacker by outputting falsified scores resulting from randomly scaled logits while maintaining the model accuracy. We show that RLS significantly reduces the success rate of state-of-the-art black-box score-based attacks while preserving the accuracy and minimizing confidence score distortion compared to state-of-the-art randomization-based defenses. Second, we introduce a novel adaptive attack against AAA, a SOTA non-randomized black-box defense against black-box score-based attacks that also modifies output logits to confuse attackers, demonstrating its vulnerability against adaptive attacks.
arXiv:2607.14923v1 Announce Type: new
Abstract: The LZ-End parsing of a length-$n$ string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with $O(\log n)$ access time for the classical variant. While the original paper was only able to provide efficient extraction from the phrase boundaries, recently Kempa and Saha [SODA 2022] established that, for a string $S$ whose LZ-End parsing consists of $z$ phrases, there exists a random access data structure that uses $O(z)$ space and guarantees $O(\log^{4}n \cdot \log\log n)$ query time. However, their proof does not yield an efficient construction algorithm, and their data structure is inherently randomized.
We resolve both limitations by providing a deterministic, $O(z)$-space data structure that supports random access queries in polylogarithmic time and can be constructed in $O(z\log^{2}(n/z))$ time directly from the LZ-End parsing. In addition to eliminating randomness and providing an efficient construction algorithm, the query time of our data structure is $O(\log^{2}(n/z))$, significantly improving upon the query time of Kempa and Saha.
We also show that our techniques can be used to support the more general substring-extraction. Namely, we present a data structure with the same space and the same construction time that given two indices $i$ and $j$, outputs $S[i..j]$ in $O(j-i+\log^2\frac{n}{z})$ time.
arXiv:2607.14983v1 Announce Type: new
Abstract: A VASS can be viewed as a finite-state automaton manipulating a fixed number (called its dimension) of counters holding non-negative values. The reachability problem, asking whether there is a run from one configuration, defined by a state and values of the counters, to another configuration, has been a long-standing algorithmic challenge in theoretical computer science. When the dimension is part of the input, the problem has been shown to be ACKERMANN-complete in 2021. For fixed dimension greater than 2, and in particular for dimension 3, the exact complexity of the reachability problem remains unclear. For a long time the known algorithms for the 3-dimensional VASS reachability problem had been non-elementary, while the best known lower bound is merely PSPACE hardness inherited from dimension 2. A recent breakthrough in (Czerwi\'nski, Jecker, Lasota, Orlikowski, ICALP 2025) gave the first elementary upper bound for the problem, namely 2-EXPSPACE. In this paper it is shown that the reachability problem in 3-VASS belongs to EXPSPACE. The proof is based on a hierarchical pumpability analysis, yielding a doubly-exponential length bound on the shortest runs between two configurations.
arXiv:2607.14990v1 Announce Type: new
Abstract: When a camera moves fast during exposure, blur destroys the intra-exposure motion a 3D model needs to recover the sharp scene, while event cameras capture exactly this signal at microsecond resolution. Turning them into reliable 3D supervision faces two obstacles. First, the two restoration priors fail in opposite ways: physics-based event-integration priors preserve edges but accumulate drift; learned networks recover texture but distort boundaries. Second, existing pipelines run in one direction only, so raw event noise or the biases of fixed 2D pseudo-labels pass uncorrected into the geometry. JADE-GS addresses both: a pixel-adaptive routing gate fuses the complementary priors, and the resulting 2D restorer is coupled to a 3D Gaussian Splatting student in a bidirectional loop, where detached, multi-view-consistent renders and a physics-based reblurring constraint regularize the restorer, turning a fixed preprocessor into a geometry-aware predictor. Across synthetic and real benchmarks, JADE-GS attains the best perceptual quality, leading LPIPS and CLIP-IQA on both benchmarks with competitive PSNR and SSIM, and trainsin about one hour under 5 GB on a single consumer GPU while preserving real-time rendering.
arXiv:2411.03747v4 Announce Type: replace
Abstract: Cooperative Localization is a promising approach to achieving safe quadrotor formation flight through precise positioning via low-cost inter-drone sensors. This paper develops an observability-aware control principle tailored to quadrotor formation flight with range-only inter-drone measurements. The control principle is based on a novel approximation of the local observability Gramian (LOG), which we name the Short-Term Local Observability Gramian (STLOG). The validity of STLOG is established by proving its link to directional estimation precision in nonlinear systems. We propose the Observability Predictive Controller (OPC), a receding-horizon controller that generates optimal inputs to enhance information gain in weakly observable state directions by maximizing the minimum eigenvalue of the STLOG. This reduces the risk of estimator divergence due to the unbounded growth of uncertainty in weakly observed state components. Monte Carlo simulations and flight experiments are conducted with quadrotors in a GNSS-denied ferrying mission, showing that the OPC improves positioning confidence and estimator robustness.
arXiv:2607.15033v1 Announce Type: new
Abstract: Neural video coding has advanced rapidly, achieving competitive compression performance while also enabling real-time coding speed. Yet, existing codecs exhibit severe rigidity when deployed in dynamic environments, failing to adapt to different video content, user requirements, and quality preferences. First, to meet the real-time constraint, they discard explicit motion estimation and motion compression, thereby losing the ability to adapt temporal prediction to motion complexity and bitrate constraints. Second, their spatial bit allocation strategy is coarse and, once trained, is fixed. It cannot adapt to dynamic user requirements at test time, preventing users from freely controlling the spatial distribution of bits. Third, they cannot adapt their quality preference to varying application requirements without deploying separate models. We address all three limitations within a single real-time neural video codec--URVC, transforming a rigid system into a unified framework with temporal, spatial, and perceptual adaptivity. First, we propose a rate-aware adaptive temporal prediction method that generates diverse prediction candidates through a multi-candidate architecture and couples candidate selection directly to rate-distortion optimization. Second, we propose a decomposition-based spatial rate control method that achieves finer-grained spatial bit allocation through feature decomposition and separate quantization, and allows users to perform direct spatial rate control at test time without retraining. Third, we propose a perceptual switching method that only requires learning a secondary module bank alongside a frame generator, enabling a codec to switch between signal fidelity and perceptual quality modes.
arXiv:2607.14202v1 Announce Type: new
Abstract: Video generation increasingly relies on keyframe-based workflows, where creators specify a sequence of reference images to guide generation. Although recent models support multi-keyframe conditioning, it remains unclear whether they can faithfully reproduce the prescribed keyframes while maintaining overall video quality. We present KeyFrame-Compass, the first comprehensive benchmark for evaluating keyframe-conditioned video generation. The benchmark contains 386 carefully curated samples spanning three application domains, two video structures, two prompt granularities, two conditioning formats, and four keyframe densities, enabling controlled analysis under diverse generation settings. We further introduce an automated evaluation framework that jointly measures keyframe execution and overall video quality. Specifically, we decompose keyframe execution into six complementary metrics covering presence, fidelity, temporal ordering, localization, persistence, and uniqueness, while assessing overall video quality through evidence-grounded MLLM judgments augmented with specialized perception models. Experiments on nine representative video generation systems reveal several fundamental limitations. Current models exhibit a clear trade-off between faithful keyframe execution and natural video synthesis. Their performance further degrades as keyframe constraints become denser and most open-source models also fail to interpret storyboard-grid inputs as temporally ordered keyframe sequences.
arXiv:2607.15046v1 Announce Type: new
Abstract: Topological concepts are frequently used to describe structured optical fields, including plasmonic near fields. Topological descriptions in terms of skyrmion numbers implicitly assume the compactness of the underlying manifold. Even when skyrmion-like textures appear locally, the compactness is usually not fulfilled in extended optical fields. Here, we use photoemission electron microscopy to investigate a plasmonic nano-focus that exhibits a sequence of radially extending alternating skyrmion and antiskyrmion textures. The full spatio-temporal reconstruction of the electric field vectors and their topology is accessible by vector polarimetry. The experiments confirm the expected oscillatory behavior of the skyrmion number and demonstrate that a global skyrmion number cannot be assigned in such non-compact fields.
arXiv:2412.03230v3 Announce Type: replace
Abstract: Chinese ASR correction is challenging because errors are often \emph{phonetic} (many characters share similar Pinyin) while the correction model must also obey a \emph{length constraint} under noisy N-best hypotheses. Existing approaches either exploit Pinyin only at the prompt/feature level without integrating it into model representations or rely on generative decoding that can drift in length. We propose \textbf{PERL}, a \textbf{constrained rephrasing pipeline} for Chinese N-best ASR correction that (i) predicts the target length and enforces it via mask budgeting, and (ii) fuses \emph{semantic} and \emph{phonetic} (Pinyin) representations through token-wise gates conditioned on sentence semantics. Experiments on Aishell-1 and our new domain N-best benchmark \textbf{DoAD} show that PERL consistently reduces CER (29.11\% on Aishell-1 and up to $\sim$70\% on DoAD) while maintaining low latency. We also provide analyzes of length generalization and phonetic--semantic interactions, showing when PERL relies on phonetic cues versus semantic constraints.
arXiv:2503.08068v3 Announce Type: replace
Abstract: Low-cost millimeter automotive radar has received more and more attention due to its ability to handle adverse weather and lighting conditions in autonomous driving. However, the lack of quality datasets hinders research and development. We report a new method that is able to simulate 4D millimeter wave radar signals including pitch, yaw, range, and Doppler velocity along with radar signal strength (RSS) using camera image, light detection and ranging (lidar) point cloud, and ego-velocity. The method is based on two new neural networks: 1) DIS-Net, which estimates the spatial distribution and number of radar signals, and 2) RSS-Net, which predicts the RSS of the signal based on appearance and geometric information. We have implemented and tested our method using open datasets from 3 different models of commercial automotive radar. The experimental results show that our method can successfully generate high-fidelity radar signals. Moreover, we have trained a popular object detection neural network with data augmented by our synthesized radar. The network outperforms the counterpart trained only on raw radar data, a promising result to facilitate future radar-based research and development.
arXiv:2505.22442v3 Announce Type: replace
Abstract: Offline RL (ORL) promises safe and sample-efficient deployment but existing methods rely on undocumented online interactions for hyperparameter tuning and lack reliable fully offline estimates of initial online performance. We introduce SOReL, a fully offline Bayesian model-based RL method that learns a posterior over dynamics, estimates policy value via predictive uncertainty, and enables complete offline hyperparameter selection. We further propose TOReL, which extends this tuning framework to arbitrary model-free and model-based ORL algorithms. We provide a regret analysis showing that Bayesian offline RL achieves the minimax-optimal parametric rate under standard regularity conditions. Together, our methods establish a practical and theoretically grounded framework for fully offline RL.
arXiv:2607.14290v1 Announce Type: new
Abstract: We present a comprehensive study of the timing resolution achievable in plastic scintillator detectors read out through wavelength-shifting (WLS) fibers coupled to silicon photomultipliers (SiPMs), combining a semi-analytical framework, toy Monte Carlo validation, and full Geant4 optical photon simulation. The analytical model traces the complete photon detection chain: scintillation emission, WLS fiber re-emission, optical transit time dispersion, SiPM single-photon time resolution, and electronics quantization. It expresses the timing resolution $\sigt$ as a function of the detected photoelectron yield $\Npe$, scintillator decay constants ($\taur$, $\taud$), WLS re-emission time ($\tauwls$), fiber numerical aperture, detector geometry, and readout electronics parameters. The analytical predictions are validated at two levels. First, toy Monte Carlo simulations ($2\times 10^5$ events per parameter point across 80 grid points spanning 8 fiber types and $\Npe$ from 5 to 200) achieve analytical-to-MC agreement of $0.9997 \pm 0.0015$. Second, full Geant4 optical photon simulations track the entire scintillation, wavelength-shifting, and fiber transport chain in realistic detector geometries, confirming the analytical timing predictions and providing first-principles photoelectron yield calibration. A comprehensive parameter scan covering 7 scintillator materials, 8 WLS fiber types, 5 SiPM models, 5 electronics configurations, 3 readout topologies, and 3 boundary conditions produces quantitative design maps and lookup tables for detector optimization.
arXiv:2607.14340v1 Announce Type: new
Abstract: AI coding agents produce code faster than humans can review it. In our approach, the prover is the judge of whether the code is correct. Under a verifier-driven loop, AI agents wrote and verified bare-metal security software in Ada/SPARK spanning classical and post-quantum cryptography, TLS 1.3, IKEv2, X.509, and a Matrix client. GNATprove discharged 49,280 proof obligations, established functional correctness for selected primitives, and proved the absence of run-time errors for the rest, at roughly 20-40 times lower supervision cost than comparable hand verification. GNATprove alone was insufficient: some defects could not be detected and were resolved using known-answer tests, interoperability, or human review of specifications. Given weak checks, the agent tried to bypass them and reported success. We report where each layer caught faults and draw the central lesson: what an agent can be trusted to establish is bounded by the strength of its feedback.
arXiv:2607.14524v1 Announce Type: new
Abstract: This study presents WrAFT, a Writing Assessment and Feedback Tool, that delivers both accurate and reliable scores and effective comprehensive feedback to argumentative essays. WrAFT adopts a modular design by dividing automated writing evaluation (AWE) tasks into scoring, surface-level feedback, and deep-level feedback. In building the system, various Large Language Models (LLMs) have been evaluated, including LLaMA-3.3-70B-Instruct, GPT-4o, and Claude 3.7, through both direct prompting and supervised fine-tuning approaches. A proprietary dataset of 480 TOEFL Independent Writing essays with official benchmark scores was utilized. Benchmark-based evaluation shows that WrAFT achieves state-of-the-art performance in scoring, with a quadratic weighted kappa (QWK) of 0.84 and a root mean square error (RMSE) of 0.44 against official scores on a scale of 0-5. Human evaluation of system-generated feedback also reveals high approval ratings: 96.14 percent for surface-level feedback, 93.03 percent for deep-level macro feedback, and 94.69 percent for deep-level micro feedback. An interactive user interface has been developed for the system and is publicly available and free to use.
arXiv:2607.14657v1 Announce Type: new
Abstract: We advocate for AI/ML issue resolution frameworks tailored to maintenance workflows and the nature of modern AI/ML systems. Existing issue resolution frameworks largely emerged for traditional software maintenance practices and do not explicitly account for characteristics common in AI/ML systems, such as stochastic behavior, experimentation-driven workflows, and heterogeneous artifacts beyond source code. To identify the unique characteristics of issue resolution in AI/ML systems and motivate the need for tailored frameworks, we conducted a qualitative study of issue resolution workflows documented in 100 issue reports and pull requests across four widely used AI/ML systems: TensorFlow, scikit-learn, MLflow, and AutoGPT. Our findings suggest that issue resolution in AI/ML systems involves: recurring AI/ML-related activities that span multiple resolution stages; iterative experimentation and adaptive verification; and coordinated changes across artifacts such as datasets, prompts, and model configurations. We also observed challenges related to reproducibility, nondeterministic behavior, and artifact coordination. Building on these findings, we present a vision for AI/ML issue resolution frameworks and discuss research directions and tooling support needed to realize this vision.
arXiv:2508.09769v2 Announce Type: replace
Abstract: Ongoing standardization efforts in 5G and Time-Sensitive Networking (TSN) aim to provide safety-critical applications with real-time communication. However, 5G-TSN network schedules often rely on idealistic delay models that can jeopardize the validity of their guarantees. This paper presents an $(m,k)$-firm Elevation Policy to uphold a base level of weakly hard real-time guarantees (WHRT). It augments the primary schedule with a dynamic priority-driven scheme to elevate the priority of $m$ out of $k$ consecutive frames if they experience unexpected delays. Our evaluations demonstrate the necessity of WHRT to increase fault-tolerance against 5G delay outliers and to uphold the quality of control within a 5G-TSN networked control system. Still, only a small resource overhead is imposed during epochs where the primary schedule is valid and can serve stronger QoS guarantees. The $(m,k)$-firm Elevation Policy thereby yields a robust but light-weight fallback mechanism to serve applications with dependable guarantees during unstable network conditions.
arXiv:2607.14556v1 Announce Type: new
Abstract: Financial institutions hold rich transaction histories, yet delivering recommendations that simultaneously maximize investment returns and ensure preference alignment remains a significant challenge. Existing approaches, namely return-based and preference-based strategies, each optimize a single objective, resulting in a fundamental trade-off between profitability (ROI) and relevance (nDCG). In this paper, we propose the Expert-Following Strategies: a framework that identifies top-performing investors based on their historical ROI and recommends the assets they purchased, scored by ROI-weighted purchase frequency. Our experiments using real-world transaction histories show that our strategy achieves statistically significant improvement over the market-average baseline in both ROI and nDCG simultaneously across all four thresholds.
arXiv:2607.14387v1 Announce Type: new
Abstract: Validating autonomous driving systems requires diverse, regulation-compliant test scenarios. In simulation-based testing, scenarios are defined as executable scripts. Yet automatically generating such scripts from regulatory descriptions remains an open challenge, and existing approaches face fundamental trade-offs. Retrieval-assemble methods achieve reasonable compilation rates but lack scalability, whereas retrieval-based full-script generation suffers from low compilation success rates. We present Chat2Scenic, the first iterative retrieval-augmented framework to generate scenario scripts in Domain Specific Language (DSL). Specifically, Chat2Scenic provides a chatbot interface that supports interactive scenario refinement and integrates Retrieval-augmented Generation (RAG) to ground scenario generation in regulatory knowledge and DSL syntax. Furthermore, we propose an open benchmark for scenario generation comprising 123 scenarios from various regulations, including NHTSA and United Nations Vehicle Regulations, as well as other sources. Extensive evaluation with State-of-the-Art (SOTA) Large Language Models (LLMs) demonstrates that Chat2Scenic achieves 76.42% Compilation Success Rate (CSR) and 58.17% Framework Accuracy (FA), outperforming existing methods (Retrieval Assemble with 30.08% CSR, 11.03% FA and Retrieval full script generation with 16.26% CSR, 10.86% FA). To facilitate future research, we release our code as open source at https://github.com/TUM-AVS/chat2scenic.
arXiv:2607.14582v1 Announce Type: new
Abstract: Existing LLM-based theorem provers have achieved impressive results on formal mathematics benchmarks, yet they remain confined to acting as autonomous agents that prove a stated proposition. In this paper, we propose MathCoPilot, a human-in-the-loop system that embodies a new human--AI symbiotic paradigm for mathematical research, in which the mathematician steers the high-level mathematical direction while AI agents carry out the detailed formalization and proof work under continuous human guidance. MathCoPilot unifies three core capabilities: (1) an interactive workbench where the mathematician and AI agents collaborate through a living proof blueprint that decomposes a proof into navigable steps the human can directly inspect, direct, and refine; (2) automated proving skill orchestration with adaptive knowledge base search and Lean-integrated iterative verification; and (3) topic-driven paper retrieval and automated formalization into a verified Lean knowledge base. Using MathCoPilot, we systematically compare four state-of-the-art LLMs, including Gemini~3.1~Pro, GPT-5.4, and Claude~Opus~4.7, on a FormalMATH subset and on two real PDE theorems requiring deep domain expertise, evaluating their ability to produce verified Lean~4 proofs and to identify errors in deliberately incorrect proofs. Our results show that while current models can handle undergraduate-level problems with high success rates under favorable autoformalization conditions, substantial challenges remain for domain-specific theorems requiring genuine mathematical understanding.
arXiv:2607.14654v1 Announce Type: new
Abstract: We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + \epsilon\ (\approx 3.694)$ and $4.9+\epsilon$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+\epsilon$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+\epsilon$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability.
Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.
arXiv:2607.14448v1 Announce Type: new
Abstract: We consider the problem of group testing, in which one seeks to identify a subset of defective items of size $k$ from a larger set of $n$ items based on pooled tests. We introduce a selectable threshold model, in which each test has an associated threshold that can be chosen, such that the test outcome is 1 if and only if the number of defectives in the test is no smaller than that threshold. In settings with a large or unbounded maximum threshold, we establish conditions under which high-probability recovery can be attained with a rate (i.e., the asymptotic ratio of $\log_2{n \choose k}$ to the number of tests) approaching its maximum possible value of 1. Moreover, in the case of a fixed maximum threshold, we establish an achievable number of tests using simple and computationally efficient decoding methods, and a converse that holds under suitable regularity conditions on the test design, with the two coinciding in the dense limit (i.e., $\theta$ approaching one in the scaling $k = \Theta(n^{\theta})$).