Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with correlated instances:
TR16-056 | 8th April 2016
Shafi Goldwasser, Dhiraj Holden

On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.
In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ... more >>>

ISSN 1433-8092 | Imprint