2698 papers
Mathematics often feels like an abstract fortress, but the "Co" in this category opens a door to computational complexity, a field dedicated to understanding the limits of what computers can solve efficiently. It explores why some problems are easy to crack while others remain stubbornly out of reach, even with the most powerful machines imaginable. This area sits at the crossroads of pure math and computer science, shaping how we approach cryptography, optimization, and the very nature of computation itself.
At Gist.Science, we bridge the gap between these dense theoretical papers and curious readers by processing every new preprint in this category directly from arXiv. Our team generates both detailed technical summaries for experts and accessible plain-language explanations for everyone else, ensuring that groundbreaking research is never locked behind a wall of jargon. Below are the latest papers in computational complexity, ranging from new algorithmic breakthroughs to deep theoretical insights.
This paper presents a unified combinatorial framework that derives strong spatial mixing directly from zero-freeness using a novel Christoffel-Darboux-type identity, thereby extending Weitz's FPTAS to all known zero-free regions of general 2-spin systems with pinned vertices, including regimes where traditional tree-recurrence proofs fail.
Using flag algebras, this paper proves that a uniformly random red/blue edge coloring asymptotically maximizes the number of color-alternating 6-cycles in a large clique, thereby resolving the first open case of a problem posed by Basit et al.
This paper investigates the existence and uniqueness of partitions of the set into subsets of size at most with sums that are powers of , proving that while such partitions fail for infinitely many when , they likely exist for all when (subject to specific constraints on potential counter-examples) and establishing exact counts for the number of such partitions for various values of .
This paper resolves Nathanson's question on the possible cardinalities of -fold sumsets by proving that for sufficiently large set sizes , the range of possible sizes consists of all integers within the theoretical bounds except for a specific set of exceptions, with the threshold established as when .
By establishing a correspondence between nowhere-zero three-bit flows and labeled triangles, this paper proves the Cycle Double Cover Conjecture, demonstrating that every finite bridgeless multigraph admits a cycle double cover.
This paper serves as a memorial tribute to Adriano Garsia (1928–2024), outlining his life journey from Tunis to the United States, his academic career at institutions including Stanford, MIT, and UC San Diego, and his passing at the age of 96.
This paper presents an efficient online algorithm based on a Metropolis fixed-point walk that extends the validity of the Beck–Fiala conjecture to logarithmic sparsity () by minimizing prefix discrepancy, a result developed with significant assistance from an AI language model.
This paper generalizes the concept of shuffle-compatibility from permutations to words, parking functions, and set partitions, systematically reviewing relevant statistics and constructing associated (shifted) shuffle algebras that connect to major combinatorial Hopf algebras while providing new combinatorial interpretations and bases.
This paper establishes universal asymptotic formulas for the number of connected, labeled, genus- Eulerian maps with arbitrary degree sequences as the vertex count grows, linking the leading constant to the Painlevé I equation via orthogonal polynomials and analytic combinatorics, while also providing the first exact enumeration for genus-1 non-regular maps.
This paper settles the first open case of the small Davenport constant for exponent- Heisenberg groups by proving through a combination of theoretical reductions to additive combinatorics and exhaustive, machine-checked computer verification, while also identifying why the proposed general formula fails for .