2 papers
cs.DS2025
A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
Katie Clinch, Serge Gaspers, Tao Zixu He +2
This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method…
cs.CC2025
NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
Serge Gaspers, Tao Zixu He, Simon Mackenzie
We prove that computing the deterministic communication complexity of a Boolean function, given its truth table, is \textsf{NP}-complete in the standard protocol-tree-depth model,…