跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+758新增论文
+578其中 AI 相关
+94已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-17 04:58 · 全站最近入库:2026-11-17 04:58各信源进度 →

统计口径与数据新鲜度

统计 2026-11-16 06:22 — 2026-11-17 06:22(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 04:58库内论文最新更新时间:2026-11-14 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

24,106 已收录论文20,158 AI 相关7,049 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 214 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
新论文 · v1arXiv:2610.40281

加权 k-路径顶点覆盖的分层与反向扩展算法

Layering and reverse extension for weighted $k$-path vertex cover

Jiajing Wu, An Zhang, Shiming Li, Guohui Lin

AI 速读 基于摘要

作者在分层与反向扩展局部比值框架下设计局部权重函数,为加权 k-路径顶点覆盖问题给出新的近似比。

cs.DS · cs.DM

查看原文摘要

We study the weighted $k$-path vertex cover problem for any fixed integer $k \ge 2$, in which a vertex non-negatively weighted simple graph $G = (V, E)$ is given and one wants to find a minimum-weight vertex subset $C \subseteq V$ such that every simple path on $k$ vertices in $G$ contains at least one vertex of $C$. The problem generalizes the classic weighted vertex cover problem, that is, $k = 2$, and it admits a $k$-approximation algorithm of Hochbaum~[SIAM J. Comput., 1982] and a $(k - \frac 12)$-approximation algorithm of Brüstle et al.~[IWOCA 2021]. In this paper, we carefully design local weight functions in the Layering and Reverse Extension local ratio framework of Bar-Yehuda et al.~[ACM Comput. Surv., 2004], leading to an approximation algorithm of ratio $\frac {3k-1}4$ for odd $k \ge 3$ and of ratio $\frac {3k}4$ for even $k \ge 4$. When $k = 3$ and $k = 4$, these ratios are $2$ and $3$, respectively, matching the state-of-the-art approximation ratios for the corresponding special cases.

版本更新 · v4arXiv:2510.25606

Fractional Iterates and Oscillatory Convergence

Steven Finch

原文摘要

The simple continued fractions for the Golden & Silver means are well-known. It is astonishing that, as far as we know, no one has published half-iterates (let alone quarter-iterates) for the corresponding algorithms. We also examine the cosine and logistic maps (with parameter $2 < λ< 3$).

math.NT · cs.DM

新论文 · v1arXiv:2610.39870

Optimal self-orthogonal binary linear codes

Sascha Kurz

原文摘要

We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.

math.CO · cs.DM · cs.IT

版本更新 · v4arXiv:2504.18489

Tight Lower Bound for Multicolor Discrepancy

Pasin Manurangsi, Raghu Meka

原文摘要

We prove the following asymptotically tight lower bound for $k$-color discrepancy: For any $k \geq 2$, there exists a hypergraph with $n$ hyperedges such that its $k$-color discrepancy is at least $Ω(\sqrt{n})$. This improves on the previously known lower bound of $Ω(\sqrt{n/\log k})$ due to Caragiannis et al. (arXiv:2502.10516). As an application, we show that our result implies improved lower bounds for group fair division.

cs.DM · cs.GT

新论文 · v1arXiv:2610.39760

EPPA for Reducts of the Random Graph

Sofia Brenner, Jan Hubička, Matěj Konečný

原文摘要

We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.

math.CO · cs.DM · math.LO

新论文 · v1arXiv:2610.39753

Four-Coloring Planar Graphs in Linear Time

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup

原文摘要

The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.

cs.DS · cs.CG · cs.DM · math.CO

新论文 · v1arXiv:2610.39653

On edge-ordered Ramsey numbers of hypergraphs

Martin Balko, Jelena Glišić

原文摘要

For an integer $h\geq2$, an edge-ordered $h$-uniform hypergraph $H^<$ is an $h$-uniform hypergraph with a linear ordering of its hyperedges. For an integer $q \geq 1$, the edge-ordered Ramsey number $R_{\mathrm{edge}}(H^<;q)$ of $H^<$ is the smallest positive integer $N$ such that there exists an edge-ordered $h$-uniform hypergraph $G^<$ on $N$ vertices such that, for every $q$-coloring of the hyperedges of $G^<$, there is a monochromatic copy of $H^<$ in $G^<$ preserving the hyperedge order. In this note, we show that, for every edge-ordered $h$-uniform hypergraph $F^<$ on $n$ vertices with $m\geq1$ hyperedges, $R_{\mathrm{edge}}(F^<;q) \leq R_h(F;q)^{Cm^2}$ where $F$ is the underlying unordered hypergraph, $R_h(F;q)$ is its standard $q$-color Ramsey number, and $C=C(h,q)>0$ is a constant. For fixed $h\geq3$ and $q\geq2$, this shows that prescribing the hyperedge order does not require an increase in the tower height of the classical upper bound. It also settles a problem posed by Fox and Li (2020), and for $h=2$ gives the bound $2^{O(n^4\log n)}$, improving their bounds for every fixed $q \geq 3$.

math.CO · cs.DM

新论文 · v1arXiv:2610.39535

Local Convergence of Triadic Closures of Sparse Random Graphs

Himasish Talukdar

原文摘要

Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph $H$, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on $H$, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of $H$. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of $\left( H_n \right)_{n \in \mathbb{N}}$ converges locally in probability to a rooted graph $H^*$, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of $H^*$. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.

math.PR · cs.DM · math-ph · math.CO

新论文 · v1arXiv:2610.39485

Strongly explicit Ramanujan 2-lift towers via Hilbert modular forms

Olga Kharlampovich, Igor Pak, Alina Vdovina

原文摘要

Expander graphs have been central objects of study for over fifty years. Ramanujan graphs attain the asymptotically optimal nontrivial adjacency-eigenvalue threshold for infinite fixed-degree families. The original arithmetic constructions by Lubotzky-Phillips-Sarnak (1988) and Margulis (1988), and the iterative $2$-lift method of Bilu-Linial (2006) provide different approaches to Ramanujan graph constructions. Motivated by work on Mealy automata, we combine both approaches to give the following new arithmetic construction. For every prime $p\equiv 1\pmod {17}$, we construct a infinite tower of $(p+1)$-regular non-bipartite Ramanujan graphs on $2^n$ vertices, with label-preserving $2$-lifts between consecutive levels. These construction is strongly explicit: for fixed $p$, a neighbor or lift sign is computable in $O_p(n^3)$ bit operations. The construction uses fixed algebraic $2$-adic transformations, specified by finite data computable in preprocessing depending only on $p$. The main number-theoretic tool is Blasius's Ramanujan-Petersson theorem for Hilbert modular forms, applied through the Jacquet-Langlands correspondence to obtain the sharp bound $|λ|\leq2\sqrt p$ for every nontrivial adjacency eigenvalue of our $(p+1)$-regular graphs. The transformations preserve $2$-adic distance, which gives the binary covers and an explicit formula for their signings.

math.CO · cs.DM · math.NT

新论文 · v1arXiv:2610.39430

Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number

Siddhesh Chaubal

原文摘要

A set $S$ of vertices of a graph $G$ is a mutual-visibility set if every pair of vertices of $S$ is joined by a shortest path whose internal vertices avoid $S$, and the mutual-visibility chromatic number $χ_μ(G)$ is the least number of mutual-visibility sets into which $V(G)$ can be partitioned. Klavžar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that $χ_μ(G)\leχ(G)$ whenever $G$ has diameter two, observed that equality holds for complete bipartite graphs, and asked whether there are any other diameter-two graphs attaining equality. We answer this question in the affirmative. We construct a graph $G_{11}$ of order 11 and diameter two with $χ_μ(G_{11})=χ(G_{11})=3$, and an infinite family of such graphs obtained from $G_{11}$ by replacing one vertex with pairwise non-adjacent copies of it.

math.CO · cs.DM

版本更新 · v3arXiv:2610.32192

Identifying codes of Archimedean grids

Rudini Sampaio

原文摘要

An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap C$ are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be $1/4$ for the triangular grid and $7/20$ for the square grid, whereas for the hexagonal grid the problem is still open, between $5/12$ and $53/126$. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is $2/3$ for the truncated hexagonal grid, $3/7$ for the truncated square grid, and $1/3$ for the trihexagonal (kagome) grid, the elongated triangular grid and the snub hexagonal grid. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between $3/7$ and $13/30$ for the truncated trihexagonal grid, between $1/3$ and $11/30$ for the rhombitrihexagonal grid, and between $2/7$ and $9/28$ for the snub square grid. As a by-product, we prove that every identifying code of a cubic graph with the slow growth property in which every vertex lies on exactly one triangle (resp. $4$-cycle) has density at least $2/3$ (resp. $3/7$).

math.CO · cs.DM

版本更新 · v2arXiv:2609.30888

Breaking the Infinite Barrier in the $\frac{1}{3}$--$\frac{2}{3}$ Conjecture

Max Aires, Swee Hong Chan, Igor Pak, Greta Panova

原文摘要

The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an $\varepsilon$-improvement for the balance constant over the bound by Brightwell, Felsner and Trotter (1995), for some small $\varepsilon>0$. This is the first general result towards the $\frac{1}{3}$--$\frac{2}{3}$ conjecture in over 30 years.

math.CO · cs.DM

新论文 · v1arXiv:2610.38664

Upper Bounds for CSP Non-redundancy via Locally Decodable Codes

Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie, Maya Sankar, Hung-Hsun Hans Yu

原文摘要

In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form $n^{k\pm o(1)}$ for some positive integer $k$.

cs.DM · cs.CC · cs.IT · math.CO

新论文 · v1arXiv:2610.38396

Destroying Rigidity in the Plane

Yu Cong, Chao Xu, Yajie Zhao

原文摘要

Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jordán and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.

cs.DM

版本更新 · v5arXiv:2512.09170

Magic Gems: Convex Hulls of Lifted Magic Squares

Kyle Elliott Mathewson

原文摘要

Given an arrangement of $\{1,\dots,n^2\}$ in an $n\times n$ grid, we lift each cell to $\mathbb{R}^3$ by centring its grid coordinates $(x,y)$ at the origin and taking its centred entry $z = s_{ij} - (n^2+1)/2$ as a vertical height. The convex hull of these $n^2$ points is the gem of the arrangement, whose lower and upper boundaries are the regular subdivisions of the grid induced by $\pm z$. While random arrangements and generic linear magic squares have gems whose vertex counts grow with $n$, our main theorem shows that the classical Siamese (de la Loubère) magic square of every odd order $n\ge5$ has $f$-vector $(12,26,16)$, isometry group $\{\pm\mathrm{id}\}$, and only the twelve vertices forced by the boundary of the grid. The proof shears the lift onto five horizontal terraces and reduces the hull calculation to a finite table of polynomials in $m=(n-1)/2$; the same method gives $f$-vector $(12,24,14)$ for the base-$n$ digit-exchanged square. Along any family of linear squares with fixed steps the $f$-vector is eventually periodic in $n$, whereas over all linear magic squares of prime order $n$ the maximum vertex count grows as $Θ(\ln n)$. Whenever the heights have vanishing first moments, a short principal-axes argument shows that the point set has a non-trivial isometry if and only if the arrangement is self-complementary up to dihedral symmetry. An exact census of the $880$ magic squares of order four yields $616$ congruence classes and $352$ combinatorial types of gems, and shows that while vertex and facet counts are nearly insensitive to the magic line-sum conditions, the volume and solid centroid shift systematically.

math.CO · cs.CG · cs.DM · math.MG

新论文 · v1arXiv:2610.38287

A Characterization of Functions on the Integer Lattice That Are L-Extendable through Local Convex Extensions

Ken Yokoyama, Yuni Iwamasa, Kei Kimura

原文摘要

L-extendable functions on the integer lattice are functions that admit a $\frac12$UJ-convex relaxation; that is, values can be assigned to the additional half-integral points, while keeping the original values at integer points, so that the resulting function is $\frac12$UJ-convex. Various examples of L-extendable functions and their applications are known. A general characterization of L-extendability for functions on the integer lattice, however, remains open. In this paper, we study the L-extendability of functions on the integer lattice. We first obtain a necessary condition: L-extendable functions are integrally convex. We then consider a special subclass of L-extendable functions, namely, those whose local convex extensions give L-convex relaxations. This subclass has a useful optimization property: the optimal value of the original function coincides with that of the $\frac12$UJ-convex relaxation given by its local convex extension, a property not guaranteed for general $\frac12$UJ-convex relaxations. We characterize this subclass by showing that a function is L-extendable through its local convex extension if and only if it is integrally convex and its restriction to every unit hypercube is D-convex, where D-convexity is a discrete convexity associated with reflected Freudenthal simplicial divisions. This subclass strictly contains the class of D-convex functions. We also give a combinatorial characterization of D-convex subsets of the vertices of a unit hypercube: a set $X\subseteq\{0,1\}^n$ is D-convex if and only if it is majority-closed and contains a relative opposite pair.

math.CO · cs.DM

版本更新 · v2arXiv:2609.06570

The list size of random linear and LDPC codes at capacity

Shashwat Silas

原文摘要

We show that for every prime power $q$ and $ρ\in(0,1-\frac1q)$ there exists $\varepsilon_0(q, ρ) > 0$ such that for all positive $\varepsilon < \varepsilon_0(q, ρ)$, a random linear code over $\mathbb{F}_q$ of rate $1-h_q(ρ)-\varepsilon$ has list size $\lfloor h_q(ρ)/\varepsilon\rfloor$ or $\lfloor h_q(ρ)/\varepsilon\rfloor+1$ with probability $1-o(1)$. Before this work, the list size was known only up to a constant factor for $q\ge3$, and for $q=2$ it was known to be either $\lfloor h_2(ρ)/\varepsilon\rfloor-1$, $\lfloor h_2(ρ)/\varepsilon\rfloor$ or $\lfloor h_2(ρ)/\varepsilon\rfloor+1$. We also show that the same two-point concentration holds for the list size of random LDPC codes. This follows from a general theorem establishing that random LDPC codes and random linear codes have the same threshold rate for distance, list decoding, list recovery from errors and any other \emph{convex} property, which answers a question of Mosheiff, Resch, Ron-Zewi, Silas and Wootters.

cs.IT · cs.DM · math.CO

版本更新 · v3arXiv:2507.16648

An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming

Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis

原文摘要

We prove that, for every fixed $ε\in(0,1]$, the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\vec c^{\top}\vec x$ subject to linear constraints, regardless of the pivot rule used. Our lower bound therefore holds for objectives arbitrarily close to the linear case $ε=0$, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough. The special case $ε=1$ yields a lower bound in convex quadratic maximization. This improves on the best previously known lower bound [IPCO 2025] requiring polynomial objectives of degree $ω(\log d)$ in dimension $d$ and firmly resolves the open question of whether a constant degree suffices. Our result is based on a novel extended formulation, recursively constructed using deformed products. Its key feature is that it projects onto a polygonal approximation of a parabola while preserving all of its exponentially many vertices. We define a convex objective with a single non-linear variable that forces the active-set method to follow the parabolic boundary of this projection, without allowing any shortcuts along chords corresponding to edges of its full-dimensional preimage.

cs.DM · cs.CC · cs.DS · math.CO

版本更新 · v2arXiv:1909.12353

Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm

Gabriel Istrate, Cosmin Bonchis, Mircea Marin

原文摘要

We analyze the expected running time of WalkSAT, a well-known local search procedure for satisfiability solving, on satisfiable instances of the k-XOR SAT problem. We obtain estimates of this expected running time by reducing the problem to a setting amenable to classical techniques from drift analysis. A crucial ingredient of this reduction is the definition of (new, explosive) hypergraph versions of interacting particle systems, notably of coalescing and annihilating random walks as well as the voter model. The use of these tools allows to show that the expected running time of WalkSAT depends on structural parameter (we call odd Cheeger drift) of the dual of the formula hypergraph.

cs.DS · cs.DM · math.CO · math.PR

版本更新 · v2arXiv:2506.12774

On the Vertices of Delta-modular Polyhedra

Bludov Mikhail, Gribanov Dmitry, Klimenko Maxim, Kupavskii Andrey, Lángi Zsolt, Rogozin Alexander, Voronov Vsevolod

原文摘要

Let $P$ be a polytope defined by the system $A x \leq b$, where $A \in R^{m \times n}$, $b \in R^m$, and $\text{rank}(A) = n$. We give a short geometric proof of the following tight upper bound on the number of vertices of $P$: $$ n! \cdot \fracΔ{Δ_{\text{average}}} \cdot \text{vol}(B_2) \sim \frac{1}{\sqrt{πn}} \cdot \left(\frac{2 π}{e}\right)^{n/2} \cdot n^{n/2} \cdot \fracΔ{Δ_{\text{average}}}, $$ where $Δ$ is the maximum absolute value of $n \times n$ subdeterminants of $A$, and $Δ_{\text{average}}$ is the average absolute value of subdeterminants of $A$ corresponding to a triangulation of $P$'s normal fan. Assuming that $A$ is integer, such polyhedra are called $Δ$-modular polyhedra. Note that in the integer case, the bound can be simplified via the inequality $Δ_{\text{average}} \geq Δ_{\min} \geq 1$, where $Δ_{\min}$ is the minimum absolute value of subdeterminants of $A$ corresponding to feasible bases of $A x \leq b$. For this, we prove and use a symmetric variant of Macbeath's theorem. Additionally, we give a direct argument based on prior results in the field, showing that the graph diameter of $P$ is bounded by $O\bigl(n^3 \cdot \fracΔ{Δ_{\min}} \cdot \ln (n \fracΔ{Δ_{\min}}) \bigr)$. Thus, both characteristic of $P$ are linear in $Δ/Δ_{\min}$. From an algorithmic perspective, we demonstrate that: Given $A \in Q^{m \times n}$, $b \in Q^m$, and an initial feasible solution to $A x \leq b$, the convex hull of $P$ can be constructed in $O(n)^{n/2} \cdot m^2 \cdot \fracΔ{Δ_{\text{average}}}$ operations. For simple polyhedra, the dependence on $m$ reduces to linear; Given $A \in Z^{m \times n}$ and $b \in Q^m$, the number $|P \cap Z^n|$ can be computed in $O(n)^n \cdot \frac{Δ^4}{Δ_{\text{average}}}$ arithmetic operations.

math.CO · cs.CG · cs.DM

新论文 · v1arXiv:2610.37721

Local-to-Global Theorems Based on Cones with Applications to Graph Coloring

Anqi Li, Shayan Oveis Gharan

原文摘要

Local-to-Global theorems are a cornerstone of many of recent developments in theoretical computer science from coding theory and PCPs all the way to analyzing mixing time of Markov chains. Building on trickledown theorems on simplicial complexes, several techniques have been established to obtain tighter local-to-global theorems to analyze the spectral gap of the Glauber dynamics, namely matrix trickledown, ${\mathcal C}$-Lorentzian polynomials and more recently Bochner type inequalities. In this paper, we adopt non-local local-to-global/Bochner type inequalities on "cones", corresponding to the local neighborhood of a given vertex, to show that the Glauber dynamics mixes in polynomial time to sample proper colorings of maximum degree $Δ$ graphs as long as $q\geq 1.7408Δ$.

math.PR · cs.DM · cs.DS · math.CO

版本更新 · v2arXiv:2610.34378

Logarithmic asymptotics for polynomial threshold functions

Martin Anthony

原文摘要

We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.

cs.DM · cs.IT · math.CO

版本更新 · v2arXiv:2210.11132

A Search-Based Algorithm for Multistage Robust Discrete Linear Optimization and its Implementation

Michael Hartisch, Ulf Lorenz

原文摘要

Robust optimization models that allow decisions to adapt to newly revealed information remain computationally challenging and are often limited to two decision stages or are addressed heuristically or via approximation schemes. This challenge is further amplified when uncertainty sets depend on earlier decisions. Conventional approaches to such problems often require problem-specific reformulations and tailored algorithms, highlighting the need for an exact model-and-run approach. We address this gap by presenting an algorithmic framework for solving multistage robust discrete linear optimization problems. This exact approach adapts and integrates ideas from game-tree search, quantified conflict-driven clause learning, and integer linear programming to explore the minimax tree and is implemented in the open-source solver Yasol. The solver supports discrete decision variables across multiple stages, discrete uncertainty sets with polyhedral or decision-dependent structure, and mixed-integer recourse in the final stage. It can be used as a standalone executable or through a C++ library interface, allowing it to serve as a reference solver for exact methods in multistage robust discrete linear optimization. In an extensive computational study, we demonstrate the capabilities of our solver. The results show competitive performance against a reference approach from the literature for a protection-interdiction problem, as well as strong performance on bilevel benchmark instances. For a multistage cutting-stock problem, we demonstrate the substantial loss in solution quality that can arise from neglecting the multistage structure and show that our solver significantly outperforms decision-rule approximations in terms of computational efficiency while certifying the true multistage optimum.

math.OC · cs.DM · cs.DS

版本更新 · v4arXiv:2411.07030

Polynomial and Hyperplane Avoidance over the Integers with Applications to Integer-Point Counting

Grigorii Dakhno, Dmitry Gribanov, Nikita Kasianov, Anastasiia Kats, Andrey Kupavskii, Nikita Kuz'min, Stanislav Moiseev

原文摘要

We study the \emph{Polynomial Avoidance Problem}: given a finite collection $F \subseteq Z[x_1,\dots,x_n]$ of nonzero polynomials, find a vector $x \in Z^n$ of minimum $\ell_p$-norm such that $f(x)\neq0$ for every $f \in F$. Each polynomial is given sparsely as a list of its nonzero terms. The affine special case is the \emph{Hyperplane Avoidance Problem}. This special case arises in Barvinok-type algorithms for counting integer points in polyhedra, when certain rational generating functions must be evaluated at a removable singularity. Our main results are as follows: 1) Let $D:=\sum_{f\in F} \text{deg} f$. Every instance admits a feasible vector $x$ satisfying \[ \|x\|_1 \leq \min\left\{D,\frac{D+n}{2}\right\}. \] This bound is tight. Such a vector can be found by a deterministic algorithm whose bit complexity is polynomial in $D$ and the sparse encoding length of the input. Our proof uses a new algorithmic variant of the \emph{Combinatorial Nullstellensatz}; 2) In the affine case, with $m$ input polynomials, such a vector can be constructed by a fast deterministic polynomial-time algorithm using $O(nm)$ arithmetic operations. For the homogeneous case, Barvinok's original approach provides only the weaker guarantee $\|x\|_1 = O((nm)^{n-1})$; 3) The problem is NP-hard for every $p\in R_{\geq 1}\cup\{\infty\}$, even for homogeneous linear forms; 4) As an application, we improve the complexity bound for counting integer points in general rational polytopes. We also improve the bound for polyhedra of bounded codimension; this includes the counting version of the \emph{Unbounded Subset-Sum} problem as a special case.

cs.CC · cs.CG · cs.DM · cs.DS · math.CO

新论文 · v1arXiv:2610.36630

Uniformity Testing for the Monomer-Dimer Model

Joy Qiping Yang, Yuichi Yoshida

原文摘要

We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $Δ$, uniformity can be tested with $\widetilde O_Δ(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $Θ(n)$ vertices and $Θ(m)$ edges on which every tester requires $Ω(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=Θ(n)$, testing uniformity over the space of matchings has $\widetilde Θ(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $Θ(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.

cs.DS · cs.DM

版本更新 · v4arXiv:2609.30302

Hull Games of Induced Path Convexities in Graphs

Eurinardo Costa, Leon Almeida, Rudini Sampaio

原文摘要

In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic $\mathrm{m}$-convexity and the $\ell_k$-convexities, based on induced paths and on induced paths of size at most $k$. We prove that the hull games $\mathrm{CHG}_{\mathrm{m}}$, $\mathrm{CHG}_{\ell_k}$ and their misère variants are PSPACE-complete for every $k\ge2$ even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games $\mathrm{CHG}_{\mathrm{m}}$ and $\mathrm{CHG}_{\ell_k}$ for any $k\ge2$ in disjoint unions of paths and cycles. For $k\ge3$ odd, we prove that Alice (1st player) wins $\mathrm{CHG}_{\ell_k}$ in the path $P_n$ if and only if $n$ is odd and she wins in the cycle $C_n$ if and only if $n=3$ or $n=α\cdot (k+1)-1$ with $α\ge2$. For $k\ge2$ even, the only periodic nimber sequences of $\mathrm{CHG}_{\ell_k}$ obtained through extensive computational testing occurred for $k=2^h-4$ with $h\ge3$, e.g, $k\in\{4,12,28,60,\ldots\}$. In this case ($k=2^h-4$ with $h\ge3$), we prove that the nimber sequences of $\mathrm{CHG}_{\ell_k}$ in $P_n$ and in $C_n$ are periodic and Alice loses (resp. wins) in $P_n$ (resp. $C_n$) with $n>k$ only when $n=3k+4$ (resp. $n\in\{2k+1,5k+3\}$). Finally, we show that, for $k=2$, the game $\mathrm{CHG}_{\ell_2}$ in paths $P_n$ is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of $n$ up to $150$ million.

cs.DM · math.CO

版本更新 · v2arXiv:2610.31489

An Improved Bound for Testing $k$-Colorability

Bangjie Xu

原文摘要

We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\varepsilon$-far from being $k$-colorable if at least $\varepsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that a uniformly random induced subgraph on $O(k\log k/\varepsilon)$ vertices is non-$k$-colorable with probability at least $2/3$ whenever the original graph is $\varepsilon$-far from $k$-colorable. The proof combines a palette-based coloring process with a container-style encoding-and-reconstruction argument. This yields $O(k\log k/\varepsilon)$, which is no worse than the previous state of the art $O(k\log (1/\varepsilon)/\varepsilon)$ throughout the nonvacuous parameter range, and is an improvement when $\log k=o(\log(1/\varepsilon))$. For each fixed $k$, combining this upper bound with the known $Ω(\log k/\varepsilon)$ lower bound gives $Θ(1/\varepsilon)$ dependence on $\varepsilon$.

cs.DM

版本更新 · v2arXiv:2605.04325

On the Architectural Complexity of Neural Networks

Nicholas J. Cooper, François G. Meyer, Michael L. Roberts, Carlos Zapata-Carratalá, Lijun Chen, Danna Gurari

原文摘要

We introduce a unified theoretical framework for the rigorous analysis and systematic construction of deep neural networks (DNNs). This framework addresses a gap in existing theory by explicitly modeling the structure of tensor operations -- lower level information that is often abstracted. Our framework enables two novel objectives: (1) analysis of the evolution of architectural complexity over deep learning history, and (2) automatic construction of novel architectures based on new types of tensor operations. Our study of DNNs introduced over the past 40 years reveals a connection between groundbreaking architectures and increases in different types of architectural complexity. Moreover, we identify several large classes of higher complexity architectures that have not yet been explored. We then collect a dataset of 3,000+ higher complexity architectures, which we publicly release at: https://github.com/combinatoriallabs/ArchitecturalComplexity.

cs.LG · cs.DM · math.CO