Michal Parnas

activity

20172026

most citedOn maximal isolation sets in the uniform intersection matrix

1 citations · 1 across the 7 of their papers we have counts for

collaborators

12 papers

math.CO2026

On the Binary Rank of Matrices with Constant Real Rank

Michal Parnas

We study the problem of determining upper bounds on the maximal binary rank, $b_{d}$ , of a $0, 1$ matrix with real rank $d$ , for small constant $d$ . We prove a general upper bound of…

cs.DS2026

Testing the Binary Rank with Polynomial Query Complexity

Michal Parnas

We design an adaptive two-sided error testing algorithm for the binary rank of a $0, 1$ matrix $M$ with query complexity $O (d^{3} lo g (d + 1) / ε^{2})$ , where $d$ is the tested binary rank b…

cs.DM2026

Mathematical and computational perspectives on the Boolean and binary rank and their relation to the real rank

Michal Parnas

This survey provides a comprehensive overview of the study of the binary and Boolean rank from both a mathematical and a computational perspective, with particular emphasis on thei…

math.CO2025

A Study of the Binary and Boolean Rank of Matrices with Small Constant Real Rank

Michal Parnas, Adi Shraibman

We initiate the study of the binary and Boolean rank of $0, 1$ matrices that have a small rank over the reals. The relationship between these three rank functions is an important op…

cs.DS2024

Testing Intersectingness of Uniform Families

Ishay Haviv, Michal Parnas

A set family $F$ is called intersecting if every two members of $F$ intersect, and it is called uniform if all members of $F$ share a common size. A uniform fa…

math.CO2022

The Binary Rank of Circulant Block Matrices

Ishay Haviv, Michal Parnas

The binary rank of a $0, 1$ matrix is the smallest size of a partition of its ones into monochromatic combinatorial rectangles. A matrix $M$ is called $(k_1, \ldots, k_m ; n_1, \ldo…

math.CO2022

On the Binary and Boolean Rank of Regular Matrices

Ishay Haviv, Michal Parnas

A $0, 1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$ , there exists a square regular $0,1…

math.CO2021

Upper Bounds on the Boolean Rank of Kronecker Products

Ishay Haviv, Michal Parnas

The Boolean rank of a $0, 1$ -matrix $A$ , denoted $R_{B} (A)$ , is the smallest number of monochromatic combinatorial rectangles needed to cover the $1$ -entries of $A$ . In 1988,…

math.CO2020

Circulant almost cross intersecting families

Michal Parnas

Let $F$ and $G$ be two $t$ -uniform families of subsets over $[k] = {1, 2, ..., k}$ , where $∣ F ∣ = ∣ G ∣$ , and let $C$ be the adjacency matrix of…

cs.DS2019

Property testing of the Boolean and binary rank

Michal Parnas, Dana Ron, Adi Shraibman

We present algorithms for testing if a $(0, 1)$ -matrix $M$ has Boolean/binary rank at most $d$ , or is $ε$ -far from Boolean/binary rank $d$ (i.e., at least an $ε$ -fraction of the ent…

math.CO2019★ 1 cited

On maximal isolation sets in the uniform intersection matrix

Michal Parnas, Adi Shraibman

Let $A_{k, t}$ be the matrix that represents the adjacency matrix of the intersection bipartite graph of all subsets of size $t$ of ${1, 2, ..., k}$ . We give constructions of large i…

cs.CC2017

The Augmentation Property of Binary Matrices for the Binary and Boolean Rank

Michal Parnas, Adi Shraibman

We define the Augmentation property for binary matrices with respect to different rank functions. A matrix $A$ has the Augmentation property for a given rank function, if for any s…