Alex Samorodnitsky

According to our database, Alex Samorodnitsky authored at least 60 papers between 1996 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection.

Itamar Katz, Alex Samorodnitsky, Yuval Kochman

IEEE Trans. Inf. Theory, April, 2024

2023

On the difficulty to beat the first linear programming bound for binary codes.

Alex Samorodnitsky

CoRR, 2023

2022

On the Round Complexity of Randomized Byzantine Agreement.

Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky

J. Cryptol., 2022

Hypercontractive Inequalities for the Second Norm of Highly Concentrated Functions, and Mrs. Gerber's-Type Inequalities for the Second Rényi Entropy.

Niv Levhari, Alex Samorodnitsky

Entropy, 2022

On some properties of random and pseudorandom codes.

Alex Samorodnitsky

CoRR, 2022

Weight distribution of random linear codes and Krawchouk polynomials.

Alex Samorodnitsky

CoRR, 2022

2021

One more proof of the first linear programming bound for binary codes and two conjectures.

Alex Samorodnitsky

CoRR, 2021

On codes decoding a constant fraction of errors on the BSC.

Jan Hazla, Alex Samorodnitsky, Ori Sberlo

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

On the <i>ℓ</i>₄: <i>ℓ</i>₂ ratio of functions with restricted Fourier support.

Naomi Kirshner, Alex Samorodnitsky

J. Comb. Theory, Ser. A, 2020

An improved bound on 𝓁_q norms of noisy functions.

Alex Samorodnitsky

CoRR, 2020

On codes decoding a constant fraction of errors on the BSC.

Alex Samorodnitsky, Ori Sberlo

CoRR, 2020

2019

A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres.

Naomi Kirshner, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2019

2018

An upper bound on $\ell_q$ norms of noisy functions.

Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2018

On ℓ₄: ℓ₂ ratio of functions with restricted Fourier support.

Naomi Kirshner, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2018

On coset leader graphs of structured linear codes.

Eran Iceland, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2018

An upper bound on ℓ_q norms of noisy functions.

Alex Samorodnitsky

CoRR, 2018

2017

An Inequality for Functions on the Hamming Cube.

Alex Samorodnitsky

Comb. Probab. Comput., 2017

2016

Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube.

Yury Polyanskiy, Alex Samorodnitsky

CoRR, 2016

Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity.

Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin

Comput. Complex., 2016

2015

On Coset Leader Graphs of LDPC Codes.

Eran Iceland, Alex Samorodnitsky

IEEE Trans. Inf. Theory, 2015

On the entropy of a noisy function.

Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2015

The "Most informative boolean function" conjecture holds for high noise.

Alex Samorodnitsky

CoRR, 2015

2014

The Zero-Undetected-Error Capacity Approaches the Sperner Capacity.

Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky

IEEE Trans. Inf. Theory, 2014

Random Gaussian matrices and Hafnian estimators.

Mark Rudelson, Alex Samorodnitsky, Ofer Zeitouni

CoRR, 2014

A proof of the Ahlswede-Cai-Zhang conjecture.

Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky

Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Bounds on the Permanent and Some Applications.

Leonid Gurvits, Alex Samorodnitsky

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

The zero-undetected-error capacity of the low-noise cyclic triangle channel.

Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky

Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013

2012

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.

Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein

ACM Trans. Comput. Theory, 2012

A note on the Newton radius.

Alex Samorodnitsky, Sergey Yekhanin

Discret. Math., 2012

2011

Inverse Conjecture for the Gowers Norm is False.

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Theory Comput., 2011

A new perspective on implementation by voting trees.

Felix A. Fischer, Ariel D. Procaccia, Alex Samorodnitsky

Random Struct. Algorithms, 2011

Computing the Partition Function for Perfect Matchings in a Hypergraph.

Alexander I. Barvinok, Alex Samorodnitsky

Comb. Probab. Comput., 2011

2010

An approximation algorithm for counting contingency tables.

Alexander I. Barvinok, Zur Luria, Alex Samorodnitsky, Alexander Yong

Random Struct. Algorithms, 2010

Lower bounds for designs in symmetric spaces.

Noa Eidelstein, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2010

2009

Learning and Smoothed Analysis.

Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

An upper bound for permanents of nonnegative matrices.

Alex Samorodnitsky

J. Comb. Theory, Ser. A, 2008

2007

Linear programming bounds for codes via a covering argument.

Michael Navon, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2007

Edge-Isoperimetric Inequalities and Influences.

Dvir Falik, Alex Samorodnitsky

Comb. Probab. Comput., 2007

Approximating entropy from sublinear samples.

Mickey Brautbar, Alex Samorodnitsky

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Low-degree tests at large distances.

Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2006

2005

Gowers Uniformity, Influence of Variables, and PCPs

Alex Samorodnitsky, Luca Trevisan

Electron. Colloquium Comput. Complex., 2005

Approximating the entropy of large alphabets

Mickey Brautbar, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2005

Random Weighting, Asymptotic Counting, and Inverse Isoperimetry.

Alexander I. Barvinok, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2005

On Delsarte's Linear Programming Bounds for Binary Codes.

Michael Navon, Alex Samorodnitsky

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

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

Leonid Gurvits, Alex Samorodnitsky

Proceedings of the 44th IEEE IEEE Conference on Decision and Control and 8th European Control Conference Control, 2005

2004

Testing juntas.

Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky

J. Comput. Syst. Sci., 2004

On Linear Programming Bounds for Spherical Codes and Designs.

Alex Samorodnitsky

Discret. Comput. Geom., 2004

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.

Michael E. Saks, Alex Samorodnitsky, Leonid Zosin

Comb., 2004

2002

Testing Basic Boolean Formulae.

Michal Parnas, Dana Ron, Alex Samorodnitsky

SIAM J. Discret. Math., 2002

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary.

Leonid Gurvits, Alex Samorodnitsky

Discret. Comput. Geom., 2002

Linear Codes and Character Sums.

Nathan Linial, Alex Samorodnitsky

Comb., 2002

Monotonicity testing over general poset domains.

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

On the Optimum of Delsarte's Linear Program.

Alex Samorodnitsky

J. Comb. Theory, Ser. A, 2001

Proclaiming Dictators and Juntas or Testing Boolean Formulae

Michal Parnas, Dana Ron, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2001

2000

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.

Nathan Linial, Alex Samorodnitsky, Avi Wigderson

Comb., 2000

Testing Monotonicity.

Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky

Comb., 2000

A PCP characterization of NP with optimal amortized query complexity.

Alex Samorodnitsky, Luca Trevisan

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume.

Leonid Gurvits, Alex Samorodnitsky

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Improved Testing Algorithms for Monotonicity.

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 1999

1996

Inclusion-Exclusion: Exact and Approximate.

Jeff Kahn, Nathan Linial, Alex Samorodnitsky

Comb., 1996