Alex Samorodnitsky

Dr. Alex Samorodnitsky


Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 December 2008 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
MNMichael Navon
Michael Navon
ASAlex Samorodnitsky
Alex Samorodnitsky

1 January 2007 in Combinatorics, Probability and Computing
Verified
Journal Article
Closed access
PDF file
DFDvir Falik
Dvir Falik
ASAlex Samorodnitsky
Alex Samorodnitsky
We give a combinatorial proof of the result of Kahn, Kalai and Linial [16], which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least $\Omega\bigl(\frac{\log n}{n}\bigr)$ . The methods of the proof are then used to recover additional isoperimetric results for the cube, with improved constants. We also state some conjectures about optimal constants.

1 December 2019 in Journal of Functional Analysis
Verified
Journal Article
Closed access
YPYury Polyanskiy
Yury Polyanskiy
ASAlex Samorodnitsky
Alex Samorodnitsky

7 April 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
NKNaomi Kirshner
Naomi Kirshner
ASAlex Samorodnitsky
Alex Samorodnitsky
Let p ≥ 2. We improve the bound ||f|| p / ||f|| 2 ≤ (p-1) s/2 for a polynomial f of degree s on the boolean cube {0,1} n , which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of p and s, which is smaller than (p-1) s/2 for any p > 2 and s > 0. We show the new bound to be tight, within a smaller order factor, for the Krawchouk polynomial of degree s. This implies several nearly-extremal properties of Krawchouk polynomials and Hamming spheres (equivalently, Hamming balls). In particular, Krawchouk polynomials have (almost) the heaviest tails among all polynomials of the same degree and l 2 norm. 1 The Hamming spheres have the following approximate edge-isoperimetric property: For all 1 ≤ s ≤ n/2, and for all even distances 0 ≤ i ≤ 2s(n-s) / n, the Hamming sphere of radius s contains, up to a multiplicative factor of O(i), as many pairs of points at distance i as possible, among sets of the same size (there is a similar, but slightly weaker and somewhat more complicated claim for all distances). This also implies that Hamming spheres are (almost) stablest with respect to noise among sets of the same size. In coding theory terms this means that a Hamming sphere (equivalently a Hamming ball) has the maximal probability of undetected error, among all binary codes of the same rate. We also describe a family of hypercontractive inequalities for functions on {0,1} n , which improve on the `usual' “ q → 2” inequality by taking into account the concentration of a function (expressed as the ratio between its l r norms), and which are nearly tight for characteristic functions of Hamming spheres. 1 This has to be interpreted with some care.

1 July 2004 in Combinatorica
Verified
Journal Article
Closed access
MSMichael Saks
Michael Saks
ASAlex Samorodnitsky
Alex Samorodnitsky
LZLeonid Zosin
Leonid Zosin

1 March 2007 in Israel Journal of Mathematics
Verified
Journal Article
Open access
PDF file
ABAlexander Barvinok
Alexander Barvinok
ASAlex Samorodnitsky
Alex Samorodnitsky
For a family X of k-subsets of the set {1, …, n}, let |X| be the cardinality of X and let Γ(X, μ) be the expected maximum weight of a subset from X when the weights of 1, …, n are chosen independently at random from a symmetric probability distribution μ on ℝ. We consider the inverse isoperimetric problem of finding μ for which Γ(X, μ) gives the best estimate of ln |X|. We prove that the optimal choice of μ is the logistic distribution, in which case Γ(X, μ) provides an asymptotically tight estimate of ln |X| as k −1 ln |X} grows. Since in many important cases Γ(X, μ) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems. Given μ, we describe families X of a given cardinality with the minimum value of Γ(X, μ), thus extending and sharpening various isoperimetric inequalities in the Boolean cube.