# Alfonso Cevallos¶

I work in the analysis and optimization of decentralized algorithms, making sure that both scalability and security goals, often at odds, are met. Another area of active work is adding the incentives layer (rewards, slashings, handling of reports) to decentralized protocols, to ensure that all dishonest behaviors are discouraged. Finally, I study multi-agent decision-making mechanisms such as committee elections, referenda, auctions, and general on-chain governance. In these processes, I work on properties such as proportional representation, transparency, strategy proofness, and participation encouragement.

**Areas of interest.** Complexity theory, approximation algorithms, algorithmic game theory, mechanism design, computational social choice, crypto economics, and governance. On a lesser level: consensus protocols, finality gadgets, inter-operability across blockchains, zero-knowledge proofs.

**Short bio.** I’m originally from Ecuador, where I studied a mathematics degree at USFQ, graduating Cum Laude. In 2011 I completed a master’s program in U. Leiden, Netherlands on number theory, with a thesis on threshold cryptography. In 2016 I finished a Ph.D. program at EPFL, Switzerland, in the Discrete Optimization group under the supervision of Prof. Friedrich Eisenbrand. My focus was on approximation algorithms for problems in graph theory and computational geometry. From 2016 to 2018 I was a post-doctoral researcher at ETH Zurich, in the Institute for Operations Research, where I worked on the extension complexity of combinatorial polytopes, and the limits of linear and integer programming. I joined the Web3 Foundation in 2019.

**Recent talks and activities.**

• (April 2020) First virtual meetup of Polkadot in Spanish: https://www.youtube.com/watch?v=FLghX_5v7eE

• (June 2019) Podcast episode at Chorus One, where I talk about NPoS: https://chorusone.libsyn.com/2-polkadots-nominated-proof-of-stake-with-alfonso-cevallos

• (April 2019) Blogpost at Medium, about validator selection with NPoS: https://medium.com/web3foundation/how-nominated-proof-of-stake-will-work-in-polkadot-377d70c6bd43

**Selected publications**

• A. Cevallos, Fr. Eisenbrand, R. Zenklusen. *An improved analysis of local search for max-sum diversification.* Mathematics of Operations Research, 2019.

• M. Aprile, A. Cevallos, Y. Faenza. *On 2-level polytopes arising in combinatorial settings.* SIAM Journal on Discrete Mathematics (SIDMA), 2018.

• A. Cevallos, S. Weltge, R. Zenklusen. *Lifting linear extension complexity bounds to the mixed-integer setting.* Symp. on Discrete Algorithms (SODA), 2018.

• A. Cevallos, F. Eisenbrand, R. Zenklusen. *Max-sum diversity via convex programming.* Symp. on Computational Geometry (SoCG), 2016.

• A. Cevallos, S. Fehr, R. Ostrovsky, Y. Rabani. *Unconditionally-secure robust secret sharing with compact shares.* Advances in Cryptology – EUROCRYPT, 2012.