The UGC hardness threshold of the Lp Grothendieck problem (2009)
Guy Kindler, Assaf Naor, Gideon Schechtman
Abstract For p> = 2 we consider the problem of, given an n * n matrix A = (ai j) whose diagonal entries vanish,approximating in polynomial time the number
William B. Johnson, Bernard Maurey, Gideon Schechtman
factorization of linear operators ∗
Optp (A) ≔ max ai jxixj: (x1,..., xn) ∈ R (2009)
Guy Kindler, Assaf Naor, Gideon Schechtman
For p ≥ 2 we consider the problem of, given an n × n matrix A = (ai j) whose diagonal entries vanish, approximating in polynomial time the number n�
Guy Kindler, Assaf Naor, Gideon Schechtman
hardness threshold of the ℓp Grothendieck problem
William B. Johnson, Bernard Maurey, Gideon Schechtman
factorization of linear operators ∗
Finite dimensional subspaces of L p (2007)
William B. Johnson, Gideon Schechtman
We discuss the finite dimensional structure theory of L p; in particular, the theory of restricted invertibility and classification of subspaces of # n p. Contents 1
An "isomorphic" Version Of Dvoretzky's Theorem, II (2007)
Vitali D. Milman, Gideon Schechtman
A different proof is given to the result announced in [MS2]: For each 1 k ! n we give an upper bound on the minimal distance of a k-dimensional subspace of an arbitrary n-dimensional normed space to...
An "isomorphic" Version Of Dvoretzky's Theorem (2007)
Vitali D. Milman, Gideon Schechtman
For each 1 k ! n we give an upper bound on the minimal distance of a k-dimensional subspace of an arbitrary n-dimensional normed space to the Hilbert space of dimension k. The result is best possible...
An Editorial Comment on the Preceding Paper (2007)
Gideon Schechtman Would, Gideon Schechtman
)j kx \Gamma yk 1 extend it to a function F on IR n with the same Lip constant with respect to k \Delta k 1 and note that jF (x) \Gamma F (y)j p nkx \Gamma yk 2 . Put S = P jx i j; T = P jy i j....
Block bases of the Haar system as complemented subspaces of L p, 2! p! 1 (2007)
Dvir Kleper, Gideon Schechtman
It is shown that the span of fa i h i \Phi b i e i g n i=1, where fh i g is the Haar system in L p and fe i g the canonical basis of ` p, is well isomorphic to a well complemented subspace of L p; 2!...
William B. Johnson, Joram Lindenstrauss, David Preiss, Gideon Schechtman
mappings between infinite dimensional Banach spaces
Very tight embeddings of subspaces of L p, 1 p 2, into n (2007)
William B. Johnson, Gideon Schechtman
We prove that for 1 p < r < 2, every n-dimensional subspace E of L r , in particular ` r , well-embeds into ` p for some m (1 + )n, where \well" depends on p, r, and the arbitrary > 0,...
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers (Extended Abstract) (2007)
Uriel Feige, Michael Langberg, Gideon Schechtman
Uriel Feige Michael Langberg Gideon Schechtman Department of Computer Science and Applied Mathematics Weizmann Institute of Science, Rehovot 76100 ffeige,mikel,gideong@wisdom.weizmann.ac.il Abstract...
Multiplication operators on L(L_p) and $\ell_p$-strictly singular operators (2007)
Johnson, William B., Schechtman, Gideon
A classification of weakly compact multiplication operators on L(L_p), $1
Asymptotic Geometric Analysis, Fall 2006 ∗ (2007)
The course will deal with convex symmetric bodies in R n. In the first few lectures we will formulate and prove Dvoretzky theorem, Theorem 1.2.
Extremal configurations for moments of sums of independent positive random variables (2007)
We find the extremal configuration for the p-moment of sums of independent positive random variables while constraining the sum of the expectations of the random variables and the sum of their...
Planar earthmover is not in l1 (2006)
We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0, 1,..., n} 2 ⊆ R 2 incurs distortion Ω � � log n �. We...
Planar Earthmover is not in $L_1$ (2005)
Naor, Assaf, Schechtman, Gideon
We show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid $\{0,1,...,n\}^2\subseteq \R^2$ incurs distortion...
Complexity measures of sign matrices (2005)
Nati Linial, Shahar Mendelson, Gideon Schechtman
z Department of Mathematics,
The shattering dimension of sets of linear functionals (2004)
Mendelson, Shahar, Schechtman, Gideon
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. The proofs here relay mostly on methods from the local theory of normed spaces and...
The shattering dimension of sets of linear functionals (2004)
Mendelson, Shahar, Schechtman, Gideon
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. The proofs here relay mostly on methods from the local theory of normed spaces and...
Special orthogonal splittings of $L_1^{2k}$ (2003)
We show that for each positive integer $k$ there is a $k\times k$ matrix $B$ with $\pm 1$ entries such that putting $E$ to be the span of the rows of the $k\times 2k$ matrix $[\sqrt{k}I_k,B]$, then...
The shattering dimension of sets of linear functionals (2003)
Shahar Mendelson, Gideon Schechtman
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. The proofs here relay mostly on methods from the Local Theory of Normed Spaces and...
Lipschitz quotients from metric trees and from Banach spaces containing l1 (2002)
William B. Johnson, Joram Lindenstrauss, David Preiss, Gideon Schechtman
containing ` 1
Lipschitz quotients from metric trees and from Banach spaces containing l1 (2002)
William B. Johnson, Joram Lindenstrauss, David Preiss, Gideon Schechtman
A Lipschitz map f between the metric spaces X and Y is called a Lipschitz quotient map if there is a C> 0 (the smallest such C, the co-Lipschitz constant, is denoted coLip(f), while Lip(f) denotes
William B. Johnson, Joram Lindenstrauss, David Preiss, Gideon Schechtman
We give several sufficient conditions on a pair of Banach spaces X and Y under which each Lipschitz mapping from a domain in X to Y has, for every #> 0, a point of #-Frechet differentiability....
Gaussian Random Field and the Range of Random Graph Homomorphisms into Z (2001)
The Erwin, Schrödinger International Boltzmanngasse, Itai Benjamini, Gideon Schechtman, Itai Benjamini, Gideon Schechtman
Bounds on the range of random graph homomorphism into Z, and the maximal height difference of the Gaussian random field, are presented. 1
On the optimality of the random hyperplane rounding technique for MAX CUT (2000)
Uriel Feige, Gideon Schechtman
MAX CUT is the problem of partitioning the vertices of a graph into two sets, maximizing the number of edges joining these sets. This problem is NP-hard. Goemans and Williamson proposed an algorithm...
On the optimality of the random hyperplane rounding technique for MAX CUT (2000)
Uriel Feige, Gideon Schechtman
MAX CUT is the problem of partitioning the vertices of a graph into two sets, maximizing the number of edges joining these sets. This problem is NP-hard. Goemans and Williamson proposed an algorithm...
William B. Johnson, Joram Lindenstrauss, David Preiss, Gideon Schechtman
We give several sufficient conditions on a pair of Banach spaces X and Y under which each Lipschitz mapping from a domain in X to Y has, for every ffl ? 0, a point of ffl-Fr'echet...
The Erwin, Schrodinger International Boltzmanngasse, Itai Benjamini, Itai Benjamini, Gideon Schechtman, Gideon Schechtman
Bounds on the range of random graph homomorphism into Z, and the maximal height dierence of the Gaussian random eld, are presented. 1 Introduction In this note we study the range of two related...
Random Graph Homomorphisms into Z (2000)
Itai Benjamini, Gideon Schechtman, Itai Benjamini
Gaussian Random Field and the Range of
Itai Benjamini, Gideon Schechtman
Bounds on the range of random graph homomorphism into Z, and the maximal height difference of the Gaussian random field, are presented. 1 Introduction In this note we study the range of two related...
Concentration, Results and Applications (1999)
this article we survey many (but not all) of the methods of proof of concentration and approximate isoperimetric inequalities. We tried to concentrate mostly on methods which are quite general or...
Itai Benjamini, Gideon Schechtman
Abstract Bounds on the range of random graph homomorphism into Z, and the maximal height difference of the Gaussian random field, are presented.
Hitczenko, Pawel; North Carolina State University; Pawel@math.ncsu.edu, Kwapien, Stanislaw; Warsaw University; Kwapstan@mimuw.edu.pl, Li, Wenbo V.; University Of Delaware; Wli@math.udel.edu, Schechtman, Gideon; The Weizmann Institute Of Science; Gideon@guitar.wisdom.weizmann.ac.il, Schlumprecht, Thomas; Texas A&M University; Schlump@math.tamu.edu, Zinn, Joel; Texas A&M University; Jzinn@plevy.math.tamu.edu
We provide necessary and sufficient conditions for hypercontractivity of the minima of nonnegative, i.i.d. random variables and of both the maxima of minima and the minima of maxima for such r.v.'s....
Pawel Hitczenko, Stanislaw Kwapien, Wenbo V. Li, Gideon Schechtman
: We provide necessary and sufficient conditions for hypercontractivity of the minima of nonnegative, i.i.d. random variables and of both the maxima of minima and the minima of maxima for such...
Bates, Sean M., Johnson, William B., Lindenstrauss, Joram, Preiss, D., Schechtman, Gideon
New concepts related to approximating a Lipschitz function between Banach spaces by affine functions are introduced. Results which clarify when such approximations are possible are proved and in some...
Banach spaces determined by their uniform structures (1997)
Johnson, William B., Lindenstrauss, Joram, Schechtman, Gideon
Following results of Bourgain and Gorelik we show that the spaces $\ell_p$, $1
A Remarkable Rearrangement Of The Haar System In L_p (1997)
We introduce a non-standard but, to our opinion natural, order on the initial segments of the Haar system and investigate the isomorphic classification of the linear span, in L p , of block bases,...
On the Best Constants in the Khintchine Inequality (1997)
Johannes Wissel, Joseph Turian, Mentor Arteom, Zvavitch Supervisor, Gideon Schechtman, A P \delta
We show a self-contained new proof for the best Bp constant in the Khintchine Inequality for p > 3 using only elementary calculus.
Hitczenko, P., Kwapień, Stanisław, Li, Wenbo V., Schechtman, Gideon, Schlumprecht, Thomas, Zinn, Joel
We provide necessary and sufficient conditions for hypercontractivity of the minima of nonnegative, i.i.d. random variables and of both the maxima of minima and the minima of maxima for such r.v.'s....
On the Gaussian measure of the intersection of symmetric, convex sets (1996)
Schechtman, Gideon, Schlumprecht, Thomas, Zinn, Joel
The Gaussian Correlation Conjecture states that for any two symmetric, convex sets in n-dimensional space and for any centered, Gaussian measure on that space, the measure of the intersection is...
Banach Spaces Determined By Their Uniform Structures (1996)
William B. Johnson, Joram Lindenstrauss, Gideon Schechtman
Following results of Bourgain and Gorelik we show that the spaces ` p , 1 ! p ! 1, as well as some related spaces have the following uniqueness property: If X is a Banach space uniformly homeomorphic...
Almost Frechet differentiability of Lipschitz maps between infinite dimensional Banach spaces (1995)
William B. Johnson, Joram Lindenstrauss, David Preiss, Gideon Schechtman
We give several sufficient conditions on a pair of Banach spaces X and Y under which each Lipschitz mapping from a domain in X to Y has, for every #> 0, a point of #-Frechet di#erentiability. Most...
Banach spaces with the $2$-summing property (1994)
Arias, Alvaro, Figiel, Tadek, Johnson, William B., Schechtman, Gideon
A Banach space $X$ has the $2$-summing property if the norm of every linear operator from $X$ to a Hilbert space is equal to the $2$-summing norm of the operator. Up to a point, the theory of spaces...
Computing p-summing norms with few vectors (1992)
Johnson, William B., Schechtman, Gideon
It is shown that the p-summing norm of any operator with n-dimensional domain can be well-aproximated using only ``few" vectors in the definition of the p-summing norm. Except for constants...
Factorizations of natural embeddings of l_p^n int L_r (1992)
Figiel, Tadek, Johnson, William B., Schechtman, Gideon
This is a continuation of the paper [FJS] with a similar title. Several results from there are strengthened, in particular: 1. If T is a "natural" embedding of l_2^n into L_1 then, for any...
Remarks on Talagrand's deviation inequality for Rademacher functions (1990)
Johnson, William B., Schechtman, Gideon
Recently Talagrand [T] estimated the deviation of a function on $\{0,1\}^n$ from its median in terms of the Lipschitz constant of a convex extension of $f$ to $\ell ^n_2$; namely, he proved that...
On the volume of the intersection of two $L_p^n$ balls (1989)
Schechtman, Gideon, Zinn, Joel
This note deals with the following problem, the case $p=1$, $q=2$ of which was introduced to us by Vitali Milman: What is the volume left in the $L_p^n$ ball after removing a t-multiple of the...
Asymptotic theory of finite dimencional normed space / Vitali D. Milman, Gideon Schechtman (1986)
Milman,Vitali D, Schechtman, Gideon
Incluye bibliogrfía e índice
Contemporary Mathematics (1984)
William B. Johnson, Gideon Schechtman
We discuss the finite dimensional structure theory of L p; in particular, the theory of restricted invertibility and classification of subspaces of ` n p. Contents 1
Finite dimensional subspaces of L_p
William B. Johnson, Gideon Schechtman
this article, we chose to devote this section to describing the change of densities that arise later. It turns out that the framework in which this technique is most naturally used is that of an L p...
The Shattering Dimension of Sets of Linear Functionals
Shahar Mendelson, Gideon Schechtman
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. This is applied in two di#erent directions. The first is the determination of whether...