Source author record

Michal Parnas

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Upper Bounds on the Boolean Rank of Kronecker Products

The Boolean rank of a $0,1$ -matrix $A$ , denoted $R_\mathbb{B}(A)$ , is the smallest number of monochromatic combinatorial rectangles needed to cover the $1$ -entries of $A$ . In 1988, de Caen, Gregory, and Pullman asked if the Boolean rank of the Kronecker product $C_n \otimes C_n$ is strictly smaller than the square of $R_\mathbb{B}(C_n)$ , where $C_n$ is the $n \times n$ matrix with zeros on the diagonal and ones everywhere else (Carib. Conf. Comb. & Comp., 1988). A positive answer was given by Watts for $n=4$ (Linear Alg. and its Appl., 2001). A result of Karchmer, Kushilevitz, and Nisan, motivated by direct-sum questions in non-deterministic communication complexity, implies that the Boolean rank of $C_n \otimes C_n$ grows linearly in that of $C_n$ (SIAM J. Disc. Math., 1995), and thus $R_\mathbb{B}(C_n \otimes C_n) < R_\mathbb{B}(C_n)^2$ for every sufficiently large $n$ . Their proof relies on a probabilistic argument. In this work, we present a general method for proving upper bounds on the Boolean rank of Kronecker products of $0,1$ -matrices. We use it to affirmatively settle the question of de Caen et al. for all integers $n \geq 7$ . We further provide an explicit construction of a cover of $C_n \otimes C_n$ , whose number of rectangles nearly matches the optimal asymptotic bound. Our method for proving upper bounds on the Boolean rank of Kronecker products might find applications in different settings as well. We express its potential applicability by extending it to the wider framework of spanoids, recently introduced by Dvir, Gopi, Gu, and Wigderson (SIAM J. Comput., 2020).

preprint2020arXiv

Circulant almost cross intersecting families

Let $\mathcal{F}$ and $\mathcal{G}$ be two $t$ -uniform families of subsets over $[k] = \{1,2,...,k\}$ , where $|\mathcal{F}| = |\mathcal{G}|$ , and let $C$ be the adjacency matrix of the bipartite graph whose vertices are the subsets in $\mathcal{F}$ and $\mathcal{G}$ , and there is an edge between $A\in \mathcal{F}$ and $B \in \mathcal{G}$ if and only if $A \cap B \neq \emptyset$ . The pair $(\mathcal{F},\mathcal{G})$ is $q$ -almost cross intersecting if every row and column of $C$ has exactly $q$ zeros. We consider $q$ -almost cross intersecting pairs that have a circulant intersection matrix $C_{p,q}$ , determined by a column vector with $p > 0$ ones followed by $q > 0$ zeros. This family of matrices includes the identity matrix in one extreme, and the adjacency matrix of the bipartite crown graph in the other extreme. We give constructions of pairs $(\mathcal{F},\mathcal{G})$ whose intersection matrix is $C_{p,q}$ , for a wide range of values of the parameters $p$ and $q$ , and in some cases also prove matching upper bounds. Specifically, we prove results for the following values of the parameters: (1) $1 \leq p \leq 2t-1$ and $1 \leq q \leq k-2t+1$ . (2) $2t \leq p \leq t^2$ and any $q> 0$ , where $k \geq p+q$ . (3) $p$ that is exponential in $t$ , for large enough $k$ . Using the first result we show that if $k \geq 4t-3$ then $C_{2t-1,k-2t+1}$ is a maximal isolation submatrix of size $k\times k$ in the $0,1$ -matrix $A_{k,t}$ , whose rows and columns are labeled by all subsets of size $t$ of $[k]$ , and there is a one in the entry on row $x$ and column $y$ if and only if subsets $x,y$ intersect.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.