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 secu- rity. Notable projects include fooling facial recognition, using Fourier Analysis to investigate MD5, and Designing Data Structures to Minimize Bit Flips on NVM

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

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. Reg- ular 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.

Publications

2023 Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, and Angelos Pelecanos. On the Computational Hardness of Quantum One-Waynesshttps://arxiv.org/abs/2312.08363
2023 Noel Arteche, Gaia Carenini, and Matthew Gray. On the Quantum Automatability of Propositional Proof Systems https://eccc.weizmann.ac.il/report/2024/029/
2019 Matthew Gray. “LOADS of Space”, Local Order Agnosticism and Bit Flip Efficient Data Structure Codes. , August 2019https://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 interested in several questions in Philosophy and have developed a Bayesian resolution to Hume's problem of Induction.

Academic Projects

(note: This section is very out of date and only includes work done before starting my PhD)

Multiparty Coin Flipping for Large Scale Sortition

Spring 2021-Summer 2021, Collaborators: Justin Raizes (CMU) & Paul Gölz (CMU) Studied the Multiparty Coin Flipping literature hoping to find tools for de- veloping secure procedures for large scale sortition. For instance in selecting US congressional representatives. Based on a deep understanding of the re- quirements for Cleve’s impossibility result I developed several approaches which are published in a series of articles on the sortitionist blog Equality by Lot.

Bit-Flip-Efficient Coding for Non-Volatile Memory

Winter 2018 - Spring 2019, Collaborators: Justin Raizes (UCSC) & Daniel Bittman (UCSC) Many implementations of Non-Volatile-RAM deteriorate or consume large amounts of energy with every bit flip. This project focused on developing data structures and data-structure codes that reduced bitflips. I think this area still has some very rich possibilities. Resulted in a paper and my thesis both listed under Publications.

Fourier Analysis of Weak Hash Functions

Winter 2018 - Winter 2018, Collaborators: Seshadhri Comandur (UCSC), Justin Raizes (UCSC), & Will Bolden (UCSC) We used techniques from the Fourier Analysis of Boolean Functions to search for high influence Juntas in weak Hash functions such as SHA-1. We were fairly successful within the first of the four rounds and discovered other interesting patterns, but did not ultimately discover a mathematically satisfying explanation for why these hash functions were breakable.

Fooling Facial Recognition

Fall 2017 - Spring 2018, Collaborators: Anastasia McTaggart (UCSC), Miriam del Cerro Marazuela (UCSC), Steven Mazliach (UCSC), & Macie Cooper (UCSC) We investigated techniques for fooling facial recognition software without the use of masks or other large facial coverings. We found some success with drag style makeup, with partial coverings, and with the use of reflective materials. Results, motivations, and methods are summarized here.

About

My name is Matthew Gray and I am currently studying for my DPhil in TCS at the University of Oxford where I am very grateful to be affiliated with Magdalen College and advised by Rahul Santhanam.

Since I guess I have your attention here for a second, be kind to someone today. That someone can be yourself.

Feel free to reach out if you are interested in Quantum Meta-Complexity. I'd be excited to talk.

Matthew Gray

DPhil Student at the University of Oxford

Theoretical Computer Scientist and Mathematician