Sergey Yekhanin: Publications

• Sergey Yekhanin
  "Locally Decodable Codes and Private Information Retrieval Schemes"

  • Ph.D. thesis, MIT, July 2007.

            Received: MIT George M. Sprowls Award for the best doctoral theses in Computer Science.

   

• Kiran S. Kedlaya, Sergey Yekhanin
  "Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers"

  • Electronic Colloquium on Computational Complexity (ECCC), TR07-040.

   

• Sergey Yekhanin
  "Towards 3-Query Locally Decodable Codes of Subexponential Length"

  • Electronic Colloquium on Computational Complexity (ECCC), TR06-127.

            (Under the title: "New Locally Decodable Codes and Private Information Retrieval Schemes")

  • Proc. of the 39th ACM Symposium on Theory of Computing (STOC), pp. 266-274, 2007. 

            Received: Best Paper Award (co-winner) and Best Student Paper Award.

   

• Alexander Razborov, Sergey Yekhanin
  "An Ω(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval"

  • Electronic Colloquium on Computational Complexity (ECCC), TR06-050.

  • Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS), pp. 739-748, 2006.

   

• Nicholas J. A. Harvey, Mihai Patrascu, Yonggang Wen, Sergey Yekhanin, Vincent W. S. Chan

  "Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs"

  • Proceedings of the 26th Annual IEEE Conference on Computer Communications (INFOCOM), 2007.

   

• Nicholas J. A. Harvey, David Karger, Sergey Yekhanin
  "On The Hardness of Matrix Completion"

  • Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.1103-1111, 2006.

   

• David Woodruff, Sergey Yekhanin
  "A Geometric Approach to Information Theoretic Private Information Retrieval"

  • Electronic Colloquium on Computational Complexity (ECCC), TR05-009.

  • Proceedings of the 20th IEEE Computational Complexity Conference (CCC), pp. 275-284, 2005.

  • Accepted to SIAM Journal on Computing, 2007.

   

• Sergey Yekhanin
  "A Note on Plane Pointless Curves"

  • Finite Fields and Their Applications, vol. 13, Issue 2, pp. 418-422, 2007.

   

• Sergey Yekhanin, Ilya Dumer
  "Long Nonbinary Codes Exceeding the Gilbert - Varshamov Bound for any Fixed Distance"

  • Proceedings of the Allerton Conference on Communication, Control, and Computing, 2004.

  • IEEE Transactions on Information Theory, vol. 50, Issue 10, pp. 2357-2362, 2004.

   

• Sergey Yekhanin
  "Improved Upper Bound for the Redundancy of Fix-Free Codes"

  • Proceedings of International Symposium on Information Theory (ISIT),  p.80, 2003.

  • IEEE Transactions on Information Theory, vol. 50, Issue 11, pp. 2815-2818, 2004.

   

• Emin Martinian, Sergey Yekhanin, Jonathan  S. Yedidia
  "Secure Biometrics Via Syndromes"

  • In Proceedings of the Allerton Conference on Communication, Control, and Computing, 2005.

   

• Arkadii D'yachkov, Vyacheslav Rykov, David Torney, Sergey Yekhanin
  "On Application of the partition distance concept to a comparative analysis of psychological or sociological tests"

  • Proceedings of International Symposium on Information Theory (ISIT), p. 256, 2004.

  • Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT), pp. 149-162, 2004.

  • Stochastic Analysis and Applications, vol. 24, pp. 61-78, 2006.

   

• Anthony J. Macula, Vyacheslav Rykov, Sergey Yekhanin
  "Trivial Two-Stage Group Testing for Complexes Using Almost Disjunct Matrices"

  • Discrete and Applied Mathematics, vol. 137, pp. 97-107, 2004.

   

• Arkadii D'yachkov, Pavel Vilenkin, Sergey Yekhanin
  "Upper Bound on the Rate of Superimposed (s,l) codes based on Engel's Inequality"

  • Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT), pp. 95-99, 2002.

   

• Sergey Yekhanin
  "Sufficient Conditions of Existence of Fix-Free Codes"

  • Proceedings of International Symposium on Information Theory (ISIT), p. 284, 2001.

   

• Arkadii D'yachkov, Vladimir Lebedev, Pavel Vilenkin, Sergey Yekhanin
  "Cover-Free Families and Superimposed Codes: Constructions, Bounds and Applications to Cryptography and Group Testing"

  • Proceedings of International Symposium on Information Theory (ISIT), p. 117, 2001.

   

• Arkadii D'yachkov, Anthony Macula, David Torney, Pavel Vilenkin, Sergey Yekhanin
  "New Results in the Theory of Superimposed Codes"

  • Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT), pp. 126-136, 2000.

   

• Sergey Yekhanin, Anna Kochetova
  "Evaluation of Estimates for Standard Learning Information in Pattern Recognition Problems"

  • Computational Mathematics and Mathematical Physics, vol. 42, N3, pp. 419-423, 2002.

   

• Sergey Yekhanin
  "Some New Constructions of Optimal Superimposed Designs"

  • Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT),  pp. 232-235, 1998.