Alex Samorodnitsky

Orcid: 0000-0001-8643-7948

Affiliations:
  • The Hebrew University of Jerusalem, Israel


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

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection.
IEEE Trans. Inf. Theory, April, 2024

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

2022
On the Round Complexity of Randomized Byzantine Agreement.
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.
Entropy, 2022

On some properties of random and pseudorandom codes.
CoRR, 2022

Weight distribution of random linear codes and Krawchouk polynomials.
CoRR, 2022

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

On codes decoding a constant fraction of errors on the BSC.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020
On the <i>ℓ</i><sub>4</sub>: <i>ℓ</i><sub>2</sub> ratio of functions with restricted Fourier support.
J. Comb. Theory A, 2020

An improved bound on 𝓁<sub>q</sub> norms of noisy functions.
CoRR, 2020

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

2019
A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres.
Electron. Colloquium Comput. Complex., 2019

2018
An upper bound on $\ell_q$ norms of noisy functions.
Electron. Colloquium Comput. Complex., 2018

On ℓ<sub>4</sub>: ℓ<sub>2</sub> ratio of functions with restricted Fourier support.
Electron. Colloquium Comput. Complex., 2018

On coset leader graphs of structured linear codes.
Electron. Colloquium Comput. Complex., 2018

An upper bound on ℓ<sub>q</sub> norms of noisy functions.
CoRR, 2018

2017
An Inequality for Functions on the Hamming Cube.
Comb. Probab. Comput., 2017

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

Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity.
Comput. Complex., 2016

2015
On Coset Leader Graphs of LDPC Codes.
IEEE Trans. Inf. Theory, 2015

On the entropy of a noisy function.
Electron. Colloquium Comput. Complex., 2015

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

2014
The Zero-Undetected-Error Capacity Approaches the Sperner Capacity.
IEEE Trans. Inf. Theory, 2014

Random Gaussian matrices and Hafnian estimators.
CoRR, 2014

A proof of the Ahlswede-Cai-Zhang conjecture.
Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Bounds on the Permanent and Some Applications.
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.
Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013

2012
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
ACM Trans. Comput. Theory, 2012

A note on the Newton radius.
Discret. Math., 2012

2011
A new perspective on implementation by voting trees.
Random Struct. Algorithms, 2011

Computing the Partition Function for Perfect Matchings in a Hypergraph.
Comb. Probab. Comput., 2011

2010
An approximation algorithm for counting contingency tables.
Random Struct. Algorithms, 2010

Lower bounds for designs in symmetric spaces.
Electron. Colloquium Comput. Complex., 2010

2009
Gowers Uniformity, Influence of Variables, and PCPs.
SIAM J. Comput., 2009

Learning and Smoothed Analysis.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
An upper bound for permanents of nonnegative matrices.
J. Comb. Theory A, 2008

2007
Linear programming bounds for codes via a covering argument.
Electron. Colloquium Comput. Complex., 2007

Inverse Conjecture for the Gowers norm is false.
Electron. Colloquium Comput. Complex., 2007

Approximating entropy from sublinear samples.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Low-degree tests at large distances.
Electron. Colloquium Comput. Complex., 2006

2005
Edge-isoperimetric inequalities and influences
Electron. Colloquium Comput. Complex., 2005

Approximating the entropy of large alphabets
Electron. Colloquium Comput. Complex., 2005

Random Weighting, Asymptotic Counting, and Inverse Isoperimetry.
Electron. Colloquium Comput. Complex., 2005

On Delsarte's Linear Programming Bounds for Binary Codes.
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.
Proceedings of the 44th IEEE IEEE Conference on Decision and Control and 8th European Control Conference Control, 2005

2004
Testing juntas.
J. Comput. Syst. Sci., 2004

On Linear Programming Bounds for Spherical Codes and Designs.
Discret. Comput. Geom., 2004

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

2002
Testing Basic Boolean Formulae.
SIAM J. Discret. Math., 2002

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary.
Discret. Comput. Geom., 2002

Linear Codes and Character Sums.
Comb., 2002

Monotonicity testing over general poset domains.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
On the Optimum of Delsarte's Linear Program.
J. Comb. Theory A, 2001

Proclaiming Dictators and Juntas or Testing Boolean Formulae
Electron. Colloquium Comput. Complex., 2001

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

Testing Monotonicity.
Comb., 2000

A PCP characterization of NP with optimal amortized query complexity.
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.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999
Improved Testing Algorithms for Monotonicity.
Electron. Colloquium Comput. Complex., 1999

1996
Inclusion-Exclusion: Exact and Approximate.
Comb., 1996


  Loading...