{"links":{},"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00234047","sets":["1164:2592:11452:11598"]},"path":["11598"],"owner":"44499","recid":"234047","title":["内積と多数決関数に対する3段論理回路"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-05-01"},"_buckets":{"deposit":"6bc72f3d-979e-4042-b0ab-ed3e48abd361"},"_deposit":{"id":"234047","pid":{"type":"depid","value":"234047","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"内積と多数決関数に対する3段論理回路","author_link":["637059","637060"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"内積と多数決関数に対する3段論理回路"},{"subitem_title":"Depth-Three Circuits for Inner Product and Majority Functions","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2024-05-01","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"群馬大学情報学部"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Faculty of Informatics, Gunma University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/234047/files/IPSJ-AL24198008.pdf","label":"IPSJ-AL24198008.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL24198008.pdf","filesize":[{"value":"785.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"cb17d544-b11d-419f-9781-2eef05db2ee6","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"天野, 一幸"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazuyuki, Amano","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"3 段 OR ◦ AND ◦ OR 論理回路で，かつ入力側の各 OR 素子の入次数が高々 ???? であるものを Σ???? 3-回路と呼ぶ．本稿では，内積と多数決関数に対する Σ???? 3  型回路の構成について論じ，以下の 2 点を与える．(i) 2???? 変数内積関数 IP????  を計算する，素子数 2 0.952????  以下の Σ2 3-回路，および，素子数 2 0.692????  以下の Σ3 3-回路の明示的構成法，(ii) 多数決関数 MAJ????  を計算する Σ???? 3  型回路で，否定リテラルの利用が回路サイズの減少に寄与していると想定される構成法．両者とも，小さな入力サイズに対する最適な論理回路の計算機による探索とその一般化により得られたものである． ","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A Σ???? 3-circuit is a depth-three OR ◦ AND ◦ OR circuit in which each bottom gate has fan-in at most ????. In this work, we investigate the Σ???? 3-complexity for the inner product function the majority function and give the following two results. (i) We give an explicit construction of a Σ2 3-circuit of size smaller than 2 0.952???? for IP???? as well as a Σ3 3-circuit of size smaller than 2 0.692????. (ii) We present a construction suggesting that the use of negations leads to a reduction in Σ???? 3-complexity for MAJ????. All these results rely on efficient circuits or formulas on a small number of variables that we found through a computer search.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"1","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2024-05-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"8","bibliographicVolumeNumber":"2024-AL-198"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:35:46.661906+00:00","updated":"2025-01-19T09:53:44.500133+00:00","id":234047}