**Sergey Yekhanin: publications**

- "DNA assembly for nanopore data storage readout"

with Randolph Lopez, Yuan-Jyue Chen, Siena Dumas Ang, Konstantin Makarychev, Miklos Racz, Georg Seelig, Karin Strauss, Luis Ceze*Nature Communications, vol. 10, 2019.*

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

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

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