archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 2
-
Bounded carving width orders Eulerian digraphs by strong immersion
Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
-
EPTAS for ConstrainedMinCut on everywhere-dense graphs
EPTAS for Hard Graph Cut Problems for Dense Graphs
-
Mutations let relaxed QUBO gradients beat heuristics on large graphs
Mutation-Guided Differentiable Quadratic Combinatorial Optimization
-
Global LLM rankings cancel out two-thirds of votes
Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML
-
Minor-closed classes get (1+o(1))log n adjacency labels
Adjacency labelling for proper minor-closed graph classes
-
Proper minor-closed graphs admit (1+o(1))log n-bit adjacency labels
Adjacency labelling for proper minor-closed graph classes
-
Random walk mixes in log time on fast dynamical random-cluster graphs
Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models
-
Online algorithms hit exact limit for independent sets in dense hypergraphs
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
-
Graph Normalization converges to binary MWIS solutions
Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS
-
Local homophily on graphs simulates Boolean circuits
Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
-
The paper develops Markov chain methods for sampling uniform simultaneous edge-colorings…
Sampling Simultaneous Edge-Colorings
-
Largest s-matching-free permutation families characterized
Matchings in permutations
-
W-state graphs reduce to W-cone assemblies
W-state graphs: Structure and Algorithms
-
Directed tori admit Hamilton decompositions for every odd modulus
Hamilton decompositions of all directed tori at odd modulus
-
Directed tori with odd cycle lengths decompose into Hamilton cycles
Hamilton decompositions of all directed tori at odd modulus
-
Demand-aware nets reach 5/8 throughput vs 1/2 for fixed ones
A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput
-
Approximate version of Frankl-Kupavskii conjecture proven for large s
More on the Erd\H os--Kleitman problem on matchings in set families
-
Neural net breakthroughs align with rising architectural complexity
On the Architectural Complexity of Neural Networks
-
Thinned quantile share is unconditionally feasible
Thinned Quantile Shares are Universally Feasible
-
The paper proves that every graph without an induced path on five vertices and without…
Tree-independence number of $P_5$-free graphs with no large bicliques
-
Packing chromatic critical graphs with radius 1 are structurally characterized
Packing chromatic critical graphs with radius at most 2
-
No online algorithm finds common induced subgraphs beyond 2 log n
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
-
Algorithms decide if required and forbidden LCA constraints fit a phylogenetic network
Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints
-
Algorithms build networks from required and forbidden LCA rules
Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints
-
Unimodular matrices with no zeros can keep inverses small too
Small Matrices with Small Inverses: Unimodular Zerofree Cases
-
Zerofree unimodular matrices can have small inverses
Small Matrices with Small Inverses: Unimodular Zerofree Cases
-
Unimodular zero-free matrices keep both self and inverse small
Small Matrices with Small Inverses: Unimodular Zerofree Cases
-
Most ReLU networks have identifiable parameters
Most ReLU Networks Admit Identifiable Parameters
-
ReLU networks with wide layers have identifiable parameters
Most ReLU Networks Admit Identifiable Parameters
-
Restricted Dyck paths yield new Catalan identity
An Identity for Catalan Numbers via Restricted Dyck Paths
-
Symmetry counting gives closed-form surface code error rates
Closed form logical error rate approximations for surface codes
-
O(k^33) kernel for deleting to proper interval graphs or trees
A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
-
Bicriteria model trades train travel time against regenerative braking overlap
Optimizing Travel Time and Regenerative Energy for Periodic Timetables
-
Shift graphs have word representations
Word-Representability of Shift Graphs
-
Shift graphs admit representing words
Word-Representability of Shift Graphs
-
Moments of group functions computed from Fourier coefficients alone
Statistics of a multi-factor function from its Fourier transform
-
Trees exist whose dominating-set counts break log-concavity at m places for any m
Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools
-
Hybrid solver finishes hard 10x10 Latin squares in 5100s
Improving SAT Solvers on Orthogonal Latin Square Problems
-
Tradable shares replace authorship to measure research impact
Liberata -- Graph Scientometrics for a Share Based System of Academic Publishing
-
Triangulation flip chain mixes in Õ(n²) time
Faster Mixing for Triangulations via Transport Flows
-
Influence-weighted butterfly layers yield Schur-convex invariant for Boolean functions
The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
-
Nonunit core of comaximal graph has connectivity phi(n)/(p-1)
Vertex connectivity of the nonzero nonunit core of the comaximal graph of $\mathbb Z_n$
-
Redundant transitivity constraints removable from clique partitioning
On the redundancy of transitivity constraints in the clique partitioning problem
-
Alpha-orderings unify two algorithms for symmetric submodular minimization
A Unified Approach to Minimizing Symmetric Submodular Functions
-
Edge twists produce circular embeddings of cubic graphs
Facial diagrams and cycle double cover
-
Winner of partizan domination fixed by any coloring on stars
The Normal Domination Partizan Game in Stars
-
Complete triplet and duet data reconstructs arboreal networks
Efficient Reconstruction of Arboreal Networks
-
For n=ms+c, max family without s disjoint sets has size sum binom(n,k) for k>m
Families without $s$-matchings: the other end
-
Near-linear algorithm finds well-spread perfect matchings in cubic graphs
A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
-
Directed 7-torus decomposes into Hamilton cycles for odd m
Hamilton decompositions of the directed 7-torus at odd modulus via root-flat certificates and a prefix-count construction