Research/Publications
Books
Numerical Linear Algebra with Julia
Eric Darve and Mary Wootters
Available from SIAM.
Algorithms for Toddlers
Aviad Rubinstein and Mary Wootters
Available here.
Dramatic reading here.
Yes, this is for real; it's Aviad's fault :)
Preprints
Improved Trade-offs Between Amortization and Bandwidth for Linear HSS
Keller Blackwell and Mary Wootters
[arXiv]
Efficient List-Decoding of Polynomial Ideal Codes with Optimal List Size
Noga Ron-Zewi, S. Venkitesh, and Mary Wootters
[arXiv]
Conference and Workshop Publications
2024.
Improved Constructions of Robust Gray Codes
Dorsa Fathollahi and Mary Wootters
[arXiv]
ISIT 2024.
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications
Keller Blackwell and Mary Wootters
[arXiv]
ITCS 2024.
Viderman's algorithm for quantum LDPC codes
Anirudh Krishna, Inbal Livni Navon, Mary Wootters
[arXiv]
SODA 2024 and QIP 2024.
2023.
Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums
Roni Con, Noah Shutty, Itzhak Tamo and Mary Wootters
ISIT 2023
Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence
Margalit Glasgow, Colin Wei, Mary Wootters, Tengyu Ma
[ arXiv ]
ICLR 2023 (poster)
2022.
Efficient Near-Optimal Codes for General Repeat Channels
Francisco Pernice, Ray Li, and Mary Wootters
[ arXiv ]
ISIT 2022.
Improved Batch Code Lower Bounds
Ray Li and Mary Wootters
[ arXiv ]
ISIT 2022.
Lower bounds on the redundancy of linear codes with multiple disjoint repair groups
Sankeerth Rao Karingula, Alexander Vardy, and Mary Wootters
ISIT 2022.
High-Probability List-Recovery, and Applications to Heavy Hitters
Dean Doron and Mary Wootters
[ ECCC ]
ICALP 2022.
Asynchronous Distributed Optimization with Randomized Delays
Margalit Glasgow and Mary Wootters
[ arXiv ]
AISTATS 2022.
Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data
Noah Shutty and Mary Wootters
ITCS 2022.
On the download rate of homomorphic secret sharing
Ingerid Fosli, Yuval Ishai, Victor Kolobov, and Mary Wootters
[ arXiv ]
ITCS 2022.
2021.
Improved List-Decodability of Reed-Solomon Codes via Tree Packings
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters
[ ECCC ]
FOCS 2021.
On Coding for an Abstracted Nanopore Channel for DNA Storage
Reyna Hulett, Shubham Chandak, Mary Wootters
[ arXiv ]
ISIT 2021.
On Greedy Approaches to Hierarchical Aggregation
Alexandra Porter and Mary Wootters
[ arXiv ]
ISIT 2021.
Wedge-Lifted Codes
Jabari Hastings, Amy Kanne, Ray Li, and Mary Wootters
[ arXiv ]
ISIT 2021.
Approximate Gradient Coding with Optimal Decoding
Margalit Glasgow and Mary Wootters
[ arXiv ]
ISIT 2021.
Sharp Threshold Rates for Random Codes
Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters
[ arXiv ]
ITCS 2021
2020.
LDPC Codes Achieve List-Decoding Capacity
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters
[ arXiv ]
FOCS 2020 (Invited to the FOCS 2020 Special Issue of SICOMP)
Reliable Computation by Formulas of Noisy AND Gates and Noiseless XOR Gates, with Applications to Quantum Mechanics
Noah Shutty, Mary Wootters and Patrick Hayden
[ arXiv ]
FOCS 2020 and QIP 2021
Bounds for list-decoding and list-recovery of random linear codes
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
[ arXiv ]
RANDOM 2020
Sparse Recovery for Orthogonal Polynomial Transformations
Anna Gilbert, Albert Gu, Christopher Re, Atri Rudra, Mary Wootters
[ arXiv ]
ICALP 2020
Linear-Time Erasure List-Decoding of Expander Codes
Noga Ron-Zewi, Mary Wootters, and Gilles Zémor
ISIT 2020
Overcoming high nanopore basecaller error rates for DNA storage via basecaller-decoder integration and convolutional codes
Shubham Chandak, Joachim Neu, Kedar Tatwawadi, Jay Mardia, Billy Lau, Matthew Kubit, Reyna Hulett, Peter Griffin, Mary Wootters, Tsachy Weissman, Hanlee Ji
[ bioRXiv ]
ICASSP 2020
2019.
Improved read/write cost tradeoff in DNA-based data storage using LDPC codes
Shubham Chandak, Kedar Tatwawadi, Billy Lau, Matt Kubit, Jay Mardia, Joachim Neu, Peter Griffin, Mary Wootters, Tsachy Weissman, Hanlee Ji
Allerton 2019
[ bioRxiv ]
Unconstraining graph-constrained group testing
Bruce Spang and Mary Wootters
RANDOM 2019
[ arXiv ]
Lifted Multiplicity Codes
Ray Li and Mary Wootters
RANDOM 2019
[ arXiv ]
Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning
Rawad Bitar, Mary Wootters and Salim El Rouayheb
ITW 2019
[ arXiv ]
Embedded Index Coding
Alexandra Porter and Mary Wootters
ITW 2019
[ arXiv ]
Large blocklength LDPC codes for Illumina sequencing-based DNA storage
Shubham Chandak, Kedar Tatwawadi, Billy Lau, Matthew Kubit, Jay Mardia, Joachim Neu, Hanlee Ji, Tsachy Weissman, Peter Griffin, Mary Wootters
ISMB/ECCB 2019
A Data-Compressive Wired-OR Readout for Massively Parallel Neural Recording
D. Muratore, P. Tandon, M. Wootters, E.J. Chichilnisky, S. Mitra and B. Murmann
IEEE International Symposium on Circuits and Systems, 2019
A 43pJ/cycle Non-volatile Microcontroller with 4.7µs Shutdown/Wake-up integrating 2.3 bits-per-cell Resistive RAM and Resilience Techniques
T. Wu, B. Le, R. Radway, A. Bartolo, W. Hwang, S. Jeong, H. Li, P. Tandon, E. Vianello, P. Vivet, E. Nowak, M. Wootters, H.-S.P. Wong, M. Aly, E. Beigne and S. Mitra
IEEE Intl. Solid-State Circuits Conf. 2019
2018.
On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
Huseyin A. Inan, Peter Kairouz, Mary Wootters, Ayfer Ozgur
Allerton 2018.
[ arXiv ]
Improved Decoding of Folded Reed-Solomon Codes and Multiplicity Codes
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf and Mary Wootters
FOCS 2018.
Improved list-decodability of random linear binary codes
Ray Li and Mary Wootters.
RANDOM 2018.
[ arXiv ]
On taking advantage of multiple requests in error correcting codes
Prasanna Ramakrishnan and Mary Wootters.
ISIT 2018.
[ arXiv ]
Load-balanced Fractional Repetition Codes
Alexandra Porter, Shashwat Silas, and Mary Wootters.
ISIT 2018.
[ arXiv ]
Average-radius list-recovery of random linear codes
Atri Rudra and Mary Wootters.
SODA 2018.
2017.
Blind Joint MIMO Channel Estimation and Decoding
Thomas Dean, Mary Wootters and Andrea Goldsmith
Globecom 2017.
Can we access a database both locally and privately?
Elette Boyle, Yuval Ishai, Rafael Pass and Mary Wootters
TCC 2017.
[ PDF ]
Repairing Multiple Failures for Scalar MDS Codes
Burak Bartan and Mary Wootters
Allerton 2017.
[ arXiv ]
Limitations on the Achievable Repair Bandwidth of Piggybacking Codes with Low Substriping
Reyna Hulett and Mary Wootters
Allerton 2017.
[ arXiv ]
Local list-recovery of high-rate tensor codes and applications.
Brett Hemenway, Noga Ron-Zewi and Mary Wootters
FOCS 2017. Invited to the special issue of SIAM Journal of Computing for FOCS 2017.
[ arXiv ]
Locality via Partially Lifted Codes.
S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters.
RANDOM 2017.
[ arXiv ]
2016.
Repairing Reed-Solomon Codes.
Venkatesan Guruswami and Mary Wootters.
STOC 2016.
[ arXiv ]
Strategic Classification.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, Mary Wootters.
ITCS 2016.
[ arXiv ]
2015.
Linear-time list recovery of high-rate expander codes.
Brett Hemenway and Mary Wootters.
ICALP 2015, to appear.
Invited to ICALP 2015's special issue of Information and Computation.
[ arXiv ]
It'll probably work out: improved list-decoding through random operations.
Atri Rudra and Mary Wootters.
ITCS 2015.
[ arXiv ]
2014.
Fast matrix completion without the condition number.
Moritz Hardt and Mary Wootters
COLT 2014.
Every list-decodable code for high noise has abundant near-optimal rate puncturings.
Atri Rudra and Mary Wootters
STOC 2014.
[ arXiv ]
New constructions of RIP matrices with fast multiplication and fewer rows.
Jelani Nelson, Eric Price, and Mary Wootters.
SODA 2014.
2013.
Accurate Decoding of Pooled Sequenced Data Using Compressed Sensing.
Denisa Duma, Mary Wootters, Anna Gilbert, Hung Q. Ngo, Atri Rudra, Matthew Alpert, Timothy J. Close, Gianfranco Ciardo and Stefano Lonardi.
WABI 2013.
[ arXiv ]
Local correctibility of expander codes.
Brett Hemenway, Rafail Ostrovsky, and Mary Wootters.
ICALP 2013.
Invited to ICALP 2013's special issue of Information and Computation.
[ arXiv ]
One-Bit Matrix Completion.
Mark Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters.
SPARS 2013.
Lower Bounds for Quantized Matrix Completion.
Mary Wootters, Yaniv Plan, Mark Davenport, and Ewout van den Berg.
ISIT 2013.
On the list decodability of random linear codes with large error rates.
Mary Wootters.
STOC 2013.
[ arXiv ]
2012.
Reusable low-error compressive sampling schemes through privacy.
Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, and Mary Wootters.
SSP 2012.
[ IEEE ]
Recovering simple signals.
Anna C. Gilbert, Brett Hemenway, Atri Rudra, Martin J. Strauss, and Mary Wootters.
ITA 2012.
[ IEEE ]
2011.
Public Key Locally Decodable Codes with Short Keys.
Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, and Mary Wootters.
RANDOM 2011.
[ ECCC ]
Journal Publications
Improved List-Decodability of Reed-Solomon Codes via Tree Packings
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters
[ ECCC ]
SICOMP, 2023
Improved Decoding of Folded Reed-Solomon Codes and Multiplicity Codes
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf and Mary Wootters
SICOMP, 2023, to appear.
Bounds for list-decoding and list-recovery of random linear codes
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
IEEE Transactions on Information Theory, 2021
[ IEEE ]
Threshold Rates for Properties of Random Codes
Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters
IEEE Transactions on Information Theory, 2021
[ IEEE ]
LDPC Codes Achieve List-Decoding Capacity
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters
FOCS 2020 Special Issue of SICOMP, to appear.
[ arXiv ]
Approximate Gradient Coding with Optimal Decoding
Margalit Glasgow and Mary Wootters
JSAIT Special Issue on Coded Computation, to appear, 2021.
Linear-Time Erasure List-Decoding of Expander Codes
Noga Ron-Zewi, Mary Wootters, and Gilles Zémor
IEEE Transactions on Information Theory, 2021.
Superbridge and bridge indices for knots
Colin Adams, Nikhil Agarwal, Rachel Allen, Tirasan Khandhawit, Alex Simons, Rebecca Winarski, Mary Wootters
Journal of Knot Theory and its Ramifications, 2021
Note: I worked on this at the SMALL REU at Williams College in 2007 as an undergrad -- finally published 14 years later! :D
[ JKTR ]
Illusion of large on-chip memory by networked computing chips for neural network inference
Robert M. Radway, Andrew Bartolo, Paul C. Jolly, Zainab F. Khan, Binh Q. Le, Pulkit Tandon, Tony F. Wu, Yunfeng Xin, Elisa Vianello, Pascal Vivet, Etienne Nowak, H.-S. Philip Wong, Mohamed M. Sabry Aly, Edith Beigne, Mary Wootters, Subhasish Mitra
Nature Electronics, 2021
Hermitian-Lifted Codes
Hiram H. López, Beth Malmskog, Gretchen L Matthews, Fernando Piñero-González, Mary Wootters
Designs, Codes, and Cryptography, 2021.
Improved list-decodability of random linear binary codes
Ray Li and Mary Wootters.
IEEE Transactions on Information Theory, 2021.
Embedded Index Coding
Alexandra Porter and Mary Wootters
IEEE Transactions on Information Theory, 2020.
Weighted matrix completion from non-random, non-uniform sampling patterns
Simon Foucart, Deanna Needell, Reese Pathak, Yaniv Plan, Mary Wootters
IEEE Transactions on Information Theory, 2021.
Lifted Multiplicity Codes
Ray Li and Mary Wootters
IEEE Transactions on Information Theory, 2021.
[ IEEE ]
Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning
Rawad Bitar, Mary Wootters and Salim El Rouayheb
IEEE Journal on Selected Applications in Information Theory, Special Issue on Deep Learning: Mathematical Foundations and Applications to Information Science, 2020.
[ IEEE ]
Local list-recovery of high-rate tensor codes and applications.
Brett Hemenway, Noga Ron-Zewi and Mary Wootters
SIAM Journal on Computing (Special issue for FOCS2017), 2019.
[ SIAM ]
A Data-Compressive Wired-OR Readout for Massively Parallel Neural Recording
D. Muratore, P. Tandon, M. Wootters, E.J. Chichilnisky, S. Mitra and B. Murmann
IEEE Transactions on Biomedical Circuits and Systems, 2019
[ IEEE ]
Fast, Blind MIMO Decoding Through Vertex-Hopping
Tom Dean, Jonathan Perlstein, Mary Wootters and Andrea Goldsmith
IEEE Transactions on Wireless Communications (2019)
[ IEEE ]
On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
Huseyin A. Inan, Peter Kairouz, Mary Wootters, Ayfer Ozgur
IEEE Transactions on Information Theory (2019)
[ IEEE ]
Resistive RAM Endurance: Array-Level Characterization and Correction Techniques Targeting Deep Learning Applications
Alessandro Grossi, Elisa Vianello, Mohamed M. Sabry, Marios Barlas, Laurent Grenouillet, Jean Coignus, Edith Beigne, Tony Wu, Binh Q. Le, Mary K. Wootters, Cristian Zambelli, Etienne Nowak, Subhasish Mitra
IEEE Transactions on Electron Devices (2019)
[IEEE]
The N3XT Approach to Energy-Efficient Abundant-Data Computing.
Mohamed M. Sabry Aly, Tony F. Wu , Andrew Bartolo, Yash H. Malviya, William Hwang, Gage Hills , Igor Markov, Mary Wootters, Max M. Shulaker, H.-S. Philip Wong, and Subhasish Mitra
Proceedings of the IEEE (2019)
[IEEE]
Linear-Time List-Recovery of High-Rate Expander Codes
Brett Hemenway and Mary Wootters
Information and Computation, 2018.
[ Information and Computation ]
Blind Joint MIMO Channel Estimation and Decoding
Tom Dean, Mary Wootters and Andrea Goldsmith
IEEE Transactions on Information Theory (2018)
Repairing Multiple Failures for Scalar MDS Codes
Jay Mardia, Burak Bartan and Mary Wootters
IEEE Transactions on Information Theory (2018)
One-bit compressed sensing of dictionary-sparse signals.
Richard Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, Mary Wootters.
Information and Inference (2018).
[ arXiv ][ Information and Inference ]
Repairing Reed-Solomon Codes.
Venkatesan Guruswami and Mary Wootters.
IEEE Transactions on Information Theory (2017).
Exponential decay of reconstruction error from binary measurements of sparse signals.
Richard Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, Mary Wootters.
IEEE Transactions on Information Theory (2017).
Local Correctibility of Expander Codes.
Brett Hemenway, Rafail Ostrovsky, and Mary Wootters.
Information and Computation (2015).
ICALP 2013 special issue.
[ arXiv ][ journal version ]
One-Bit Matrix Completion.
Mark A. Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters.
Information and Inference (2014).
[ arXiv ][ journal version ]
On optimal entanglement assisted one-shot classical communication.
Brett Hemenway, Carl A. Miller, Yaoyun Shi, and Mary Wootters.
Physical Review A, 87, 062301 (2013).
[ arXiv ][ journal version ]
Other Manuscripts and Notes
A note on the permuted puzzles toy conjecture
Keller Blackwell and Mary Wootters, 2021
[ arXiv ]
Linear codes with disjoint repair groups.
(A short argument that the codimension of any linear code of length n which satisfies a "2-disjoint repair group" property is Omega(\sqrt{n}))
Mary Wootters, 2016.
[ PDF ]
Biological screens from linear codes: theory and tools.
Yaniv Erlich, Anna Gilbert, Hung Ngo, Atri Rudra, Nicolas Thierry-Mieg, Mary Wootters, Dina Zielinski, Or Zuk.
[ biorXiv ]
Thesis
Any errors in this dissertation are probably fixable: topics in probability and error correcting codes.
Mary Wootters, 2014.
Recipient of the 2014 Sumner B. Myers thesis prize (UMich Math Dept.)
Recipient of the 2015 EATCS Distinguished Dissertation award
[ PDF ]
An algebraic geometer once told me that my research seemed "applied but respectable."