CS Paper Radar

Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete

Qiuyu Chen, Baao Xie

cs.CC ·submitted 2026-10-30 17:25 UTC · v2
theory

Abstract

An important question in counting complexity is whether exact counting can remain hard under restrictions that make feasibility easy. Tilings of squares by a fixed family of polyominoes provide a stringent test of this question, since tileability is polynomial-time decidable and the only varying input is a binary-encoded side length. We prove that there exists a fixed finite family of connected polyominoes for which counting translation-only square tilings is #EXP-complete under polynomial-time metric reductions, while the counting function belongs to #E. The resulting separation reveals that solution multiplicities can retain computational information that feasibility alone cannot capture. The proof develops a two-stage numerical isolation technique that combines a boundary-amplified Wang system with a rigid geometric compiler to recover accepting-computation counts while controlling all noncanonical tilings.

Closest papers

Nearest neighbours by meaning across the whole index.

Tiling 3D by Translates of a Single Polycube is Undecidable

cs.CG math.COmath.MG ·2026-10-08 ·Erik D. Demaine, Stefan Langerman
theory similarity 0.72
Abstract · 7 pages, 1 figure, 1 table

We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. We reduce from Wang tiling using the decorated two-prime Sudoku construction of Greenfeld and Tao and a cyclic encoding adapted from OpenAI's 3D aperiodic tile, and apply a reduction of Kim to make the prototile connected (via faces). Dimension three is optimal: translational monotiling is known to be decidable in $\mathbb{Z}^2$ and for a single (possibly disconnected) polyomino in $\mathbb{R}^2$.

0.43

Perfect Rectangular Tilings with Two Colors

cs.CG cs.DM ·2026-09-22 ·Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer +3 more
published similarity 0.66
Abstract · Full version of a paper with the same title to appear at ISAAC 2026

We study a finite tiling problem, where tiles are unit squares whose four edges are colored with one of two colors. We ask whether a given rectangle admits a perfect rectangular tiling: every cell of the rectangle is occupied by one tile, neighboring edge colors match, and exactly $n_i$ tiles of type $i$ are used, where rotations of the tiles are allowed. Our problem is related to classical Wang tilings, more general finite tile-placement problems, and edge placement puzzles. But in our problem, the multiplicities of the tile types are part of the input and the tile alphabet is fixed and extremely small; thus the complexity of the problem arises from the interaction between the rectangle dimensions and the prescribed tile multiplicities. We provide a comprehensive study of the perfect rectangular tiling problem. For this we consider all classes of subsets of the six possible tile types for two-colored edges, and we characterize for each class whether multiplicities either always allow a perfect rectangular tiling or whether their existence can be decided efficiently.

0.46

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.63
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27

Large-Scale Autonomous Discovery of Kissing Number Constructions

cs.IT ·2026-09-28 ·Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Fujia Chen +11 more
code/data similarity 0.62
Abstract · 49 pages, 13 tables. Construction data and verification programs: https://github.com/Oxelra-AI/Qiushi-Engine-Kissing-Number-Research

The kissing-number problem is a classical problem in discrete geometry whose exact solution is known in only a few dimensions. Recent artificial-intelligence approaches have begun to discover improved configurations through large-scale numerical and combinatorial search, but converting such searches into general mathematical constructions and rigorous proofs remains challenging. Here we use Qiushi Engine, an autonomous multi-agent research system, to investigate kissing numbers and obtain new lower bounds in nineteen dimensions: $25$, $27$, $32$--$39$, $43$, $45$, and $49$--$55$. The resulting constructions arise from distinct structural mechanisms, including coordinated motions of contact layers, labelled direction reuse, joint support exchanges, signed-code replacements, cross-shell lattice constructions, low-overlap lattice isometries, and spherical-design moment certificates. They yield sharp capacities for parameterized signed-code models, deterministic image-union guarantees, and exact section and projection counts controlled by embedded root systems and anchor-graph statistics. These methods yield, among others, $K(25)\ge197580$, $K(27)\ge201567$, $K(38)\ge591900$, $K(43)\ge2553792$, $K(45)\ge7380090$, and $K(55)\ge53301140$. The autonomous system carried out the construction searches, mathematical analysis and computational verification, while each final result was reduced to explicit mathematical arguments and independently checkable finite certificates. Our results illustrate how autonomous research systems can move beyond optimization within fixed formulations to discover new mathematical representations and constructions at scale.

0.69

Interlocking Tiling of 3D Finite Domains

cs.GR ·2026-11-16 ·Xuyang Ma, Rulin Chen, Chaewoon Kim, Ying He, Peng Song
similarity 0.61
Abstract

A K-hedral tiling of a 3D finite domain is a covering of the domain with tiles without gaps or overlaps, where each tile is congruent to one of the K distinct shapes called prototiles. To use 3D K-hedral tilings in practice, they need to satisfy two requirements. First, K should be small to reduce the fabrication cost (e.g., through reusable molds) and simplify the (dis)assembly process. Second, a K-hedral tiling result should be structurally stable, in particular via interlocking, where all the tiles are immobilized by their geometric arrangement, except the key. Since these two requirements are often in conflict, existing approaches always trade one for the other. In this work, we formulate a new tiling problem called interlocking tiling, aiming to generate 3D K-hedral tilings that satisfy the above two requirements simultaneously. Given a 3D finite domain represented as a voxel grid, our goal is to compute a small prototile set whose instances exactly tile the input domain while ensuring that the tiling result forms an interlocking assembly. To solve this challenging problem, we propose a twolevel computational approach that hierarchically decomposes the input domain into interlocking parts (domain-level partitioning) and further partitions each part into interlocking tiles (part-level partitioning). To guide the part-level partitioning, we propose a new graph representation with regular structures to facilitate the generation of tiles with identical shapes while ensuring that they are interlocking. Our approach allows generating interlocking tilings that exactly cover 3D finite domains with diverse shapes while achieving high prototile reuse. We compared our approach with state-of-the-art methods to demonstrate its superiority, and validated the practicality of our interlocking tiling results via fabricating two of them.

0.21

Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration

cs.LO math.COmath.OC ·2026-10-08 ·Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub
similarity 0.60
Abstract · 20 pages, 3 figures, 2 tables

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

0.28

Computing the minimal perimeter polygon for digital objects in the triangular tiling

cs.CG ·2026-09-12 ·Petra Wiederhold
published similarity 0.59
Abstract · Preprint from November 11, 2024

This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.

0.58

Quantitative Tiling Stability From Quadratic Discrepancy In Hamming Spaces

cs.IT math.CO ·2026-08-26 ·Valery, Grishin, Aryeh Lev Zabokritskiy
theory similarity 0.59
Abstract · 39 pages; no figures. Revised exposition and reference locators. Exact-arithmetic verification companion: https://doi.org/10.5281/zenodo.221…

Quadratic ball discrepancy measures how uniformly a code meets Hamming balls over all centers and radii. Perfect codes minimize this quantity among codes of the same cardinality. We prove a quantitative refinement: at the parameters of every perfect code other than a one-word code or the full space, the discrepancy excess over the minimum is at least an explicit positive multiple of the discrepancy at the packing radius. The latter equals the tiling defect divided by the square of the code cardinality. This defect is the total squared deviation of the covering multiplicity from one. The comparison applies to all codes of that cardinality. For one-error perfect codes, the coefficient is at least one, and no larger constant holds for all such codes; explicit coefficients depending on the parameters can be much larger. The tiling defect also measures the failure of uniform ball noise to smooth a code distribution. Consequently, the same discrepancy excess gives explicit bounds on holes, overlaps, and divergence from the uniform distribution.

0.52