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 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

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 coset leader graphs of LDPC codes , E. Iceland, A. Samorodnitsky, 2014.
Bounds on the permanent and some applications , L. Gurvits, A. Samorodnitsky, 2013.
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. We plan to write a joint paper at some point.
The zero-undetected-error capacity approaches the Sperner capacity , C. Bunte, A. Lapidoth, and A. Samorodnitsky, 2013.
An inequality for functions on the Hamming cube, A. Samorodnitsky, 2012.
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.