Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Lower Bounds for Monotone q-Multilinear Boolean Circuits

Lingas, Andrzej LU (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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
0302-9743
1611-3349
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-13 23:39:38
@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         = {{0302-9743}},
  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}},
}