Alex Samorodnitsky

Publication Activity (10 Years)

Years Active: 1996-2024
Publications (10 Years): 29

Top Topics

Essential Matrices

Linear Programming

Top Venues

IEEE Trans. Inf. Theory

Electron. Colloquium Comput. Complex.

Comb. Probab. Comput.

Publications

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