# ∑II∑ threshold formulas

## Abstract

A ∑II∑ formula has the form

, where eachL is either a variable or a negated variable. In this paper we study the computation of threshold functions by ∑II∑ formulas. By combining the proof of the Fredman-Komlós bound [5, 10] and a counting argument, we show that fork andn large andkn/2, every ∑II∑ formula computing the threshold functionT nk has size at least exp$$(\Omega (\sqrt {k/\ln k} ))nlogn$$. Fork andn large andkn 2/3, we show that there exist ∑II∑ formulas for computingT nk with size at most exp$$(2(\sqrt {k/\ln k} ))nlogn$$.

This is a preview of subscription content, access via your institution.

## References

1. 

R. B. Boppana: Optimal separations between concurrent-write parallel machines.Proceedings of the 23rd ACM STOC, 1989, 320–326.

2. 

R. B. Boppana: Amplification of probabilistic boolean formulas,Advances in Computing Research,5 (1989), 27–45.

3. 

R. B. Boppana, andMichael Sipser:The Complexity of Finite Functions, Chapter 14, The Handbook of Theoretical Computer Science, (J. van Leeuven, ed.), Elsevier Science Publishers B. B., 1990, 759–804.

4. 

I. Csiszár, andJ. Körner:Information Theory, Coding Theorems for Discrete Memoryless Systems, Akadémiai Kiadó, Budapest, 1981.

5. 

M. Fredman, andJ. Komlós: On the size of separating systems and perfect hash functions,Siam J. Alg. Disc. Meth., 1984, 61–68.

6. 

J. Hastad:Computational Limitations for Small Depth Circuits, MIT Press, 1986.

7. 

G. Hansel: Nombre minimal de contacts de fermature nécessaires pour réaliser une fonction booléenne symétrique den variables,C. R. Acad. Sci. Paris 258 (1964), 6037–6040.

8. 

L. S. Khasin: Complexity bounds for the realization of monotone symmetrical functions by means of formulas in the basis ∨, ∧, ⌍,Sov. Phys. Dokl. 14 (1970), 1149–1151.

9. 

V. M. Khrapchenko: A method of obtaining lower bounds for the complexity π-schemes,Math. Notes Acad. Sci. USSR 11 (1972), 474–479.

10. 

J. Körner: Fredman-Komlós bound and information theory,Siam J. Alg. Disc. Meth., 1986, 560–570.

11. 

R. E. Krichevskii: Complexity of contact circuits realizing a function of logical algebra,Sov. Phys. Dokl. 8 (1964), 770–772.

12. 

I. Newman, P. Ragde, andA. Wigderson: Perfect hashing, graph entropy and circuit complexity,Proceedings of the 5th Annual Conference on Structure in Complexity Theory, 1990, 91–99.

13. 

M. S. Paterson, N. Pippenger, andU. Zwick: Optimal carry save networks,Boolean Function Complexity: selected papers for the LMS symposium Durham 1990., Cambridge Univ. Press, 1992, 174–201.

14. 

J. Radhakrishnan: Better bounds for threshold formulas.Proceedings of the 32nd IEEE FOCS, 1991, 314–323.

15. 

J. Radhakrishnan: Improved bounds for covering complete uniform hypergraphs.Information Processing Letters 41 (1992), 203–207.

16. 

M. Snir: The covering problem of complete uniform hypergraphs,Discrete Math. 27 1979, 103–105.

17. 

L. G. Valiant: Short monotone formulae for the majority function,Journal of Algorithms 5 (1984), 363–366.

18. 

I. Wegener:The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science, 1987.

Download references

Authors

## Rights and permissions

Reprints and Permissions

## About this article

### Cite this article

Radhakrishnan, J. ∑II∑ threshold formulas. Combinatorica 14, 345–374 (1994). https://doi.org/10.1007/BF01212982

Download citation

• Received:

• Revised:

• Issue Date:

• 68 R 05
• 94 C 10
{"ft_lang_label":"__label__en","ft_lang_prob":0.5852145,"math_prob":0.74797577,"size":3355,"snap":"2021-04-2021-17","text_gpt3_token_len":1057,"char_repetition_ratio":0.102655925,"word_repetition_ratio":0.0,"special_character_ratio":0.31356186,"punctuation_ratio":0.2538787,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96951276,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-23T08:57:13Z\",\"WARC-Record-ID\":\"<urn:uuid:ef11c30c-d244-4a6e-a628-3f7f29b6f0c8>\",\"Content-Length\":\"92153\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:328e713c-8bc8-4a5c-8758-57c72b987252>\",\"WARC-Concurrent-To\":\"<urn:uuid:b1cc5420-1db9-4f70-b54e-085394cbac7a>\",\"WARC-IP-Address\":\"151.101.248.95\",\"WARC-Target-URI\":\"https://link.springer.com/article/10.1007/BF01212982?error=cookies_not_supported&code=1227bcf3-34e8-46d7-8eb8-088c9f55bf7d\",\"WARC-Payload-Digest\":\"sha1:6REL43JBHAPQY675A33FPPJEWCTIQBGZ\",\"WARC-Block-Digest\":\"sha1:7FFEWXBIPNVEQWB7ZMV4J4GSVAHRUDOE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618039568689.89_warc_CC-MAIN-20210423070953-20210423100953-00385.warc.gz\"}"}