9 citations · 14 across the 6 of their papers we have counts for
11 papers
Larger Corner-Free Sets from Better NOF Exactly- Protocols
Nati Linial, Adi Shraibman
A subset of the integer planar grid is called corner-free if it contains no triple of the form . It is known that such a set has a vanishi…
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…
Property testing of the Boolean and binary rank
Michal Parnas, Dana Ron, Adi Shraibman
We present algorithms for testing if a -matrix has Boolean/binary rank at most , or is -far from Boolean/binary rank (i.e., at least an -fraction of the ent…
On maximal isolation sets in the uniform intersection matrix
Michal Parnas, Adi Shraibman
Let be the matrix that represents the adjacency matrix of the intersection bipartite graph of all subsets of size of . We give constructions of large i…
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…