9 citations · 14 across the 6 of their papers we have counts for
4 papers · 1 filter
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…
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 has the Augmentation property for a given rank function, if for any s…
A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem
Adi Shraibman
For integers and , the density Hales-Jewett number is defined as the maximal size of a subset of that contains no combinatorial line. We show that for $k \…
On The Communication Complexity of High-Dimensional Permutations
Nati Linial, and Toniann Pitassi, Adi Shraibman
We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) w…