OpenRaiser/Intern-Atlas huggingface dataset:
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
Venue: arXiv cs.CC 2025
Year: 2025

The k-Clique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the k-Clique problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a clique of size at least k/F(k) whenever the graph G has a clique of size k. When such an algorithm runs in time T(k)poly(n) (i.e., FPT-time) for some computable function T, it is said to be an F(k)-FPT-approximation algorithm for the k-Clique problem. Although, the non-existence of an F(k)-FPT-approximation algorithm for any computable sublinear function F is known under gap-ETH [Chalermsook et al., FOCS 2017], it has remained a long standing open problem to prove the same inapproximability result under the more standard and weaker assumption, W[1]$\neq$FPT. In a recent breakthrough, Lin [STOC 2021] ruled out constant factor (i.e., F(k)=O(1)) FPT-approximation algorithms under W[1]$\neq$FPT. In this paper, we improve this inapproximability result (under the same assumption) to rule out every $F(k)=k^{1/H(k)}$ factor FPT-approximation algorithm for any increasing computable function H (for example $H(k)=\log^\ast k$). Our main technical contribution is introducing list decoding of Hadamard codes over large prime fields into the proof framework of Lin.
Superpixel-Based Building Damage Detection from Post-earthquake Imagery Using Deep Neural Networks
Venue: arXiv cs.CV 2025
Year: 2025

Building damage detection after natural disasters like earthquakes is crucial for initiating effective emergency response actions. Remotely sensed very high spatial resolution (VHR) imagery can provide vital information due to their ability to map the affected buildings with high geometric precision. However, we suffer from suboptimal performances in detecting damaged buildings due to earthquakes. This paper presents a novel superpixel based approach incorporates Deep Neural Networks (DNN) with a modified segmentation method, for more precise building damage detection from VHR imagery. Firstly, a modified Fast Scanning and Adaptive Merging method is extended to create initial over-segmentation. Secondly, the segments are properly merged based on the Region Adjacent Graph (RAG). Thirdly, a pre-trained DNN using Stacked Denoising Auto-Encoders (SDAE-DNN) is presented, to exploit the rich semantic features for building damage detection. Experimental results on a WorldView-2 imagery from Nepal Earthquake of 2015 demonstrate the feasibility and effectiveness of our method, which could boost detection accuracy through learning more intrinsic and discriminative features, which outperforms other methods using alternative classifiers.
Dense Video Captioning Using Unsupervised Semantic Information
Venue: arXiv cs.CV 2025
Year: 2025

We introduce a method to learn unsupervised semantic visual information based on the premise that complex events can be decomposed into simpler events and that these simple events are shared across several complex events. We first employ a clustering method to group representations producing a visual codebook. Then, we learn a dense representation by encoding the co-occurrence probability matrix for the codebook entries. This representation leverages the performance of the dense video captioning task in a scenario with only visual features. For example, we replace the audio signal in the BMT method and produce temporal proposals with comparable performance. Furthermore, we concatenate the visual representation with our descriptor in a vanilla transformer method to achieve state-of-the-art performance in the captioning subtask compared to the methods that explore only visual features, as well as a competitive performance with multi-modal methods. Our code is available at https://github.com/valterlej/dvcusi.
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
Venue: arXiv cs.FL 2025
Year: 2025

We study the computational complexity of finite intersections and finite unions of deterministic context-free (dcf) languages. Earlier, Wotschke [J. Comput. System Sci. 16 (1978) 456--461] demonstrated that intersections of $(d+1)$ dcf languages are in general more powerful than intersections of $d$ dcf languages for any positive integer $d$ based on the separation result of the intersection hierarchy of Liu and Weiner [Math. Systems Theory 7 (1973) 185--192]. The argument of Liu and Weiner, however, works only on bounded languages of particular forms, and therefore Wotschke's result is not directly extendable to other non-bounded languages. To deal with a wide range of languages for the non-membership to the intersection hierarchy, we circumvent the specialization of their proof technics and devise a new and practical technical tool: two pumping lemmas for finite unions of dcf languages. Since the family of dcf languages is closed under complementation and also under intersection with regular languages, these pumping lemmas help us establish the non-membership relation of languages formed by finite intersections of target languages. We also concern ourselves with a relationship to deterministic limited automata of Hibbard [Inf. Control 11 (1967) 196--238] in this regard.
Quantifying Gender Biases Towards Politicians on Reddit
Venue: arXiv cs.CL 2025
Year: 2025

Despite attempts to increase gender parity in politics, global efforts have struggled to ensure equal female representation. This is likely tied to implicit gender biases against women in authority. In this work, we present a comprehensive study of gender biases that appear in online political discussion. To this end, we collect 10 million comments on Reddit in conversations about male and female politicians, which enables an exhaustive study of automatic gender bias detection. We address not only misogynistic language, but also other manifestations of bias, like benevolent sexism in the form of seemingly positive sentiment and dominance attributed to female politicians, or differences in descriptor attribution. Finally, we conduct a multi-faceted study of gender bias towards politicians investigating both linguistic and extra-linguistic cues. We assess 5 different types of gender bias, evaluating coverage, combinatorial, nominal, sentimental, and lexical biases extant in social media language and discourse. Overall, we find that, contrary to previous research, coverage and sentiment biases suggest equal public interest in female politicians. Rather than overt hostile or benevolent sexism, the results of the nominal and lexical analyses suggest this interest is not as professional or respectful as that expressed about male politicians. Female politicians are often named by their first names and are described in relation to their body, clothing, or family; this is a treatment that is not similarly extended to men. On the now banned far-right subreddits, this disparity is greatest, though differences in gender biases still appear in the right and left-leaning subreddits. We release the curated dataset to the public for future studies.
Combining Minkowski and Chebyshev: New distance proposal and survey of distance metrics using k-nearest neighbours classifier
Venue: arXiv cs.LG 2025
Year: 2025

This work proposes a distance that combines Minkowski and Chebyshev distances and can be seen as an intermediary distance. This combination not only achieves efficient run times in neighbourhood iteration tasks in Z^2, but also obtains good accuracies when coupled with the k-Nearest Neighbours (k-NN) classifier. The proposed distance is approximately 1.3 times faster than Manhattan distance and 329.5 times faster than Euclidean distance in discrete neighbourhood iterations. An accuracy analysis of the k-NN classifier using a total of 33 datasets from the UCI repository, 15 distances and values assigned to k that vary from 1 to 200 is presented. In this experiment, the proposed distance obtained accuracies that were better than the average more often than its counterparts (in 26 cases out of 33), and also obtained the best accuracy more frequently (in 9 out of 33 cases).
Tutorial on amortized optimization
Venue: arXiv cs.LG 2025
Year: 2025

Optimization is a ubiquitous modeling tool and is often deployed in settings which repeatedly solve similar instances of the same problem. Amortized optimization methods use learning to predict the solutions to problems in these settings, exploiting the shared structure between similar problem instances. These methods have been crucial in variational inference and reinforcement learning and are capable of solving optimization problems many orders of magnitudes faster than traditional optimization methods that do not use amortization. This tutorial presents an introduction to the amortized optimization foundations behind these advancements and overviews their applications in variational inference, sparse coding, gradient-based meta-learning, control, reinforcement learning, convex optimization, optimal transport, and deep equilibrium networks. The source code for this tutorial is available at https://github.com/facebookresearch/amortized-optimization-tutorial.
Training Differentially Private Models with Secure Multiparty Computation
Venue: arXiv cs.CR 2025
Year: 2025

We address the problem of learning a machine learning model from training data that originates at multiple data owners while providing formal privacy guarantees regarding the protection of each owner's data. Existing solutions based on Differential Privacy (DP) achieve this at the cost of a drop in accuracy. Solutions based on Secure Multiparty Computation (MPC) do not incur such accuracy loss but leak information when the trained model is made publicly available. We propose an MPC solution for training DP models. Our solution relies on an MPC protocol for model training, and an MPC protocol for perturbing the trained model coefficients with Laplace noise in a privacy-preserving manner. The resulting MPC+DP approach achieves higher accuracy than a pure DP approach while providing the same formal privacy guarantees. Our work obtained first place in the iDASH2021 Track III competition on confidential computing for secure genome analysis.
Spoiler Susceptibility in Party Elections
Venue: arXiv cs.GT 2025
Year: 2025

An electoral spoiler is usually defined as a losing candidate whose removal would affect the outcome by changing the winner. So far, spoiler effects have been analyzed primarily for single-winner electoral systems. We consider this subject in the context of party elections, where there is no longer a sharp distinction between winners and losers. Hence, we propose a more general definition, under which a party is a spoiler if their elimination causes any other party's share in the outcome to decrease. We characterize spoiler-proof electoral allocation rules for zero-sum voting methods. In particular, we prove that for seats-votes functions only identity is spoiler-proof. However, even if spoilers are unavoidable under common electoral rules, their expected impact can vary depending on the rule. Hence, we introduce a measure of spoilership, which allows us to experimentally compare a number of multiwinner social choice rules according to their spoiler susceptibility. Since the probabilistic models used in COMSOC have been developed for nonparty elections, we extend them to generate multidistrict party elections.
Multi-scale Attention Guided Pose Transfer
Venue: arXiv cs.CV 2025
Year: 2025

Pose transfer refers to the probabilistic image generation of a person with a previously unseen novel pose from another image of that person having a different pose. Due to potential academic and commercial applications, this problem is extensively studied in recent years. Among the various approaches to the problem, attention guided progressive generation is shown to produce state-of-the-art results in most cases. In this paper, we present an improved network architecture for pose transfer by introducing attention links at every resolution level of the encoder and decoder. By utilizing such dense multi-scale attention guided approach, we are able to achieve significant improvement over the existing methods both visually and analytically. We conclude our findings with extensive qualitative and quantitative comparisons against several existing methods on the DeepFashion dataset.
Towards a maturity model for crypto-agility assessment
Venue: arXiv cs.CR 2025
Year: 2025

This work proposes the Crypto-Agility Maturity Model (CAMM for short), a maturity model for determining the state of crypto-agility of a given software or IT landscape. CAMM consists of five levels, for each level a set of requirements have been formulated based on literature review. Initial feedback from field experts confirms that CAMM has a well-designed structure and is easy to comprehend. Based on our model, the crytographic agility of an IT landscape can be systematically measured and improved step by step. We expect that this will enable companies and to respond better and faster to threats resulting from broken cryptographic schemes. This work serves to promote CAMM and encourage others to apply it in practice and develop it jointly.
Lower Bounds for Subset Sum in Resolution with Modular Counting
Venue: arXiv cs.CC 2025
Year: 2025

In this paper we prove lower bounds for sizes of refutations of unsatisfiable vector Subset Sum instances $\overrightarrow{a}_1 x_1 + \dots + \overrightarrow{a}_n x_n = \overrightarrow{b}$ in the proof system Res(lin$_{\mathbb{F}_q}$) where $char(\mathbb{F}_{q})\geq 5$. As a basis for the hardness criterion for such instances we choose the property of the matrix $A$ with columns $(\overrightarrow{a}_1, \ldots, \overrightarrow{a}_n)$ to be (the transpose of) the generating matrix for a good error-correcting code $C_{A} := \{x\cdot A\, |\, x \in \mathbb{F}_{q}^k\}\subset \mathbb{F}_{q}^n$ and prove the following lower bounds: 1) For a dag-like fragment of Res(lin$_{\mathbb{F}_q}$). We introduce the notion of $(s,r)$-robustness for Subset Sum instances, which in particular implies that $A$ defines an error-correcting code with the minimal distance $s\geq r$. For $(s,r)$-robust instances we prove $2^{Ω(r)}$ lower bound for sizes of refutations in a dag-like fragment of Res(lin$_{\mathbb{F}_q}$). We show that random instances are $(n / 3, Ω\left((n/(q + 1)\ln q))^{1/3}\right))$-robust and that specific examples achieving these bounds can be constructed using algebraic geometry codes. 2) For tree-like Res(lin$_{\mathbb{F}_q}$) refutations we show the size lower bound $2^{Ω({((q+1)\ln q)^{-1/3}}d^{1/5})}$ for any Subset Sum instance where $d$ is the minimal distance of $C_{A}$.
SOInter: A Novel Deep Energy Based Interpretation Method for Explaining Structured Output Models
Venue: arXiv cs.LG 2025
Year: 2025

We propose a novel interpretation technique to explain the behavior of structured output models, which learn mappings between an input vector to a set of output variables simultaneously. Because of the complex relationship between the computational path of output variables in structured models, a feature can affect the value of output through other ones. We focus on one of the outputs as the target and try to find the most important features utilized by the structured model to decide on the target in each locality of the input space. In this paper, we assume an arbitrary structured output model is available as a black box and argue how considering the correlations between output variables can improve the explanation performance. The goal is to train a function as an interpreter for the target output variable over the input space. We introduce an energy-based training process for the interpreter function, which effectively considers the structural information incorporated into the model to be explained. The effectiveness of the proposed method is confirmed using a variety of simulated and real data sets.
Differential equation and probability inspired graph neural networks for latent variable learning
Venue: arXiv cs.LG 2025
Year: 2025

Probabilistic theory and differential equation are powerful tools for the interpretability and guidance of the design of machine learning models, especially for illuminating the mathematical motivation of learning latent variable from observation. Subspace learning maps high-dimensional features on low-dimensional subspace to capture efficient representation. Graphs are widely applied for modeling latent variable learning problems, and graph neural networks implement deep learning architectures on graphs. Inspired by probabilistic theory and differential equations, this paper conducts notes and proposals about graph neural networks to solve subspace learning problems by variational inference and differential equation.
Automatic Test-Case Reduction in Proof Assistants: A Case Study in Coq
Venue: arXiv cs.SE 2025
Year: 2025

As the adoption of proof assistants increases, there is a need for efficiency in identifying, documenting, and fixing compatibility issues that arise from proof assistant evolution. We present the Coq Bug Minimizer, a tool for reproducing buggy behavior with minimal and standalone files, integrated with coqbot to trigger automatically on Coq reverse CI failures. Our tool eliminates the overhead of having to download, set up, compile, and then explore and understand large developments: enabling Coq developers to easily obtain modular test-case files for fast experimentation. In this paper, we describe insights about how test-case reduction is different in Coq than in traditional compilers. We expect that our insights will generalize to other proof assistants. We evaluate the Coq Bug Minimizer on over 150 CI failures. Our tool succeeds in reducing failures to smaller test cases in roughly 75% of the time. The minimizer produces a fully standalone test case 89% of the time, and it is on average about one-third the size of the original test. The average reduced test case compiles in 1.25 seconds, with 75% taking under half a second.
An Achievable Rate Region for $3-$User Classical-Quantum Broadcast Channels
Venue: arXiv cs.IT 2025
Year: 2025

We consider the scenario of communicating on a $3\mhyphen$user classical-quantum broadcast channel. We undertake an information theoretic study and focus on the problem of characterizing an inner bound to its capacity region. We design a new coding scheme based \textit{partitioned coset codes} - an ensemble of codes possessing algebraic properties. Analyzing its information-theoretic performance, we characterize a new inner bound. We identify examples for which the derived inner bound is strictly larger than that achievable using IID random codes. Proceeding further, we incorporate Sen's technique of tilting smoothing and augmentation to perform simultaneous decoding via a simultaneous decoding POVM and thereby characterize a further enlarged achievable rate region for communicating classical bits over the $3-$user classical-quantum broadcast channel. Finally, in our last step, we characterize a new inner bound to the classical-quantum capacity region of the $3-$user classical-quantum broadcast channel that subsumes all previous known inner bounds by combining the conventional unstructured IID codes with structured coset code strategies.
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Venue: arXiv cs.DS 2025
Year: 2025

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O(m\log^8(n)\log W)$ time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\tilde O((m+n^{1.5})\log W)$ [BLNPSSSW FOCS'20] and $m^{4/3+o(1)}\log W$ [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic $\tilde O(m\sqrt{n}\log W)$ bound from over three decades ago [Gabow and Tarjan SICOMP'89].
Hierarchical Codebook based Multiuser Beam Training for Millimeter Wave Massive MIMO
Venue: arXiv cs.IT 2025
Year: 2025

In this paper, multiuser beam training based on hierarchical codebook for millimeter wave massive multi-input multi-output is investigated, where the base station (BS) simultaneously performs beam training with multiple user equipments (UEs). For the UEs, an alternative minimization method with a closed-form expression (AMCF) is proposed to design the hierarchical codebook under the constant modulus constraint. To speed up the convergence of the AMCF, an initialization method based on Zadoff-Chu sequence is proposed. For the BS, a simultaneous multiuser beam training scheme based on an adaptively designed hierarchical codebook is proposed, where the codewords in the current layer of the codebook are designed according to the beam training results of the previous layer. The codewords at the BS are designed with multiple mainlobes, each covering a spatial region for one or more UEs. Simulation results verify the effectiveness of the proposed hierarchical codebook design schemes and show that the proposed multiuser beam training scheme can approach the performance of the beam sweeping but with significantly reduced beam training overhead.
Distributed Subgraph Finding: Progress and Challenges
Venue: arXiv cs.DS 2025
Year: 2025

This is a survey of the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. It overviews the results and techniques for assorted variants of subgraph finding problems in various models of distributed computing, and states intriguing open questions. This version contains some updates over the ICALP 2021 version, and I will try to keep updating it as additional progress is made.
SimHawNet: A Modified Hawkes Process for Temporal Network Simulation
Venue: arXiv cs.LG 2025
Year: 2025

Temporal networks allow representing connections between objects while incorporating the temporal dimension. While static network models can capture unchanging topological regularities, they often fail to model the effects associated with the causal generative process of the network that occurs in time. Hence, exploiting the temporal aspect of networks has been the focus of many recent studies. In this context, we propose a new framework for generative models of continuous-time temporal networks. We assume that the activation of the edges in a temporal network is driven by a specified temporal point process. This approach allows to directly model the waiting time between events while incorporating time-varying history-based features as covariates in the predictions. Coupled with a thinning algorithm designed for the simulation of point processes, SimHawNet enables simulation of the evolution of temporal networks in continuous time. Finally, we introduce a comprehensive evaluation framework to assess the performance of such an approach, in which we demonstrate that SimHawNet successfully simulates the evolution of networks with very different generative processes and achieves performance comparable to the state of the art, while being significantly faster.