Alex Samorodnitsky

Alex Samorodnitsky


The Institute of Computer Science
The Hebrew University of Jerusalem
Jerusalem 91904
Israel

e-mail: salex - at - cs.huji.ac.il
phone: +972-2-5494552
fax: +972-2-5494552
office: 427, Rothberg A building, Givat Ram Campus

Research Interests




Publications:

Journal Papers

A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres, N. Kirshner and A. Samorodnitsky, IEEE Trans. Inform. Theory, 2021.
An upper bound on l_q norms of noisy functions, A. Samorodnitsky, IEEE Trans. Inform. Theory, 66(2), 2020.
On coset leader graphs of structured linear codes, E. Iceland and A. Samorodnitsky, Discrete and Computational Geometry, 63(30), 2020.
On the l4:l2 ratio of functions with restricted Fourier support, N. Kirshner and A. Samorodnitsky, Journal of Combinatorial Theory, Ser. A, 172, 2020.
Improved log-Sobolev inequalities, hypercontractivity, and uncertainty principle on the hypercube, Y. Polyanskiy and A. Samorodnitsky, Journal of Functional Analysis, 277, 11, 2019.
An inequality for functions on the Hamming cube, A. Samorodnitsky, Combinatorics, Probability, and Computing, 26, 2017.
Random Gaussian matrices and Hafnian estimators , M. Rudelson, A. Samorodnitsky, O. Zeitouni, Annals of Probability, 44, 4, 2016.
On the entropy of a noisy function, A. Samorodnitsky, IEEE Trans. Inform. Theory, 62, 10, 2016.
Kolmogorov Width of discrete linear spaces: an approach to matrix rigidity , A. Samorodnitsky, I. Shkredov, S. Yekhanin, Computational Complexity, 25, 2, 2016.
On coset leader graphs of LDPC codes , E. Iceland, A. Samorodnitsky, IEEE Trans. Inform. Theory, 61, 8, 2015.
The zero-undetected-error capacity approaches the Sperner capacity , C. Bunte, A. Lapidoth, and A. Samorodnitsky, IEEE Trans. Inform. Theory, 60, 7, 2014.
A Note on the Newton radius, A. Samorodnitsky and S. Yekhanin, Discrete Mathematics, 312, 15, 2012.
Computing the partition function for perfect matchings in a hypergraph, A. Barvinok and A. Samorodnitsky, Combinatorics, Probability, and Computing, 20, 6, 2011.
On Voting Caterpillars: Approximating Maximum Degree in a Tournament by Binary Trees, F. Fischer, A. D. Procaccia, and A. Samorodnitsky, Random Structures and Algorithms, 39, 1, 2011.
Counting magic squares in quasi-polynomial time, A. Barvinok, A. Samorodnitsky, and A. Yong, Random Structures and Algorithms, 37, 1, 2010.
Linear programming bounds for codes via a covering argument, M. Navon, A. Samorodnitsky, Discrete and Computational Geometry, 41, 2, 2009.
An upper bound for permanents of nonnegative matrices, A. Samorodnitsky, Journal of Combinatorial Theory, Ser. A, 115, 2, 2008.
Edge-isoperimetric inequalities and influences, D. Falik, A. Samorodnitsky, Combinatorics, Probability, and Computing, 16, 5, 2007.
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry, A. Barvinok and A. Samorodnitsky, Israel Journal of Mathematics, 158, 2007.
On linear programming bounds for spherical codes and designs, A. Samorodnitsky, Discrete and Computational Geometry, 31, 3, 2004.
Testing Juntas, E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Journal of Computer and Systems Sciences, 68, 3, 2004.
A lower bound on the integrality gap for minimum multicut in directed networks, M. Saks, A. Samorodnitsky, and L. Zosin, Combinatorica, 24, 3, 2004.
Testing Basic Boolean Formulae, M. Parnas, D. Ron and A. Samorodnitsky, SIAM Journal on Discrete Mathematics, 16, 1, 2002.
A deterministic algorithm for approximating mixed discriminant and mixed volume, and a combinatorial corollary, L. Gurvits and A. Samorodnitsky, DCG, 27, 4, 2002.
Linear codes and sums of characters, N. Linial and A. Samorodnitsky, Combinatorica, 22, 4, 2002.
The distance approach to approximate combinatorial counting, A. Barvinok and A. Samorodnitsky, Geometric and Functional Analysis, 11, 5, 2001.
On the optimum of Delsarte's linear program, A. Samorodnitsky, Journal of Combinatorial Theory, Ser. A, 96, 2, 2001.
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, N. Linial, A. Samorodnitsky, and A. Wigderson Combinatorica, 20, 4, 2000.
Testing Monotonicity, O. Goldreich, S. Goldwasser, E. Lehman, D. Ron and A. Samorodnitsky, Combinatorica, 20, 3, 2000.
Inclusion-exclusion: exact and approximate, J. Kahn, N. Linial and A. Samorodnitsky, Combinatorica, 16, 4, 1996.

Conference Papers not covered by Journal Articles

On codes decoding a constant fraction of errors on the BSC , J. Hazla, A. Samorodnitsky, and O. Sberlo, STOC'21
On the round complexity of randomized Byzantine agreement , R. Cohen, I. Haitner, N. Makriyannis, M. Orland, and A. Samorodnitsky, DISC'19.
Bounds on the permanent and some applications , L. Gurvits, A. Samorodnitsky, FOCS'14.
The zero-undetected-error capacity of the low-noise cyclic triangle channel , C. Bunte, A. Lapidoth, and A. Samorodnitsky, ISIT'13.
Learning and smoothed analysis, A. Kalai, A. Samorodnitsky, S. Teng, FOCS'09.
Inverse conjecture for the Gowers norm is false, S. Lovett, R. Meshulam, A. Samorodnitsky, STOC'08.
Low degree tests at large distances, A. Samorodnitsky, STOC'07.
Approximating Entropy from Sublinear Samples, M. Brautbar and A. Samorodnitsky, SODA'07.
Gowers Uniformity, Influence of Variables, and PCPs, A. Samorodnitsky, L. Trevisan. STOC'06.
On Delsarte's Linear Programming Bounds for Binary Codes, M. Navon and A. Samorodnitsky, FOCS'05.
A note on common quadratic Lyapunov functions for linear inclusions: Exact results and Open Problems, L. Gurvits and A. Samorodnitsky, CDC-ECC'05.
Monotonicity testing over general poset domains, E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld and A. Samorodnitsky, STOC'02.
A deterministic polynomial-time algorithm for approximate computation of mixed discriminants and mixed volumes, L. Gurvits and A. Samorodnitsky, STOC'00.
A PCP Characterization of NP with Optimal Amortized Query Complexity, A. Samorodnitsky and L.Trevisan, STOC'00.
Improved Testing Algorithms for Monotonicity, E. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky, RANDOM'99.

Manuscripts

On some properties of random and pseudorandom codes , A. Samorodnitsky, 2022.
Weight distribution of random linear codes and Krawchouk polynomials , A. Samorodnitsky, 2022.
Hypercontractive inequalities for the second norm of highly concentrated functions, and Mrs. Gerber's-type inequalities for the second Renyi entropy , N. Levhari and A. Samorodnitsky, 2021.
One more proof of the first linear programming bound for binary codea and two conjectures , A. Samorodnitsky, 2021.
An improved bound on l_q norms of noisy functions , A. Samorodnitsky, 2020.
A bound on L1 codes , A. Samorodnitsky, 2013. The same result was proved independently and somewhat earlier by Lee and Moharrami via a different approach.
Lower bounds for designs in symmetric spaces, N. Eidelstein and A. Samorodnitsky, 2010.
A modified logarithmic Sobolev inequality for the Hamming cube and some applications, A. Samorodnitsky, 2008.
On efficient entropy approximation via Lempel-Ziv compression, M. Brautbar, A. Samorodnitsky, 2007.
Approximate inclusion-exclusion and orthogonal polynomials, A. Samorodnitsky, 1999.
Special classes of solutions for Delsarte's linear program, A. Samorodnitsky, 1998.