Natural proofs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Natural proofs

Full text

Pdf (1.06 MB)

Source

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

Montreal, Quebec, Canada

Pages: 204 - 213

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Alexander A. Razborov	School of Mathematics, Institute for Advanced Study Princeton, NJ and Steklov Mathematical Institute Vavilova 42, 117966, GSP-1 Moscow, Russia
Steven Rudich	Computer Science Department, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 65, Citation Count: 5

Additional Information:

references cited by 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/195058.195134 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.

	1	Ajtai. 1 Z#l-formulae on finite structures. Annals of Pure and Applied Logic, 24:1-48, May 1983.
	2	N. Alon , R. B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, v.7 n.1, p.1-22, Jan. 1987 [doi>10.1007/BF02579196]
	3	James Aspnes , Richard Beigel , Merrick Furst , Steven Rudich, The expressive power of voting polynomials, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.402-409, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103461]
	4	T.P. Baker, J. Gill, and R. Solovay. Relativizations of the P = NP question. SIAM journal on Computing, 4:431-442, 1975.
	5	David A. M Barrington, A Note on a Theorem of Razborov, University of Massachusetts, Amherst, MA, 1987
	6	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	7	M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits and the polynomial time hierarchy. Math. Syst. Theory, 17:13-27, 1984.
	8	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	9	A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, G. Turan. Threshold circuits of bounded depth. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 99-110, 1987.
	10	J. Hastad. Computational limilations on Small Depth Circuits. PhD thesis, Massachusetts Institute of Technology, 1986.
	11	J. Hastad. The shrinkage exponent is 2. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 114-123, 1993.
	12	R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 236-243, 1989.
	13	Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62265]
	14	M. Karchmer and A. Wigderson. On span programs. In Proceedings of the 8th Structure in Complexity Theory Annual Conference, pages 102-111, 1993.
	15	N. Linial, Y. Monsour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 574- 579, 1989.
	16	S. Muroga. Threshold logic and its applications. Wiley-Interscience, 1971.
	17	N. Nisan. Pseudorandom bits for constant depth circuits. In Combinatorica 11 (1), pp. 63-70, 1991.
	18	N. Nisan and R. Impagliazzo. The effect of random restrictions on formula size. Random Structures and Algorithms, Vol. 4, No. 2, 1993.
	19	Michael S. Paterson , Uri Zwick, Shrinkage of de Morgan formulae under restriction, Proceedings of the 32nd annual symposium on Foundations of computer science, p.324-333, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185385]
	20	R. Raz , A. Wigderson, Monotone circuits for matching require linear depth, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.287-292, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100253]
	21	A. A. Razborov, On submodular complexity measures, Poceedings of the London Mathematical Society symposium on Boolean function complexity, p.76-83, December 1992, London, United Kingdom
	22	A. Razborov. On small size approximation models. Submitted to the volume The Mathematics of Paul Erdos, 1993.
	23	A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of Bounded Arithmetic. Manuscript, 1994.
	24	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
	25	E. Tardos. The gap between monotone and nonmonotone circuit complexity is exponential. Combinatorica, 8:141-142, 1988.
	26	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
	27	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States
	28	A.E. Andreev, On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Math. Dokl. 31(3):530- 534, 1985.
	29	A.E. Andreev, On one method of obtaining effective lower bounds of monotone complexity. Algebra i logika, 26(1)'3-21, 1987. in Russian.
	30	A.E. Andreev, On a method for obtaining more than quadratic effective lower bounds for the complexity of 7r-sckemes. Moscow Univ. Math. Bull. 42(1)'63-66, 1987. In Russian.
	31	A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl., 31:354-357, 1985.
	32	A. A. Razborov, Lower bounds of monotone complexity of the logical permanent function, Mathem. Notes of lhe Academy of Sci. of the USSR, 37:485-493, 1985.
	33	A. A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition, Mathem. Noles of the Academy of Sci. of the USSR, 41(4):333-338, 1987.
	34	A. A. Razborov, Lower bounds on the size of switching-andrectifier networks for symmetric Boolean functions, Malhem. Notes of the Academy of Sc#. of the USSR.

CITED BY 5

	Eli Ben-Sasson , Avi Wigderson, Short proofs are narrow—resolution made simple, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.517-526, May 01-04, 1999, Atlanta, Georgia, United States
	Eli Ben-Sasson , Avi Wigderson, Short proofs are narrow—resolution made simple, Journal of the ACM (JACM), v.48 n.2, p.149-169, March 2001
	Ketan Mulmuley, Is there an algebraic proof for P ≠ NC? (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.210-219, May 04-06, 1997, El Paso, Texas, United States
	Frederic Green, The correlation between parity and quadratic polynomials mod 3, Journal of Computer and System Sciences, v.69 n.1, p.28-44, August 2004
	Matthew Clegg , Jeffery Edmonds , Russell Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.174-183, May 22-24, 1996, Philadelphia, Pennsylvania, United States