![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Alex Samorodnitsky
Person information
- affiliation: The Hebrew University of Jerusalem, Israel
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j32]Itamar Katz
, Alex Samorodnitsky
, Yuval Kochman
:
Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection. IEEE Trans. Inf. Theory 70(4): 2701-2712 (2024) - 2023
- [i35]Alex Samorodnitsky:
On the difficulty to beat the first linear programming bound for binary codes. CoRR abs/2308.16038 (2023) - [i34]Itamar Katz, Alex Samorodnitsky, Yuval Kochman:
Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection. CoRR abs/2311.02366 (2023) - 2022
- [j31]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): 1376 (2022) - [j30]Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky:
On the Round Complexity of Randomized Byzantine Agreement. J. Cryptol. 35(2): 10 (2022) - [i33]Alex Samorodnitsky:
Weight distribution of random linear codes and Krawchouk polynomials. CoRR abs/2205.02051 (2022) - [i32]Alex Samorodnitsky:
On some properties of random and pseudorandom codes. CoRR abs/2206.05135 (2022) - 2021
- [j29]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): 3509-3541 (2021) - [c21]Jan Hazla, Alex Samorodnitsky, Ori Sberlo:
On codes decoding a constant fraction of errors on the BSC. STOC 2021: 1479-1488 - [i31]Alex Samorodnitsky:
One more proof of the first linear programming bound for binary codes and two conjectures. CoRR abs/2104.14587 (2021) - [i30]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 abs/2112.09039 (2021) - 2020
- [j28]Eran Iceland
, Alex Samorodnitsky:
On Coset Leader Graphs of Structured Linear Codes. Discret. Comput. Geom. 63(3): 560-576 (2020) - [j27]Naomi Kirshner, Alex Samorodnitsky:
On the ℓ4: ℓ2 ratio of functions with restricted Fourier support. J. Comb. Theory A 172: 105202 (2020) - [j26]Alex Samorodnitsky
:
An Upper Bound on $\ell_q$ Norms of Noisy Functions. IEEE Trans. Inf. Theory 66(2): 742-748 (2020) - [i29]Alex Samorodnitsky, Ori Sberlo:
On codes decoding a constant fraction of errors on the BSC. CoRR abs/2008.07236 (2020) - [i28]Alex Samorodnitsky:
An improved bound on 𝓁q norms of noisy functions. CoRR abs/2010.02721 (2020)
2010 – 2019
- 2019
- [c20]Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky:
On the Round Complexity of Randomized Byzantine Agreement. DISC 2019: 12:1-12:17 - [i27]Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky:
On the Round Complexity of Randomized Byzantine Agreement. CoRR abs/1907.11329 (2019) - [i26]Naomi Kirshner, Alex Samorodnitsky:
A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres. CoRR abs/1909.11929 (2019) - [i25]Naomi Kirshner, Alex Samorodnitsky:
A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres. Electron. Colloquium Comput. Complex. TR19 (2019) - [i24]Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky:
On the Round Complexity of Randomized Byzantine Agreement. IACR Cryptol. ePrint Arch. 2019: 868 (2019) - 2018
- [i23]Alex Samorodnitsky:
An upper bound on ℓq norms of noisy functions. CoRR abs/1809.09696 (2018) - [i22]Eran Iceland, Alex Samorodnitsky:
On coset leader graphs of structured linear codes. Electron. Colloquium Comput. Complex. TR18 (2018) - [i21]Naomi Kirshner, Alex Samorodnitsky:
On ℓ4: ℓ2 ratio of functions with restricted Fourier support. Electron. Colloquium Comput. Complex. TR18 (2018) - [i20]Alex Samorodnitsky:
An upper bound on $\ell_q$ norms of noisy functions. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j25]Alex Samorodnitsky:
An Inequality for Functions on the Hamming Cube. Comb. Probab. Comput. 26(3): 468-480 (2017) - 2016
- [j24]Alex Samorodnitsky, Ilya D. Shkredov
, Sergey Yekhanin:
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. Comput. Complex. 25(2): 309-348 (2016) - [j23]Alex Samorodnitsky
:
On the Entropy of a Noisy Function. IEEE Trans. Inf. Theory 62(10): 5446-5464 (2016) - [i19]Yury Polyanskiy, Alex Samorodnitsky:
Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube. CoRR abs/1606.07491 (2016) - 2015
- [j22]Eran Iceland, Alex Samorodnitsky:
On Coset Leader Graphs of LDPC Codes. IEEE Trans. Inf. Theory 61(8): 4158-4163 (2015) - [c19]Alex Samorodnitsky, Ilya D. Shkredov
, Sergey Yekhanin:
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. CCC 2015: 347-364 - [i18]Alex Samorodnitsky:
On the entropy of a noisy function. CoRR abs/1508.01464 (2015) - [i17]Alex Samorodnitsky:
The "Most informative boolean function" conjecture holds for high noise. CoRR abs/1510.08656 (2015) - [i16]Alex Samorodnitsky:
On the entropy of a noisy function. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j21]Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky:
The Zero-Undetected-Error Capacity Approaches the Sperner Capacity. IEEE Trans. Inf. Theory 60(7): 3825-3833 (2014) - [c18]Leonid Gurvits, Alex Samorodnitsky:
Bounds on the Permanent and Some Applications. FOCS 2014: 90-99 - [c17]Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky:
A proof of the Ahlswede-Cai-Zhang conjecture. ISIT 2014: 1116-1120 - [i15]Eran Iceland, Alex Samorodnitsky:
On Coset Leader Graphs of LDPC codes. CoRR abs/1402.5051 (2014) - [i14]Mark Rudelson, Alex Samorodnitsky, Ofer Zeitouni:
Random Gaussian matrices and Hafnian estimators. CoRR abs/1409.3905 (2014) - [i13]Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin:
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c16]Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky:
The zero-undetected-error capacity of the low-noise cyclic triangle channel. ISIT 2013: 91-95 - [i12]Christoph Bunte, Amos Lapidoth, Alex Samorodnitsky:
The Zero-Undetected-Error Capacity Approaches the Sperner Capacity. CoRR abs/1309.4930 (2013) - 2012
- [j20]Alex Samorodnitsky, Sergey Yekhanin:
A note on the Newton radius. Discret. Math. 312(15): 2392-2393 (2012) - [j19]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): 11:1-11:12 (2012) - 2011
- [j18]Alexander I. Barvinok, Alex Samorodnitsky:
Computing the Partition Function for Perfect Matchings in a Hypergraph. Comb. Probab. Comput. 20(6): 815-835 (2011) - [j17]Felix A. Fischer, Ariel D. Procaccia, Alex Samorodnitsky:
A new perspective on implementation by voting trees. Random Struct. Algorithms 39(1): 59-82 (2011) - [j16]Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse Conjecture for the Gowers Norm is False. Theory Comput. 7(1): 131-145 (2011) - 2010
- [j15]Alexander I. Barvinok, Zur Luria, Alex Samorodnitsky, Alexander Yong:
An approximation algorithm for counting contingency tables. Random Struct. Algorithms 37(1): 25-66 (2010) - [i11]Noa Eidelstein, Alex Samorodnitsky:
Lower bounds for designs in symmetric spaces. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j14]Michael Navon, Alex Samorodnitsky:
Linear Programming Bounds for Codes via a Covering Argument. Discret. Comput. Geom. 41(2): 199-207 (2009) - [j13]Alex Samorodnitsky, Luca Trevisan
:
Gowers Uniformity, Influence of Variables, and PCPs. SIAM J. Comput. 39(1): 323-360 (2009) - [c15]Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng:
Learning and Smoothed Analysis. FOCS 2009: 395-404 - [c14]Felix A. Fischer, Ariel D. Procaccia, Alex Samorodnitsky:
A new perspective on implementation by voting trees. EC 2009: 31-40 - 2008
- [j12]Alex Samorodnitsky:
An upper bound for permanents of nonnegative matrices. J. Comb. Theory A 115(2): 279-292 (2008) - [c13]Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse conjecture for the gowers norm is false. STOC 2008: 547-556 - 2007
- [j11]Dvir Falik, Alex Samorodnitsky:
Edge-Isoperimetric Inequalities and Influences. Comb. Probab. Comput. 16(5): 693-712 (2007) - [c12]Mickey Brautbar, Alex Samorodnitsky:
Approximating entropy from sublinear samples. SODA 2007: 366-375 - [c11]Alex Samorodnitsky:
Low-degree tests at large distances. STOC 2007: 506-515 - [i10]Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse Conjecture for the Gowers norm is false. Electron. Colloquium Comput. Complex. TR07 (2007) - [i9]Michael Navon, Alex Samorodnitsky:
Linear programming bounds for codes via a covering argument. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c10]Alex Samorodnitsky, Luca Trevisan:
Gowers uniformity, influence of variables, and PCPs. STOC 2006: 11-20 - [i8]Alex Samorodnitsky:
Low-degree tests at large distances. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c9]Leonid Gurvits, Alex Samorodnitsky:
A note on common quadratic Lyapunov functions for linear inclusions: Exact results and Open Problems. CDC/ECC 2005: 2350-2355 - [c8]Michael Navon, Alex Samorodnitsky:
On Delsarte's Linear Programming Bounds for Binary Codes. FOCS 2005: 327-338 - [i7]Alex Samorodnitsky, Luca Trevisan:
Gowers Uniformity, Influence of Variables, and PCPs. CoRR abs/math/0510264 (2005) - [i6]Alexander I. Barvinok, Alex Samorodnitsky:
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry. Electron. Colloquium Comput. Complex. TR05 (2005) - [i5]Mickey Brautbar, Alex Samorodnitsky:
Approximating the entropy of large alphabets. Electron. Colloquium Comput. Complex. TR05 (2005) - [i4]Alex Samorodnitsky, Luca Trevisan:
Gowers Uniformity, Influence of Variables, and PCPs. Electron. Colloquium Comput. Complex. TR05 (2005) - [i3]Dvir Falik, Alex Samorodnitsky:
Edge-isoperimetric inequalities and influences. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j10]Michael E. Saks, Alex Samorodnitsky, Leonid Zosin:
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks. Comb. 24(3): 525-530 (2004) - [j9]Alex Samorodnitsky:
On Linear Programming Bounds for Spherical Codes and Designs. Discret. Comput. Geom. 31(3): 385-394 (2004) - [j8]Eldar Fischer, Guy Kindler, Dana Ron
, Shmuel Safra
, Alex Samorodnitsky:
Testing juntas. J. Comput. Syst. Sci. 68(4): 753-787 (2004) - 2002
- [j7]Nathan Linial, Alex Samorodnitsky:
Linear Codes and Character Sums. Comb. 22(4): 497-522 (2002) - [j6]Leonid Gurvits, Alex Samorodnitsky:
A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary. Discret. Comput. Geom. 27(4): 531-550 (2002) - [j5]Michal Parnas, Dana Ron
, Alex Samorodnitsky:
Testing Basic Boolean Formulae. SIAM J. Discret. Math. 16(1): 20-46 (2002) - [c7]Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra
, Alex Samorodnitsky:
Testing Juntas. FOCS 2002: 103-112 - [c6]Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky:
Monotonicity testing over general poset domains. STOC 2002: 474-483 - 2001
- [j4]Alex Samorodnitsky:
On the Optimum of Delsarte's Linear Program. J. Comb. Theory A 96(2): 261-287 (2001) - [c5]Michal Parnas, Dana Ron, Alex Samorodnitsky:
Proclaiming Dictators and Juntas or Testing Boolean Formulae. RANDOM-APPROX 2001: 273-284 - [i2]Michal Parnas, Dana Ron, Alex Samorodnitsky:
Proclaiming Dictators and Juntas or Testing Boolean Formulae. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j3]Oded Goldreich
, Shafi Goldwasser, Eric Lehman, Dana Ron
, Alex Samorodnitsky:
Testing Monotonicity. Comb. 20(3): 301-337 (2000) - [j2]Nathan Linial, Alex Samorodnitsky, Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Comb. 20(4): 545-568 (2000) - [c4]Leonid Gurvits, Alex Samorodnitsky:
A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume. STOC 2000: 48-57 - [c3]Alex Samorodnitsky, Luca Trevisan
:
A PCP characterization of NP with optimal amortized query complexity. STOC 2000: 191-199
1990 – 1999
- 1999
- [c2]Yevgeniy Dodis, Oded Goldreich
, Eric Lehman, Sofya Raskhodnikova, Dana Ron
, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999: 97-108 - [i1]Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [c1]Nathan Linial, Alex Samorodnitsky, Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC 1998: 644-652 - 1996
- [j1]Jeff Kahn, Nathan Linial, Alex Samorodnitsky:
Inclusion-Exclusion: Exact and Approximate. Comb. 16(4): 465-477 (1996)
Coauthor Index
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-06-10 20:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint