archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 5
-
LLM lemmas certify 0.8559 lower bound on Steiner ratio
Towards Solving the Gilbert-Pollak Conjecture via Large Language Models
-
Local guesses force quadratic turns in permutation Mastermind
Price of Locality in Permutation Mastermind: Are TikTok influencers Chaotic Enough?
-
Orbit Problem decidable for logarithmic-dimension targets
On the Subspace Orbit Problem and the Simultaneous Skolem Problem
-
Linear Turán bound for 4-edge hypertree is (r+1)n/r
Bounds on Linear Tur\'{a}n Number for Trees
-
Geodetic graphs reduce to bigeodetic even building blocks
A Characterization of Geodetic Graphs in Terms of their Embedded Even Graphs
-
Pathwidth three forces exponential ascents in local search
All ascents exponential from valued constraint graphs of pathwidth three
-
Free expander walks build explicit codes matching GV bound
Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
-
Bond polytopes of summed graphs are built from their parts
Bond Polytope under Vertex- and Edge-sums
-
Boolean function degree at most cube of rational degree
Rational degree is polynomially related to degree
-
Deterministic algorithms match free-probability matrix bounds
Derandomizing Matrix Concentration Inequalities from Free Probability
-
Phases in ERGMs satisfy approximate FKG inequality
Approximate FKG inequalities for phase-bound spin systems, with applications to central limit theorems for exponential random graphs
-
Planar multigraphs contain induced forests of size at least n/4
Large induced forests in planar multigraphs
-
Secure domination NP-complete on bisplit graphs
Secure Domination in Bisplit graphs -- A Structural and algorithmic study
-
Deterministic algo finds log-sized guards for near-full area visibility
A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
-
Construction gives first infinite family of non-weakly regular cubic ternary bent vectors
Results on cubic bent and weakly regular bent $p$-ary functions leading to a class of cubic ternary non-weakly regular bent functions
-
Z_2^8-flows reconfigure on all 2-edge-connected graphs
Nowhere-zero flow reconfiguration
-
Co-bipartite graphs are word-representable exactly when circle graphs
Forbidden Induced Subgraph Characterization of Word-Representable Co-bipartite Graphs
-
3D SFT enforces at most two symbols per vertical column
A Three-Dimensional SFT with Sparse Columns
-
Design combination yields first non-extremal triple arrays
Resolvable Triple Arrays
-
Strictly interval graphs recognized in linear time
Structural and Spectral Properties of Strictly Interval Graphs
-
SAT solver finds 327-step path avoiding seven collinear points
North-East Lattice Paths Avoiding $k$ Collinear Points via Satisfiability
-
Computer proofs confirm lonely runner conjecture for 9 and 10 runners
Nine and ten lonely runners
-
Restricted Stirling numbers give new recurrence for bottleneck birthdays
The Bottleneck Birthday Problem
-
Conjectures from small k-path graphs on extremal eigenvalues
$k$-path graphs: experiments and conjectures about algebraic connectivity and $\alpha$-index
-
Greedy algorithm matches best shortcut set tradeoffs up to log n
Greedy Algorithms for Shortcut Sets and Hopsets
-
Hypercube heat flow beats Markov tails up to loglog factor
Talagrand's convolution conjecture up to loglog via perturbed reverse heat
-
Constraint embedding lifts QAOA feasible mass exponentially for permutations
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
-
Online algorithm colors k-colorable graphs with fewer colors
Online Graph Coloring for $k$-Colorable Graphs
-
One-bit sensing recovers sparse supports in sublinear time
Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
-
Canonical DAG realizes LCA constraints exactly when any DAG does
Inferring DAGs and Phylogenetic Networks from Least Common Ancestors
-
Quasipolylog rounds for (Δ+1)-coloring when neighborhood independence is bounded
Distributed $(\Delta+1)$-Coloring in Graphs of Bounded Neighborhood Independence
-
Three axioms fix Shapley values on weighted acyclic multigraphs
M\"obius transforms and Shapley values for vector-valued functions on weighted directed acyclic multigraphs
-
Automata decide balance of Fibonacci word rectangles
Balanced Fibonacci word rectangles, and beyond
-
ReLU positivity is W[1]-hard parameterized by dimension
Parameterized Hardness of Zonotope Containment and Neural Network Verification
-
Winner decision for 4-uniform Maker-Breaker games is PSPACE-complete
4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
-
Grid power contamination number proven exact
The Power Contamination Problem on Grids Revisited: Optimality, Combinatorics, and Links to Integer Sequences
-
First algorithm finds optimal trees with hypersurface splits
Optimal hypersurface decision trees
-
Bound of (2r+1)^{2^{k-1}-1} on progressing moves in splitter games
A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
-
Min-forced vertices capped at 2/5 of graph order
New Results on Vertices that Belong to Every Minimum Locating-Dominating Code
-
Treewidth k graphs get decompositions of width 14k+13
Tree decompositions with small width, spread, order and degree
-
Signed inversion count of partition matrices equals inversion sequence subclass
Signed counting of partition matrices
-
Grundy Domination Variants Are W[1]-Complete by Sequence Length
On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
-
Direct sampler draws balanced partitions without trees
Sampling Tree-Weighted Partitions Without Sampling Trees
-
Quantum solver cuts 3D fracture flow runtime to N to the two-thirds
Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
-
Bichromatic triangle search is PPP-complete
The PPP-completeness of the Ward-Szabo theorem
-
Undecidability of Θ(n)-block gluing shown for homshifts
Undecidability of the block gluing classes of homshifts
-
Uncrossed number lower bound tightened with square-root corrections
General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
-
Edge-coloring with odd-cycle and clique forbids splits into P or NP-complete
Edge-coloring problems with forbidden patterns and planted colors
-
Variables merge to strongly sparsify 1-in-3-SAT
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
-
Random points covered by O(n log n) monotone paths
Covering Complete Geometric Graphs by Monotone Paths