archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 1
-
Signs keep vector sums in zonotopes within C sqrt(d) bound
Optimal Vector Balancing for Zonotopes
-
Square grids have the most spanning trees among fixed-vertex rectangles
A Balancing Theorem for Spanning Trees of Rectangular Grid Graphs
-
Uniform distribution maximizes independent-set sampling probability
Maximum Probability of Independence in Transitive Matroids
-
Entropy testing needs fewer samples than closeness testing
Entropy Equivalence Testing
-
Connected collision graphs uniquely recover object positions
Positional Identifiability from Pairwise Collision Data
-
Projection of flags complex gives sub-polynomial expander
A Simple Sub-Polynomial Degree Coboundary Expander
5 Piths -
Algorithm exactly samples weighted polygon triangulations in O(n√λ log n) time
On weighted partial triangulations of convex polygons
-
Min sum set cover cost at most tau log of hyperedges
Minimum Sum Set Cover: Structures and Algorithm
-
Quadratic forms classify undirected graphs on finite field subspaces
Graphs from quadratic forms and vector spaces over finite fields
-
Randomized cake cutting needs Omega(n log n) queries
An $\Omega(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
-
Graphs of genus g need at least (8/3)^g Pfaffians
Exponential Lower Bounds for the Pfaffian Number of Graphs
-
Hop and 2-step domination NP-complete even on regular graphs
On the Complexity of Hop Domination and 2-Step Domination in Graph Classes
-
r-graphs can avoid full Ramsey arrow but satisfy reduced version
A note on hypergraphs with asymmetric Ramsey properties
-
Contradiction graph decides VC dimension threshold for any m
Contradiction Graphs Determine VC Dimension
5 Piths -
Arc-deletion distance to orchard networks is NP-hard
Computing the Arc-Deletion Distance to Orchard Networks is NP-hard
-
Exact conditions found for multi-room wakeup solutions
A parallel wakeup problem and multi-room light switch strategies
-
Number of finite additive 2-bases grows exponentially
On the number of finite additive 2-bases
-
Probabilistic proof shows exponential growth of additive 2-bases
On the number of finite additive 2-bases
-
Shrinking factors enable super-linear NRD bounds for CSP predicates
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
-
ILPs compute exact harmonious chromatic numbers
Harmonious Colorings: bounds, heuristics and integer-linear formulations
-
Forbidden sets solve capacitated power domination 1.7x faster
Capacitated power dominating set problem: a solution approach based on forbidden propagation sets
-
Three-layer ReLU nets have explicit parameter symmetries
The Symmetries of Three-Layer ReLU Networks
-
Weighted Hanoi yields closed forms via two move strategies
The Weighted Tower of Hanoi: Algebraic Structure, Phase Transitions, and Integer Sequences
-
Closed forms derived for weighted Tower of Hanoi costs
The Weighted Tower of Hanoi: Algebraic Structure, Phase Transitions, and Integer Sequences
-
Closed forms found for weighted Tower of Hanoi costs
The Weighted Tower of Hanoi: Algebraic Structure, Phase Transitions, and Integer Sequences
-
FPT algorithms for broadcast independence via treewidth and diameter
On the parameterized complexity of Broadcast Independence and Broadcast Packing
-
k-edge-deficient temporal graphs explored in O(nk log k) time
Exploration of $k$-edge-deficient temporal graphs in linear time
-
Bounded clique-width iff H induced subgraph of P4
Clique-width and induced topological minors
-
Counterexamples disprove Laplacian ratio conjecture for trees
Counterexamples to a Conjecture on Laplacian Ratios of Trees
-
Non-convex solvers find exact nonnegative ranks for some matrices
Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
-
Cochordal property yields exact Betti numbers for chain ring graphs
Betti numbers for cochordal zero-divisor graphs of commutative rings
-
Gallai vertex decision is Θ₂^p-complete
The Gallai Vertex Problem is $\Theta_2^p$-Complete
4 Piths -
Twin cover bounds conflict-free vertex colors to chi plus t
Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
-
BFS width plus few backward arcs yields FPT for PAFP
Layer-Based Width for PAFP
-
One central variable turns linear ascents exponential
Binary constraints on one additional variable can create exponential ascents
-
Planar digraph feedback vertex sets bounded by (n-2)/(g-2)
Feedback vertex sets of planar digraphs with fixed digirth
-
Ternary sum entropy maximized by mostly binary variables
Maximum Entropy of Sums of Independent Ternary Random Variables
-
Coarse Menger theorem holds on every surface with bounded modulator
A coarse Menger's Theorem for planar and bounded genus graphs
-
Paths maximize zero forcing sets among distance-hereditary graphs
The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction
-
O(k ln Δ) bound for conflict-free choice numbers in K1,k-free graphs
Computational and Combinatorial Results on Conflict-free Choosability
-
8/3 approximation for matroid-constrained randomized vertex-cover interdiction
Randomized Max-Vertex-Cover Interdiction with Matroid Constraints
-
Exact optimal repair bandwidth for (n,n-2,2) MDS codes found
Optimal Repair Bandwidth and Repair I/O of $(n,n-2,2)$ MDS Array Codes
-
Graphs without dominating K5-models are 4-colorable
The Dominating 4-Colour Theorem
-
Excluded-minor graphs pack paths or block with f(k) balls of radius O(r)
Coarse Menger property of quasi-minor excluded graphs and length spaces
-
Deterministic algorithm finds high-order element or factors N
Deterministically finding an element of large order in $\mathbb{Z}_N^*$
-
Simpler algorithm solves node-weighted triangles in MM(n) time
Node-Weighted Triangles: Faster and Simpler
-
Planarizing gadgets do not exist for (k,l)-tight graphs
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
-
Vertex cover local search runs in ℓ^{f(k)} n time
Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
-
Bijections via tableaux with walls prove Pons-Batle conjecture for bounded-k networks
A Combinatorial Framework for the Pons-Batle Identity: Young Tableaux, Lattice Paths, and Limit Laws
-
Brik recursion yields binary word with transcendental 1-density
Brik's sequence: a strange recursion