3 papers
cs.DS2026
Faster Exponential-Time Approximate Counting via Bounded Self-Reductions
Katie Clinch, Serge Gaspers, Simon Mackenzie +1
We give faster exponential-time randomised approximation algorithms for counting problems where polynomial-time approximation is unavailable and exact exponential-time counting rem…
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,…