Which formulae shrink under random restrictions?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Which formulae shrink under random restrictions?

Full text

Pdf (505 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms table of contents

Washington, D.C., United States

Pages: 702 - 708

Year of Publication: 2001

ISBN:0-89871-490-7

Authors

Hana Chockler	School of Computer Science and Engineering, The Hebrew University, Givat Ram, Jerusalem 91904, Israel
Uri Zwick	School of Computer Science, Raymond and Beverly Sackler, Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

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

Additional Information:

abstract references index terms collaborative colleagues

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

ABSTRACT

We show that the shrinkage exponent, under random restrictions, of formulae over a finite complete basis B of Boolean functions is strictly greater than 1 if and only if all the functions in B are monotone increasing or monotone decreasing in each one of their variables. As a consequence, we get non-linear lower bounds on the formula complexity of the parity function over any basis composed only of monotone increasing or decreasing functions.

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.

	And87a	A.E. Andreev. A method for obtaining efficient lower bounds for monotone complexity. Algebra and Logica, 26:1-18, 1987.
	And87b	A.E. Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of a-schemes. Vestnik Moskov. Univ. Mat., 42, 1987. (In Russian.) English translation in Moscow Univ. Math. Bull. 42:63-66, 1987.
	GM97	Arvind Gupta , Sanjeev Mahajan, Using amplification to compute majority with small majority gates, Computational Complexity, v.6 n.1, p.46-63, 1996/1997 [doi>10.1007/BF01202041]
	Hâs98	Johan HÅ stad, The Shrinkage Exponent of de Morgan Formulas is 2, SIAM Journal on Computing, v.27 n.1, p.48-64, Feb. 1998 [doi>10.1137/S0097539794261556]
	Kva96	H. Kvartin. Formulae with 3-bit majority gates. Master's thesis, Department of Computer Science, Tel Aviv University, 1996.
	NI93	N. Nisan and R. Impagliazzo. The effect of random restrictions on formulae size. Random Structures Algorithms, 4:121-133, 1993.
	Pos41	E.L. Post. The two-valued iterative systems of mathematical logic. Annals of Math. Studies, 5, 1941. Princeton University Press, N.J.
	PZ93a	Michael Paterson , Uri Zwick, Shallow circuits and concise formulae for multiple addition and multiplication, Computational Complexity, v.3 n.3, p.262-291, July 1993 [doi>10.1007/BF01271371]
	PZ93b	M. Paterson and U. Zwick. Shrinkage of de Morgan formulae under restriction. Random Structures Algorithms, 4:135-150, 1993.
	Rok70	M.M. Rokhlina. On formulae for improving reliability. Problemy Kibernetiki, 23:295-301, 1970. (In Russian.).
	Sub61	B.A. Subbotovskaya. Realizations of linear functions by formulas using +, *,-. Doklady Akademii Nauk SSSR, 136:553-555, 1961. (In Russian.) English translation in SovietMathematics Doklady, 2:110- 112, 1961.
	Val84	L.G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms, 5:363-366, 1984.