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

Showing cs.DSShow all

3 papers · 1 filter

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.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…

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…