No photo of Alex Samorodnitsky

View Scopus Profile

Alex Samorodnitsky

 https://orcid.org/0000-0001-8643-7948
    Calculated based on number of publications stored in Pure and citations from Scopus
    1996 …2024

    Research activity per year

    • 38 Article
    • 18 Conference contribution
    • 3 Conference article
    Filter
    Conference contribution

    Search results

    • 2021

      On codes decoding a constant fraction of errors on the BSC

      Hązła, J., Samorodnitsky, A. & Sberlo, O., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1479-1488 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      9 Scopus citations
    • 2019

      On the round complexity of randomized byzantine agreement

      Cohen, R., Haitner, I., Makriyannis, N., Orland, M. & Samorodnitsky, A., Oct 2019, 33rd International Symposium on Distributed Computing, DISC 2019. Suomela, J. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 12. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 146).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      9 Scopus citations
    • 2015

      Kolmogorov width of discrete linear spaces: An approach to matrix rigidity

      Samorodnitsky, A., Shkredov, I. & Yekhanin, S., 1 Jun 2015, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 347-364 18 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 33).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Proclaiming dictators and juntas or testing boolean formulae

      Parnas, M., Ron, D. & Samorodnitsky, A., 2015, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. Trevisan, L., Jansen, K., Goemans, M. & Rolim, J. D. P. (eds.). Springer Verlag, p. 273-285 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2129).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      2 Scopus citations
    • 2014

      A proof of the Ahlswede-Cai-Zhang conjecture

      Bunte, C., Lapidoth, A. & Samorodnitsky, A., 2014, 2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc., p. 1116-1120 5 p. 6875006. (IEEE International Symposium on Information Theory - Proceedings).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access

    • Bounds on the permanent and some applications

      Gurvits, L. & Samorodnitsky, A., 7 Dec 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 90-99 10 p. 6978993. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      27 Scopus citations
    • 2013

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

      Bunte, C., Lapidoth, A. & Samorodnitsky, A., 2013, 2013 IEEE International Symposium on Information Theory, ISIT 2013. p. 91-95 5 p. 6620194. (IEEE International Symposium on Information Theory - Proceedings).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      3 Scopus citations
    • 2009

      A new perspective on implementation by voting trees

      Fischer, F., Procaccia, A. D. & Samorodnitsky, A., 2009, EC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce. p. 31-40 10 p. (Proceedings of the ACM Conference on Electronic Commerce).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      8 Scopus citations

    • Learning and smoothed analysis

      Kalai, A. T., Samorodnitsky, A. & Teng, S. H., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 395-404 10 p. 5438615. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      37 Scopus citations
    • 2008

      Inverse conjecture for the gowers norm is false

      Lovett, S., Meshulam, R. & Samorodnitsky, A., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 547-556 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      24 Scopus citations
    • 2007

      Approximating entropy from sublinear samples

      Brautbar, M. & Samorodnitsky, A., 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 366-375 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      9 Scopus citations

    • Low-degree tests at large distances

      Samorodnitsky, A., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 506-515 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      87 Scopus citations
    • 2006

      Gowers uniformity, influence of variables, and PCPs

      Samorodnitsky, A. & Trevisan, L., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 11-20 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      64 Scopus citations
    • 2005

      A note on common quadratic Lyapunov functions for linear inclusions: Exact results and open problems

      Gurvits, L. & Samorodnitsky, A., 2005, Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05. p. 2350-2355 6 p. 1582513. (Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05; vol. 2005).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      5 Scopus citations

    • On Delsarte's linear programming bounds for binary codes

      Navon, M. & Samorodnitsky, A., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 327-336 10 p. 1530725. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      10 Scopus citations
    • 2000

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

      Gurvits, L. & Samorodnitsky, A., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 48-57 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      14 Scopus citations

    • A PCP characterization of NP with optimal amortized query complexity

      Samorodnitsky, A. & Trevisan, L., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 191-199 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      134 Scopus citations
    • 1999

      Improved testing algorithms for monotonicity

      Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D. & Samorodnitsky, A., 1999, Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Rolim, J. D. P., Sinclair, A., Hochbaum, D. & Jansen, K. (eds.). Springer Verlag, p. 97-108 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1671).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      136 Scopus citations
    Your message has successfully been sent.
    Your message was not sent due to an error.