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-658-6176
fax: +972-2-658-5439
office: 210, Ross Building, Givat Ram Campus

Research Interests




Publications:

Journal Papers

On Voting Caterpillars: Approximating Maximum Degree in a Tournament by Binary Trees, F. Fischer, A. D. Procaccia, and A. Samorodnitsky, Random Structures and Algorithms, to appear
Counting magic squares in quasi-polynomial time, A. Barvinok, A. Samorodnitsky, and A. Yong, Random Structures and Algorithms, to appear.
Linear programming bounds for codes via a covering argument, M. Navon, A. Samorodnitsky, Discrete and Computational Geometry, to appear.
An upper bound for permanents of nonnegative matrices, A. Samorodnitsky, Journal of Combinatorial Theory, Ser. A, to appear.
Edge-isoperimetric inequalities and influences, D. Falik, A. Samorodnitsky, Combinatorics, Probability, and Computing, to appear.
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry, A. Barvinok and A. Samorodnitsky, Israel Journal of Mathematics, to appear.
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

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

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.