Mary Wootters

All Publications

• Optimization by decoded quantum interferometry. Nature Jordan, S. P., Shutty, N., Wootters, M., Zalcman, A., Schmidhuber, A., King, R., Isakov, S. V., Khattar, T., Babbush, R. 2025; 646 (8086): 831-836

  Abstract

  Achieving superpolynomial speed-ups for optimization has long been a central goal for quantum algorithms1. Here we introduce decoded quantum interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. When approximating optimal polynomial fits over finite fields, DQI achieves a superpolynomial speed-up over known classical algorithms. The speed-up arises because the algebraic structure of the problem is reflected in the decoding problem, which can be solved efficiently. We then investigate whether this approach can achieve a speed-up for optimization problems that lack an algebraic structure but have sparse clauses. These problems reduce to decoding low-density parity-check codes, for which powerful decoders are known2,3. To test this, we construct a max-XORSAT instance for which DQI finds an approximate optimum substantially faster than general-purpose classical heuristics, such as simulated annealing. Although a tailored classical solver can outperform DQI on this instance, our results establish that combining quantum Fourier transforms with powerful decoding primitives provides a promising new path towards quantum speed-ups for hard optimization problems.

  View details for DOI 10.1038/s41586-025-09527-5

  View details for PubMedID 41125774

  View details for PubMedCentralID PMC12545177

• Robust Gray Codes Approaching the Optimal Rate IEEE TRANSACTIONS ON INFORMATION THEORY Con, R., Fathollahi, D., Gabrys, R., Wootters, M., Yaakobi, E. 2025; 71 (3): 1647-1665

  View details for DOI 10.1109/TIT.2024.3522986

  View details for Web of Science ID 001468449300033

• List-Decoding Capacity Implies Capacity on the <i>q</i>-ary Symmetric Channel Pernice, F., Sprumont, O., Wootters, M. edited by Koucky, M., Bansal, N. ASSOC COMPUTING MACHINERY. 2025: 855-866

  View details for DOI 10.1145/3717823.3718206

  View details for Web of Science ID 001595410700082

• Repairing Reed-Solomon Codes Over Prime Fields via Exponential Sums IEEE TRANSACTIONS ON INFORMATION THEORY Con, R., Shutty, N., Tamo, I., Wootters, M. 2024; 70 (12): 8587-8594

  View details for DOI 10.1109/TIT.2024.3449041

  View details for Web of Science ID 001400994700012

• 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

• Improved Construction of Robust Gray Codes Fathollahi, D., Wootters, M., IEEE IEEE. 2024: 37-42

  View details for DOI 10.1109/ISIT57864.2024.10619585

  View details for Web of Science ID 001304426900008

• When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? Doron, D., Mosheiff, J., Wootters, M. edited by Kumar, A., Ron-Zewi, N. SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2024

  View details for DOI 10.4230/LIPIcs.APPROX/RANDOM.2024.53

  View details for Web of Science ID 001545634500053

• A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications Blackwell, K., Wootters, M. edited by Guruswami SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2024

  View details for DOI 10.4230/LIPIcs.ITCS.2024.16

  View details for Web of Science ID 001300389400016

• LOW-DENSITY PARITY-CHECK CODES ACHIEVE LIST-DECODING CAPACITY SIAM JOURNAL ON COMPUTING Mosheiff, J., Resch, N., Ron-zewi, N., Silas, S., Wootters, M. 2024; 53 (6): 38-73

  View details for DOI 10.1137/20M1365934

  View details for Web of Science ID 001406377200003

• Viderman's algorithm for quantum LDPC codes Krishna, A., Navon, I., Wootters, M. edited by Woodruff, D. P. SIAM. 2024: 2481-2507

  View details for Web of Science ID 001267398705004

• 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

  View details for DOI 10.1109/TIT.2021.3127126

  View details for Web of Science ID 000745528100017

• 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

  View details for DOI 10.1109/TIT.2021.3123497

  View details for Web of Science ID 000745528100016

• Asynchronous Distributed Optimization with Stochastic Delays Glasgow, M., Wootters, M. edited by Camps-Valls, G., Ruiz, F. J., Valera JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2022

  View details for Web of Science ID 000841852303028

• 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

  View details for DOI 10.1109/FOCS52979.2021.00074

  View details for Web of Science ID 000802209600064

• 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

  View details for DOI 10.1109/TIT.2021.3086805

  View details for Web of Science ID 000690440100015

• Improved List-Decodability of Random Linear Binary Codes Li, R., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2021: 1522–36

  View details for DOI 10.1109/TIT.2020.3041650

  View details for Web of Science ID 000619322300009

• Embedded Index Coding Porter, A., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2021: 1461–77

  View details for DOI 10.1109/TIT.2020.3043767

  View details for Web of Science ID 000619322300006

• Lifted Multiplicity Codes and the Disjoint Repair Group Property IEEE TRANSACTIONS ON INFORMATION THEORY Li, R., Wootters, M. 2021; 67 (2): 716–25

  View details for DOI 10.1109/TIT.2020.3034962

  View details for Web of Science ID 000612137400004

• 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)

  View details for DOI 10.1142/S0218216521500097

  View details for Web of Science ID 000641745600003

• 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

  View details for DOI 10.1109/TIT.2020.3039308

  View details for Web of Science ID 000613330500001

• Hermitian-lifted codes DESIGNS CODES AND CRYPTOGRAPHY Lopez, H. H., Malmskog, B., Matthews, G. L., Pinero-Gonzalez, F., Wootters, M. 2021

  View details for DOI 10.1007/s10623-020-00836-6

  View details for Web of Science ID 000607364600001

• 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

  View details for DOI 10.1038/s41928-020-00515-3

  View details for Web of Science ID 000607033100001

• Wedge-Lifted Codes Hastings, J., Kanne, A., Li, R., Wootters, M., IEEE IEEE. 2021: 2990-2995

  View details for DOI 10.1109/ISIT45174.2021.9518246

  View details for Web of Science ID 000701502203015

• Approximate Gradient Coding with Optimal Decoding Glasgow, M., Wootters, M., IEEE IEEE. 2021: 2280-2285

  View details for DOI 10.1109/ISIT45174.2021.9517990

  View details for Web of Science ID 000701502202063

• On Greedy Approaches to Hierarchical Aggregation Porter, A., Wootters, M., IEEE IEEE. 2021: 2649-2654

  View details for DOI 10.1109/ISIT45174.2021.9517814

  View details for Web of Science ID 000701502202125

• On Coding for an Abstracted Nanopore Channel for DNA Storage Hulett, R., Chandak, S., Wootters, M., IEEE IEEE. 2021: 2465-2470

  View details for DOI 10.1109/ISIT45174.2021.9518236

  View details for Web of Science ID 000701502202094

• 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

  View details for Web of Science ID 000714963400065

• LDPC Codes Achieve List Decoding Capacity Mosheiff, J., Resch, N., Ron-Zewi, N., Silas, S., Wootters, M., IEEE IEEE. 2020: 458-469

  View details for DOI 10.1109/FOCS46700.2020.00050

  View details for Web of Science ID 000652333400042

• 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

  View details for DOI 10.1109/FOCS46700.2020.00028

  View details for Web of Science ID 000652333400020

• 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

  View details for Web of Science ID 000615970409020

• 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

  View details for DOI 10.1109/TIT.2019.2902397

  View details for Web of Science ID 000481981000022

• 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

  View details for DOI 10.1109/TWC.2019.2917002

  View details for Web of Science ID 000475339700024

• Repairing Multiple Failures for Scalar MDS Codes Mardia, J., Bartan, B., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2019: 2661–72

  View details for DOI 10.1109/TIT.2018.2876542

  View details for Web of Science ID 000466029900003

• 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

  View details for DOI 10.1109/TIT.2018.2878016

  View details for Web of Science ID 000461840600035

• 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

  View details for DOI 10.1109/TED.2019.2894387

  View details for Web of Science ID 000460970400022

• 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. edited by Fujino, L. C., Anderson, J. H., Belostotski, L., Dunwell, D., Gaudet, Gulak, G., Haslett, J. W., Halupka, D., Smith, K. C. IEEE. 2019: 226-+

  View details for Web of Science ID 000463153600071

• 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

  View details for Web of Science ID 000483076401065

• Stochastic Gradient Coding for Flexible Straggler Mitigation in Distributed Learning Bitar, R., Wootters, M., El Rouayheb, S., IEEE IEEE. 2019: 394–98

  View details for Web of Science ID 000540384500080

• Embedded Index Coding Porter, A., Wootters, M., IEEE IEEE. 2019: 354–58

  View details for Web of Science ID 000540384500072

• 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

  View details for Web of Science ID 000535355700022

• 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

  View details for DOI 10.1109/JPROC.2018.2882603

  View details for Web of Science ID 000454770800004

• Linear-time list recovery of high-rate expander codes Hemenwaya, B., Wootters, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2018: 202–18

  View details for DOI 10.1016/j.ic.2018.02.004

  View details for Web of Science ID 000436490400004

• Fast Blind MIMO Decoding through Vertex Hopping Perlstein, J., Dean, T., Wootters, M., Goldsmith, A. edited by Matthews, M. B. IEEE. 2018: 148–49

  View details for Web of Science ID 000467845100025

• Average-radius list-recoverability of random linear codes Rudra, A., Wootters, M., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 644–62

  View details for Web of Science ID 000483921200043

• 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

  View details for Web of Science ID 000461021200028

• On taking advantage of multiple requests in error correcting codes Ramakrishnan, P., Wootters, M., IEEE IEEE. 2018: 1340–44

  View details for Web of Science ID 000448139300269

• Load-Balanced Fractional Repetition Codes Porter, A., Silas, S., Wootters, M., IEEE IEEE. 2018: 2072–76

  View details for Web of Science ID 000448139300416

• Improved decoding of Folded Reed-Solomon and Multiplicity Codes Kopparty, S., Ron-Zewi, N., Saraf, S., Wootters, M. edited by Thorup, M. IEEE COMPUTER SOC. 2018: 212–23

  View details for DOI 10.1109/FOCS.2018.00029

  View details for Web of Science ID 000455014500020

• Repairing Reed-Solomon Codes Guruswami, V., Wootters, M. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. 2017: 5684–98

  View details for DOI 10.1109/TIT.2017.2702660

  View details for Web of Science ID 000411016000017

• 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

  View details for DOI 10.1109/TIT.2017.2688381

  View details for Web of Science ID 000402058900003

• De-biasing low-rank projection for matrix completion Foucart, S., Needell, D., Plan, Y., Wootters, M. edited by 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

  View details for Web of Science ID 000428047800156

• Blind Joint MIMO Channel Estimation and Decoding Dean, T., Wootters, M., Goldsmith, A., IEEE IEEE. 2017

  View details for Web of Science ID 000428054301082

• Limitations of Piggybacking Codes with Low Substriping Hulett, R., Wootters, M., IEEE IEEE. 2017: 1131–38

  View details for Web of Science ID 000428047800154

• SPECIAL ISSUE: APPROX-RANDOM 2015 Foreword THEORY OF COMPUTING Megow, N., Wootters, M. 2016; 12

  View details for DOI 10.4086/toc.2016.v012a013

  View details for Web of Science ID 000433607300004

• Local correctability of expander codes Hemenway, B., Ostrovsky, R., Wootters, M. ACADEMIC PRESS INC ELSEVIER SCIENCE. 2015: 178–90

  View details for DOI 10.1016/j.ic.2014.12.013

  View details for Web of Science ID 000355665500012

• Linear-Time List Recovery of High-Rate Expander Codes Hemenway, B., Wootters, M. edited by Halldorsson, M. M., Iwama, K., Kobayashi, N., Speckmann, B. SPRINGER-VERLAG BERLIN. 2015: 701–12

  View details for DOI 10.1007/978-3-662-47672-7_57

  View details for Web of Science ID 000364317700057

• Configuration spaces of convex and embedded polygons in the plane GEOMETRIAE DEDICATA Shimamoto, D., Wootters, M. 2014; 172 (1): 121–34

  View details for DOI 10.1007/s10711-013-9910-x

  View details for Web of Science ID 000341500400005

• 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

  View details for DOI 10.1093/imaiai/iau006

  View details for Web of Science ID 000218926400001

• Optimal entanglement-assisted one-shot classical communication PHYSICAL REVIEW A Hemenway, B., Miller, C. A., Shi, Y., Wootters, M. 2013; 87 (6)

  View details for DOI 10.1103/PhysRevA.87.062301

  View details for Web of Science ID 000319909500001

• Lower Bounds for Quantized Matrix Completion Wootters, M., Plan, Y., Davenport, M. A., van den Berg, E., IEEE IEEE. 2013: 296-+

  View details for Web of Science ID 000348913400060

• Local Correctability of Expander Codes Hemenway, B., Ostrovsky, R., Wootters, M. edited by Fomin, F. V., Freivalds, R., Kwiatkowska, M., Peleg, D. SPRINGER-VERLAG BERLIN. 2013: 540–51

  View details for Web of Science ID 000342686600046

• 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

  View details for Web of Science ID 000309943200135