There are significant obstacles to establishing an equivalence between the worst-case and
average-case hardness of NP: Several results suggest that black-box worst-case to …

Can we design efficient algorithms for finding fast algorithms? This question is captured by
various circuit minimization problems, and algorithms for the corresponding tasks have …

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal with
time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status …

A PAC learning model involves two worst-case requirements: a learner must learn all
functions in a class on all example distributions. However, basing the hardness of learning …

Symmetry of information for time-bounded Kolmogorov complexity is a hypothetical
inequality that relates time-bounded Kolmogorov complexity and its conditional analogue. In …

It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and
related meta-complexity problems are NP-complete. Even for the rare cases where the NP …

We show that a decidable promise problem has a non-interactive statistical zero-knowledge
proof system if and only if it is randomly reducible via an honest polynomial-time reduction to …

We give a new FPT algorithm testing isomorphism of n-vertex graphs of tree-width k in time 2
kpolylog (k) n3, improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and …

VAUGHAN JONES, KOLMOGOROV COMPLEXITY, AND THE NEW COMPLEXITY LANDSCAPE
AROUND CIRCUIT MINIMIZATION Eric Allender 1. Introduction Page 1 NEW ZEALAND …

The New Complexity Landscape Around Circuit Minimization | SpringerLink Skip to main content
Advertisement SpringerLink Account Menu Find a journal Publish with us Track your research …