Reducing the complexity of reductions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reducing the complexity of reductions

Full text

Pdf (1.62 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 730 - 738

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Manindra Agrawal	Dept. of Computer Science, Indian Institute of Technology
Eric Allender	Dept. of Computer Science, Rutgers University
Russell Impagliazzo	Dept. of Computer Science, UCSD
Toniann Pitassi	Dept. of Computer Science, University of Arizona
Steven Rudich	Dept. of Computer Science, Carnegie Mellon University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 20, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258671 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Ag95	M. Agrawal, DSPACE(n)=?NSPACE(n): a degree theoretic characterization, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.315, June 19-22, 1995
	AA96	Manindra Agrawal , Eric Allender, An Isomorphism Theorem for Circuit Complexity, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.2, May 24-27, 1996
	Aj83	M. Ajtai, Ei formulae on finite structures, Annals of Pure and Applied Logic 24, 1-48.
	Al89	Eric W. Allender, P-uniform circuit complexity, Journal of the ACM (JACM), v.36 n.4, p.912-928, Oct. 1989 [doi>10.1145/76359.76370]
	ABI93	Eric Allender , José Balcázar , Neil Immerman, A First-Order Isomorphism Theorem, SIAM Journal on Computing, v.26 n.2, p.557-567, April 1997 [doi>10.1137/S0097539794270236]
	AG91	E. Allender and V. Gore, Rudimentary reductions revisited, Information Processing Letters 40 (1991) 89-95.
	AS92	N. Alon and J. Spencer, The Probabilistic Method, John Wiley and Sons, (1992).
	Ar95	Sanjeev Arora, A C~-reductions cannot prove the PUP theorem, manuscript, 1995.
	BDG88	José Luis Balcazar , Jose Diaz , Joaquim Gabarro, Structural complexity 1, Springer-Verlag New York, Inc., New York, NY, 1988
	BIS90	David A. Mix-Barrington , Neil Immerman , Howard Straubing, On uniformity within NC1, Journal of Computer and System Sciences, v.41 n.3, p.274-306, Dec. 1990 [doi>10.1016/0022-0000(90)90022-D]
	BH77	L. Berman and J. Hartmanis, On isomorphism and density of NP and other complete sets, SIAM J. Comput. 6 (1977) 305-322.
	FSS84	Merrick Furst, James Saxe, and Michael Sipser, Parity, Circuits, and the Polynomial-Time Hierarchy, Math. Systems Theory 17 (1984), 13-27.
	Hå87	J. Hastad, One-way permutations in NC0, Information Processing Letters, v.26 n.3, p.153-155, Nov. 23, 1987 [doi>10.1016/0020-0190(87)90053-6]
	HILL90	J. Hb. stad, R. lmpagliazzo, L. Levin, and M. Luby, Construction of a pseudo-random generator from any one.way function, ICSI Technical Report, No. 91-068 (1990).
	Jo75	Neil Jones, Space. Bounded Reducibility among Combinatorial Problems, J. Computer Sys. Sci. 11 (1975), 68-85.
	JY85	D. Joseph and P. Young, Some remarks on witness functions for non-polynomial and non-complete sets in NP, Theoretical Computer Science 39 (1985) 225-237.
	J72	J. Justesen, A class of constructive asymptotically good algebraic codes, IEEE Trans. Inform. Theory, 18 (1972), 652-656.
	KLD86	Ker-I Ko , Timothy J. Long , Ding-Zhu Du, On one-way functions and polynomial-time isomorphisms, Theoretical Computer Science, v.47 n.3, p.263-276, Nov., 1986
	KMR90	S. Kurtz, S. Mahaney, and J. Royer, The structure of complete degrees, in A. Selman, editor, Complexity Theory Retrospective, Springer-Verlag, 1990, pp. 108-146.
	KMR95	Stuart A. Kurtz , Stephen R. Mahaney , James S. Royer, The isomorphism conjecture fails relative to a random oracle, Journal of the ACM (JACM), v.42 n.2, p.401-420, March 1995 [doi>10.1145/201019.201030]
	Li94	Steven Linden, How to define exponentiation ,from addition and multiplication in first-order logic on .finite structures, (manuscript). This improves an earlier characterization that appears in: Steven Linde!l, A purely logical characterization of circuit uniformity, Proc. 7th Structure in Complexity Theory Conference (1992) pp. 185-192.
	Ni92	Noam Nisan, Using hard problems to create pseudorandom generators, MIT Press, Cambridge, MA, 1992
	Se92	A. Selman, A survey of one way functions in complexity theory, Mathematical Systems Theory 25 (1992) 203-221.