Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Parameterization:
TR12-018 | 24th February 2012
Joerg Flum, Moritz Müller

Some definitorial suggestions for parameterized proof complexity

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>

TR17-103 | 12th June 2017
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

Parameterized Property Testing of Functions

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>

ISSN 1433-8092 | Imprint