We show that verifiable secret sharing (VSS) and secure multi-party computation (MPC)
among a set of n players can efficiently be based on any linear secret sharing scheme …

Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …

This book is a concise, self-contained, up-to-date introduction to extremal combinatorics for
nonspecialists. There is a strong emphasis on theorems with particularly elegant and …

Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra
and computer science. This self-contained book presents the basic concepts, classical …

We initiate the investigation of the class of relations that admit extremely efficient perfect zero
knowledge proofs of knowledge: constant number of rounds, communication linear in the …

These lecture notes introduce the notion of secure multiparty computation. We introduce
some concepts necessary to define what it means for a multiparty protocol to be secure, and …

This note, based on my 4ECM lecture, exposes few basic points of proof complexity in a way
accessible to any mathematician. In many parts of mathematics one finds statements …

monotone span programs computing explicit functions. The best previous lower bound was
by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion …

We characterize the size of monotone span programs computing certain “structured”
boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula …

Monotone span programs are a linear-algebraic model of computation which were
introduced by Karchmer and Wigderson in 1993 [1]. They are known to be equivalent to …