Alex Samorodnitsky

Most-cited papers

Learning and Smoothed Analysis
A. Kalai, Alex Samorodnitsky, Shang-Hua Teng
20092009 50th Annual IEEE Symposium on Foundations of Computer Science254 citations
Semantic Scholar
Testing Monotonicity
Oded Goldreich, S. Goldwasser, E. Lehman, D. Ron +1 more
1998Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)247 citations
Semantic Scholar
Monotonicity testing over general poset domains
Eldar Fischer, E. Lehman, Ilan Newman, Sofya Raskhodnikova +2 more
2002Symposium on the Theory of Computing234 citations Open access
Semantic Scholar
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents
N. Linial, Alex Samorodnitsky, A. Wigderson
1998Symposium on the Theory of Computing230 citations Open access
Semantic Scholar
A PCP characterization of NP with optimal amortized query complexity
Alex Samorodnitsky, L. Trevisan
2000Symposium on the Theory of Computing182 citations
Semantic Scholar
Improved Testing Algorithms for Monotonicity
Yevgeniy Dodis, Oded Goldreich, E. Lehman, Sofya Raskhodnikova +2 more
1999Electron. Colloquium Comput. Complex.177 citations
Semantic Scholar
Low-degree tests at large distances
Alex Samorodnitsky
2006Symposium on the Theory of Computing153 citations
Semantic Scholar
Gowers uniformity, influence of variables, and PCPs
Alex Samorodnitsky, L. Trevisan
2005Symposium on the Theory of Computing149 citations Open access
Semantic Scholar
Testing Basic Boolean Formulae
Michal Parnas, D. Ron, Alex Samorodnitsky
2002SIAM Journal on Discrete Mathematics109 citations
Semantic Scholar
Inclusion-exclusion: Exact and approximate
J. Kahn, N. Linial, Alex Samorodnitsky
1996Comb.79 citations
Semantic Scholar
Inverse conjecture for the gowers norm is false
Shachar Lovett, R. Meshulam, Alex Samorodnitsky
2007Theory of Computing65 citations Open access
Semantic Scholar
A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary
L. Gurvits, Alex Samorodnitsky
2002Discrete & Computational Geometry59 citations Open access
Semantic Scholar
Bounds on the Permanent and Some Applications
L. Gurvits, Alex Samorodnitsky
2014IEEE Annual Symposium on Foundations of Computer Science56 citations Open access
Semantic Scholar
Edge-Isoperimetric Inequalities and Influences
Dvir Falik, Alex Samorodnitsky
2005Combinatorics, probability & computing52 citations
Semantic Scholar
On the Optimum of Delsarte's Linear Program
Alex Samorodnitsky
2001Journal of Combinatorial Theory45 citations Open access
Semantic Scholar
On the Entropy of a Noisy Function
Alex Samorodnitsky
2015IEEE Transactions on Information Theory44 citations Open access
Semantic Scholar
Linear Programming Bounds for Codes via a Covering Argument
M. Navon, Alex Samorodnitsky
2007Electron. Colloquium Comput. Complex.38 citations Open access
Semantic Scholar
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks
M. Saks, Alex Samorodnitsky, L. Zosin
2004Comb.34 citations
Semantic Scholar
A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
L. Gurvits, Alex Samorodnitsky
2000Symposium on the Theory of Computing34 citations Open access
Semantic Scholar
Computing the Partition Function for Perfect Matchings in a Hypergraph
A. Barvinok, Alex Samorodnitsky
2010Combinatorics, probability & computing27 citations
Semantic Scholar
A Moment Ratio Bound for Polynomials and Some Extremal Properties of Krawchouk Polynomials and Hamming Spheres
Naomi Kirshner, Alex Samorodnitsky
2019IEEE Transactions on Information Theory26 citations Open access
Semantic Scholar
Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube
Yury Polyanskiy, Alex Samorodnitsky
2016Journal of Functional Analysis26 citations Open access
Semantic Scholar
On Delsarte's linear programming bounds for binary codes
M. Navon, Alex Samorodnitsky
2005IEEE Annual Symposium on Foundations of Computer Science26 citations
Semantic Scholar
An approximation algorithm for counting contingency tables
A. Barvinok, Zur Luria, Alex Samorodnitsky, A. Yong
2008Random Struct. Algorithms25 citations Open access
Semantic Scholar
Random weighting, asymptotic counting, and inverse isoperimetry
A. Barvinok, Alex Samorodnitsky
2003Electron. Colloquium Comput. Complex.25 citations Open access
Semantic Scholar
On codes decoding a constant fraction of errors on the BSC
Jan Hązła, Alex Samorodnitsky, Ori Sberlo
2020Symposium on the Theory of Computing24 citations Open access
Semantic Scholar
An upper bound on ℓ q norms of noisy functions.
Alex Samorodnitsky
201824 citations
Semantic Scholar
On the Round Complexity of Randomized Byzantine Agreement
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland +1 more
2019Journal of Cryptology23 citations Open access
Semantic Scholar
A new perspective on implementation by voting trees
Felix A. Fischer, Ariel D. Procaccia, Alex Samorodnitsky
2009ACM Conference on Economics and Computation22 citations
Semantic Scholar
An upper bound for permanents of nonnegative matrices
Alex Samorodnitsky
2006Journal of Combinatorial Theory21 citations Open access
Semantic Scholar
Proclaiming Dictators and Juntas or Testing Boolean Formulae
Michal Parnas, D. Ron, Alex Samorodnitsky
2001RANDOM-APPROX21 citations
Semantic Scholar
The Zero-Undetected-Error Capacity Approaches the Sperner Capacity
Christoph Bunte, A. Lapidoth, Alex Samorodnitsky
2013IEEE Transactions on Information Theory16 citations Open access
Semantic Scholar
One more proof of the first linear programming bound for binary codes and two conjectures
Alex Samorodnitsky
2021Israel Journal of Mathematics15 citations Open access
Semantic Scholar
Random Gaussian matrices and Hafnian estimators
M. Rudelson, Alex Samorodnitsky, O. Zeitouni
2014arXiv.org15 citations Open access
Semantic Scholar
A modified logarithmic Sobolev inequality for the Hamming cube and some applications
Alex Samorodnitsky
200814 citations
Semantic Scholar
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
Dana Ron, R. Rubinfeld, M. Safra, Alex Samorodnitsky +1 more
2012TOCT13 citations
Semantic Scholar
Approximating entropy from sublinear samples
Mickey Brautbar, Alex Samorodnitsky
2007ACM-SIAM Symposium on Discrete Algorithms12 citations
Semantic Scholar
Linear Codes and Character Sums
N. Linial, Alex Samorodnitsky
2002Comb.11 citations
Semantic Scholar
An Inequality for Functions on the Hamming Cube
Alex Samorodnitsky
2012Combinatorics, probability & computing9 citations Open access
Semantic Scholar
An improved bound on 𝓁q norms of noisy functions
Alex Samorodnitsky
2020arXiv.org8 citations
Semantic Scholar
A note on common quadratic Lyapunov functions for linear inclusions: Exact results and Open Problems
L. Gurvits, Alex Samorodnitsky
2005Proceedings of the 44th IEEE Conference on Decision and Control8 citations
Semantic Scholar
An Upper Bound on $\ell_q$ Norms of Noisy Functions
Alex Samorodnitsky
2018IEEE Transactions on Information Theory7 citations Open access
Semantic Scholar
The "Most informative boolean function" conjecture holds for high noise
Alex Samorodnitsky
2015arXiv.org7 citations
Semantic Scholar
Counting magic squares in quasi-polynomial time
A. Barvinok, Alex Samorodnitsky, A. Yong
20076 citations
Semantic Scholar
On Linear Programming Bounds for Spherical Codes and Designs
Alex Samorodnitsky
2002Discrete & Computational Geometry6 citations Open access
Semantic Scholar
On the ℓ4: ℓ2 ratio of functions with restricted Fourier support
Naomi Kirshner, Alex Samorodnitsky
2020Journal of Combinatorial Theory5 citations Open access
Semantic Scholar
On Coset Leader Graphs of Structured Linear Codes
E. Iceland, Alex Samorodnitsky
2018Discrete & Computational Geometry5 citations Open access
Semantic Scholar
On Coset Leader Graphs of LDPC Codes
E. Iceland, Alex Samorodnitsky
2014IEEE Transactions on Information Theory5 citations Open access
Semantic Scholar
The distance approach to approximate combinatorial counting
A. Barvinok, Alex Samorodnitsky
20005 citations Open access
Semantic Scholar
Weight distribution of random linear codes and Krawtchouk polynomials
Alex Samorodnitsky
2022Random Struct. Algorithms4 citations Open access
Semantic Scholar