Counts of $k$-cliques are commonly used metrics in subgraph mining. Since graphs often have sensitive data, there also has been a lot of work on $k$-clique counts with differential privacy. However, these metrics have very high global sensitivity, and so more sophisticated techniques have been developed for counting $k$-cliques with privacy. Smooth sensitivity and ladder functions were developed for reducing the noise magnitude for private estim... Read more ›
A convex scene communicates more than shape: the pattern of which groups of objects are mutually apart and which cross is a discrete relational payload. We treat the apartness table of a finite family of convex bodies, a separoid, as a source signal; a renderable convex scene as its encoder; and the rendered image as a noisy visual channel from which the apartness structure is decoded. For disjoint index sets $A,B$, the source bit records whethe... Read more ›
The detection of malicious PyPI packages is crucial for maintaining the security of the open source software supply chain. Existing methods, which primarily rely on rules or traditional machine learning, suffer from poor interpretability and difficulty in adapting to novel attacks. To address this, we propose PYPILINE, a novel detection method that combines a suspicious API knowledge base with an Agent workflow. PYPILINE first conducts static an... Read more ›
A recent line of work motivated by cryptographic applications has studied the complexity of the Lattice Isomorphism Problem (LIP). In this work, we study LIP on self-dual lattices $\cal{L} \subset \mathbb{R}^n$, which appear naturally in many applications. Our main results are a $2^{n/2 + o(n)}$-time randomized algorithm for LIP and a $\mathsf{coNP}$ protocol for LIP on a broad class of self-dual lattices. These results extend recent work on ZLI... Read more ›
Equalization-enhanced phase noise is avoided by applying phase noise compensation (PNC) before chromatic dispersion compensation. Feedforward and iterative PNC algorithms based on expectation propagation are proposed. Both achieve information rates close to channels without phase noise for 100 GBaud 64-QAM and 10,000 km of fiber. Read more ›
When a single software artifact changes - a requirement, a configuration value, or a function - engineers must determine what else is impacted. Existing change-impact-analysis (CIA) tooling tends to rely on one of two signals in isolation: semantic similarity recovered from text (information-retrieval traceability, code search, embeddings), or structural dependency following (call graphs, IDE "find usages", test-impact selection). Each has a cha... Read more ›
In this paper, we study the information-theoretic characterization of simultaneous signalling and control over channels modeled by partially observable Markov decision processes (POMDPs). The problem is formulated as an optimization over randomized control strategies that maximize the directed information from actions to observations, subject to an average-cost constraint. We derive a novel dynamic programming framework in which the state is def... Read more ›
Communication-centric ISAC is a promising paradigm for future 6G networks, in which data payload signals are expected to be reused for sensing to enhance time-frequency resource efficiency. For random payload signals, existing studies have mainly characterized the expected sidelobe level (ESL) of the periodic auto-correlation function (P-ACF). However, ESL only captures the average sidelobe behavior and does not control large spurious sidelobe p... Read more ›
We study a directed version of the three-terminal reachability-preserving minimum edge cut problem. Given a directed graph $G=(V,A)$ with arc costs and terminals $s_1,s_2,t$, the one-way directed RPMEC problem asks for a minimum-cost set of arcs whose deletion preserves the reachability $s_1\leadsto s_2$ while destroying the reachability $s_1\leadsto t$. We first give a path--cut formulation in terms of a rooted directed cut function. Using a ro... Read more ›
The Coupled Model Intercomparison Project Phase 6 (CMIP6) has generated thousands of peer-reviewed publications documenting model configurations, evaluation procedures, emergent constraints, and projection uncertainties. As the community transitions toward CMIP7, efficiently extracting and operationalizing this unstructured knowledge alongside live data analysis represents a critical bottleneck. Here we present CMIP-Forge, a hybrid retrieval-a... Read more ›
We construct division algebras and linear maximum rank distance (MRD) matrix codes using skew polynomials over fields. The non-unital division algebras we obtain generalize several prominent constructions: Sheekey's twisted cyclic pre-semifields, i.e. the pre-semifields associated with Jha-Johnson semifields and the semifields associated with Albert's generalized twisted fields. Our linear MRD codes generalize the constructions of Lobillo, Santo... Read more ›
The prize-collecting stroll is the path version of the prize-collecting TSP. Given a complete metric graph, two prescribed terminal vertices $s,t$, and nonnegative penalties on vertices, the prize-collecting stroll asks for an $s$-$t$ tour minimizing the length of the tour plus the total penalty of vertices that are not visited by the $s,t$ tour. We study a common generalization of the prize-collecting stroll and several related prize-collecting... Read more ›
In this short note, we prove that if $A \in \mathbb C^{N \times M}$ with $N=4M-5$ has i.i.d.\ standard complex Gaussian entries, then the probability that the phase retrieval map generated by $A$ is not injective is positive. This proves Part (1) of a conjecture of Cynthia Vinzant, which was later restated by Afonso S. Bandeira in \cite{BDL+26}. The main result of this paper was obtained using generative AI, in particular the Rethlas system. Read more ›
Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erd\H{o}s-R\'enyi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program,... Read more ›
Faster-than-Nyquist (FTN) signaling is gaining attention as a smart way to pack more data into limited spectrum by intentionally breaking the traditional symbol-spacing rules. This article takes a fresh look at FTN's potential to boost capacity, examining how performance varies across different acceleration factors and signal-to-noise ratio (SNR) definitions. Beyond the theory, we explore what it takes to make FTN work in practice, such as dea... Read more ›
Simulation based solvers for optimal stopping problems must discretize the stopping decision. Under classical dynamic programming, a coarse exercise grid with only a few stopping opportunities can materially undervalue the optimal expected reward, whereas on a very fine grid, approximation errors accumulate through the backward recursion. To remove this limitation, we develop a new reinforcement-learning inspired algorithm that enables us to lea... Read more ›
In joint source-channel coding (JSCC)-based semantic communication systems, achieving stable and reliable image semantic transmission under channel constraints remains a key challenge. In most channel adaptation modules, the signal-to-noise ratio (SNR) is often injected into each layer of a channel-adaptation model in an independent and layer-wise manner, which undermines global coordination across layers. Therefore, consistent noise-robust repr... Read more ›
Many nonsmooth, nonconvex objectives in learning and signal recovery are $\rho$-weakly convex. We minimize such a function in deterministic and stochastic settings when the weak-convexity parameter $\rho$ is unknown. The objective is not required to be globally Lipschitz continuous or smooth. We propose the Adaptive Prox-Guided Scheme (APS), a one-trial proximal algorithm that adapts the proximal parameter online and bidirectionally through a ... Read more ›
In 1998, E. Couselo, S. Gonz\'alez, V. T. Markov, and A. A. Nechaev introduced the notions of recursive codes and recursively differentiable quasigroups. They conjectured that recursive MDS codes of dimension $2$ and length $4$ exist over every finite alphabet of size $q \not\in \{2, 6\}$, and verified this conjecture in all cases except $q \in \{14, 18, 26, 42\}$. In 2008, V. T. Markov, A. A. Nechaev, S. S. Skazhenik, and E. O. Tveritinov r... Read more ›
Cartesian tree matching (CTM) is a structural pattern matching approach that identifies sequences with the same Cartesian tree topology, making it suitable for data with natural variability where exact comparisons carry little semantic meaning. While theoretical algorithms for CTM have been studied extensively, systematic empirical evaluations of practical implementations remain rare. This article presents an implementation of the Cartesian Exte... Read more ›