Chris Beck


About me

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:

See also my resume and CV.

Email me at [my last name].ct@gmail.com.

Academic Research Thesis
  • PhD Thesis [pdf]

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

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.

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 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

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]

Articles Some unpublished notes of mine:
  • A PSD criteria for combinatorial matrices. This is a self-contained exposition of a result of Lovasz and Szegedy. [tex pdf]

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