A. Shraibman

activity

20072021

most citedAlgorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs

2 citations · 3 across the 3 of their papers we have counts for

collaborators

7 papers

math.CO2021

Larger Corner-Free Sets from Better NOF Exactly- $N$ Protocols

Nati Linial, Adi Shraibman

A subset of the integer planar grid $[N] \times [N]$ is called corner-free if it contains no triple of the form $(x, y), (x + δ, y), (x, y + δ)$ . It is known that such a set has a vanishi…

cs.CC2020★ 2 cited

Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs

Noga Alon, Adi Shraibman

We describe algorithmic Number On the Forehead protocols that provide dense Ruzsa-Szemerédi graphs. One protocol leads to a simple and natural extension of the original constructio…

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

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

Nondeterministic Communication Complexity with Help and Graph Functions

Adi Shraibman

We define nondeterministic communication complexity in the model of communication complexity with help of Babai, Hayes and Kimmel. We use it to prove logarithmic lower bounds on th…