Academic Appointments


2024-25 Courses


Stanford Advisees


All Publications


  • IMPROVED LIST-DECODABILITY AND LIST-RECOVERABILITY OF REED-SOLOMON CODES VIA TREE PACKINGS SIAM JOURNAL ON COMPUTING Guo, Z., Li, R., Shangguan Chong, Tamo, I., Wootters, M. 2024; 53 (2): 389-430

    View details for DOI 10.1137/21M1463707

    View details for Web of Science ID 001189705300001

  • A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications Blackwell, K., Wootters, M., Guruswami SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2024
  • Viderman's algorithm for quantum LDPC codes Krishna, A., Navon, I., Wootters, M., Woodruff, D. P. SIAM. 2024: 2481-2507
  • Magnetic DNA random access memory with nanopore readouts and exponentially-scaled combinatorial addressing. Scientific reports Lau, B., Chandak, S., Roy, S., Tatwawadi, K., Wootters, M., Weissman, T., Ji, H. P. 2023; 13 (1): 8514

    Abstract

    The storage of data in DNA typically involves encoding and synthesizing data into short oligonucleotides, followed by reading with a sequencing instrument. Major challenges include the molecular consumption of synthesized DNA, basecalling errors, and limitations with scaling up read operations for individual data elements. Addressing these challenges, we describe a DNA storage system called MDRAM (Magnetic DNA-based Random Access Memory) that enables repetitive and efficient readouts of targeted files with nanopore-based sequencing. By conjugating synthesized DNA to magnetic agarose beads, we enabled repeated data readouts while preserving the original DNA analyte and maintaining data readout quality. MDRAM utilizes an efficient convolutional coding scheme that leverages soft information in raw nanopore sequencing signals to achieve information reading costs comparable to Illumina sequencing despite higher error rates. Finally, we demonstrate a proof-of-concept DNA-based proto-filesystem that enables an exponentially-scalable data address space using only small numbers of targeting primers for assembly and readout.

    View details for DOI 10.1038/s41598-023-29575-z

    View details for PubMedID 37231057

  • IMPROVED LIST DECODING OF FOLDED REED-SOLOMON AND MULTIPLICITY CODES SIAM JOURNAL ON COMPUTING Kopparty, S., Ron-Zewi, N., Saraf, S., Wootters, M. 2023; 52 (3): 794-840

    View details for DOI 10.1137/20M1370215

    View details for Web of Science ID 001082560700002

  • Bounds for List-Decoding and List-Recovery of Random Linear Codes IEEE TRANSACTIONS ON INFORMATION THEORY Guruswami, V., Li, R., Mosheiff, J., Resch, N., Silas, S., Wootters, M. 2022; 68 (2): 923-939
  • Threshold Rates for Properties of Random Codes IEEE TRANSACTIONS ON INFORMATION THEORY Guruswami, V., Moshieff, J., Resch, N., Silas, S., Wootters, M. 2022; 68 (2): 905-922
  • Asynchronous Distributed Optimization with Stochastic Delays Glasgow, M., Wootters, M., Camps-Valls, G., Ruiz, F. J., Valera JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2022
  • Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings Guo, Z., Li, R., Shangguan, C., Tamo, I., Wootters, M., IEEE COMP SOC IEEE COMPUTER SOC. 2022: 708-719
  • Linear-Time Erasure List-Decoding of Expander Codes IEEE TRANSACTIONS ON INFORMATION THEORY Ron-Zewi, N., Wootters, M., Zemor, G. 2021; 67 (9): 5827-5839
  • Improved List-Decodability of Random Linear Binary Codes Li, R., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2021: 1522–36
  • Embedded Index Coding Porter, A., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2021: 1461–77
  • Lifted Multiplicity Codes and the Disjoint Repair Group Property IEEE TRANSACTIONS ON INFORMATION THEORY Li, R., Wootters, M. 2021; 67 (2): 716–25
  • Superbridge and bridge indices for knots JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS Adams, C., Agarwal, N., Allen, R., Khandhawit, T., Simons, A., Winarski, R., Wootters, M. 2021; 30 (2)
  • Weighted Matrix Completion From Non-Random, Non-Uniform Sampling Patterns IEEE TRANSACTIONS ON INFORMATION THEORY Foucart, S., Needell, D., Pathak, R., Plan, Y., Wootters, M. 2021; 67 (2): 1264–90
  • Hermitian-lifted codes DESIGNS CODES AND CRYPTOGRAPHY Lopez, H. H., Malmskog, B., Matthews, G. L., Pinero-Gonzalez, F., Wootters, M. 2021
  • Illusion of large on-chip memory by networked computing chips for neural network inference NATURE ELECTRONICS Radway, R. M., Bartolo, A., Jolly, P. C., Khan, Z. F., Le, B. Q., Tandon, P., Wu, T. F., Xin, Y., Vianello, E., Vivet, P., Nowak, E., Wong, H., Aly, M., Beigne, E., Wootters, M., Mitra, S. 2021
  • Wedge-Lifted Codes Hastings, J., Kanne, A., Li, R., Wootters, M., IEEE IEEE. 2021: 2990-2995
  • Approximate Gradient Coding with Optimal Decoding Glasgow, M., Wootters, M., IEEE IEEE. 2021: 2280-2285
  • On Greedy Approaches to Hierarchical Aggregation Porter, A., Wootters, M., IEEE IEEE. 2021: 2649-2654
  • On Coding for an Abstracted Nanopore Channel for DNA Storage Hulett, R., Chandak, S., Wootters, M., IEEE IEEE. 2021: 2465-2470
  • LOCAL LIST RECOVERY OF HIGH-RATE TENSOR CODES AND APPLICATIONS SIAM JOURNAL ON COMPUTING Hemenway, B., Ron-Zewi, N., Wootters, M. 2020; 49 (4)

    View details for DOI 10.1137/17M116149X

    View details for Web of Science ID 000568207500005

  • Linear-time Erasure List-decoding of Expander Codes Ron-Zewi, N., Wootters, M., Zemor, G., IEEE IEEE. 2020: 379-383
  • LDPC Codes Achieve List Decoding Capacity Mosheiff, J., Resch, N., Ron-Zewi, N., Silas, S., Wootters, M., IEEE IEEE. 2020: 458-469
  • Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise Shutty, N., Wootters, M., Hayden, P., IEEE IEEE. 2020: 206-217
  • OVERCOMING HIGH NANOPORE BASECALLER ERROR RATES FOR DNA STORAGE VIA BASECALLER-DECODER INTEGRATION AND CONVOLUTIONAL CODES Chandak, S., Neu, J., Tatwawadi, K., Mardia, J., Lau, B., Kubit, M., Hulett, R., Griffin, P., Wootters, M., Weissman, T., Ji, H., IEEE IEEE. 2020: 8822–26
  • A Data-Compressive Wired-OR Readout for Massively Parallel Neural Recording Muratore, D., Tandon, P., Wootters, M., Chichilnisky, E. J., Mitra, S., Murmann, B. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2019: 1128–40

    Abstract

    Neural interfaces of the future will be used to help restore lost sensory, motor, and other capabilities. However, realizing this futuristic promise requires a major leap forward in how electronic devices interface with the nervous system. Next generation neural interfaces must support parallel recording from tens of thousands of electrodes within the form factor and power budget of a fully implanted device, posing a number of significant engineering challenges. In this paper, we exploit sparsity and diversity of neural signals to achieve simultaneous data compression and channel multiplexing for neural recordings. The architecture uses wired-OR interactions within an array of single-slope A/D converters to obtain massively parallel digitization of neural action potentials. The achieved compression is lossy but effective at retaining the critical samples belonging to action potentials, enabling efficient spike sorting and cell type identification. Simulation results of the architecture using data obtained from primate retina ex-vivo with a 512-channel electrode array show average compression rates up to  ∼ 40× while missing less than 5% of cells. In principle, the techniques presented here could be used to design interfaces to other parts of the nervous system.

    View details for DOI 10.1109/TBCAS.2019.2935468

    View details for Web of Science ID 000507321400002

    View details for PubMedID 31425051

  • On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing Inan, H. A., Kairouz, P., Wootters, M., Ozgur, A. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2019: 5592–5603
  • Fast Blind MIMO Decoding Through Vertex Hopping IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS Dean, T. R., Perlstein, J. R., Wootters, M., Goldsmith, A. J. 2019; 18 (7): 3669–82
  • Repairing Multiple Failures for Scalar MDS Codes Mardia, J., Bartan, B., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2019: 2661–72
  • Blind Joint MIMO Channel Estimation and Decoding IEEE TRANSACTIONS ON INFORMATION THEORY Dean, T. R., Wootters, M., Goldsmith, A. J. 2019; 65 (4): 2507–24
  • Resistive RAM Endurance: Array-Level Characterization and Correction Techniques Targeting Deep Learning Applications IEEE TRANSACTIONS ON ELECTRON DEVICES Grossi, A., Vianello, E., Sabry, M. M., Barlas, M., Grenouillet, L., Coignus, J., Beigne, E., Wu, T., Le, B. Q., Wootters, M. K., Zambelli, C., Nowak, E., Mitra, S. 2019; 66 (3): 1281–88
  • A 43pJ/Cycle Non-Volatile Microcontroller with 4.7 mu s Shutdown/Wake-up Integrating 2.3-bit/Cell Resistive RAM and Resilience Techniques Wu, T. F., Le, B. Q., Radway, R., Bartolo, A., Hwang, W., Jeong, S., Li, H., Tandon, P., Vianello, E., Vivet, P., Nowak, E., Wootters, M. K., Wong, H., Aly, M., Beigne, E., Mitra, S., Fujino, L. C., Anderson, J. H., Belostotski, L., Dunwell, D., Gaudet, Gulak, G., Haslett, J. W., Halupka, D., Smith, K. C. IEEE. 2019: 226-+
  • A Data-Compressive Wired-OR Readout for Massively Parallel Neural Recording Muratore, D. G., Tandon, P., Wootters, M., Chichilnisky, E. J., Mitra, S., Murmann, B., IEEE IEEE. 2019
  • Stochastic Gradient Coding for Flexible Straggler Mitigation in Distributed Learning Bitar, R., Wootters, M., El Rouayheb, S., IEEE IEEE. 2019: 394–98
  • Embedded Index Coding Porter, A., Wootters, M., IEEE IEEE. 2019: 354–58
  • Improved read/write cost tradeoff in DNA-based data storage using LDPC codes Chandak, S., Tatwawadi, K., Lau, B., Mardia, J., Kubit, M., Neu, J., Griffin, P., Wootters, M., Weissman, T., Ji, H., IEEE IEEE. 2019: 147–56
  • The N3XT Approach to Energy-Efficient Abundant-Data Computing PROCEEDINGS OF THE IEEE Aly, M., Wu, T. F., Bartolo, A., Malviya, Y. H., Hwang, W., Hills, G., Markov, I., Wootters, M., Shulaker, M. M., Wong, H., Mitra, S. 2019; 107 (1): 19–48
  • Linear-time list recovery of high-rate expander codes Hemenwaya, B., Wootters, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2018: 202–18
  • Fast Blind MIMO Decoding through Vertex Hopping Perlstein, J., Dean, T., Wootters, M., Goldsmith, A., Matthews, M. B. IEEE. 2018: 148–49
  • Average-radius list-recoverability of random linear codes Rudra, A., Wootters, M., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 644–62
  • On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing Inan, H. A., Kairouz, P., Wootters, M., Ozgur, A., IEEE IEEE. 2018: 188–95
  • On taking advantage of multiple requests in error correcting codes Ramakrishnan, P., Wootters, M., IEEE IEEE. 2018: 1340–44
  • Load-Balanced Fractional Repetition Codes Porter, A., Silas, S., Wootters, M., IEEE IEEE. 2018: 2072–76
  • Improved decoding of Folded Reed-Solomon and Multiplicity Codes Kopparty, S., Ron-Zewi, N., Saraf, S., Wootters, M., Thorup, M. IEEE COMPUTER SOC. 2018: 212–23
  • Repairing Reed-Solomon Codes Guruswami, V., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2017: 5684–98
  • Exponential Decay of Reconstruction Error From Binary Measurements of Sparse Signals IEEE TRANSACTIONS ON INFORMATION THEORY Baraniuk, R. G., Foucart, S., Needell, D., Plan, Y., Wootters, M. 2017; 63 (6): 3368–85
  • De-biasing low-rank projection for matrix completion Foucart, S., Needell, D., Plan, Y., Wootters, M., Lu, Y. M., VanDeVille, D., Papadakis, M. SPIE-INT SOC OPTICAL ENGINEERING. 2017

    View details for DOI 10.1117/12.2275004

    View details for Web of Science ID 000416302900033

  • Repairing multiple failures for scalar MDS codes Bartan, B., Wootters, M., IEEE IEEE. 2017: 1145–52
  • Blind Joint MIMO Channel Estimation and Decoding Dean, T., Wootters, M., Goldsmith, A., IEEE IEEE. 2017
  • Limitations of Piggybacking Codes with Low Substriping Hulett, R., Wootters, M., IEEE IEEE. 2017: 1131–38
  • SPECIAL ISSUE: APPROX-RANDOM 2015 Foreword THEORY OF COMPUTING Megow, N., Wootters, M. 2016; 12
  • Local correctability of expander codes Hemenway, B., Ostrovsky, R., Wootters, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2015: 178–90
  • Linear-Time List Recovery of High-Rate Expander Codes Hemenway, B., Wootters, M., Halldorsson, M. M., Iwama, K., Kobayashi, N., Speckmann, B. SPRINGER-VERLAG BERLIN. 2015: 701–12
  • Configuration spaces of convex and embedded polygons in the plane GEOMETRIAE DEDICATA Shimamoto, D., Wootters, M. 2014; 172 (1): 121–34
  • 1-Bit matrix completion INFORMATION AND INFERENCE-A JOURNAL OF THE IMA Davenport, M. A., Plan, Y., van den Berg, E., Wootters, M. 2014; 3 (3): 189–223
  • Optimal entanglement-assisted one-shot classical communication PHYSICAL REVIEW A Hemenway, B., Miller, C. A., Shi, Y., Wootters, M. 2013; 87 (6)
  • Lower Bounds for Quantized Matrix Completion Wootters, M., Plan, Y., Davenport, M. A., van den Berg, E., IEEE IEEE. 2013: 296-+
  • Local Correctability of Expander Codes Hemenway, B., Ostrovsky, R., Wootters, M., Fomin, F. V., Freivalds, R., Kwiatkowska, M., Peleg, D. SPRINGER-VERLAG BERLIN. 2013: 540–51
  • REUSABLE LOW-ERROR COMPRESSIVE SAMPLING SCHEMES THROUGH PRIVACY Gilbert, A. C., Hemenway, B., Strauss, M. J., Woodruff, D. P., Wootters, M., IEEE IEEE. 2012: 536–39