Adi Shraibman

According to our database, Adi Shraibman authored at least 30 papers between 2005 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

An improved protocol for ExactlyN with more than 3 players.

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman

Electron. Colloquium Comput. Complex., 2023

2022

The Strength of Equality Oracles in Communication.

Toniann Pitassi, Morgan Shirley, Adi Shraibman

Electron. Colloquium Comput. Complex., 2022

2021

Property Testing of the Boolean and Binary Rank.

Michal Parnas, Dana Ron, Adi Shraibman

Theory Comput. Syst., 2021

An Improved Protocol for the Exactly-N Problem.

Nati Linial, Adi Shraibman

Proceedings of the 36th Computational Complexity Conference, 2021

2020

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

Noga Alon, Adi Shraibman

CoRR, 2020

On maximal isolation sets in the uniform intersection matrix.

Michal Parnas, Adi Shraibman

Australas. J Comb., 2020

2019

Nondeterministic communication complexity with help and graph functions.

Adi Shraibman

Theor. Comput. Sci., 2019

The corruption bound, log-rank, and communication complexity.

Adi Shraibman

Inf. Process. Lett., 2019

On the Communication Complexity of High-Dimensional Permutations.

Nati Linial, Toniann Pitassi, Adi Shraibman

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

A note on multiparty communication complexity and the Hales-Jewett theorem.

Adi Shraibman

Inf. Process. Lett., 2018

2017

The Augmentation Property of Binary Matrices for the Binary and Boolean Rank.

Michal Parnas, Adi Shraibman

CoRR, 2017

On The Communication Complexity of High-Dimensional Permutations.

Nati Linial, Adi Shraibman

CoRR, 2017

2014

Deterministic algorithms for matrix completion.

Eyal Heiman, Gideon Schechtman, Adi Shraibman

Random Struct. Algorithms, 2014

The Cover Number of a Matrix and its Algorithmic Applications.

Noga Alon, Troy Lee, Adi Shraibman

Proceedings of the Approximation, 2014

2013

The approximate rank of a matrix and its algorithmic applications: approximate rank.

Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala

Proceedings of the Symposium on Theory of Computing Conference, 2013

Matrix Completion From any Given Set of Observations.

Troy Lee, Adi Shraibman

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

2009

Lower bounds in communication complexity based on factorization norms.

Nati Linial, Adi Shraibman

Random Struct. Algorithms, 2009

Lower Bounds in Communication Complexity.

Troy Lee, Adi Shraibman

Found. Trends Theor. Comput. Sci., 2009

Lower Bounds for Local Versions of Dimension Reductions.

Gideon Schechtman, Adi Shraibman

Discret. Comput. Geom., 2009

Learning Complexity vs Communication Complexity.

Nathan Linial, Adi Shraibman

Comb. Probab. Comput., 2009

Disjointness is Hard in the Multiparty Number-on-the-Forehead Model.

Troy Lee, Adi Shraibman

Comput. Complex., 2009

Lower Bounds on Quantum Multiparty Communication Complexity.

Troy Lee, Gideon Schechtman, Adi Shraibman

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

An Approximation Algorithm for Approximation Rank.

Troy Lee, Adi Shraibman

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Disjointness is hard in the multi-party number-on-the-forehead model.

Troy Lee, Adi Shraibman

Electron. Colloquium Comput. Complex., 2008

Approximation norms and duality for communication complexity lower bounds.

Troy Lee, Adi Shraibman

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

A Direct Product Theorem for Discrepancy.

Troy Lee, Adi Shraibman, Robert Spalek

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Complexity measures of sign matrices (מדדי מורכבות של מטריצות סימנים.).

Adi Shraibman

PhD thesis, 2007

Complexity measures of sign matrices.

Nati Linial, Shahar Mendelson, Gideon Schechtman, Adi Shraibman

Comb., 2007

On Approximating the Average Distance Between Points.

Kfir Barhum, Oded Goldreich, Adi Shraibman

Proceedings of the Approximation, 2007

2005

Rank, Trace-Norm and Max-Norm.

Nathan Srebro, Adi Shraibman

Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005