CS Paper Radar

On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices

Costin Bădică, Amelia Bădică

cs.AI cs.DMmath.CO ·submitted 2026-08-18 15:36 UTC · v1
theory

Abstract

This paper presents new theoretical results on generalizing the Jaccard distance for lattices and real valuations. We demonstrate that when the valuation is strictly positive, monotone, and modular, the Jaccard distance satisfies the triangle inequality on arbitrary lattices, effectively generalizing earlier results that depended heavily on distributivity. Moving to relatively complemented distributive lattices (which safely drop the requirement for the global bounds found in Boolean algebras), we prove the triangle inequality holds as long as the valuation is positive, monotone, supermodular, and $\log$-submodular. Additionally, we adapt the symmetric-difference Jaccard formulation for submodular valuations to sectionally complemented distributive lattices. Shifting to necessary conditions, we prove that supermodularity is a strict requirement for the standard generalized Jaccard distance to operate as a valid metric. Finally, we map the practical value of relaxing these structural constraints to computational fields like quantum information theory, formal concept analysis, and machine learning, closing with a brief look at open mathematical problems.

Closest papers

Nearest neighbours by meaning across the whole index.

Gaussian mass inequalities for lattices

cs.IT math.NT ·2026-11-15 ·Minjia Shi, Xinguang Dai, Patrick Solé
similarity 0.61
Abstract · 50 pages

The Gaussian mass of a lattice is the evaluation of its theta series at a real nome and is relevant to lattice coding for the wiretap Gaussian channel. The ratio of the Gaussian mass of stable lattices to the Gaussian mass of the integer lattice was conjectured to be $\le 1$ (Regev et al., 2024). Kominers proved this bound recently for lattices obtained by Construction~A from binary self-dual codes. Building on Kominers' bound, we establish corresponding inequalities on average for Construction~$A_4$ lattices obtained from free self-dual quaternary codes and for Construction~$A_6$ lattices obtained from self-dual senary codes. We also prove the strict Gaussian-mass inequality for extremal unimodular lattices of both Type~II and Type~I. The Type~I result uses the Rains--Sloane definition of extremality. Its proof combines a universal theta truncation with an exact inversion of the shadow coefficients, and a Gaussian inequality for translated lattices. In addition, we obtain an averaging bound over the genus of Type~II lattices, and extend the binary Construction~A inequality to Siegel theta series of arbitrary genus, with further quaternary results under conditions on the residue code.

0.39

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

cs.IT ·2026-09-30 ·Fengqi Hou
similarity 0.57
Abstract · 15 pages. Lean formalization included as ancillary files

We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.

0.12

Beyond LWE: Post-Quantum Assumptions under a Counterfactual Break of the Dihedral Coset Problem

cs.CR ·2026-10-27 ·Ramses Fernandez
survey similarity 0.57
Abstract

A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below $1/2$, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.

0.37

UTVPI-representable integer point sets: discrete convexity, polymorphisms, and pairwise closure

cs.DM ·2026-08-25 ·Kei Kimura, Kazuhisa Makino, Shota Yamada, Ryo Yoshizumi
theory similarity 0.57
Abstract · 48 pages, v2: acknowledgments updated, references added

We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and two-variable-per-inequality (TVPI) systems. We relate five viewpoints: inequality representation, discrete convexity, polymorphisms, reconstruction from two-coordinate projections, and fixed points of closure operators. Our central result completely characterizes UTVPI-representability. For every set $S\subseteq\mathbb Z^n$ with $n>1$, \[ \begin{aligned} &S\text{ is UTVPI-representable}\\ &\;\Longleftrightarrow\; S\text{ is closed under the directed midpoint and median operations}\\ &\;\Longleftrightarrow\; S\text{ is integrally convex and $2$-decomposable}. \end{aligned} \] The median condition may instead be replaced by closedness under some majority operation, and the same class is the fixed-point class of a pairwise directed-midpoint closure operator. Thus, all five viewpoints yield equivalent characterizations of UTVPI-representability. In particular, $2$-decomposability is exactly the global condition needed to lift the known two-dimensional equivalence between integral convexity and UTVPI-representability to arbitrary dimension. This theorem is embedded in a broader pairwise-closure theory. For a family $F$ of operations, we define a closure operator by closing every two-coordinate projection under $F$ and joining the resulting sets. Its fixed points are precisely the sets that are both $2$-decomposable and $F$-closed, and we establish a local-to-global criterion for such characterizations. A closed-convex-hull analogue characterizes TVPI-representability. We also characterize SVPI-representability by natural multioperations, prove limitations of operation-based characterizations for several related classes, and determine the complete inclusion hierarchies in the general, Boolean, and two-dimensional settings.

0.26

Containment of Conjunctive Queries with Negative Information over Semirings

cs.LO cs.DB ·2026-10-20 ·Guillermo Badia, Carles Noguera, Gaia Petreni, Alice Portone, Val Tannen
similarity 0.56
Abstract

We study the containment problem for (unions of) conjunctive queries ((U)CQs) with negative information on semiring-annotated databases. Our approach to negative information follows the treatment of negation proposed by Grädel and Tannen (2017, 2019, 2021 and 2024) for first-order logic and fixed point logic which applies productively to large classes of semirings, including bounded distributive lattices, as well as the important provenance semirings studied for positive CQ containment by Green (2009). Negation features in (U)CQs along two dimensions: negated equalities (disequations), and negated relational atoms. We study complexity for each of them separately, as well as jointly. For disequations, we extend a methodology that proves the same complexity bounds as the ones already known for the standard Boolean semiring (in the second level of the polynomial hierarchy) for most semirings of interest. Two prominent exceptions are $\mathbb{N}[X]$ and Trio(X) where the complexity bound for containment is in the second level of the counting hierarchy. For CQs with negated relational atoms we show that the complexity, surprisingly, is the same as that of the containment of CQs without negation when one considers model-defining and provenance-tracking interpretations (namely, nondeterministic polynomial time). Interestingly, among bounded distributive lattices, the Boolean two-element case is the only one where the complexity of the problem continues to be hard for the second level of the polynomial hierarchy for model-defining interpretations. Furthermore, we show that the complexity increases again for distributive lattices if we focus on other classes of interpretations. Finally, we consider queries that have both negated equalities and negated relational atoms and show that the complexity of containment continues to be that of the case with just negated equalities.

0.18

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

cs.CC quant-phcs.IT ·2026-09-19 ·Rafail Ostrovsky
theory similarity 0.56
Abstract

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

0.27

The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions

cs.IT ·2026-09-22 ·Hessam Mahdavifar, Ahmad Beirami
benchmarktheoryhighly cited similarity 0.56
Abstract

Let \(X=(X_1,\ldots,X_n)\) be uniform on the Boolean cube, and let \(Y\) be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability \(p\). For a \(k\)-bit quantizer \(Q(X)\), reporting \(k\) input coordinates retains \(k(1-h_2(p))\) bits of information, making coordinate projections a natural quantization benchmark. For \(k=1\), this is the Courtade--Kumar conjecture: every Boolean function \(f\) satisfies \(I(f(X);Y)\leq 1-h_2(p)\), with equality for coordinate functions. We prove the conjecture in every dimension and for every crossover probability, without a balance assumption. The proof tracks the information gap relative to a coordinate as the channel correlation varies. After a monotone rearrangement, an entropy-flow identity relates the derivative of this gap to the edge boundary of the associated Boolean decision set. A sharp local entropy comparison, Fourier analysis, and logarithmic Sobolev estimates for pivotal sets imply that any positive gap must grow as the noise decreases, contradicting its nonpositive value at the noiseless endpoint. For \(k\geq8\), a coding-theoretic phenomenon emerges. We construct a shortened-Hamming-code quantizer that beats the coordinate benchmark for \(k=8\), and a direct-sum argument extends the failure to every \(k\geq8\). Thus structured coding can retain more information than coordinate selection. Exhaustive searches within several structured code families and Monte Carlo searches over random codebooks for \(2\leq k\leq7\) find that structured codebooks outperform random ones but remain below the coordinate benchmark. This motivates our conjecture that coordinate projections are optimal for \(2\leq k\leq7\).

0.48

On the Complexity of Locally Dense Lattices

cs.CC ·2026-08-15 ·Shuichi Hirahara, Kazuki Ogitsuka
published similarity 0.55
Abstract · Full version of MFCS 2026

\emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a lattice $\mathcal{L}$ that contains exponentially many lattice vectors inside some $\ell_p$ ball centered at $\vec{s}$ with radius at most an $α< 1$ fraction of the length of its shortest nonzero lattice vector. In this paper, taking a ``meta'' viewpoint on locally dense lattices, we introduce the \emph{Locally Dense Lattice Problem} (LDLP), the decision problem of determining whether a given input specifies a locally dense lattice. Our main result is that LDLP in $\ell_p$ norms for all finite $p \geq \log_2 3$ and for the infinity norm is complete for the second level of the polynomial hierarchy. We also compare two standard definitions of local density that appear in prior work. Micciancio's original definition (FOCS 1998 and SICOMP 2001) uses integer coefficient vectors, while later work by Micciancio (ToC 2012) and by Bennett and Peikert (RANDOM 2023) uses short vectors in a shifted coset. We show that the corresponding promise problems are mutually reducible in deterministic polynomial time, which shows that the two formulations are robust.

0.52