Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with fixed-parameter tractability:
TR12-150 | 1st November 2012
Michael Elberfeld, Christoph Stockhusen, Till Tantau

On the Space Complexity of Parameterized Problems

Revisions: 1

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>

TR22-164 | 20th November 2022
Shuichi Hirahara, Mikito Nanashima

Learning versus Pseudorandom Generators in Constant Parallel Time

A polynomial-stretch pseudorandom generator (PPRG) in NC$^0$ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators ... more >>>

ISSN 1433-8092 | Imprint