{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T18:23:39Z","timestamp":1765045419293},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,12,22]],"date-time":"2011-12-22T00:00:00Z","timestamp":1324512000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s00224-011-9381-0","type":"journal-article","created":{"date-parts":[[2011,12,21]],"date-time":"2011-12-21T05:45:24Z","timestamp":1324446324000},"page":"221-270","source":"Crossref","is-referenced-by-count":9,"title":["Parameterized Random Complexity"],"prefix":"10.1007","volume":"52","author":[{"given":"Juan Andr\u00e9s","family":"Montoya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,12,22]]},"reference":[{"key":"9381_CR1","first-page":"132","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201987)","author":"M. Ajtai","year":"1987","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Deterministic simulation in LOGSPACE. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201987), pp. 132\u2013140 (1987)"},{"key":"9381_CR2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1109\/SFCS.2001.959895","volume-title":"Proceedings of the 41th IEEE Symposium on Foundations of Computer Science (FOCS\u201901)","author":"M. Alekhnovich","year":"2001","unstructured":"Alekhnovich, M., Razborov, A.A.: Resolution is not automatizable unless W[P] is tractable. In: Proceedings of the 41th IEEE Symposium on Foundations of Computer Science (FOCS\u201901), pp. 210\u2013219 (2001)"},{"key":"9381_CR3","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9381_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Perspective","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Perspective. Cambridge University Press, Cambridge (2009)"},{"key":"9381_CR5","series-title":"LNCS","first-page":"453","volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, I., Morin, P. (eds.) Proceedings of the 13th International Symposium on Algorithms and Computation. LNCS, vol. 2518, pp. 453\u2013464. Springer, Berlin (2002)"},{"key":"9381_CR6","first-page":"80","volume":"55","author":"A. Blass","year":"1982","unstructured":"Blass, A., Gurevich, Y.: On the unique satisfiability problem. Inf. Comput. 55, 80\u201388 (1982)","journal-title":"Inf. Comput."},{"key":"9381_CR7","series-title":"Springer Texts in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3124-8","volume-title":"Markov Chains, Gibbs Fields, Monte Carlo Simulation and Qeues","author":"P. Bremaud","year":"1999","unstructured":"Bremaud, P.: Markov Chains, Gibbs Fields, Monte Carlo Simulation and Qeues. Springer Texts in Applied Mathematics, vol.\u00a031 (1999)"},{"key":"9381_CR8","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1109\/T-C.1973.223757","volume":"C-22","author":"R.P. Brent","year":"1973","unstructured":"Brent, R.P., Kuck, D.J., Maruyama, K.: The parallel evaluation of arithmetic expressions without division. IEEE Trans. Comput. C-22, 532\u2013534 (1973)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"9381_CR9","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. J. ACM 21(2), 201\u2013206 (1974)","journal-title":"J. ACM"},{"key":"9381_CR10","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/11847250_22","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906)","author":"L. Cai","year":"2006","unstructured":"Cai, L.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906). LNCS, vol. 4169, pp. 239\u2013250 (2006)"},{"key":"9381_CR11","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/inco.1995.1156","volume":"123","author":"L. Cai","year":"1995","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the structure of parameterized problems in NP. Inf. Comput. 123, 38\u201349 (1995)","journal-title":"Inf. Comput."},{"key":"9381_CR12","first-page":"135","volume-title":"Proceedings of the 18th IEEE Conference on Computational Complexity (CCC\u201903)","author":"C. Calabro","year":"2003","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of unique k-SAT: an isolation lemma for k-CNFs. In: Proceedings of the 18th IEEE Conference on Computational Complexity (CCC\u201903), pp. 135\u2013141 (2003)"},{"issue":"3","key":"9381_CR13","first-page":"173","volume":"28","author":"R. Chang","year":"1995","unstructured":"Chang, R., Kadin, J.: On computing boolean connectives of characteristic functions. Theory Comput. Syst. 28(3), 173\u2013198 (1995)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"9381_CR14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1006\/jcss.1995.1028","volume":"50","author":"R. Chang","year":"1995","unstructured":"Chang, R., Kadin, J., Rohatgi, P.: On unique satisfiability and the threshold behavior of randomized reductions. J. Comput. Syst. Sci. 50(3), 359\u2013373 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9381_CR15","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1145\/167088.167213","volume-title":"Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC\u201993)","author":"S. Chari","year":"1993","unstructured":"Chari, S., Rohatgi, P., Srinivasan, A.: Randomness-optimal unique element isolation, with applications to perfect matching and related problems. In: Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC\u201993), pp. 458\u2013467 (1993)"},{"key":"9381_CR16","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-79723-4_1","volume-title":"Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC\u201908)","author":"J. Chen","year":"2008","unstructured":"Chen, J.: Randomized disposal of unknowns and implicitly enforced bounds on parameters. In: Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC\u201908), Victoria. LNCS, vol. 5018, pp. 1\u20138 (2008)"},{"key":"9381_CR17","first-page":"298","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"J. Chen","year":"2007","unstructured":"Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching and packing problems. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907), pp. 298\u2013307 (2007)"},{"key":"9381_CR18","unstructured":"Chen, Y.: Model-checking problems, machines and parameterized complexity. Dissertation, Albert-Ludwigs-Universit\u00e4t Freiburg i.Br. (2004)"},{"key":"9381_CR19","series-title":"LNCS","first-page":"389","volume-title":"Proceedings of the 21st International Workshop on Computer Science Logic (CSL\u201907)","author":"Y. Chen","year":"2007","unstructured":"Chen, Y., Flum, J.: Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping. In: Proceedings of the 21st International Workshop on Computer Science Logic (CSL\u201907). LNCS, vol. 4646, pp. 389\u2013404 (2007)"},{"issue":"1","key":"9381_CR20","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.apal.2007.09.003","volume":"151","author":"Y. Chen","year":"2008","unstructured":"Chen, Y., Flum, J.: The parameterized complexity of maximality and minimality problems. Ann. Pure Appl. Log. 151(1), 22\u201361 (2008)","journal-title":"Ann. Pure Appl. Log."},{"issue":"4","key":"9381_CR21","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1137\/070687153","volume":"37","author":"Y. Chen","year":"2007","unstructured":"Chen, Y., Grohe, M.: An isomorphism between subexponential and parameterized complexity theory. SIAM J. Comput. 37(4), 1228\u20131258 (2007)","journal-title":"SIAM J. Comput."},{"key":"9381_CR22","first-page":"13","volume-title":"Proceedings of the 18th IEEE Conference on Computational Complexity (CCC\u201903)","author":"Y. Chen","year":"2003","unstructured":"Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: Proceedings of the 18th IEEE Conference on Computational Complexity (CCC\u201903), pp. 13\u201329 (2003)"},{"key":"9381_CR23","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.tcs.2005.02.003","volume":"339","author":"Y. Chen","year":"2005","unstructured":"Chen, Y., Flum, J., Grohe, M.: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339, 167\u2013199 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9381_CR24","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1007\/s00224-010-9270-y","volume":"48","author":"Y. Chen","year":"2011","unstructured":"Chen, Y., Flum, J., M\u00fcller, M.: Lower bounds for kernelizations and other preprocessing procedures. Theory Comput. Syst. 48(4), 803\u2013839 (2011)","journal-title":"Theory Comput. Syst."},{"key":"9381_CR25","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A., Reckhoff, R.A.: Time bounded random access machines. J. Comput. Syst. Sci. 7, 354\u2013375 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"9381_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9381_CR27","series-title":"Australian Computer Science Communications","first-page":"1","volume-title":"Proceedings of Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity after almost ten years: review and open questions. In: Proceedings of Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999. Australian Computer Science Communications, vol. 21, pp. 1\u201333. Springer, Berlin (1999)"},{"issue":"1\u20132","key":"9381_CR28","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0304-3975(96)00317-9","volume":"191","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R., Regan, K.W.: Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1\u20132), 97\u2013115 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9381_CR29","series-title":"Electronic Notes in Theoretical Computer Science","first-page":"209","volume-title":"Proceeding of the Australasian Theory Symposium (CATS\u201903)","author":"R.G. Downey","year":"2003","unstructured":"Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prietoc, E., Rosamond, F.A.: Cutting up is hard to do: the parameterised complexity of k-cut and related problems. In: Harland, J. (ed.) Proceeding of the Australasian Theory Symposium (CATS\u201903). Electronic Notes in Theoretical Computer Science, vol. 78, pp. 209\u2013222 (2003)"},{"key":"9381_CR30","first-page":"25","volume-title":"Model-Theoretical Logics","author":"H.D. Ebbinghaus","year":"1985","unstructured":"Ebbinghaus, H.D.: Extended logics: the general framework. In: Barwise, J., Feferman, S. (eds.) Model-Theoretical Logics, pp. 25\u201376. Springer, Berlin (1985)"},{"key":"9381_CR31","volume-title":"Proceedings of the 24th International Workshop Computer Science Logic (CSL\u201910)","author":"K. Eickmeyer","year":"2010","unstructured":"Eickmeyer, K., Grohe, M.: Randomisation and derandomisation in descriptive complexity theory. In: Proceedings of the 24th International Workshop Computer Science Logic (CSL\u201910) (2010)"},{"key":"9381_CR32","first-page":"8","volume-title":"Proceedings 23rd IEEE Conference on Computational Complexity (CCC\u201908)","author":"K. Eickmeyer","year":"2008","unstructured":"Eickmeyer, K., Grohe, M., Gr\u00fcbner, M.: Approximisation of W[P]-complete minimisation problems is hard. In: Proceedings 23rd IEEE Conference on Computational Complexity (CCC\u201908), pp. 8\u201318 (2008)"},{"key":"9381_CR33","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-56686-4_38","volume-title":"Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC\u201993)","author":"M.R. Fellows","year":"1993","unstructured":"Fellows, M.R., Koblitz, N.: Fixed-parameter complexity and cryptography. In: Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC\u201993). LNCS, vol. 673, pp. 121\u2013131. Springer, Berlin (1993)"},{"key":"9381_CR34","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/S0097539799360768","volume":"31","author":"J. Flum","year":"2001","unstructured":"Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model checking. SIAM J. Comput. 31, 113\u2013145 (2001)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9381_CR35","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"key":"9381_CR36","doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M.: Model-checking problems as a basis for parameterized intractability. Log. Methods Comput. Sci. 1(1) (2005). Conference version in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS\u201904), pp.\u00a0388\u2013397 (2004)","DOI":"10.1109\/LICS.2004.1319633"},{"key":"9381_CR37","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9381_CR38","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.jcss.2005.06.003","volume":"72","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M., Weyer, M.: Bounded fixed-parameter tractability and log2 n nondeterministic bits. J. Comput. Syst. Sci. 72, 34\u201371 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9381_CR39","unstructured":"Goldreich, O.: Randomized methods in computation\u2014lecture notes (2001); available at http:\/\/www.wisdom.weizmann.ac.il\/~oded\/homepage.html"},{"key":"9381_CR40","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008)"},{"issue":"4","key":"9381_CR41","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1093\/logcom\/7.4.457","volume":"7","author":"E. Grandjean","year":"1997","unstructured":"Grandjean, E., Kleine-B\u00fcning, H.: SAT-problems and reductions with respect to the number of variables. J. Log. Comput. 7(4), 457\u2013471 (1997)","journal-title":"J. Log. Comput."},{"key":"9381_CR42","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of generalized model-checking problems. Unpublished manuscript (2001)","DOI":"10.1007\/3-540-44693-1_2"},{"issue":"4","key":"9381_CR43","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc."},{"key":"9381_CR44","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Intergrating: Algorithms and Complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, Sampling and Intergrating: Algorithms and Complexity. Birkh\u00e4user, Basel (2003)"},{"key":"9381_CR45","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9381_CR46","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/11847250_8","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906)","author":"Y. Liu","year":"2006","unstructured":"Liu, Y., Lu, S., Chen, J., Sze, S.-H.: Greedy localization and color-coding: improved matching and packing algorithms. In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906). LNCS, vol. 4169, pp. 84\u201395 (2006)"},{"issue":"4","key":"9381_CR47","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1561\/0400000009","volume":"1","author":"M. Luby","year":"2005","unstructured":"Luby, M., Wigderson, A.: Pairwise independence and derandomization. Found. Trends Theor. Comput. Sci. 1(4), 237\u2013301 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"9381_CR48","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s00037-005-0195-9","volume":"14","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Parameterized complexity of constraint satisfaction problems. Comput. Complex. 14(2), 153\u2013183 (2005)","journal-title":"Comput. Complex."},{"key":"9381_CR49","unstructured":"Montoya, J.A.: On parameterized counting. Dissertation, Albert-Ludwigs-Universit\u00e4t Freiburg i.Br. (2008)"},{"issue":"1","key":"9381_CR50","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.ipl.2008.06.007","volume":"109","author":"J.A. Montoya","year":"2008","unstructured":"Montoya, J.A.: The parameterized complexity of probability amplification. Inf. Process. Lett. 109(1), 46\u201353 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9381_CR51","doi-asserted-by":"crossref","unstructured":"Montoya, J.A.: On the parameterized complexity of approximate counting. RAIRO Theor. Inform. Appl. doi: 10.1051\/ita\/2011007","DOI":"10.1051\/ita\/2011007"},{"key":"9381_CR52","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/11847250_5","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906)","author":"M. M\u00fcller","year":"2006","unstructured":"M\u00fcller, M.: Randomized approximations of parameterized counting problems. In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906). LNCS, vol. 4169, pp. 50\u201359 (2006)"},{"key":"9381_CR53","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-540-79723-4_15","volume-title":"Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC\u201908)","author":"M. M\u00fcller","year":"2008","unstructured":"M\u00fcller, M.: Parameterized derandomization. In: Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC\u201908). LNCS, vol. 5018, pp. 148\u2013159 (2008)"},{"key":"9381_CR54","unstructured":"M\u00fcller, M.: Valiant-Vazirani lemmata for various logics. Electronic Colloquium on Computational Complexity (ECCC\u201908), Report TR08-063 (2008); available at http:\/\/eccc.hpi-web.de\/eccc-reports\/2008\/TR08-063\/index.html"},{"key":"9381_CR55","unstructured":"M\u00fcller, M.: Parameterized randomization. Dissertation, Albert-Ludwigs-Universit\u00e4t Freiburg i.Br. (2009)"},{"key":"9381_CR56","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22, 213\u2013223 (1993)","journal-title":"SIAM J. Comput."},{"key":"9381_CR57","first-page":"182","volume-title":"Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS\u201995)","author":"M. Naor","year":"1995","unstructured":"Naor, M., Schulman, L., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS\u201995), pp. 182\u2013190 (1995)"},{"issue":"2","key":"9381_CR58","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"M. Ogiwara","year":"1992","unstructured":"Ogiwara, M., Toda, S.: Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput. 21(2), 316\u2013328 (1992)","journal-title":"SIAM J. Comput."},{"key":"9381_CR59","unstructured":"Regan, K.W.: Efficient reductions from NP to parity using error-correcting codes (preliminary version). State University of New York at Buffalo, Technical Report 93-24 (1993); available at http:\/\/www.cse.buffalo.edu\/tech-reports\/"},{"key":"9381_CR60","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O. Reingold","year":"2002","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant degree expanders. Ann. Math. 155, 157\u2013187 (2002)","journal-title":"Ann. Math."},{"key":"9381_CR61","first-page":"330","volume-title":"Proceedings of the 15. ACM Symposium on Theory of Computing (STOC\u201983)","author":"M. Sipser","year":"1983","unstructured":"Sipser, M.: A\u00a0complexity theoretic approach to randomness. In: Proceedings of the 15. ACM Symposium on Theory of Computing (STOC\u201983), pp. 330\u2013335 (1983)"},{"issue":"4","key":"9381_CR62","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"L. Stockmeyer","year":"1985","unstructured":"Stockmeyer, L.: On approximation algorithms for #P. SIAM J. Comput. 14(4), 849\u2013861 (1985)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9381_CR63","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9381_CR64","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"9381_CR65","first-page":"458","volume-title":"Proceedings of the 17th ACM Symposium on Theory of Computing (STOC\u201985)","author":"L.G. Valiant","year":"1985","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. In: Proceedings of the 17th ACM Symposium on Theory of Computing (STOC\u201985), pp. 458\u2013463 (1985)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9381-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9381-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9381-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T04:19:43Z","timestamp":1561090783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9381-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,22]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["9381"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9381-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2011,12,22]]}}}