Alex Samorodnitsky

90 papers A* 14A 2B 2Journal 69Unranked 3
YearRankTypeTitle / Venue / Authors
2025 J jnl
On the Difficulty to Beat the First Linear Programming Bound for Binary Codes.
IEEE Trans. Inf. Theory
Alex Samorodnitsky
2024 J jnl
Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection.
IEEE Trans. Inf. Theory
Itamar Katz, Alex Samorodnitsky, Yuval Kochman
2024 J jnl
Weight distribution of random linear codes and Krawtchouk polynomials.
Random Struct. Algorithms
Alex Samorodnitsky
2023 J jnl
On the difficulty to beat the first linear programming bound for binary codes.
CoRR
Alex Samorodnitsky
2023 J jnl
Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection.
CoRR
Itamar Katz, Alex Samorodnitsky, Yuval Kochman
2022 J jnl
Hypercontractive Inequalities for the Second Norm of Highly Concentrated Functions, and Mrs. Gerber's-Type Inequalities for the Second Rรฉnyi Entropy.
Entropy
Niv Levhari, Alex Samorodnitsky
2022 J jnl
On some properties of random and pseudorandom codes.
CoRR
Alex Samorodnitsky
2022 J jnl
On the Round Complexity of Randomized Byzantine Agreement.
J. Cryptol.
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky
2022 J jnl
Weight distribution of random linear codes and Krawchouk polynomials.
CoRR
Alex Samorodnitsky
2021 J jnl
A Moment Ratio Bound for Polynomials and Some Extremal Properties of Krawchouk Polynomials and Hamming Spheres.
IEEE Trans. Inf. Theory
Naomi Kirshner, Alex Samorodnitsky
2021 J jnl
Hypercontractive inequalities for the second norm of highly concentrated functions, and Mrs. Gerber's-type inequalities for the second Renyi entropy.
CoRR
Niv Levhari, Alex Samorodnitsky
2021 A* conf
On codes decoding a constant fraction of errors on the BSC.
STOC
Jan Hazla, Alex Samorodnitsky, Ori Sberlo
2021 J jnl
One more proof of the first linear programming bound for binary codes and two conjectures.
CoRR
Alex Samorodnitsky
2020 J jnl
An Upper Bound on $\ell_q$ Norms of Noisy Functions.
IEEE Trans. Inf. Theory
Alex Samorodnitsky
2020 J jnl
An improved bound on ๐“
CoRR
Alex Samorodnitsky
2020 J jnl
On Coset Leader Graphs of Structured Linear Codes.
Discret. Comput. Geom.
Eran Iceland, Alex Samorodnitsky
2020 J jnl
On codes decoding a constant fraction of errors on the BSC.
CoRR
Alex Samorodnitsky, Ori Sberlo
2020 J jnl
On the
J. Comb. Theory A
Naomi Kirshner, Alex Samorodnitsky
2019 J jnl
A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres.
CoRR
Naomi Kirshner, Alex Samorodnitsky
2019 J jnl
A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres.
Electron. Colloquium Comput. Complex.
Naomi Kirshner, Alex Samorodnitsky
2019 A conf
On the Round Complexity of Randomized Byzantine Agreement.
DISC
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky
2019 J jnl
On the Round Complexity of Randomized Byzantine Agreement.
CoRR
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky
2019 J jnl
On the Round Complexity of Randomized Byzantine Agreement.
IACR Cryptol. ePrint Arch.
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky
2018 J jnl
An upper bound on $\ell_q$ norms of noisy functions.
Electron. Colloquium Comput. Complex.
Alex Samorodnitsky
2018 J jnl
An upper bound on โ„“
CoRR
Alex Samorodnitsky
2018 J jnl
On coset leader graphs of structured linear codes.
Electron. Colloquium Comput. Complex.
Eran Iceland, Alex Samorodnitsky
2018 J jnl
On โ„“
Electron. Colloquium Comput. Complex.
Naomi Kirshner, Alex Samorodnitsky
2017 J jnl
An Inequality for Functions on the Hamming Cube.
Comb. Probab. Comput.
Alex Samorodnitsky
2016 J jnl
Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube.
CoRR
Yury Polyanskiy, Alex Samorodnitsky
2016 J jnl
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity.
Comput. Complex.
Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin
2016 J jnl
On the Entropy of a Noisy Function.
IEEE Trans. Inf. Theory
Alex Samorodnitsky
2015 A conf
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity.
CCC
Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin
2015 J jnl
On Coset Leader Graphs of LDPC Codes.
IEEE Trans. Inf. Theory
Eran Iceland, Alex Samorodnitsky
2015 J jnl
On the entropy of a noisy function.
CoRR
Alex Samorodnitsky
2015 J jnl
On the entropy of a noisy function.
Electron. Colloquium Comput. Complex.
Alex Samorodnitsky
2015 J jnl
The "Most informative boolean function" conjecture holds for high noise.
CoRR
Alex Samorodnitsky
2014 B conf
A proof of the Ahlswede-Cai-Zhang conjecture.
ISIT
Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky
2014 A* conf
Bounds on the Permanent and Some Applications.
FOCS
Leonid Gurvits, Alex Samorodnitsky
2014 J jnl
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity.
Electron. Colloquium Comput. Complex.
Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin
2014 J jnl
On Coset Leader Graphs of LDPC codes.
CoRR
Eran Iceland, Alex Samorodnitsky
2014 J jnl
Random Gaussian matrices and Hafnian estimators.
CoRR
Mark Rudelson, Alex Samorodnitsky, Ofer Zeitouni
2014 J jnl
The Zero-Undetected-Error Capacity Approaches the Sperner Capacity.
IEEE Trans. Inf. Theory
Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky
2013 J jnl
The Zero-Undetected-Error Capacity Approaches the Sperner Capacity.
CoRR
Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky
2013 B conf
The zero-undetected-error capacity of the low-noise cyclic triangle channel.
ISIT
Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky
2012 J jnl
A note on the Newton radius.
Discret. Math.
Alex Samorodnitsky, Sergey Yekhanin
2012 J jnl
Approximating the Influence of Monotone Boolean Functions in O(โˆšn) Query Complexity.
ACM Trans. Comput. Theory
Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein
2011 J jnl
A new perspective on implementation by voting trees.
Random Struct. Algorithms
Felix A. Fischer, Ariel D. Procaccia, Alex Samorodnitsky
2011 J jnl
Computing the Partition Function for Perfect Matchings in a Hypergraph.
Comb. Probab. Comput.
Alexander I. Barvinok, Alex Samorodnitsky
2011 J jnl
Inverse Conjecture for the Gowers Norm is False.
Theory Comput.
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
2010 J jnl
An approximation algorithm for counting contingency tables.
Random Struct. Algorithms
Alexander I. Barvinok, Zur Luria, Alex Samorodnitsky, Alexander Yong
2010 J jnl
Lower bounds for designs in symmetric spaces.
Electron. Colloquium Comput. Complex.
Noa Eidelstein, Alex Samorodnitsky
2009 A* conf
A new perspective on implementation by voting trees.
EC
Felix A. Fischer, Ariel D. Procaccia, Alex Samorodnitsky
2009 J jnl
Gowers Uniformity, Influence of Variables, and PCPs.
SIAM J. Comput.
Alex Samorodnitsky, Luca Trevisan
2009 A* conf
Learning and Smoothed Analysis.
FOCS
Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng
2009 J jnl
Linear Programming Bounds for Codes via a Covering Argument.
Discret. Comput. Geom.
Michael Navon, Alex Samorodnitsky
2008 J jnl
An upper bound for permanents of nonnegative matrices.
J. Comb. Theory A
Alex Samorodnitsky
2008 A* conf
Inverse conjecture for the gowers norm is false.
STOC
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
2007 A* conf
Approximating entropy from sublinear samples.
SODA
Mickey Brautbar, Alex Samorodnitsky
2007 J jnl
Edge-Isoperimetric Inequalities and Influences.
Comb. Probab. Comput.
Dvir Falik, Alex Samorodnitsky
2007 J jnl
Inverse Conjecture for the Gowers norm is false.
Electron. Colloquium Comput. Complex.
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
2007 J jnl
Linear programming bounds for codes via a covering argument.
Electron. Colloquium Comput. Complex.
Michael Navon, Alex Samorodnitsky
2007 A* conf
Low-degree tests at large distances.
STOC
Alex Samorodnitsky
2006 A* conf
Gowers uniformity, influence of variables, and PCPs.
STOC
Alex Samorodnitsky, Luca Trevisan
2006 J jnl
Low-degree tests at large distances.
Electron. Colloquium Comput. Complex.
Alex Samorodnitsky
2005 โ€” conf
A note on common quadratic Lyapunov functions for linear inclusions: Exact results and Open Problems.
CDC/ECC
Leonid Gurvits, Alex Samorodnitsky
2005 J jnl
Approximating the entropy of large alphabets
Electron. Colloquium Comput. Complex.
Mickey Brautbar, Alex Samorodnitsky
2005 J jnl
Edge-isoperimetric inequalities and influences
Electron. Colloquium Comput. Complex.
Dvir Falik, Alex Samorodnitsky
2005 J jnl
Gowers Uniformity, Influence of Variables, and PCPs
CoRR
Alex Samorodnitsky, Luca Trevisan
2005 J jnl
Gowers Uniformity, Influence of Variables, and PCPs
Electron. Colloquium Comput. Complex.
Alex Samorodnitsky, Luca Trevisan
2005 A* conf
On Delsarte's Linear Programming Bounds for Binary Codes.
FOCS
Michael Navon, Alex Samorodnitsky
2005 J jnl
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry.
Electron. Colloquium Comput. Complex.
Alexander I. Barvinok, Alex Samorodnitsky
2004 J jnl
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.
Comb.
Michael E. Saks, Alex Samorodnitsky, Leonid Zosin
2004 J jnl
On Linear Programming Bounds for Spherical Codes and Designs.
Discret. Comput. Geom.
Alex Samorodnitsky
2004 J jnl
Testing juntas.
J. Comput. Syst. Sci.
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2002 J jnl
A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary.
Discret. Comput. Geom.
Leonid Gurvits, Alex Samorodnitsky
2002 J jnl
Linear Codes and Character Sums.
Comb.
Nathan Linial, Alex Samorodnitsky
2002 A* conf
Monotonicity testing over general poset domains.
STOC
Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
2002 J jnl
Testing Basic Boolean Formulae.
SIAM J. Discret. Math.
Michal Parnas, Dana Ron, Alex Samorodnitsky
2002 A* conf
Testing Juntas.
FOCS
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2001 J jnl
On the Optimum of Delsarte's Linear Program.
J. Comb. Theory A
Alex Samorodnitsky
2001 J jnl
Proclaiming Dictators and Juntas or Testing Boolean Formulae
Electron. Colloquium Comput. Complex.
Michal Parnas, Dana Ron, Alex Samorodnitsky
2001 โ€” conf
Proclaiming Dictators and Juntas or Testing Boolean Formulae.
RANDOM-APPROX
Michal Parnas, Dana Ron, Alex Samorodnitsky
2000 J jnl
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Comb.
Nathan Linial, Alex Samorodnitsky, Avi Wigderson
2000 A* conf
A PCP characterization of NP with optimal amortized query complexity.
STOC
Alex Samorodnitsky, Luca Trevisan
2000 A* conf
A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume.
STOC
Leonid Gurvits, Alex Samorodnitsky
2000 J jnl
Testing Monotonicity.
Comb.
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
1999 โ€” conf
Improved Testing Algorithms for Monotonicity.
RANDOM-APPROX
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1999 J jnl
Improved Testing Algorithms for Monotonicity.
Electron. Colloquium Comput. Complex.
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1998 A* conf
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
STOC
Nathan Linial, Alex Samorodnitsky, Avi Wigderson
1996 J jnl
Inclusion-Exclusion: Exact and Approximate.
Comb.
Jeff Kahn, Nathan Linial, Alex Samorodnitsky