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

- Theory of CS
- Coding Theory
- Combinatorics

A Note on the Newton radius, A. Samorodnitsky and S. Yekhanin,

Computing the partition function for perfect matchings in a hypergraph, A. Barvinok and A. Samorodnitsky,

On Voting Caterpillars: Approximating Maximum Degree in a Tournament by Binary Trees, F. Fischer, A. D. Procaccia, and A. Samorodnitsky,

Counting magic squares in quasi-polynomial time, A. Barvinok, A. Samorodnitsky, and A. Yong,

Linear programming bounds for codes via a covering argument, M. Navon, A. Samorodnitsky,

An upper bound for permanents of nonnegative matrices, A. Samorodnitsky,

Edge-isoperimetric inequalities and influences, D. Falik, A. Samorodnitsky,

Random Weighting, Asymptotic Counting, and Inverse Isoperimetry, A. Barvinok and A. Samorodnitsky,

On linear programming bounds for spherical codes and designs, A. Samorodnitsky,

Testing Juntas, E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky,

A lower bound on the integrality gap for minimum multicut in directed networks, M. Saks, A. Samorodnitsky, and L. Zosin,

Testing Basic Boolean Formulae, M. Parnas, D. Ron and A. Samorodnitsky,

A deterministic algorithm for approximating mixed discriminant and mixed volume, and a combinatorial corollary, L. Gurvits and A. Samorodnitsky,

Linear codes and sums of characters, N. Linial and A. Samorodnitsky,

The distance approach to approximate combinatorial counting, A. Barvinok and A. Samorodnitsky,

On the optimum of Delsarte's linear program, A. Samorodnitsky,

A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, N. Linial, A. Samorodnitsky, and A. Wigderson

Testing Monotonicity, O. Goldreich, S. Goldwasser, E. Lehman, D. Ron and A. Samorodnitsky,

Inclusion-exclusion: exact and approximate, J. Kahn, N. Linial and A. Samorodnitsky,

Learning and smoothed analysis, A. Kalai, A. Samorodnitsky, S. Teng,

Inverse conjecture for the Gowers norm is false, S. Lovett, R. Meshulam, A. Samorodnitsky,

Low degree tests at large distances, A. Samorodnitsky,

Approximating Entropy from Sublinear Samples, M. Brautbar and A. Samorodnitsky,

Gowers Uniformity, Influence of Variables, and PCPs, A. Samorodnitsky, L. Trevisan.

On Delsarte's Linear Programming Bounds for Binary Codes, M. Navon and A. Samorodnitsky,

A note on common quadratic Lyapunov functions for linear inclusions: Exact results and Open Problems, L. Gurvits and A. Samorodnitsky,

Monotonicity testing over general poset domains, E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld and A. Samorodnitsky,

A deterministic polynomial-time algorithm for approximate computation of mixed discriminants and mixed volumes, L. Gurvits and A. Samorodnitsky,

A PCP Characterization of NP with Optimal Amortized Query Complexity, A. Samorodnitsky and L.Trevisan,

Improved Testing Algorithms for Monotonicity, E. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky,

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.