Search

We study the problem of bounding the posterior distribution of discrete probabilistic programs with unbounded support, loops, and conditioning. Loops pose the main difficulty in this setting: even if exact Bayesian inference is possible, the state of the art requires user-provided loop invariant templates. By contrast, we aim to find guaranteed bounds, which sandwich the true distribution. They are fully automated, applicable to more programs and provide more provable guarantees than approximate sampling-based inference. Since lower bounds can be obtained by unrolling loops, the main challenge is upper bounds, and we attack it in two ways. The first is called residual mass semantics, which is a flat bound based on the residual probability mass of a loop. The approach is simple, efficient, and has provable guarantees. The main novelty of our work is the second approach, called geometric bound semantics. It operates on a novel family of distributions, called eventually geometric distributions (EGDs), and can bound the distribution of loops with a new form of loop invariants called contraction invariants. The invariant synthesis problem reduces to a system of polynomial inequality constraints, which is a decidable problem with automated solvers. If a solution exists, it yields an exponentially decreasing bound on the whole distribution, and can therefore bound moments and tail asymptotics as well, not just probabilities as in the first approach. Both semantics enjoy desirable theoretical properties. In particular, we prove soundness and convergence, i.e. the bounds converge to the exact posterior as loops are unrolled further. On the practical side, we describe Diabolo, a fully-automated implementation of both semantics, and evaluate them on a variety of benchmarks from the literature, demonstrating their general applicability and the utility of the resulting bounds., Comment: Full version of the POPL 2025 article, including proofs and other supplementary material

Can outreach inspire and lead to research and vice versa? In this work, we introduce our approach to the gamification of research in mathematics and computer science through three illustrative examples. We discuss our primary motivations and provide insights into what makes our proposed gamification effective for three research topics in discrete and computational geometry and topology: (1) DominatriX, an art gallery problem involving polyominoes with rooks and queens; (2) Cubical Sliding Puzzles, an exploration of the discrete configuration spaces of sliding puzzles on the $d$-cube with topological obstructions; and (3) The Fence Challenge, a participatory isoperimetric problem based on polyforms. Additionally, we report on the collaborative development of the game Le Carr\'e du Diable, inspired by The Fence Challenge and created during the workshop Let's talk about outreach!, held in October 2022 in Les Diablerets, Switzerland. All of our outreach encounters and creations are designed and curated with an inclusive culture and a strong commitment to welcoming the most diverse audience possible., Comment: 16 pages, 11 figures

We give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. We also discuss the complexity of computing the distances.

The study of SAT and its variants has provided numerous NP-complete problems, from which most NP-hardness results were derived. Due to the NP-hardness of SAT, adding constraints to either specify a more precise NP-complete problem or to obtain a tractable one helps better understand the complexity class of several problems. In 1984, Tovey proved that bounded-degree SAT is also NP-complete, thereby providing a tool for performing NP-hardness reductions even with bounded parameters, when the size of the reduction gadget is a function of the variable degree. In this work, we initiate a similar study for QBF, the quantified version of SAT. We prove that, like SAT, the truth value of a maximum degree two quantified formula is polynomial-time computable. However, surprisingly, while the truth value of a 3-regular 3-SAT formula can be decided in polynomial time, it is PSPACE-complete for a 3-regular QBF formula. A direct consequence of these results is that Avoider-Enforcer and Client-Waiter positional games are PSPACE-complete when restricted to bounded-degree hypergraphs. To complete the study, we also show that Maker-Breaker and Maker-Maker positional games are PSPACE-complete for bounded-degree hypergraphs.

A recent result by Kardo\v{s}, M\'a\v{c}ajov\'a and Zerafa [J. Comb. Theory, Ser. B. 160 (2023) 1--14] related to the famous Berge-Fulkerson conjecture implies that given an arbitrary set of odd pairwise edge-disjoint cycles, say $\mathcal O$, in a bridgeless cubic graph, there exists a $1$-factor intersecting all cycles in $\mathcal O$ in at least one edge. This remarkable result opens up natural generalizations in the case of an $r$-regular graph $G$ and a $t$-factor $F$, with $r$ and $t$ being positive integers. In this paper, we start the study of this problem by proving necessary and sufficient conditions on $G$, $t$ and $r$ to assure the existence of a suitable $F$ for any possible choice of the set $\mathcal O$. First of all, we show that $G$ needs to be $2$-connected. Under this additional assumption, we highlight how the ratio $\frac{t}{r}$ seems to play a crucial role in assuring the existence of a $t$-factor $F$ with the required properties by proving that $\frac{t}{r} \geq \frac{1}{3}$ is a further necessary condition. We suspect that this condition is also sufficient, and we confirm it in the case $\frac{t}{r}=\frac{1}{3}$, generalizing the case $t=1$ and $r=3$ proved by Kardo\v{s}, M\'a\v{c}ajov\'a, Zerafa, and in the case $\frac{t}{r}=\frac{1}{2}$ with $t$ even. Finally, we provide further results in the case of cycles of arbitrary length., Comment: 17 pages

Consider a graph $G$ with a path $P$ of order $n$. What conditions force $G$ to also have a long induced path? As complete bipartite graphs have long paths but no long induced paths, a natural restriction is to forbid some fixed complete bipartite graph $K_{t,t}$ as a subgraph. In this case we show that $G$ has an induced path of order $(\log \log n)^{1/5-o(1)}$. This is an exponential improvement over a result of Galvin, Rival, and Sands (1982) and comes close to a recent upper bound of order $O((\log \log n)^2)$. Another way to approach this problem is by viewing $G$ as an ordered graph (where the vertices are ordered according to their position on the path $P$). From this point of view it is most natural to consider which ordered subgraphs need to be forbidden in order to force the existence of a long induced path. Focusing on the exclusion of ordered matchings, we improve or recover a number of existing results with much simpler proofs, in a unified way. We also show that if some forbidden ordered subgraph forces the existence of a long induced path in $G$, then this induced path has size at least $\Omega((\log \log \log n)^{1/3})$, and can be chosen to be increasing with respect to $P$., Comment: 26 pages, 8 figures. Comments welcome !

Positive spanning sets (PSSs) are families of vectors that span a given linear space through non-negative linear combinations. Despite certain classes of PSSs being well understood, a complete characterization of PSSs remains elusive. In this paper, we explore a relatively understudied relationship between positive spanning sets and strongly edge-connected digraphs, in that the former can be viewed as a generalization of the latter. We leverage this connection to define a decomposition structure for positive spanning sets inspired by the ear decomposition from digraph theory.

Given a non-negative $n \times n$ matrix viewed as a set of distances between $n$ points, we consider the property testing problem of deciding if it is a metric. We also consider the same problem for two special classes of metrics, tree metrics and ultrametrics. For general metrics, our paper is the first to consider these questions. We prove an upper bound of $O(n^{2/3}/\epsilon^{4/3})$ on the query complexity for this problem. Our algorithm is simple, but the analysis requires great care in bounding the variance on the number of violating triangles in a sample. When $\epsilon$ is a slowly decreasing function of $n$ (rather than a constant, as is standard), we prove a lower bound of matching dependence on $n$ of $\Omega (n^{2/3})$, ruling out any property testers with $o(n^{2/3})$ query complexity unless their dependence on $1/\epsilon$ is super-polynomial. Next, we turn to tree metrics and ultrametrics. While there were known upper and lower bounds, we considerably improve these bounds showing essentially tight bounds of $\tilde{O}(1/\epsilon )$ on the sample complexity. We also show a lower bound of $\Omega ( 1/\epsilon^{4/3} )$ on the query complexity. Our upper bounds are derived by doing a more careful analysis of a natural, simple algorithm. For the lower bounds, we construct distributions on NO instances, where it is hard to find a witness showing that these are not ultrametrics.

We present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group $\mathbb{F}_2^n$. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree $\exp(n^\epsilon)$ for every $\epsilon >0$, improving on a construction by Golowich [Gol23] which achieves $\epsilon =1/2$. [Gol23] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmannian posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDXs of any polynomial degree $\exp(\epsilon n$) for any constant $\epsilon > 0$, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [LMSY23]. Establishing coboundary expansion through Gromov's "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.

Finite element methods typically require a high resolution to satisfactorily approximate micro and even macro patterns of an underlying physical model. This issue can be circumvented by appropriate numerical homogenization or multiscale strategies that are able to obtain reasonable approximations on under-resolved scales. In this paper, we study the implicit neural representation and propose a continuous super-resolution network as a numerical homogenization strategy. It can take coarse finite element data to learn both in-distribution and out-of-distribution high-resolution finite element predictions. Our highlight is the design of a local implicit transformer, which is able to learn multiscale features. We also propose Gabor wavelet-based coordinate encodings which can overcome the bias of neural networks learning low-frequency features. Finally, perception is often preferred over distortion so scientists can recognize the visual pattern for further investigation. However, implicit neural representation is known for its lack of local pattern supervision. We propose to use stochastic cosine similarities to compare the local feature differences between prediction and ground truth. It shows better performance on structural alignments. Our experiments show that our proposed strategy achieves superior performance as an in-distribution and out-of-distribution super-resolution strategy., Comment: 13 pages, 10 figures

We study skew-tolerant Gray codes, which are Gray codes in which changes in consecutive codewords occur in adjacent positions. We present the first construction of asymptotically non-vanishing skew-tolerant Gray codes, offering an exponential improvement over the known construction. We also provide linear-time encoding and decoding algorithms for our codes. Finally, we extend the definition to non-binary alphabets, and provide constructions of complete $m$-ary skew-tolerant Gray codes for every base $m\geq 3$., Comment: 13 pages

This work establishes novel, optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models using the powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. These bounds are expressed in terms of the local connective constant of the underlying graph $G$. This is a notion of effective degree of $G$ on a local scale. Our results have some interesting consequences for bounded degree graphs: (a) They include the max-degree bounds as a special case, (b) They improve on the running time of the FPTAS considered in [Sinclair, Srivastava, Stefankonic and Yin: PTRF 2017], (c) They allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on results in [Hayes: FOCS 2006], (d) They also allow us to refine the celebrated connection between the hardness of approximate counting and the phase transitions from statistical physics. We obtain our mixing bounds by utilising the $k$-non-backtracking matrix $H_{G,k}$. This is a very interesting, alas technically intricate, object to work with. We upper bound the spectral radius of the pairwise influence matrix $I^{\Lambda,\tau}_{G}$ by means of the 2-norm of $H_{G,k}$. To our knowledge, obtaining mixing bound using $H_{G,k}$ has not been considered before in the literature., Comment: arXiv admin note: text overlap with arXiv:2402.11647, arXiv:2211.03753

For a subfamily ${F}\subseteq 2^{[n]}$ of the Boolean lattice, consider the graph $G_{F}$ on ${F}$ based on the pairwise inclusion relations among its members. Given a positive integer $t$, how large can ${F}$ be before $G_{F}$ must contain some component of order greater than $t$? For $t=1$, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For $t=2^n$, this question is trivial. We are interested in what happens between these two extremes. For $t=2^{g}$ with $g=g(n)$ being any integer function that satisfies $g(n)=o(n/\log n)$ as $n\to\infty$, we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer. This constitutes a nontrivial generalisation of Sperner's theorem. We do so by a reduction to a Tur\'an-type problem for rainbow cycles in properly edge-coloured graphs. Among other results, we also give a sharp answer to the question, how large can ${F}$ be before $G_{F}$ must be connected?, Comment: 23 pages, 2 figures

Classical simulations of quantum circuits are essential for verifying and benchmarking quantum algorithms, particularly for large circuits, where computational demands increase exponentially with the number of qubits. Among available methods, the classical simulation of quantum circuits inspired by density functional theory -- the so-called QC-DFT method, shows promise for large circuit simulations as it approximates the quantum circuits using single-qubit reduced density matrices to model multi-qubit systems. However, the QC-DFT method performs very poorly when dealing with multi-qubit gates. In this work, we introduce a novel CNOT "functional" that leverages neural networks to generate unitary transformations, effectively mitigating the simulation errors observed in the original QC-DFT method. For random circuit simulations, our modified QC-DFT enables efficient computation of single-qubit marginal measurement probabilities, or single-qubit probability (SQPs), and achieves lower SQP errors and higher fidelities than the original QC-DFT method. Despite limitations in capturing full entanglement and joint probability distributions, we find potential applications of SQPs in simulating Shor's and Grover's algorithms for specific solution classes. These findings advance the capabilities of classical simulations for some quantum problems and provide insights into managing entanglement and gate errors in practical quantum computing., Comment: 6 pages, 2 figures, and supplemental materials

We study the problem of determining the minimal genus of a given finite connected graph. We present an algorithm which, for an arbitrary graph $G$ with $n$ vertices, determines the orientable genus of $G$ in $\mathcal{O}({2^{(n^2+3n)}}/{n^{(n+1)}})$ steps. This algorithm avoids the difficulties that many other genus algorithms have with handling bridge placements which is a well-known issue. The algorithm has a number of properties that make it useful for practical use: it is simple to implement, it outputs the faces of the optimal embedding, it outputs a proof certificate for verification and it can be used to obtain upper and lower bounds. We illustrate the algorithm by determining the genus of the $(3,12)$ cage (which is 17); other graphs are also considered.

In our work, we consider the problem of computing a vector $x \in Z^n$ of minimum $\|\cdot\|_p$-norm such that $a^\top x \not= a_0$, for any vector $(a,a_0)$ from a given subset of $Z^n$ of size $m$. In other words, we search for a vector of minimum norm that avoids a given finite set of hyperplanes, which is natural to call as the $\textit{Hyperplanes Avoiding Problem}$. This problem naturally appears as a subproblem in Barvinok-type algorithms for counting integer points in polyhedra. More precisely, it appears when one needs to evaluate certain rational generating functions in an avoidable critical point. We show that: 1) With respect to $\|\cdot\|_1$, the problem admits a feasible solution $x$ with $\|x\|_1 \leq (m+n)/2$, and show that such solution can be constructed by a deterministic polynomial-time algorithm with $O(n \cdot m)$ operations. Moreover, this inequality is the best possible. This is a significant improvement over the previous randomized algorithm, which computes $x$ with a guaranty $\|x\|_{1} \leq n \cdot m$. The original approach of A.~Barvinok can guarantee only $\|x\|_1 = O\bigl((n \cdot m)^n\bigr)$; 2) The problem is NP-hard with respect to any norm $\|\cdot\|_p$, for $p \in \bigl(R_{\geq 1} \cup \{\infty\}\bigr)$. 3) As an application, we show that the problem to count integer points in a polytope $P = \{x \in R^n \colon A x \leq b\}$, for given $A \in Z^{m \times n}$ and $b \in Q^m$, can be solved by an algorithm with $O\bigl(\nu^2 \cdot n^3 \cdot \Delta^3 \bigr)$ operations, where $\nu$ is the maximum size of a normal fan triangulation of $P$, and $\Delta$ is the maximum value of rank-order subdeterminants of $A$. It refines the previous state-of-the-art $O\bigl(\nu^2 \cdot n^4 \cdot \Delta^3\bigr)$-time algorithm.

Optical orthogonal codes (OOCs) are sets of $(0,1)$-sequences with good auto- and cross-correlation properties. They were originally introduced for use in multi-access communication, particularly in the setting of optical CDMA communications systems. They can also be formulated in terms of families of subsets of $\mathbb{Z}_v$, where the correlation properties can be expressed in terms of conditions on the internal and external differences within and between the subsets. With this link there have been many studies on their combinatorial properties. However, in most of these studies it is assumed that the auto- and cross-correlation values are equal; in particular, many constructions focus on the case where both correlation values are $1$. This is not a requirement of the original communications application. In this paper, we "decouple" the two correlation values and consider the situation with correlation values greater than $1$. We consider the bounds on each of the correlation values, and the structural implications of meeting these separately, as well as associated links with other combinatorial objects. We survey definitions, properties and constructions, establish some new connections and concepts, and discuss open questions.

We study algebraic properties of partition functions, particularly the location of zeros, through the lens of rapidly mixing Markov chains. The classical Lee-Yang program initiated the study of phase transitions via locating complex zeros of partition functions. Markov chains, besides serving as algorithms, have also been used to model physical processes tending to equilibrium. In many scenarios, rapid mixing of Markov chains coincides with the absence of phase transitions (complex zeros). Prior works have shown that the absence of phase transitions implies rapid mixing of Markov chains. We reveal a converse connection by lifting probabilistic tools for the analysis of Markov chains to study complex zeros of partition functions. Our motivating example is the independence polynomial on $k$-uniform hypergraphs, where the best-known zero-free regime has been significantly lagging behind the regime where we have rapidly mixing Markov chains for the underlying hypergraph independent sets. Specifically, the Glauber dynamics is known to mix rapidly on independent sets in a $k$-uniform hypergraph of maximum degree $\Delta$ provided that $\Delta \lesssim 2^{k/2}$. On the other hand, the best-known zero-freeness around the point $1$ of the independence polynomial on $k$-uniform hypergraphs requires $\Delta \le 5$, the same bound as on a graph. By introducing a complex extension of Markov chains, we lift an existing percolation argument to the complex plane, and show that if $\Delta \lesssim 2^{k/2}$, the Markov chain converges in a complex neighborhood, and the independence polynomial itself does not vanish in the same neighborhood. In the same regime, our result also implies central limit theorems for the size of a uniformly random independent set, and deterministic approximation algorithms for the number of hypergraph independent sets of size $k \le \alpha n$ for some constant $\alpha$., Comment: 37 pages

Recent major results in property testing~\cite{BLM24,DDL24} and PCPs~\cite{BMV24} were unlocked by moving to high-dimensional expanders (HDXs) constructed from $\widetilde{C}_d$-type buildings, rather than the long-known $\widetilde{A}_d$-type ones. At the same time, these building quotient HDXs are not as easy to understand as the more elementary (and more symmetric/explicit) \emph{coset complex} HDXs constructed by Kaufman--Oppenheim~\cite{KO18} (of $A_d$-type) and O'Donnell--Pratt~\cite{OP22} (of $B_d$-, $C_d$-, $D_d$-type). Motivated by these considerations, we study the $B_3$-type generalization of a recent work of Kaufman--Oppenheim~\cite{KO21}, which showed that the $A_3$-type coset complex HDXs have good $1$-coboundary expansion in their links, and thus yield $2$-dimensional topological expanders. The crux of Kaufman--Oppenheim's proof of $1$-coboundary expansion was: (1)~identifying a group-theoretic result by Biss and Dasgupta~\cite{BD01} on small presentations for the $A_3$-unipotent group over~$\mathbb{F}_q$; (2)~``lifting'' it to an analogous result for an $A_3$-unipotent group over polynomial extensions~$\mathbb{F}_q[x]$. For our $B_3$-type generalization, the analogue of~(1) appears to not hold. We manage to circumvent this with a significantly more involved strategy: (1)~getting a computer-assisted proof of vanishing $1$-cohomology of $B_3$-type unipotent groups over~$\mathbb{F}_5$; (2)~developing significant new ``lifting'' technology to deduce the required quantitative $1$-cohomology results in $B_3$-type unipotent groups over $\mathbb{F}_{5^k}[x]$., Comment: 130 pages

We prove that the number of partitions of the hypercube ${\bf Z}_q^n$ into $q^m$ subcubes of dimension $n-m$ each for fixed $q$, $m$ and growing $n$ is asymptotically equal to $n^{(q^m-1)/(q-1)}$. For the proof, we introduce the operation of the bang of a star matrix and demonstrate that any star matrix, except for a fractal, is expandable under some bang, whereas a fractal remains to be a fractal under any bang.

Online Budgeted Matching (OBM) is a classic problem with important applications in online advertising, online service matching, revenue management, and beyond. Traditional online algorithms typically assume a small bid setting, where the maximum bid-to-budget ratio (\kappa) is infinitesimally small. While recent algorithms have tried to address scenarios with non-small or general bids, they often rely on the Fractional Last Matching (FLM) assumption, which allows for accepting partial bids when the remaining budget is insufficient. This assumption, however, does not hold for many applications with indivisible bids. In this paper, we remove the FLM assumption and tackle the open problem of OBM with general bids. We first establish an upper bound of 1-\kappa on the competitive ratio for any deterministic online algorithm. We then propose a novel meta algorithm, called MetaAd, which reduces to different algorithms with first known provable competitive ratios parameterized by the maximum bid-to-budget ratio \kappa \in [0, 1]. As a by-product, we extend MetaAd to the FLM setting and get provable competitive algorithms. Finally, we apply our competitive analysis to the design learning-augmented algorithms., Comment: Accepted by NeurIPS 2024

In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability $\alpha$, independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants $c$ such that $cn\log n$ tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting.

The problem of identifying the satisfiability threshold of random $3$-SAT formulas has received a lot of attention during the last decades and has inspired the study of other threshold phenomena in random combinatorial structures. The classical assumption in this line of research is that, for a given set of $n$ Boolean variables, each clause is drawn uniformly at random among all sets of three literals from these variables, independently from other clauses. Here, we keep the uniform distribution of each clause, but deviate significantly from the independence assumption and consider richer families of probability distributions. For integer parameters $n$, $m$, and $k$, we denote by $\DistFamily_k(n,m)$ the family of probability distributions that produce formulas with $m$ clauses, each selected uniformly at random from all sets of three literals from the $n$ variables, so that the clauses are $k$-wise independent. Our aim is to make general statements about the satisfiability or unsatisfiability of formulas produced by distributions in $\DistFamily_k(n,m)$ for different values of the parameters $n$, $m$, and $k$., Comment: 26 pages, 1 fugure

Motivated by studies of data retrieval in polymer-based storage systems, we consider the problem of reconstructing a multiset of binary strings that have the same length and the same weight from the compositions of their prefixes and suffixes of every possible length. We provide necessary and sufficient conditions for which unique reconstruction up to reversal of the strings is possible. Additionally, we present two algorithms for reconstructing strings from the compositions of prefixes and suffixes of constant-length constant-weight strings.

The seminal work of Bencz\'ur and Karger demonstrated cut sparsifiers of near-linear size, with several applications throughout theoretical computer science. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction problems (CSPs). For this question, a trivial lower bound is the size of a non-redundant CSP instance, which admits, for each constraint, an assignment satisfying only that constraint (so that no constraint can be dropped by the sparsifier). For graph cuts, spanning trees are non-redundant instances. Our main result is that redundant clauses are sufficient for sparsification: for any CSP predicate R, every unweighted instance of CSP(R) has a sparsifier of size at most its non-redundancy (up to polylog factors). For weighted instances, we similarly pin down the sparsifiability to the so-called chain length of the predicate. These results precisely determine the extent to which any CSP can be sparsified. A key technical ingredient in our work is a novel application of the entropy method from Gilmer's recent breakthrough on the union-closed sets conjecture. As an immediate consequence of our main theorem, a number of results in the non-redundancy literature immediately extend to CSP sparsification. We also contribute new techniques for understanding the non-redundancy of CSP predicates. In particular, we give an explicit family of predicates whose non-redundancy roughly corresponds to the structure of matching vector families in coding theory. By adapting methods from the matching vector codes literature, we are able to construct an explicit predicate whose non-redundancy lies between $\Omega(n^{1.5})$ and $\widetilde{O}(n^{1.6})$, the first example with a provably non-integral exponent., Comment: 66 pages

The $q$-chorded $k$-cycle inequalities are a class of valid inequalities for the clique partitioning polytope. It is known that for $q = 2$ or $q = \tfrac{k-1}{2}$, these inequalities induce facets of the clique partitioning polytope if and only if $k$ is odd. We solve the open problem of characterizing such facets for arbitrary $k$ and $q$. More specifically, we prove that the $q$-chorded $k$-cycle inequalities induce facets of the clique partitioning polytope if and only if two conditions are satisfied: $k = 1$ mod $q$, and if $k=3q+1$ then $q=3$ or $q$ is even. This establishes the existence of many facets induced by $q$-chorded $k$-cycle inequalities beyond those previously known., Comment: 17 pages

A cornerstone of social choice theory is Condorcet's paradox which says that in an election where $n$ voters rank $m$ candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters? Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet winning set. They showed that winning sets of size $2$ may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size $6$ always exist, regardless of the number of candidates or the number of voters. More generally, we show that if $\frac{\alpha}{1 - \ln \alpha} \geq \frac{2}{k + 1}$, then there always exists a committee of size $k$ such that less than an $\alpha$ fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all $k \geq 2$. Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection. We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support., Comment: Added relevant reference

The literature on word-representable graphs is quite rich, and a number of variations of the original definition have been proposed over the years. We are initiating a systematic study of such variations based on formal languages. In our framework, we can associate a graph class to each language over the binary alphabet \{0,1\}. All graph classes that are language-representable in this sense are hereditary and enjoy further common properties. Besides word-representable graphs and, more generally, 1^k- or k-11-representable graphs, we can identify many more graph classes in our framework, like (co)bipartite graphs, (co)comparability graphs, to name a few. It was already known that any graph is 111- or 2-11-representable. When such representations are considered for storing graphs, 111- or 2-11-representability bears the disadvantage of being significantly inferior to standard adjacency matrices or lists. We prove that quite famous languages like the palindromes, the copy language or the Lyndon words can match the efficiency of standard graph representations. The perspective of language theory allows us to prove general results that hold for all graph classes that can be defined in this way. This includes certain closure properties (e.g., all language-definable graph classes are hereditary) as well as certain limitations (e.g., all language-representable graph classes contain graphs of arbitrarily large treewidth and of arbitrarily large degeneracy, except a trivial case). As each language describes a graph class, we can also ask decidability questions concerning graph classes, given a concrete presentation of a formal language. We also present a systematic study of graph classes that can be represented by languages in which each letter occurs at most twice. Here, we find graph classes like interval, permutation, circle, bipartite chain, convex, and threshold graphs.

This paper presents an approach to semi-supervised learning for the classification of data using the Lipschitz Learning on graphs. We develop a graph-based semi-supervised learning framework that leverages the properties of the infinity Laplacian to propagate labels in a dataset where only a few samples are labeled. By extending the theory of spatial segregation from the Laplace operator to the infinity Laplace operator, both in continuum and discrete settings, our approach provides a robust method for dealing with class imbalance, a common challenge in machine learning. Experimental validation on several benchmark datasets demonstrates that our method not only improves classification accuracy compared to existing methods but also ensures efficient label propagation in scenarios with limited labeled data.

Neural networks with piecewise linear activation functions, such as rectified linear units (ReLU) or maxout, are among the most fundamental models in modern machine learning. We make a step towards proving lower bounds on the size of such neural networks by linking their representative capabilities to the notion of the extension complexity $\mathrm{xc}(P)$ of a polytope $P$, a well-studied quantity in combinatorial optimization and polyhedral geometry. To this end, we propose the notion of virtual extension complexity $\mathrm{vxc}(P)=\min\{\mathrm{xc}(Q)+\mathrm{xc}(R)\mid P+Q=R\}$. This generalizes $\mathrm{xc}(P)$ and describes the number of inequalities needed to represent the linear optimization problem over $P$ as a difference of two linear programs. We prove that $\mathrm{vxc}(P)$ is a lower bound on the size of a neural network that optimizes over $P$. While it remains open to derive strong lower bounds on virtual extension complexity, we show that powerful results on the ordinary extension complexity can be converted into lower bounds for monotone neural networks, that is, neural networks with only nonnegative weights. Furthermore, we show that one can efficiently optimize over a polytope $P$ using a small virtual extended formulation. We therefore believe that virtual extension complexity deserves to be studied independently from neural networks, just like the ordinary extension complexity. As a first step in this direction, we derive an example showing that extension complexity can go down under Minkowski sum.

Recently, Van Hoeve proposed an algorithm for graph coloring based on an integer flow formulation on decision diagrams for stable sets. We prove that the solution to the linear flow relaxation on exact decision diagrams determines the fractional chromatic number of a graph. This settles the question whether the decision diagram formulation or the fractional chromatic number establishes a stronger lower bound. It also establishes that the integrality gap of the linear programming relaxation is O(log n), where n represents the number of vertices in the graph. We also conduct experiments using exact decision diagrams and could determine the chromatic number of r1000.1c from the DIMACS benchmark set. It was previously unknown and is one of the few newly solved DIMACS instances in the last 10 years., Comment: 11 pages, 1 Figure, 1 Table, source code published at https://github.com/trewes/ddcolors, Scripts, logfiles, results and instructions for the experiments are archived at https://bonndata.uni-bonn.de/dataset.xhtml?persistentId=doi:10.60507/FK2/ZE9C3L

We present efficient counting and sampling algorithms for random $k$-SAT when the clause density satisfies $\alpha \le \frac{2^k}{\mathrm{poly}(k)}.$ In particular, the exponential term $2^k$ matches the satisfiability threshold $\Theta(2^k)$ for the existence of a solution and the (conjectured) algorithmic threshold $2^k (\ln k) / k$ for efficiently finding a solution. Previously, the best-known counting and sampling algorithms required far more restricted densities $\alpha\lesssim 2^{k/3}$ [He, Wu, Yang, SODA '23]. Notably, our result goes beyond the lower bound $d\gtrsim 2^{k/2}$ for worst-case $k$-SAT with bounded-degree $d$ [Bez\'akov\'a et al, SICOMP '19], showing that for counting and sampling, the average-case random $k$-SAT model is computationally much easier than the worst-case model. At the heart of our approach is a new refined analysis of the recent novel coupling procedure by [Wang, Yin, FOCS '24], utilizing the structural properties of random constraint satisfaction problems (CSPs). Crucially, our analysis avoids reliance on the $2$-tree structure used in prior works, which cannot extend beyond the worst-case threshold $2^{k/2}$. Instead, we employ a witness tree similar to that used in the analysis of the Moser-Tardos algorithm [Moser, Tardos, JACM '10] for the Lov\'{a}sz Local lemma, which may be of independent interest. Our new analysis provides a universal framework for efficient counting and sampling for random atomic CSPs, including, for example, random hypergraph colorings. At the same time, it immediately implies as corollaries several structural and probabilistic properties of random CSPs that have been widely studied but rarely justified, including replica symmetry and non-reconstruction., Comment: 39 pages

The study of matroid products traces back to the 1970s, when Lov\'asz and Mason studied the existence of various types of matroid products with different strengths. Among these, the tensor product is arguably the most important, which can be considered as an extension of the tensor product from linear algebra. However, Las Vergnas showed that the tensor product of two matroids does not always exist. Over the following four decades, matroid products remained surprisingly underexplored, regaining attention only in recent years due to applications in tropical geometry and the limit theory of matroids. In this paper, inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids -- or, more generally, for submodular set functions. This operation can be viewed as a relaxation of the tensor product. Unlike the tensor product, however, we prove that a coupling always exists for any two submodular functions and can be chosen to be increasing if the original functions are increasing. As a corollary, we show that two matroids always admit a matroid coupling, leading to a novel operation on matroids. Our construction is algorithmic, providing an oracle for the coupling matroid through a polynomial number of oracle calls to the original matroids. We apply this construction to derive new necessary conditions for matroid representability and establish connection between tensor products and Ingleton's inequality. Additionally, we verify the existence of set functions that are universal with respect to a given property, meaning any set function over a finite domain with that property can be obtained as a quotient., Comment: 24 pages

We consider facet-Hamiltonian cycles of polytopes, defined as cycles in their skeleton such that every facet is visited exactly once. These cycles can be understood as optimal watchman routes that guard the facets of a polytope. We consider the existence of such cycles for a variety of polytopes, the facets of which have a natural combinatorial interpretation. In particular, we prove the following results: - Every permutahedron has a facet-Hamiltonian cycle. These cycles consist of circular sequences of permutations of $n$ elements, where two successive permutations differ by a single adjacent transposition, and such that every subset of $[n]$ appears as a prefix in a contiguous subsequence. With these cycles we associate what we call rhombic strips which encode interleaved Gray codes of the Boolean lattice, one Gray code for each rank. These rhombic strips correspond to simple Venn diagrams. - Every generalized associahedron has a facet-Hamiltonian cycle. This generalizes the so-called rainbow cycles of Felsner, Kleist, M\"utze, and Sering (SIDMA 2020) to associahedra of any finite type. We relate the constructions to the Conway-Coxeter friezes and the bipartite belts of finite type cluster algebras. - Graph associahedra of wheels, fans, and complete split graphs have facet-Hamiltonian cycles. For associahedra of complete bipartite graphs and caterpillars, we construct facet-Hamiltonian paths. The construction involves new insights on the combinatorics of graph tubings. We also consider the computational complexity of deciding whether a given polytope has a facet-Hamiltonian cycle and show that the problem is NP-complete, even when restricted to simple 3-dimensional polytopes., Comment: ACM-SIAM Symposium on Discrete Algorithms (SODA'25)

A vertex coloring $\varphi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$, either $\varphi$ uses more than $p$ colors on $H$, or there is a color that appears exactly once on $H$. We prove that for every fixed positive integer $t$, every $K_t$-minor-free graph admits a $p$-centered coloring using $\mathcal{O}(p^{t-1})$ colors., Comment: 23 pages, 10 figures

The $d$-independence number of a graph $G$ is the largest possible size of an independent set $I$ in $G$ where each vertex of $I$ has degree at least $d$ in $G$. Upper bounds for the $d$-independence number in planar graphs are well-known for $d=3,4,5$, and can in fact be matched with constructions that actually have minimum degree $d$. In this paper, we explore the same questions for 1-planar graphs, i.e., graphs that can be drawn in the plane with at most one crossing per edge. We give upper bounds for the $d$-independence number for all $d$. Then we give constructions that match the upper bound, and (for small $d$) also have minimum degree $d$., Comment: Comments are welcome

A celebrated result of Hastad established that, for any constant $\varepsilon>0$, it is NP-hard to find an assignment satisfying a $(1/|G|+\varepsilon)$-fraction of the constraints of a given 3-LIN instance over an Abelian group $G$ even if one is promised that an assignment satisfying a $(1-\varepsilon)$-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.

N. G. de Bruijn (1958) studied the asymptotic expansion of iterates of sin$(x)$ with $0 < x \leq \pi/2$. Bencherif & Robin (1994) generalized this result to increasing analytic functions $f(x)$ with an attractive fixed point at 0 and $x > 0$ suitably small. Mavecha & Laohakosol (2013) formulated an algorithm for explicitly deriving required parameters. We review their method, testing it initally on the logistic function $\ell(x)$, a certain radical function $r(x)$, and later on several transcendental functions. Along the way, we show how $\ell(x)$ and $r(x)$ are kindred functions; the same is also true for sin$(x)$ and arcsinh$(x)$., Comment: 24 pages

The greedy algorithm adapted from Kruskal's algorithm is an efficient and folklore way to produce a $k$-spanner with girth at least $k+2$. The greedy algorithm has shown to be `existentially optimal', while it's not `universally optimal' for any constant $k$. Here, `universal optimality' means an algorithm can produce the smallest $k$-spanner $H$ given any $n$-vertex input graph $G$. However, how well the greedy algorithm works compared to `universal optimality' is still unclear for superconstant $k:=k(n)$. In this paper, we aim to give a new and fine-grained analysis of this problem in undirected unweighted graph setting. Specifically, we show some bounds on this problem including the following two (1) On the negative side, when $k<\frac{1}{3}n-O(1)$, the greedy algorithm is not `universally optimal'. (2) On the positive side, when $k>\frac{2}{3}n+O(1)$, the greedy algorithm is `universally optimal'. We also introduce an appropriate notion for `approximately universal optimality'. An algorithm is $(\alpha,\beta)$-universally optimal iff given any $n$-vertex input graph $G$, it can produce a $k$-spanner $H$ of $G$ with size $|H|\leq n+\alpha(|H^*|-n)+\beta$, where $H^*$ is the smallest $k$-spanner of $G$. We show the following positive bounds. (1) When $k>\frac{4}{7}n+O(1)$, the greedy algorithm is $(2,O(1))$-universally optimal. (2) When $k>\frac{12}{23}n+O(1)$, the greedy algorithm is $(18,O(1))$-universally optimal. (3) When $k>\frac{1}{2}n+O(1)$, the greedy algorithm is $(32,O(1))$-universally optimal. All our proofs are constructive building on new structural analysis on spanners. We give some ideas about how to break small cycles in a spanner to increase the girth. These ideas may help us to understand the relation between girth and spanners., Comment: 33 pages

Data deduplication, one of the key features of modern Big Data storage devices, is the process of removing replicas of data chunks stored by different users. Despite the importance of deduplication, several drawbacks of the method, such as storage robustness and file fragmentation, have not been previously analyzed from a theoretical point of view. Storage robustness pertains to ensuring that deduplicated data can be used to reconstruct the original files without service disruptions and data loss. Fragmentation pertains to the problems of placing deduplicated data chunks of different user files in a proximity-preserving linear order, since neighboring chunks of the same file may be stored in sectors far apart on the server. This work proposes a new theoretical model for data fragmentation and introduces novel graph- and coding-theoretic approaches for reducing fragmentation via limited duplication (repetition coding) and coded deduplication (e.g., linear coding). In addition to alleviating issues with fragmentation, limited duplication and coded deduplication can also serve the dual purpose of increasing the robusteness of the system design. The contributions of our work are three-fold. First, we describe a new model for file structures in the form of self-avoiding (simple) paths in specialized graphs. Second, we introduce several new metrics for measuring the fragmentation level in deduplication systems on graph-structured files, including the stretch metric that captures the worst-case "spread" of adjacent data chunks within a file when deduplicated and placed on the server; and, the jump metric that captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. For the stretch metric, we establish a connection between the level of fragmentation and the bandwidth of the file-graph. In particular, ...

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. A connected graph $G$ is said to be $t$-admissible if admits a spanning tree in which the distance between any two adjacent vertices of $G$ is at most $t$. Given a graph $G$, determining the smallest $t$ for which $G$ is $t$-admissible, i.e., the stretch index of $G$ denoted by $\sigma(G)$, is the goal of the $t$-admissibility problem. Split graphs are $3$-admissible and can be partitioned into three subclasses: split graphs with $\sigma = 1$, $2$ or $3$. In this work we consider such a partition while dealing with the problem of coloring the edges of a split graph. Vizing proved that any graph can have its edges colored with $\Delta$ or $\Delta+1$ colors, and thus can be classified as Class $1$ or Class $2$, respectively. The edge coloring problem is open for split graphs in general. In previous results, we classified split graphs with $\sigma = 2$ and in this paper we classify and provide an algorithm to color the edges of a subclass of split graphs with $\sigma = 3$.

There is a long list of open questions rooted in the same underlying problem: understanding the structure of bases or common bases of matroids. These conjectures suggest that matroids may possess much stronger structural properties than are currently known. One example is related to cyclic orderings of matroids. A rank-$r$ matroid is called cyclically orderable if its ground set admits a cyclic ordering such that any interval of $r$ consecutive elements forms a basis. In this paper, we show that if the ground set of a split matroid decomposes into pairwise disjoint bases, then it is cyclically orderable. This result answers a conjecture of Kajitani, Ueno, and Miyano in a special case, and also strengthens Gabow's conjecture for this class of matroids. Our proof is algorithmic, hence it provides a procedure for determining a cyclic ordering in question using a polynomial number of independence oracle calls., Comment: 11 pages

A Boolean function $f$ on $k$~bits induces a shift-invariant vectorial Boolean function $F$ from $n$ bits to $n$ bits for every $n\geq k$. If $F$ is bijective for every $n$, we say that $f$ is a proper lifting, and it is known that proper liftings are exactly those functions that arise as local rules of reversible cellular automata. We construct new families of such liftings for arbitrary large $k$ and discuss whether all have been identified for $k\leq 6$., Comment: 11 pages

Rooted phylogenetic networks, or more generally, directed acyclic graphs (DAGs), are widely used to model species or gene relationships that traditional rooted trees cannot fully capture, especially in the presence of reticulate processes or horizontal gene transfers. Such networks or DAGs are typically inferred from genomic data of extant taxa, providing only an estimate of the true evolutionary history. However, these inferred DAGs are often complex and difficult to interpret. In particular, many contain vertices that do not serve as least common ancestors (LCAs) for any subset of the underlying genes or species, thus lacking direct support from the observed data. In contrast, LCA vertices represent ancestral states substantiated by the data, offering important insights into evolutionary relationships among subsets of taxa. To reduce unnecessary complexity and eliminate unsupported vertices, we aim to simplify a DAG to retain only LCA vertices while preserving essential evolutionary information. In this paper, we characterize $\mathrm{LCA}$-relevant and $\mathrm{lca}$-relevant DAGs, defined as those in which every vertex serves as an LCA (or unique LCA) for some subset of taxa. We introduce methods to identify LCAs in DAGs and efficiently transform any DAG into an $\mathrm{LCA}$-relevant or $\mathrm{lca}$-relevant one while preserving key structural properties of the original DAG or network. This transformation is achieved using a simple operator ``$\ominus$'' that mimics vertex suppression.

We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any $c \in \mathbb{N}$, there is a planar graph $G$ such that for any tree $T$ and graph $H$ with $\text{tw}(H) \leq 2$, $G$ is not contained in $H \boxtimes T \boxtimes K_c$., Comment: arXiv admin note: text overlap with arXiv:2410.20333

Given an integer or a non-negative integer solution $x$ to a system $Ax = b$, where the number of non-zero components of $x$ is at most $n$. This paper addresses the following question: How closely can we approximate $b$ with $Ay$, where $y$ is an integer or non-negative integer solution constrained to have at most $k$ non-zero components with $k

We study the asymptotic discrepancy of $m \times m$ matrices $A_1,\ldots,A_n$ belonging to the Gaussian orthogonal ensemble, which is a class of random symmetric matrices with independent normally distributed entries. In the setting $m^2 = o(n)$, our results show that there exists a signing $x \in \{\pm1\}^n$ such that the spectral norm of $\sum_{i=1}^n x_iA_i$ is $\Theta(\sqrt{nm}4^{-(1 + o(1))n/m^2})$ with high probability. This is best possible and settles a recent conjecture by Kunisky and Zhang.

In this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Triangle Hitting (TH). We focus on the class of pseudo-disk graphs, which forms a common generalization of several graph classes where such results exist, like disk graphs and square graphs. In these graphs, we show that TH can be solved in time $2^{O(k^{3/4}\log k)}n^{O(1)}$, and given a geometric representation FVS can be solved in time $2^{O(k^{6/7}\log k)}n^{O(1)}$., Comment: Presented at the conference WG 2024

For a set $P$ of $n$ points in general position in the plane, the flip graph $F(P)$ has a vertex for each non-crossing spanning tree on $P$ and an edge between any two spanning trees that can be transformed into each other by one edge flip. The diameter ${\rm diam}(F(P))$ of this graph is subject of intensive study. For points in general position, it is between $3n/2-5$ and $2n-4$, with no improvement for 25 years. For points in convex position, it lies between $3n/2 - 5$ and $\approx1.95n$, where the lower bound was conjectured to be tight up to an additive constant and the upper bound is a recent breakthrough improvement over several bounds of the form $2n-o(n)$. In this work, we provide new upper and lower bounds on ${\rm diam}(F(P))$, mainly focusing on points in convex position. We show $14n/9 - O(1) \le {\rm diam}(F(P)) \le 5n/3 - 3$, by this disproving the conjectured upper bound of $3n/2$ for convex position, and relevantly improving both the long-standing lower bound for general position and the recent new upper bound for convex position. We complement these by showing that if one of $T,T'$ has at most two boundary edges, then ${\rm dist}(T,T') \le 2d/2 < 3n/2$, where $d = |T-T'|$ is the number of edges in one tree that are not in the other. To prove both the upper and the lower bound, we introduce a new powerful tool. Specifically, we convert the flip distance problem for given $T,T'$ to the problem of a largest acyclic subset in an associated conflict graph $H(T,T')$. In fact, this method is powerful enough to give an equivalent formulation of the diameter of $F(P)$ for points $P$ in convex position up to lower-order terms. As such, conflict graphs are likely the key to a complete resolution of this and possibly also other reconfiguration problems., Comment: an extended abstract appears at SODA 2025

Hypergraphs are generalizations of simple graphs that allow for the representation of complex group interactions beyond pairwise relationships. Clustering coefficients, which quantify the local link density in networks, have been widely studied even for hypergraphs. However, existing definitions of clustering coefficients for hypergraphs do not fully capture the pairwise relationships within hyperedges. In this study, we propose a novel clustering coefficient for hypergraphs that addresses this limitation by transforming the hypergraph into a weighted graph and calculating the clustering coefficient on the resulting graph. Our definition reflects the local link density more accurately than existing definitions. We demonstrate through theoretical evaluation on higher-order motifs that the proposed definition is consistent with the clustering coefficient for simple graphs and effectively captures relationships within hyperedges missed by existing definitions. Empirical evaluation on real-world hypergraph datasets shows that our definition exhibits similar overall clustering tendencies as existing definitions while providing more precise measurements, especially for hypergraphs with larger hyperedges. The proposed clustering coefficient has the potential to reveal structural characteristics in complex hypergraphs that are not detected by existing definitions, leading to a deeper understanding of the underlying interaction patterns in complex hypergraphs.