Search for Author All Reviews
	Allender, Eric     Options: All Media Types Journals Proceedings Div Books Whole Books Other Date Reviewed Title Author Publisher Published Date Descending Ascending Date Reviewed     1 - 4 of 4 reviews       NL-printable sets and nondeterministic Kolmogorov complexity Allender E. Theoretical Computer Science 355(2): 127-138, 2006.  Type: Article The study of printability (namely, polynomial time (P) printability) was introduced by Hartmanis and Yesha [1]. Jenner and Kirsig [2] proved that every nondeterministic logspace (NL) printable set is a sparse set that is accepted by a ...... Sep 22 2006     Reducing the complexity of reductions Agrawal M., Allender E., Impagliazzo R., Pitassi T., Rudich S. Computational Complexity 10(2): 117-138, 2002.  Type: Article The authors investigate separations and collapses in the power of reductions, in terms of their making sets complete for classes, and the stronger results implicit in certain types of completeness....... Nov 22 2002     A uniform circuit lower bound for the permanent Allender E., Gore V. SIAM Journal on Computing 23(5): 1026-1049, 1994.  Type: Article Let subexp denote the class of all monotonic functions that are bounded above by some constructible function f such that, for any d > 0, f ( n ) = o ( 2 nd... May 1 1996     Relating equivalence and reducibility to sparse sets Allender E., Hemachandra L., Ogiwara M., Watanabe O. SIAM Journal on Computing 21(3): 521-539, 1992.  Type: Article Several classes of sets that are equivalent to sparse sets or can be reduced to sparse sets are identified and studied. Also, several fundamental questions about the relationships between equivalence to sparse sets and reducibility to...... Apr 1 1993
	Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud® Terms of Use | Privacy Policy