Hi. I'm a computer scientist now living in Arvada, Colorado.
I am now working as a software engineer on the core team at MobileCoin.
Some things I like:
godbolt compiler explorer
Mathematics: especially, combinatorics, computational complexity, pseudorandomness, cryptography, algorithms
See also my resume and CV.
Email me at [my last name].firstname.lastname@example.org.
PhD Thesis [pdf]
Strong ETH holds for Regular Resolution.
Chris Beck, Russell Impagliazzo. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing. [STOC][ECCC]
Some Tradeoff Results for Polynomial Calculus
Chris Beck, Jakob Nordström, Bangsheng Tang. Proceeding
STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing. [STOC][ECCC]
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits.
Chris Beck, Russell Impagliazzo, Shachar Lovett. In Proceedings of the Fifty-Third Annual Symposium on Foundations of Computer Science, 2012. [FOCS][ECCC]
Time Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
Paul Beame, Chris Beck, Russell Impagliazzo. In Proceedings of the Fourty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, May
My github account.
The largest open source project that I have worked on is MobileCoin.
Besides working on parts of SGX infrastructure and transaction cryptography, I also had a lead role in the design
and implementation of the "MobileCoin Fog" system.
MobileCoin Fog creates a way for mobile devices to privately download only their MobileCoin transactions from a service operated by a third party, without revealing to that third party which if any transactions they received.
This was designed to meet the requirements of integration with Signal App
Users can find their transactions very quickly and without downloading the whole blockchain, even if they lose their phone and only have their private keys
The service provider (Signal) has as little information as possible about which if any transactions belong to which users
Our solution required the use of Oblivious RAM inside of Intel SGX enclaves.
This was the first project in the world to ship an ORAM web service to millions of users.
This is the only scalable way to do balance checking on a privacy coin that I know of without giving away your private keys to a third party.
All Signal clients now obtain all of their MobileCoin balance information using Fog, and submit all of their MobileCoin transactions with the help of Fog.
Fog is now open source and has been merged into the MobileCoin repo. See the README for more information.
mc-oblivious, an optimized and production-ready implementation of Oblivious RAM and Oblivious Hash Maps in Rust, which underlies MobileCoin Fog. This has been optimized with x86-64 architecture and SGX in mind, although this code does not directly rely on SGX. One particularly novel aspect of this is an oblivious hash table
in which it is possible to insert-or-modify the value associated to a key whilst remaining oblivious as to whether or not a new item was inserted.
visit_struct, a miniature library for struct-field reflection in C++11
strict_variant, an elegant type-safe union for C++11
See slides for a talk I gave about this. [pptx][pdf]
lua primer, a collection of C++11 bindings over lua and lua-eris
spirit_po, a high-performance parser for the gettext po format in C++11, using boost::spirit
frozen, a header-only C++14 constexpr alternative to gperf
The Battle for Wesnoth, an open source tactical strategy game distributed under the GNU GPL license
CEGUI, a GUI library for C++
magic_get, a library for struct-field reflection in C++14, using template metaprogramming
An elegant proof by Van Vu of the Chernoff-Hoeffding inequality. (Scribe notes by Kirill Levchenko) [link pdf]
An introduction to the switching lemma. (Paul Beame) [link]
Time-Space trade-offs in a pebble game. Paul and Tarjan '78 [link pdf]
Self-adjusting binary search trees. Sleator and Tarjan '85 [link]
Pseudorandom generators for space-bounded computation. Nisan '90 [link pdf]
Short proofs are narrow: Resolution made simple. Ben-Sasson and Wigderson '00 [link pdf]
A proof of Johnson Lindenstrauss Dimensionality Reduction. Gupta and Dasgupta '01 [link]
Randomness-efficient sampling within NC. Healy '07 [pdf]
The Multiplicative Weights Update Method. Arora, Harzan, Kale, '12 [link]
Type-punning, strict-aliasing, and optimization (John Regehr) [html]
What every C programmer should know about undefined behavior (Chris Lattner) [html]
The lost art of structure packing (esr) [html]
Notes on structured concurrency, or: Go statement considered harmful (Nathaniel J. Smith) [html]
1024 cores: Intro to lockfree algorithms [html]
Tuning C++ (Chandler Carruth)[youtube]
Atomic Weapons: The C++11 Memory Model and Modern Hardware (Herb Sutter)[youtube part 1 part 2]
What has my compiler done for me lately? (Matt Godbolt) [youtube]
A PSD criteria for combinatorial matrices. This is a self-contained exposition of a result of Lovasz and Szegedy. [tex pdf]
wealoneonearth, a blog written by two of my good friends where I have occasionally made cameos
main is usually a function, a nice programming blog by another good friend
Andrzej's C++ blog, a top notch C++ blog
Tim Gowers' mathematics blog. I am linking to "A conversation on Complexity Lower Bounds" which is a well-written series about why complexity lower bounds are hard to prove in ways that the uninitiated might not expect.
All pdf's representing my own research hosted on this website are available with No Rights Reserved,
under the terms of the Creative Commons CC0 License.