# Sciweavers

Share
CC
2008
Springer
• Email discuss report
150views System Software» more  CC 2008»

# Balancing Syntactically Multilinear Arithmetic Circuits

12 years 3 months ago
In their seminal paper, Valiant, Skyum, Berkowitz and Rackoff proved that arithmetic circuits can be balanced [VSBR]. That is, [VSBR] showed that for every arithmetic circuit of size s and degree r, there exists an arithmetic circuit of size poly(r, s) and depth O(log(r) log(s)) computing the same polynomial. In the first part of this paper, we follow the proof of [VSBR] and show that syntactically multilinear arithmetic circuits can be balanced. That is, we show that if is syntactically multilinear, then so is . Recently, [R04b] proved a super-polynomial separation between multilinear arithmetic formula and circuit size. In the second part of this paper, we use the result of the first part to simplify the proof of this separation. That is, we construct a (simpler) polynomial f(x1, . . . , xn) such that
Ran Raz, Amir Yehudayoff
 Added 24 Dec 2010 Updated 24 Dec 2010 Type Journal Year 2008 Where CC Authors Ran Raz, Amir Yehudayoff
{"ft_lang_label":"__label__en","ft_lang_prob":0.87319493,"math_prob":0.95469046,"size":814,"snap":"2023-14-2023-23","text_gpt3_token_len":192,"char_repetition_ratio":0.13580246,"word_repetition_ratio":0.015267176,"special_character_ratio":0.22235872,"punctuation_ratio":0.1446541,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9872327,"pos_list":[0,1,2,3,4,5,6,7,8,9,10],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-04-01T16:27:45Z\",\"WARC-Record-ID\":\"<urn:uuid:4d7aec9e-835d-46dc-b9a0-30779a140126>\",\"Content-Length\":\"36633\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fe3c119e-dd09-45da-842f-597b5c1f934f>\",\"WARC-Concurrent-To\":\"<urn:uuid:c3d41026-c92a-48a3-b9fa-0d429cde8431>\",\"WARC-IP-Address\":\"96.87.153.69\",\"WARC-Target-URI\":\"http://www.sciweavers.org/publications/balancing-syntactically-multilinear-arithmetic-circuits\",\"WARC-Payload-Digest\":\"sha1:C5PYO7DO2JXHVPQAT6KQ3LGLOSMMVGI7\",\"WARC-Block-Digest\":\"sha1:PBZCK56JZAIZRKK4EDXRZLPCJT4C7V34\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-14/CC-MAIN-2023-14_segments_1679296950110.72_warc_CC-MAIN-20230401160259-20230401190259-00340.warc.gz\"}"}