Cited By
View all- Downey R(2012)The birth and early years of parameterized complexityThe Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344239(17-38)Online publication date: 1-Jan-2012
Parameterized derandomization
Pages 148 - 159
Abstract
The class W[P] is a parameterized analogue of NP. Chen etal. [4] have given a machine characterization of W[P]. The correspondingmachine model gives rise to a parameterized analogue of BPP. What isthe connection between parameterized and classical derandomization?
References
[1]
Alekhnovich, M., Razborov, A.A.: Resolution is Not Automatizable Unless W{P}is Tractable. In: Proceedings of the 41th IEEE Symposium on Foundations ofComputer Science, pp. 210-219 (2001).
[2]
Arvind, V., Raman, V.: Approximation Algorithms for Some Parameterized CountingProblems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp.453-464. Springer, Heidelberg (2002).
[3]
Chen, Y., Flum, J.: The Parameterized Complexity of Maximality and MinimalityProblems. Annals of Pure and Applied Logic 151(1), 22-61 (2008); In: Bodlaender,H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 22-61. Springer,Heidelberg (2006).
[4]
Chen, Y., Flum, J., Grohe, M.: Machine-based methods in parameterized complexitytheory. Theoretical Computer Science 339, 167-199 (2005).
[5]
Downey, R.G., Fellows, M.R., Regan, K.W.: Parameterized Circuit Complexity andthe W Hierarchy. Theoretical Computer Science 191(1-2), 97-115 (1998).
[6]
Eickmeyer, K., Grohe, M., Grübner, M.: Approximisation of W{P}-complete minimisationproblems is hard. In: 23rd CCC (2008).
[7]
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg(2006).
[8]
Grohe, M.: Communication.
[9]
Montoya, J.A.: Communication.
[10]
Müller, M.: Randomized Approximations of Parameterized Counting Problems.In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp.50-59. Springer, Heidelberg (2006).
[11]
Müller, M.: Valiant-Vazirani Lemmata for Various Logics (manuscript).
[12]
Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Reading (1994).
[13]
Sloper, C., Telle, J.A.: Towards a Taxonomy of Techniques for Designing ParameterizedAlgorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006.LNCS, vol. 4169, pp. 251-263. Springer, Heidelberg (2006).
[14]
Toda, S.: PP is as Hard as the Polynomial Hierarchy. SIAM Journal on Computing20(5), 865-877 (1991).
Index Terms
- Parameterized derandomization
Recommendations
Holographic Proofs and Derandomization
We derive a stronger consequence of $\mathsf{EXP}$ (deterministic exponential time) having polynomial-size circuits than was known previously, namely that for each language $L \in \mathsf{P}$ (polynomial time), and for each efficiently decidable error-...
Natural proofs versus derandomization
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingWe study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as NEXP ⊄ TC0, which are still wide open. Natural Proofs have three properties: they are constructive (an efficient algorithm A is ...
Pseudorandom Generators and Typically-Correct Derandomization
APPROX '09 / RANDOM '09: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and TechniquesThe area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 14 May 2008
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 3Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Downey R(2012)The birth and early years of parameterized complexityThe Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344239(17-38)Online publication date: 1-Jan-2012
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in