Gideon Schechtman

According to our database, Gideon Schechtman authored at least 18 papers between 1976 and 2020.

Collaborative distances:

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

2020

Impossibility of Dimension Reduction in the Nuclear Norm.

Assaf Naor, Gilles Pisier, Gideon Schechtman

Discret. Comput. Geom., 2020

Entropy versus influence for complex functions of modulus one.

Gideon Schechtman

CoRR, 2020

2014

Deterministic algorithms for matrix completion.

Eyal Heiman, Gideon Schechtman, Adi Shraibman

Random Struct. Algorithms, 2014

No greedy bases for matrix spaces with mixed l_p and l_q norms.

Gideon Schechtman

J. Approx. Theory, 2014

2010

The UGC Hardness Threshold of the <i>L_p</i> Grothendieck Problem.

Guy Kindler, Assaf Naor, Gideon Schechtman

Math. Oper. Res., 2010

2009

Lower Bounds for Local Versions of Dimension Reductions.

Gideon Schechtman, Adi Shraibman

Discret. Comput. Geom., 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

2008

The UGC hardness threshold of the ℓ_<i>p</i> Grothendieck problem.

Guy Kindler, Assaf Naor, Gideon Schechtman

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Planar Earthmover Is Not in L₁.

Assaf Naor, Gideon Schechtman

SIAM J. Comput., 2007

Complexity measures of sign matrices.

Nati Linial, Shahar Mendelson, Gideon Schechtman, Adi Shraibman

Comb., 2007

2006

Planar Earthmover is not in L_1.

Assaf Naor, Gideon Schechtman

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2004

Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.

Uriel Feige, Michael Langberg, Gideon Schechtman

SIAM J. Comput., 2004

2002

On the optimality of the random hyperplane rounding technique for MAX CUT.

Uriel Feige, Gideon Schechtman

Random Struct. Algorithms, 2002

2001

On the integrality ratio of semidefinite relaxations of MAX CUT.

Uriel Feige, Gideon Schechtman

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into Z.

Itai Benjamini, Gideon Schechtman

Random Struct. Algorithms, 2000

1997

Randomized Approximation of Bounded Multicovering Problems.

David Peleg, Gideon Schechtman, Avishai Wool

Algorithmica, 1997

1993

Approximating Bounded 0-1 Integer Linear Programs.

David Peleg, Gideon Schechtman, Avishai Wool

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1976

מחוברים ישרים של LP ומרחבים אוניברסליים (Complemented subspaces of Lp and universal spaces.).

Gideon Schechtman

PhD thesis, 1976