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 and ETH-Based Additive Inapproximability of Deterministic Communication Complexity via Relaxed Interlacing
Serge Gaspers, Tao Zixu He, Simon Mackenzie
How difficult is it to find an efficient communication protocol when the entire truth table of the function is given? We give a unified interlacing proof of NP-completeness for exa…