Academic Research
Thesis
Publications
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
2012. [STOC ][ECCC ]
After my PhD, I was a scholar at IAS in Princeton from 2014-2016 in Avi Wigderson's CSDM group .
Open Source Software
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. You can see recordings of several talks that I gave about Fog.
Stanford Science of Blockchain Conference 2022 Lightning Round (3 minutes)[youtube ][slides ]
Ethereum Denver 2023 Public Goods Stage (20 minutes) [twitch ][slides ]
OC3 Open Confidential Computing Conference 2023 (25 minutes) [youtube ][slides ]
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.
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.
I also designed and implemented MobileCoin's protocol for privacy-preserving on-chain atomic swaps. See here and here for more information.
Some other open source projects that I created:
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 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
Some open source projects that I have contributed to
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
My stackoverflow questions and answers.
Recommended Reading (Math)
Some notes and papers that I particularly like
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 ]
Recommended Reading (Systems Programming)
Some blog posts and conference presentations that I recommend
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 ]