Sergey Yekhanin:  publications

• "Maximally recoverable LRCs: lower bounds and constructions for few heavy parities" with Sivakanth Gopi, Venkatesan Guruswami
  • Electronic Colloquium on Computational Complexity (ECCC), TR17-183, November 2017.
  • Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019. 
    

​​

• "Collecting telemetry data privately" with Bolin Ding, Janardhan Kulkarni​
  • Proceedings of Advances in Neural Information Processing Systems (NIPS), pp. 3574-3583, 2017.  

• "Clustering billions of reads for DNA data storage"
   with Cyrus Rashtchian, Konstantin Makarychev, Miklos Racz, Siena Dumas Ang, Djordje Jevdjic, Luis Ceze, Karin Strauss
  
  • Proceedings of Advances in Neural Information Processing Systems (NIPS), pp. 3362-3373, 2017. 
    

• "Random access in large-scale DNA storage"
  with Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Konstantin Makarychev, Miklos Z. Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, Christopher Takahashi, Sharon Newman, Hsing-Yeh Parker, Cyrus Rashtchian, Kendall Stewart, Gagan Gupta, Robert Carlson, John Mulligan, Douglas Carmean, Georg Seelig, Luis Ceze, Karin Strauss
  • Nature Biotechnology, vol. 36, pp. 242-248, 2018.

• "Maximally recoverable codes for grid-like topologies"
   with Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang
  
  • Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2092-2108, 2017.  
    

• "New constructions of MR and SD codes over small finite fields" with Guangda Hu
  
  • Proceedings of International Symposium on Information Theory (ISIT), pp.1591-1595, 2016.
    

• "Kolmogorov width of discrete linear spaces: an approach to matrix rigidity" with Alex Samorodnitsky and Ilya Shkredov
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR14-172, December 2014.
    
  • Proceedings of the 26th Computational Complexity Conference (CCC), pp. 347-364, 2015.
  • Computational Complexity, vol. 25, issue 2, pp. 309-348, 2016.

• "Codes with local decoding procedures"
  
  • Proc. of the International Congress of Mathematicians (ICM), August 2014.

• "Explicit maximally recoverable codes with locality" with Parikshit Gopalan, Cheng Huang, Bob Jenkins
  
  • IEEE Transactions on Information Theory, vol. 60, issue 9, pp. 5245-5256, 2014.

• "On the locality of codeword symbols in non-linear codes" with Michael Forbes
  
  • Discrete mathematics, vol. 324, pp. 78-84, 2014.

• ​"Extending memory lifetime by reviving dead blocks"
   with Rodolfo Azevedo, John D. Davis, Karin Strauss, Parikshit Gopalan, Mark Manasse
  
  • Proceedings of International Symposium on Computer Architecture (ISCA) 2013, pp. 452-463, 2013.   
    

• "Erasure coding in Windows Azure Storage"
   with Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li
  
  • Proceedings of USENIX Annual Technical Conference (USENIX ATC), pp.15-26, 2012.   
    

• "A note on the Newton radius" with Alex Samorodnitsky
  • Discrete mathematics, vol. 312, issue 15, pp. 2392-2393, 2012.
    

• "On the locality of codeword symbols" with Parikshit Gopalan, Cheng Huang, Huseyin Simitci
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR11-100.
  • IEEE Transactions on Information Theory, vol. 58, issue 11, pp. 6925-6934, 2012.  
    

• "Noisy interpolation of sparse polynomials, and applications" with Shubhangi Saraf
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR11-044.
  • Proceedings of the 26th IEEE Computational Complexity Conference (CCC), pp. 86-92, 2011.

• "Locally decodable codes: a brief survey"
  • Proceedings of the 3rd International Workshop on Coding and Cryptography (IWCC), 2011.   
    

• "High-rate codes with sublinear-time decoding" with Swastik Kopparty, Shubhangi Saraf
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR10-148.
  • Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pp.167-176, 2011.
  • Journal of ACM, vol. 61, issue 5, 2014.
    

• "Locally decodable codes"
  
  • Foundations and Trends in Theoretical Computer Science, vol. 6, issue 3, pp. 139-255, 2012.   

• "Private information retrieval"
  
  • Communications of the ACM, vol. 53, issue 4, pp. 68-73, 2010.   
    

​

• "Sets with large additive energy and symmetric sets" with Ilya Shkredov
  
  • Journal of Combinatorial Theory Ser A., vol. 118, issue 3, pp 1086-1093, 2011.   
    

• "Matching vector codes" with Zeev Dvir, Parikshit Gopalan
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR10-012.
  • Proceedings of the 51st Symposium on Foundations of Computer Science (FOCS), pp. 705-714, 2010.   
  • SIAM Journal on Computing, vol. 40, issue 4, pp. 1154-1178, 2011.
    

• "Pan-private streaming algorithms" with Cynthia Dwork, Moni Naor, Toni Pitassi, Guy Rothblum
  
  • Proceedings of the 1st Symposium on Innovations in Computer Science (ICS), 2010.   
    

• "Deterministic approximation algorithms for the nearest codeword problem" with Noga Alon, Rina Panigrahy
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR08-065.   
    
  • Proceedings of the 13th International Workshop (RANDOM), pp. 339-351, 2009.
    

• "New efficient attacks on statistical disclosure control mechanisms" with Cynthia Dwork
  
  • Proceedings of the 28th International Cryptology Conference (CRYPTO), pp. 469-480, 2008.   
    

• "Detecting rational points on hypersurfaces over finite fields"with Swastik Kopparty
  
  • Proceedings of the 23th IEEE Computational Complexity Conference (CCC), pp. 311-320, 2008

• "Locally decodable codes and private information retrieval schemes"
  • Ph.D. thesis, MIT, July 2007.
    
  • Book version published by Springer, 2010.  
    

• "Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers" with Kiran Kedlaya
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR07-040.
    
  • Proceedings of the 23th IEEE Computational Complexity Conference (CCC), pp. 175-186, 2008.
    
  • SIAM Journal on Computing, vol. 38, issue 5, pp. 1952-1969, 2009.
    

• "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.
  • Journal of ACM, vol. 55, issue 1, pp.1-16, 2007.
    

​

• "An Ω(n^{1/3}) lower bound for bilinear group based private information retrieval" with Alexander Razborov
  • Electronic Colloquium on Computational Complexity (ECCC), TR06-050.
  • Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS), pp. 739-748, 2006.
  •  Theory of Computing, vol. 3, issue 1, pp. 221-238, 2007.
    

• "Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs"
   with Nicholas J. A. Harvey, Mihai Patrascu, Yonggang Wen, Vincent W. S. Chan
  
  • Proceedings of the 26th Annual IEEE Conference on Computer Communications (INFOCOM), pp.697-705, 2007.  
    

​

• "On the hardness of matrix completion" with  Nicholas J. A. Harvey, David Karger
  
  • Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.1103-1111, 2006.

• "A geometric approach to information theoretic private information retrieval" with David Woodruff
  
  • Electronic Colloquium on Computational Complexity (ECCC), TR05-009.
  • Proceedings of the 20th IEEE Computational Complexity Conference (CCC), pp. 275-284, 2005.
  •  SIAM Journal on Computing, vol. 47, issue 4, pp. 1046-1056, 2007.
    
    
• "A note on plane pointless curves"
  
  • Finite Fields and Their Applications, vol. 13, Issue 2, pp. 418-422, 2007.
    

• "Long nonbinary codes exceeding the Gilbert - Varshamov bound for any fixed distance" with Ilya Dumer
  
  • Proceedings of the Allerton Conference on Communication, Control, and Computing, 2004.
  • IEEE Transactions on Information Theory, vol. 50, Issue 10, pp. 2357-2362, 2004.
    

• "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.
    

• "Secure biometrics via syndromes" with Emin Martinian, Jonathan  S. Yedidia
  
  • In Proceedings of the Allerton Conference on Communication, Control, and Computing, 2005.

• "On application of the partition distance concept to a comparative analysis of psychological or sociological tests" 
    with Arkadii D'yachkov, Vyacheslav Rykov, David Torney 
  
  • 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.
    

​

• "Trivial two-stage group testing for complexes using almost disjunct matrices" with Anthony J. Macula, Vyacheslav Rykov
  
  • Discrete and Applied Mathematics, vol. 137, pp. 97-107, 2004.

• "Upper bound on the rate of superimposed (s,l) codes based on Engel's inequality" with Arkadii D'yachkov, Pavel Vilenkin
  
  •  Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT), pp. 95-99, 2002.

• "Sufficient conditions of existence of fix-free codes"
  
  • Proceedings of International Symposium on Information Theory (ISIT), p. 284, 2001.

• "Cover-free families and superimposed codes: constructions, bounds and applications to cryptography and group testing"
   with Arkadii D'yachkov, Vladimir Lebedev, Pavel Vilenkin
  
  • Proceedings of International Symposium on Information Theory (ISIT), p. 117, 2001. 

• "New results in the theory of superimposed codes" with Arkadii D'yachkov, Anthony Macula, David Torney, Pavel Vilenkin     
  • Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT), pp. 126-136, 2000.   

• "Evaluation of estimates for standard learning information in pattern recognition problems" with Anna Kochetova
  • Computational Mathematics and Mathematical Physics, vol. 42, Issue 3, pp. 419-423, 2002.

• "Some new constructions of optimal superimposed designs"
  • Proceedings of International Conf. on Algebraic and Combinatorial Coding Theory (ACCT),  pp. 232-235, 1998.