Publications
- 2024 Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall. A Meta-Complexity Characterization of Quantum Cryptography https://eccc.weizmann.ac.il/report/2024/156/download
- 2024 (Crypto 2024) Kai-Min Chuang, Eli Goldin, Matthew Gray. On Central Primitives for Quantum Cryptography with Classical Communication https://arxiv.org/abs/2402.17715
- 2023 Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, and Angelos Pelecanos. On the Computational Hardness of Quantum One-Wayness https://arxiv.org/abs/2312.08363
- 2023 (CCC 2024) Noel Arteche, Gaia Carenini, and Matthew Gray. On the Quantum Automatability of Propositional Proof Systems https://eccc.weizmann.ac.il/report/2024/029/
- 2021 Matthew Gray. Large Scale Secure Sortition https://equalitybylot.com/2021/12/05/
- 2019 Matthew Gray. “LOADS of Space”, Local Order Agnosticism and Bit Flip Efficient Data Structure Codes https://arxiv.org/abs/1908.05415
- 2018 (IEEE NVMSA) Daniel Bittman, Matthew Gray, Justin Raizes, Sinjoni Mukhopadhyay, Matt Bryson, Peter Alvaro, Darrell Long, and Ethan L Miller. Designing Data Structures to Minimize Bit Flips On NVM.
Research Interests
My primary area of interest is the intersection of Quantum Computing, Cryptography, and Meta Complexity.
In particular I am interested in the connections between the hardness of quantum meta complexity problems and the existence of quantum crypto primitives. I want to formalize a notion of Quantum Algorithmica and Quantum Impagliazzo worlds. I want to understand the connections between post quantum crypto and proof complexity. And I want to understand the ultimate limits of classical computation on ideal quantum computers.
I am also secondarily interested in several questions in Philosophy. My main work in this area is a personalist Bayesian resolution to Hume's problem of Induction, that I really hope to publish this year.
I am also interested in historical cryptography and am working on decrypting diplomatic letters from Italian city states in the fifteenth through seventeenth centuries.
Work Experience
Renton Technical College: Adjunct Faculty
Renton WA: Teaching Web Development. Bringing in Guest Speakers from across Industry and Academia to expose Students to career paths and show them how to pursue those paths. And helping redesign the AAS curriculum to focus on web as a more accessible entry point into the Industry.
Microsoft: Software Engineering
Oslo Norway: Working with a large team on React Native components used across Office 365 with a focus on iOS and Android development. My most notable project was implementing the accessibility API for React Native macOS.
Storage Systems Research Center: Research Assistant
Santa Cruz, CA: Worked with graduate students and professors on research into storage and security. Notable projects include fooling facial recognition, using Fourier Analysis to investigate MD5, and Designing Data Structures to Minimize Bit Flips on NVM
Santa Cruz, CA: Worked with graduate students and professors on research into storage and security. Notable projects include fooling facial recognition, using Fourier Analysis to investigate MD5, and Designing Data Structures to Minimize...
UC Santa Cruz: Teaching Assistant
Santa Cruz, CA: TA'ed several algorithms, data structures, and programming courses. Developed and ran two student lead courses on the Mathematics of Communication (CS42A). Topics I have taught include Number Theoretic Cryptography, Information Theoretic Compression, Error Correcting Codes, Stack Frames, and Memory Management
Santa Cruz, CA: TA'ed several algorithms, data structures, and programming courses. Developed and ran two student lead courses on the Mathematics of Communication (CS42A). Topics I have taught include Number Theoretic Cryptography, Information Theoretic Compression, Error Correcting...
Sandia National Labs: Research and Developement Intern
Livermore, CA: Worked on Cyber Security Research, with a focus on on write efficient databases, applied cryptography, secure multi-party computation, and passive data collection. Worked on a large C++ codebase.
Last Minute Gear: Web Developer
San Francisco, CA: Maintained and expanded a full stack web app and it's associated testing suite. Regular use of Ruby, Javascript, HTML, CSS, Heroku, git etc. Occasionally did odd jobs as needed since I was half of a two man start up.
General Assembly: Teaching Assistant
San Francisco, CA: Explained difficult Javascript and Ruby on Rails concepts. Drew out student's knowl- edge by listening and asking questions. Guided students through troubleshooting so they could use similar techniques in the future.
I am
I am made of stories. Told to myself, by myself, about myself. A paradox perhaps, but also undoubtably the truth. I wear them like armor in a universe that I can only build out of stories but which is ultimately made out of details. Stories are the death of detail and details the death of stories. Let me be a story of infinite omission, rather than a lie with an intent to deceive. Let my armor be made of reality, though it be pruned to near non existence.
I am a cartoon character drawn with lines to separate me from infinity. I am also the cartoon world I navigate. The only lines separating the pen I write with from the air it moves through exist in me, and us, for now. I paint mountains and my mountains are me.
I am a fuzzy collection of quantum amplitudes representing a trillion micro-organisms working together for their greater good in a world, the true world, without color, without smells, without stories. Only details, only infinite truth, austere but filled with overwhelming, fractal multiplicity.
I am not alone. I am made of stories, told by us, about everything. I am made of mathematics, star stuff, and recipes for cake discovered or invented by you, by us, by we. I am not alone, and neither are you.
I am made of hugs, from my parents, friends, family. I am made of my wife's fingers, playing with my hair. I am made of the simple syrup and orange juice which were all I could keep down in the illness that left me floor ridden, crawling across Yosemite cabin carpet.
I get to choose. Which circle will I draw through infinity and label as me? Which parts of you will I include? My cartoon painting of your face? Your voice, your stories, your laughter, your pain?
My choice will not be final. I am a breathing, flexing circle, drawn again and yet again. The pen, which is the air and the page till lines are drawn, cuts its circuit every day, every day taking a different path.
As we sit here and paint these mountains together. I hope your mountains, the you that is the mountains, the story of mountains told to yourself, by yourself, about yourself, is at least as beautiful as mine.
About
My name is Matthew Gray. I was born in Berkeley California, did my undergrad at UC Santa Cruz, worked for Microsoft Norway in Oslo, worked for Renton Technical College outside of Seattle, and am now persuing a DPhil in Computer Science at the University of Oxford. I am grateful to be affiliated with Magdalen College and advised by Rahul Santhanam.
My primary research lies at the intersection of quantum computing, cryptography, and meta-complexity. So far, my most significant result is the characterization of the existence of OWPuzz from the hardness of GapK on quantum samplable distributions.
I have pretty wide secondary interests. Both in the wider world of TCS and in the social sciences. I have deep interests in Philosophy, History, Economics, and Political Science. Here's a breif (and very non exuastive) sampling of my interests in these areas: Monetary theory and the macro-economics of state finance, Sortition (aka the democratic lottery), the successes and failures of computational meta-physics, the philosophy of simulation (Bostrom messed up in at least 2 important ways), formal theories of politics and coercive negotiations, the practiciality of a nuclear first strike and American nuclear hegemony in the 1940s, Historical cryptography and conspiracy.
More personally, I really like to cook, play board games, read, listen to podcasts, and exist near trees and bodies of water.
Feel free to reach out if you are interested in Quantum Meta-Complexity or Quantum Cryptography. I'd be excited to talk.