Lower Bounds for Monotone q-Multilinear Boolean Circuits
(2023) 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13878 LNCS. p.301-312- Abstract
A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is multilinear if for any AND gate the two input functions have no variable in common. We consider a generalization of monotone multilinear Boolean circuits to include monotone q-multilinear Boolean circuits. Roughly, a sufficient condition for the q-multilinearity is that in the formal Boolean polynomials at the output gates of the circuit no variable has degree larger than q. First, we study a relationship between q-multilinearity and the conjunction depth of a monotone Boolean circuit, i.e., the maximum number of AND gates on a path from an input gate to an output gate. As a corollary, we... (More)
A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is multilinear if for any AND gate the two input functions have no variable in common. We consider a generalization of monotone multilinear Boolean circuits to include monotone q-multilinear Boolean circuits. Roughly, a sufficient condition for the q-multilinearity is that in the formal Boolean polynomials at the output gates of the circuit no variable has degree larger than q. First, we study a relationship between q-multilinearity and the conjunction depth of a monotone Boolean circuit, i.e., the maximum number of AND gates on a path from an input gate to an output gate. As a corollary, we obtain a trade-off between the lower bounds on the size of monotone q-multilinear Boolean circuits for semi-disjoint bilinear forms and the parameter q. Next, we study the complexity of the monotone Boolean function Isolk,n verifying if a k-dimensional matrix has at least one 1 in each line (e.g., each row and column when k= 2 ) in terms of monotone k-multilinear Boolean circuits. We show that the function admits Π 2 monotone k-multilinear circuits of O(nk) size. On the other hand, we demonstrate that any Π 2 monotone Boolean circuit for Isolk,n is at least k-multilinear. Also, we show under an additional assumption that any Σ3 monotone Boolean circuit for Isolk,n is not (k- 1 ) -multilinear or it has an exponential in n size.
(Less)
- author
- Lingas, Andrzej LU
- organization
- publishing date
- 2023
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Circuit size, Monotone arithmetic circuit, Monotone Boolean circuit, Monotone multilinear Boolean circuit
- host publication
- SOFSEM 2023 : Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings - Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Gasieniec, Leszek
- volume
- 13878 LNCS
- pages
- 12 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023
- conference location
- Nový Smokovec, Slovakia
- conference dates
- 2023-01-15 - 2023-01-18
- external identifiers
-
- scopus:85146713838
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783031231001
- DOI
- 10.1007/978-3-031-23101-8_20
- language
- English
- LU publication?
- yes
- id
- 1232e54a-59a5-453f-a66c-9bd4cb0c1121
- date added to LUP
- 2023-02-13 14:19:17
- date last changed
- 2024-06-28 01:01:05
@inproceedings{1232e54a-59a5-453f-a66c-9bd4cb0c1121,
abstract = {{<p>A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is multilinear if for any AND gate the two input functions have no variable in common. We consider a generalization of monotone multilinear Boolean circuits to include monotone q-multilinear Boolean circuits. Roughly, a sufficient condition for the q-multilinearity is that in the formal Boolean polynomials at the output gates of the circuit no variable has degree larger than q. First, we study a relationship between q-multilinearity and the conjunction depth of a monotone Boolean circuit, i.e., the maximum number of AND gates on a path from an input gate to an output gate. As a corollary, we obtain a trade-off between the lower bounds on the size of monotone q-multilinear Boolean circuits for semi-disjoint bilinear forms and the parameter q. Next, we study the complexity of the monotone Boolean function Isol<sub>k</sub><sub>,</sub><sub>n</sub> verifying if a k-dimensional matrix has at least one 1 in each line (e.g., each row and column when k= 2 ) in terms of monotone k-multilinear Boolean circuits. We show that the function admits Π <sub>2</sub> monotone k-multilinear circuits of O(n<sup>k</sup>) size. On the other hand, we demonstrate that any Π <sub>2</sub> monotone Boolean circuit for Isol<sub>k</sub><sub>,</sub><sub>n</sub> is at least k-multilinear. Also, we show under an additional assumption that any Σ<sub>3</sub> monotone Boolean circuit for Isol<sub>k</sub><sub>,</sub><sub>n</sub> is not (k- 1 ) -multilinear or it has an exponential in n size.</p>}},
author = {{Lingas, Andrzej}},
booktitle = {{SOFSEM 2023 : Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings}},
editor = {{Gasieniec, Leszek}},
isbn = {{9783031231001}},
issn = {{1611-3349}},
keywords = {{Circuit size; Monotone arithmetic circuit; Monotone Boolean circuit; Monotone multilinear Boolean circuit}},
language = {{eng}},
pages = {{301--312}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{Lower Bounds for Monotone q-Multilinear Boolean Circuits}},
url = {{http://dx.doi.org/10.1007/978-3-031-23101-8_20}},
doi = {{10.1007/978-3-031-23101-8_20}},
volume = {{13878 LNCS}},
year = {{2023}},
}