arXiv:2607.07228v1 Announce Type: new
Abstract: We predict a class of bound states in the continuum (BICs) in non-subwavelength periodic metasurfaces -- Rayleigh BICs -- that emerge precisely at Rayleigh anomalies, where diffraction channels open. In contrast to conventional symmetry-protected and accidental BICs, which are typically engineered in the subwavelength regime with only a few radiation channels, Rayleigh BICs remain nonradiating far beyond this limit, even when multiple diffraction channels are open. Their formation originates from the interplay between collective lattice resonances, Rayleigh anomalies, and anapole states of the constituent metaatoms. We show that Rayleigh BICs are characterized by an unusual cubic scaling of the quality factor in reciprocal space, ($Q \propto 1/k^3$), an asymptotic behavior that is not characteristic of either symmetry-protected or accidental BICs. Our results establish a constructive route for engineering nonradiating states in metasurfaces beyond the subwavelength regime.
Science Journals
arXiv:2411.17077v2 Announce Type: replace
Abstract: As Classifier-Free Guidance (CFG) has proven effective in conditional diffusion model sampling for improved condition alignment, many applications use a negated CFG term as a Negative Prompting (NP) to filter out unwanted features from samples. However, simply negating CFG guidance creates an inverted probability distribution, often distorting samples away from the marginal distribution. Inspired by recent advances in conditional diffusion models for inverse problems, here we present a novel method to achieve guidance toward the given condition using contrastive loss. Specifically, our guidance term aligns or repels the denoising direction based on the given condition through contrastive loss, achieving a similar guiding effect to traditional CFG for positive conditions while overcoming the limitations of existing negative guidance methods. Experimental results demonstrate that our approach effectively injects or removes the given concepts while maintaining sample quality across diverse scenarios, from simple class conditions to complex and overlapping text prompts.
arXiv:2607.07386v1 Announce Type: new
Abstract: Linear attention models allow a fixed state size and a fixed amount of compute per token. However, due to their limited state size, linear attention models fall behind in long-context recall compared to softmax-attention-based transformer architectures. Increasing the state size of linear attention improves recall performance but at the cost of higher FLOPs. In this work, we introduce Sparse Delta Memory (SDM), an architecture that scales the hidden state of gated linear RNNs to orders of magnitude higher capacity using a sparse addressing scheme. SDM extends the Gated DeltaNet architecture by replacing the dense key-value outer product with sparse reads and writes to a large explicit memory. We show that, under an isoFLOP constraint and with an identical number of parameters, a higher state memory capacity significantly improves performance on in-context learning and long-context retrieval tasks. Moreover, by learning the initial state of the SDM memory and therefore using it as a parametric memory, we show that the model further improves on a wide range of common-knowledge and reasoning tasks.
arXiv:2607.07409v1 Announce Type: new
Abstract: Speculative decoding accelerates LLM inference by drafting multiple tokens and verifying them in parallel. Block-parallel drafters such as DFlash further improve drafting efficiency by predicting an entire block in one pass, but their position-wise predictions lack explicit intra-block causal conditioning. Recent methods such as Domino and DSpark attempt to introduce such causality into block-parallel drafting, but they require training the draft model from scratch, which limits their flexibility and increases training cost. We propose DeLS-Spec, a decoupled long-short context speculative decoding method. DeLS-Spec treats the fixed DFlash model as a long-context expert and introduces a lightweight local head as a short-context expert. The local head can be trained independently with a standard next-token prediction objective, without joint training with the target model or the DFlash backbone, leading to extremely low training cost. At inference time, DeLS-Spec combines long-context and short-context logits, and the local head is not tied to a specific DFlash checkpoint, making the method more modular and flexible. Experiments on Qwen3 models show that DeLS-Spec consistently improves speedup and average acceptance length over DFlash across math, code, and dialogue benchmarks.
arXiv:2506.18579v3 Announce Type: replace
Abstract: High-frequency (HF) ray tracing in complex ionospheric media generally involves a fundamental trade-off between path accuracy and computational efficiency, which directly affects practical applications such as over-the-horizon radar, ionospheric monitoring, and HF skywave communication systems. This paper presents RTM-GD, a ray-tracing framework that combines Hamiltonian ray integration with a continuously differentiable Galerkin--Difference (GD) interpolation strategy. Under discretized ionospheric grid conditions, the electron density is reconstructed as a $C^1$-continuous function within each grid cell, yielding an everywhere differentiable electron-density field for stable numerical integration and improved propagation-path accuracy. Numerical simulations and validations using measured HF oblique sounding data are conducted under diverse conditions, including different ionospheric states, low- and high-elevation angles, multiple operating frequencies, and both ordinary (O) and extraordinary (X) wave modes. Results show that RTM-GD consistently achieves sub-kilometer RMSE in both group-path and ground-distance metrics and sub-0.01-degree azimuth deviation relative to Richardson extrapolation, while reducing computational time by 98\%. Compared with Catmull--Rom interpolation, RTM-GD reduces the RMSEs of ray parameters by approximately one order of magnitude with less than 4\% additional computational cost. Measured-data validation based on ionogram synthesis further shows that the mean relative group-path error remains within 7\%, confirming reliable reproduction of practical HF oblique propagation characteristics. Overall, RTM-GD provides an accurate and computationally efficient framework for HF ray tracing in discretized ionospheric environments.
arXiv:2607.07116v1 Announce Type: new
Abstract: In some cases, end-user programming allows the design of stand-alone applications. But none of the existing approaches is concerned by safety aspects of programming. Heavy techniques exist to develop safe applications, particularly in non-interactive domains. They involve software engineering techniques, and sometimes, formal methods. All these techniques are very far from end-users. Our idea is to let this part to experts, and to connect end-user programming onto this safe conventional development. Starting from an existing functional core, we built an interactive end-user programming environment called GenBuild, which allows designing interactive stand-alone applications. GenBuild is composed of two distinct modules. The Generator is the first one. It is a specialized tool developed for a domain expert who sets out a safe functional core. The Builder is the second module. It is a purely interactive tool that allows an end-user to develop some complete interactive application among an existing functional core. It allows the verification of some properties that are a first step towards the development of safe end-user programming.
arXiv:2607.07153v1 Announce Type: new
Abstract: We study ranking and rank aggregation under the Kendall tau distance, subject to matroid or flag matroid constraints on prefixes of the output ranking. In the matroid case, the top-$k$ prefix is required to form a base of a matroid; in the flag matroid case, several prescribed prefixes are required to form bases of a sequence of matroids linked by quotient relations. This framework contains the previously studied notions of $k$-fairness and block-fairness as special cases, and also captures more general hierarchical and assignment-type lower- and upper-quota constraints.
We provide a polynomial-time algorithm for finding, given a single input ranking, a closest feasible ranking under flag matroid prefix constraints. The algorithm is a natural greedy procedure, and its optimality is proved via a Bruhat order argument on the symmetric group. As a consequence, existing approximation frameworks for fair rank aggregation carry over to the matroidal setting. We also prove that rank aggregation with matroid constraints is NP-hard for every fixed number $m\ge 2$ of input rankings, even under partition matroid constraints.
arXiv:2607.07452v1 Announce Type: new
Abstract: Dense visual SLAM is a fundamental problem in robotics. Recent advances in 3DGS have demonstrated its potential for dense SLAM. Existing 3DGS frameworks focus on both appearance and geometry modeling. However, scene geometry is typically more critical for SLAM than novel view synthesis because downstream robotic tasks, such as navigation and obstacle avoidance, rely primarily on accurate spatial geometry rather than photorealistic rendering. This observation raises a natural question: Is it feasible for 3DGS to perform 3D reconstruction without scene appearance modeling? Motivated by this, we propose Geometry-only Gaussian Splatting (GeoGS), which directly reconstructs scene geometry, and further present GeoGS-SLAM, a dense visual SLAM system built upon this representation. Specifically, GeoGS retains only spatial parameters to reduce the number of per-primitive parameters by over 80%. In contrast to existing 3DGS methods, GeoGS focuses solely on geometric reconstruction, which significantly reduces the number of Gaussian primitives, accelerates geometric convergence, and enhances robustness to illumination variations. In addition, we present an effective training framework that optimizes the Gaussian primitives via single-view and multi-view geometric and photometric supervision, and speeds up geometry convergence with a local-plane driven initialization that better aligns primitives with local structures. Furthermore, we introduce a map update strategy for loop closure that globally transforms the Gaussian map to align it with the corrected pose estimates, thereby preventing map tearing caused by inconsistent per-viewpoint pose corrections in existing methods. Extensive experiments on synthetic and real-world benchmarks demonstrate that our method outperforms SOTA methods in terms of online mapping efficiency and geometric reconstruction quality.
arXiv:2607.07519v1 Announce Type: new
Abstract: We address the problem of efficiently sampling multimodal probability distributions, where standard Markov Chain Monte Carlo methods often suffer from poor mixing and mode trapping. To mitigate these issues, we propose Gradient-free Riemannian Langevin Sampler (GRiLS), a novel proposal that improves exploration without requiring gradient evaluations of the target density. Our approach introduces a Riemannian metric which reshapes the local geometry in order to facilitate transitions across modes. The resulting gradient-free MCMC algorithm is particularly suitable for complex, computationally expensive targets where derivatives are unavailable or impractical. The GRiLS proposal requires knowing the mean and covariance of the target density, which we estimate using an ensemble of interacting particles. Empirical results on multimodal benchmarks demonstrate that GRiLS achieves improved mixing compared to existing gradient-based and gradient-free MCMC approaches.
When Distillation Breaks Motion Control: Restoring Generative Trajectories for Fast Video Generators
arXiv:2506.19348v2 Announce Type: replace
Abstract: Training-free motion customization imposes motion patterns from reference videos onto video generators through test-time computation. Most existing methods target full diffusion models, requiring many denoising steps and high computational cost. With the rise of efficient distilled models, a natural question arises: can test-time motion customization be applied directly to distilled generators with their accelerated sampling and efficiency gains? However, our analysis reveals that existing training-free techniques fail on distilled models. Distillation fundamentally alters the denoising dynamics that prior test-time guidance relies on, and the large denoising steps of distilled generators discard the dense intermediate states that score guidance requires, rendering existing motion control strategies incompatible with fast generation. To address this limitation, we propose MotionEcho, a novel training-free test-time distillation framework that enables motion customization for distilled video generators. The key idea is to correct the student model's sampling trajectory with restricted usage of a high-quality diffusion teacher at inference time. Teacher supervises the student's denoising by re-noising the student's endpoint onto its dense trajectory to form a motion-aligned clean endpoint, then interpolating it with the student's, while an adaptive scheduling mechanism determines when and how much teacher guidance is needed. As a result, MotionEcho restores generative trajectories for distilled video generators via lightweight, adaptive test-time teacher guidance, enabling accurate motion control without compromising generation efficiency. Extensive experiments on multiple distilled video generation models demonstrate that our method significantly improves motion fidelity and visual quality while retaining the efficiency advantages of distilled generation.
arXiv:2607.07444v1 Announce Type: new
Abstract: Assertion-based Verification (ABV) plays a critical role in the Design Verification (DV) process. However, ABV requires substantial manual effort in generating assertion from specification by verification engineers, making it a time-consuming stage in the chip design flow. With the recent development of Large Language Models (LLMs), researchers have started exploring their use as an assistance in the ABV process, particularly for generating SystemVerilog Assertions (SVAs) from design specification. In this paper, we provide an overview of recent works, highlighting the different methods used to generate SVAs. In particular, we investigate LLM-based SVA generation and ask a central question: How can LLM-based assertion generation be made systematic and quality-aware? While addressing this key question, we provide Key Takeaways at the end of each challenge, summarizing the important methodological insights, and also provide guidelines and directions in solving those challenges that can help generate a high-quality set of assertions using LLMs.
arXiv:2607.07707v1 Announce Type: new
Abstract: Limited memory language models (LMLMs) externalize factual knowledge during pretraining to a knowledge base (KB), rather than memorizing it in their weights. During generation, the model then fetches knowledge from the KB as needed. This recently introduced paradigm provides multiple advantages, including knowledge control capabilities that remain beyond conventional LLMs. We propose continuous-query LMLM (CO-LMLM), where the KB pairs continuous keys with textual knowledge values, a significant departure from prior reliance on relational KB and queries. CO-LMLM generates flexible vector queries at minimal cost, while still integrating human-readable and attributable retrieved knowledge into its generation. We pair this design with an annotation pipeline that tags free-form factual spans in arbitrary text, removing prior work's restriction to Wikipedia. Across pretraining on Wikipedia and FineWeb-Edu and at multiple model scales, CO-LMLM outperforms prior LMLMs and vanilla LLMs in both perplexity and factual precision. At 360M scale, this includes lower perplexity than models pretrained on 40x more data, and SimpleQA-verified performance that is in line with gpt-4o-mini and higher than Claude Sonnet 4.5.
arXiv:2507.01477v2 Announce Type: replace
Abstract: Automated unit test generation is an established research field that has so far focused on statically-typed programming languages. The lack of type information in dynamically-typed programming languages, such as Python, inhibits test generators, which heavily rely on information about parameter and return types of functions to select suitable arguments when constructing test cases. Since automated test generators inherently rely on frequent execution of candidate tests, we make use of these frequent executions to address this problem by introducing type tracing, which extracts type-related information during execution and gradually refines the available type information. We implement type tracing as an extension of the Pynguin test-generation framework for Python, allowing it (i) to infer parameter types by observing how parameters are used during runtime, (ii) to record the types of values that function calls return, and (iii) to use this type information to increase code coverage. The approach leads to up to 87.8 % more branch coverage, improved mutation scores, and to type information of similar quality to that produced by other state-of-the-art type-inference tools.
arXiv:2412.03405v3 Announce Type: replace
Abstract: Motivated by dynamic risk measures and conditional $g$-expectations, in this work we propose a numerical method to approximate the solution operator given by a Backward Stochastic Differential Equation (BSDE). The main ingredients for this are the Wiener chaos decomposition and the classical Euler scheme for BSDEs. We show convergence of this scheme under very mild assumptions, and provide a rate of convergence in more restrictive cases. We then implement it using neural networks, and we present several numerical examples where we can check the accuracy of the method.
arXiv:2607.06886v1 Announce Type: cross
Abstract: Fluid injection into the earth's crust can induce small and frequent earthquakes in the subsurface. Predicting their sizes and temporal occurrences via statistical analysis is crucial for safe operations in unconventional oil and gas recovery, enhanced geothermal systems, and geologic carbon storage. Here we show that a simple micromechanical model of slip avalanches in slowly deforming solids predicts the slip statistics observed over drastically different spatial scales, namely meter-scale microseismic observations and nanometer- to micrometer-scale nanoindentation experiments can be described with this model. Microseismic catalogs extracted from high-pressure fluid injection operations into geological basins with various lithologies and nanoindentation experiments on shale across a wide range of temperatures and mineral compositions yield statistics consistent with model predictions. This universality across materials, temperatures, and scales is consistent with the prediction that the slip statistics result from only a few basic properties. Previously debated deviations of the statistics in layered sedimentary formations are explained by finite-size and stress-integrative effects resulting from mechanically weak bedding planes. The slip statistics therefore provide important information about the structure and scales of the bedding planes. Conversely, the basin structure can also be used to predict the probability distribution for the sizes of triggered microseismic events.
arXiv:2607.06953v1 Announce Type: cross
Abstract: We propose a quantum model for finding a resetting input sequence (RS) which can take a finite state transition system (FA), to particular state independent of its current state. The complexity of finding such sequences for various types of FA can be NP-Hard or even PSPACE-Complete. To this end, we represent the FA states, inputs, and transition function in quantum space. Accordingly, we propose a model to represent the execution of an input sequence of a particular length $l$ starting form an initial FA state. The model is extended considering the application in superposition of all input sequences of length $l$ to an initial state of the FA. The model is further extended considering the application of all input sequences to all initial states of the FA capturing for every input sequence the collection (ordered list) of states reached by applying the sequence to all states of the FA. The amplitude amplification algorithm is then used as it combines similar collections of reached states while preserving all input sequences that reach these collections. A Grover search for a reached collection where its elements correspond to the same FA state provides a RS for the FA. Our approach offers a quadratic gain over the exponential complexity of traditional brute-force method, which is the only method that can be applied to a general FA class. As a proof of concept we provide results of several simulated FAs on a quantum simulator.
arXiv:2506.18025v5 Announce Type: replace
Abstract: Record wall-plug efficiencies in long-wavelength, III-nitride light-emitting diodes (LEDs) have recently been achieved through improvements in electrical efficiency in devices containing V-defects. Numerical modeling suggests this may be due to reduced barrier heights for charge injection in thinned, low-Indium quantum wells parallel to semi-polar V-defect facets. To test this proposition, a novel approach in which the tip of a scanning tunneling luminescence microscope as a local hole injector, is used to map the optoelectronic properties of commercial, green-emitting LED heterostructures around V-defects with nanoscale spatial resolution. A 1 V reduction in the forward bias necessary for current injection at V-defect rims is observed. This, combined with the observation of small (~10 meV) blue shifts in the locally emitted electroluminescence, unambiguously confirms the charge injection mechanism.
arXiv:2607.06617v1 Announce Type: new
Abstract: Wearable motion sensing provides a continuous and scalable window into human behavior and health, making it a natural fit for foundation models, yet its pretraining and scaling principles remain poorly understood. Prior work studies isolated design choices, such as sensor placement or sampling frequency, often under fixed settings and narrow downstream tasks that fail to capture real-world sensing diversity. We introduce Inertia-1, a fully open exploration of wearable motion foundation models. Using massive corpora of accelerometer data from global sources spanning more than 18.2M hours, we build a controlled framework for studying the full lifecycle of wearable motion foundation models, covering data choices such as sensor modality, device placement, sampling rate, window length; model choices such as architectures and model size; and training choices such as pretraining objective and data scale. Extensive evaluations across 15 datasets spanning human activity recognition, freezing-of-gait detection, and disease prediction reveal intriguing findings for building motion foundation models that generalize across tasks and sensing conditions. Collectively, Inertia-1 not only presents state-of-the-art recipes for diverse downstream tasks, but also serves as a comprehensive, practical, and open cookbook for wearable motion representation learning.
arXiv:2607.06641v1 Announce Type: new
Abstract: Large language models (LLMs) achieve promising results on medical question answering benchmarks, yet their use in public health is constrained by hallucinations and the rapid evolution of official guidance. Retrieval-Augmented Generation (RAG) mitigates these risks by grounding responses in an explicitly maintained corpus, but end-to-end performance depends critically on retrieval configuration and on evaluation beyond multiple-choice formats. We extend PubHealthBench, a question answering (QA) benchmark of 7,929 questions derived from UK Government public health guidance, into a retrieval-augmented setting and systematically evaluate retrieval and generation choices. We compare dense, sparse, and hybrid retrieval across multiple embedding models and corpus variants, and show that hybrid retrieval consistently improves recall and ranking quality, with chunk length and topic interacting with ranking performance. Providing retrieved context substantially increases multiple-choice accuracy across a diverse set of LLMs, enabling smaller open-weight models to match or outperform larger models used without retrieval, with gains primarily driven by retrieval quality and careful context selection. To assess realistic free-form answering, we introduce a rubric-based LLM-as-a-judge covering faithfulness, completeness, clarity, and factual consistency, and validate it against dual human annotations. Judge-human agreement is strongest for faithfulness and completeness, while factual consistency and clarity are less reliably reproduced, motivating caution when interpreting those dimensions at scale. Overall, our results highlight retrieval as a primary lever for reliable public health QA and provide practical guidance for building and evaluating RAG systems grounded in official guidance.
arXiv:2607.06721v1 Announce Type: new
Abstract: Building upon found examples is a popular way people learn to code, especially in creative coding communities where sharing projects and remixing are common practices. But effectively doing so requires being able to 1) understand how existing code works, and 2) extend it by writing code that implements your own ideas, practices that can be challenging for new creative coders. We explored how to support these two processes through the design of Flowcode, a creative coding programming environment that integrates a flowchart for visualizing code structure and a chat interface tailored to support learning to code over vibe coding. We share how we iterated on the design of Flowcode over two studies with new creative coders, reflecting on the roles visualization and friction may play in enabling productive AI-use in computing education.
arXiv:2507.05116v5 Announce Type: replace
Abstract: Recent large-scale Vision Language Action (VLA) models have shown superior performance in robotic manipulation tasks guided by natural language. However, current VLA models suffer from two drawbacks: (i) generation of massive tokens leading to high inference latency and increased training cost, and (ii) insufficient utilization of generated actions resulting in potential performance loss. To address these issues, we develop a training framework to finetune VLA models for generating significantly fewer action tokens with high parallelism, effectively reducing inference latency and training cost. Furthermore, we introduce an inference optimization technique with a novel voting-based ensemble strategy to combine current and previous action predictions, improving the utilization of generated actions and overall performance. Our results demonstrate that we achieve superior performance compared with state-of-the-art VLA models, achieving significantly higher success rates and 39$\times$ faster inference than OpenVLA with 46 Hz throughput on edge platforms, demonstrating practical deployability. The code is available at https://github.com/LukeLIN-web/VOTE.
arXiv:2607.06764v1 Announce Type: new
Abstract: Recent progress on ARC-AGI-1 from disclosed architectures has come broadly from two regimes: heavy test-time compute over frontier models (evolutionary search, exhaustive sampling, extended chain-of-thought), or benchmark-specific training in which small models are fine-tuned on ARC data, often with task-specialized architectures. We study a third regime: an open-weight model in non-thinking mode (DeepSeek V3.2) under a strict budget, with no ARC-specific fine-tuning. We study what is recoverable through architecture alone, building agentic harnesses that decompose pattern-discovery and program-synthesis stages explicitly. First, we introduce an Explorer-Definer Pipeline that separates pattern discovery from executable transformation synthesis, implemented as a two-stage agent pipeline. Next, we present the Reflective Orchestrator, which augments the pipeline with autonomous exploration of new transformations when previous hypotheses fail on training pairs. On the ARC-AGI-1 public 400-task evaluation set, the pipeline reaches 57.50% pass@2 at \$0.25 per task, and the orchestrator reaches 67.25% pass@2 at \$0.62 per task. Together these architectures lift a 15.50% one-shot baseline by ~52 points without benchmark-specific training or heavy test-time compute. Furthermore, the orchestrator-driven lift tests a falsifiable diagnostic the pipeline produces; unbiased pass@k analysis suggests the pipeline is generation-bound, not selection-bound (selection via training-pair accuracy captures ~95% of the candidate ceiling) and predicts that significant improvement requires broader generation, not better ranking. The orchestrator implements this prediction via adaptive re-exploration and confirms it (unbiased pass@1 lift +9.81 pp, matching selection-mediated pass@2 lift). An additional pipeline ablation identifies its think tool as a significant component, with removal reducing pass@2 by 5.75 pp.
arXiv:2607.07453v1 Announce Type: new
Abstract: We present Hamiltonian Replica Exchange Transition Interface Sampling (HRETIS), a path sampling framework designed to efficiently sample rare events in systems with complex potential energy landscapes. HRETIS introduces a helper potential within a Hamiltonian replica exchange scheme, which enhances exploration of path space when the underlying potential is not well suited for conventional path sampling approaches. This is particularly advantageous for systems exhibiting multiple pathways separated by orthogonal barriers such as in drug (un)binding, where standard algorithms often show slow convergence since they become trapped within specific pathways. By exchanging Hamiltonians between the path ensembles, HRETIS overcomes these limitations and increases the decorrelation between subsequent paths in the Monte Carlo chain. We demonstrate that HRETIS provides robust and accurate kinetics in several systems, including coarse-grained simulations of amino acid permeation through a dipalmitoylphosphatidylcholine (DPPC) membrane. Moreover, HRETIS is found to improve sampling efficiency and convergence, illustrating its potential as a powerful tool for rare event sampling in complex molecular systems.
arXiv:2607.06903v1 Announce Type: new
Abstract: We present a variational framework in which (i) guiding-center kinetic theory, (ii) macroscopic force balance with gyrotropic/anisotropic pressure, and (iii) quasisymmetry (QS) constraints appear as different facets of a single structure. Starting from a guiding-center Vlasov--Maxwell action, constrained variations yield the guiding-center kinetic equation and Maxwell equations. Without phenomenological closure, momentum conservation yields macroscopic force balance $\mathbf{J} \times \mathbf{B}/c = \nabla\cdot\boldsymbol{\Pi}$, where $\mathbf{J}$ is the current density, $\mathbf{B}$ is the magnetic field, and $\boldsymbol{\Pi}$ is the gyrotropic stress tensor. We connect QS to an integrability condition expressed in coordinate-free form via $$f_T \equiv \nabla\psi \cdot \bigl(\nabla B \times \nabla(\mathbf{B} \cdot \nabla B)\bigr) = 0,$$ where $\psi$ is the flux surface label, and show how this condition leads to solvability constraints on anisotropy closely related to those found in a recent constrained Kruskal--Kulsrud variational formulation.
arXiv:2607.06852v1 Announce Type: new
Abstract: The parameterized Minimum Monotone Satisfying Assignment ($k$-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most $k$. The MMSA hierarchy is defined by allowing a bounded number of alternations between AND and OR gates in the circuit. While the polynomial-time approximability of the MMSA hierarchy has been studied extensively, much less is known in the parameterized setting. In particular, $k$-MMSA$_2$ is the well-known $k$-SetCover problem, whose parameterized inapproximability lies in the $\text{polylog}(n)$ regime. In contrast, $k$-MMSA$_4$ captures $k$-MinLabel, for which known lower bounds give $\text{poly}(n)$ inapproximability. Sandwiched by $k$-MMSA$_2$ and $k$-MMSA$_4$, the inapproximability of $k$-MMSA$_3$ remained comparatively unexplored.
In this paper, we give an FPT-time $O(2^k \log n)$-approximation algorithm for $k$-MMSA$_3$, suggesting that in the fixed-parameter regime, the third level of MMSA remains surprisingly close to the second level. Complementing this algorithm, we also give an FPT-time gap-preserving reduction from $k$-MMSA$_3$ to $k$-MMSA$_2$. Thus, stronger inapproximability for $k$-MMSA$_3$ would imply new hardness for $k$-MMSA$_2$, potentially offering a route around the current barriers for the latter problem.
Revisiting Marx's reduction from $k$-MMSA$_t$ to gap $k$-MMSA$_{t+2}$, we also show that $k$-MMSA$_4$ admits no $n^{o(1)}$-factor FPT approximation unless W[2]=FPT, and no $n^{O(1/k)}$-factor approximation running in $n^{o(k)}$ time under ETH. These results separate the parameterized approximability behavior of the third and fourth levels and clarify where stronger inapproximability enters the $k$-MMSA hierarchy.