4 papers
Lossless Hardness Condensation in Deterministic Communication Complexity
Simon Mackenzie
A communication problem can have far more possible inputs than its communication cost would suggest. Must its difficulty already be present on a much smaller set of inputs? We prov…
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…
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…
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…