Chris Beck

• 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 2012. [STOC][ECCC]

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

• 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 good 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.