9 citations · 14 across the 6 of their papers we have counts for
8 papers · 1 filter
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…
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…
The Corruption Bound, Log Rank, and Communication Complexity
Adi Shraibman
We prove upper bounds on deterministic communication complexity in terms of log of the rank and simple versions of the corruption bound. Our bounds are a simplified version of the…
An approximation algorithm for approximation rank
Troy Lee, Adi Shraibman
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the m…
Disjointness is hard in the multi-party number on the forehead model
Troy Lee, Adi Shraibman
We show that disjointness requires randomized communication Omega(n^{1/(k+1)}/2^{2^k}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bo…