Benny Sudakov

Lenny Fukshansky, Deanna Needell, Benny Sudakov

Compressed sensing is a relatively new mathematical paradigm that shows a small number of linear measurements are enough to efficiently reconstruct a large dimensional signal under the assumption the signal is sparse. Applications for this technology are ubiquitous, ranging from wireless communications to medical imaging, and there is now a solid foundation of mathematical theory and algorithms to robustly and efficiently reconstruct such signals. However, in many of these applications, the signals of interest do not only have a sparse representation, but have other structure such as lattice-valued coefficients. While there has been a small amount of work in this setting, it is still not very well understood how such extra information can be utilized during sampling and reconstruction. Here, we explore the problem of integer sparse reconstruction, lending insight into when this knowledge can be useful, and what types of sampling designs lead to robust reconstruction guarantees. We use a combination of combinatorial, probabilistic and number-theoretic methods to discuss existence and some constructions of such sensing matrices with concrete examples. We also prove sparse versions of Minkowski's Convex Body and Linear Forms theorems that exhibit some limitations of this framework.

Zach Hunter, Aleksa Milojević, Benny Sudakov et al.

Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of Babai, Frankl, and Simon in the 1980s and culminating in the famous works of Kalyanasundaram-Schnitger and Razborov in 1992. However, the question of obtaining tight bounds for product distributions persisted until the more recent work of Bottesch, Gavinsky, and Klauck resolved it. In this note we revisit this classical problem and give a short, streamlined proof of the best bounds, with improved quantitative dependence on the error parameter. Our approach is based on a simple combinatorial lemma that may be of independent interest: if two sets drawn independently from two distributions are disjoint with non-negligible probability, then one can extract two subfamilies of reasonably large measure that are fully cross-disjoint (equivalently, a large monochromatic rectangle for disjointness).

Akaki Mamageishvili, Benny Sudakov

We compare the total capital efficiency of secure restaking and Proof-of-Stake (PoS) protocols. First, we consider the sufficient condition for the restaking graph to be secure. The condition implies that it is always possible to transform such a restaking graph into separate secure PoS protocols. Next, we derive two main results: upper and lower bounds on the required extra stakes to add to the validators of the secure restaking graph to be able to transform it into secure PoS protocols. In particular, we show that the restaking savings compared to PoS protocols can be very large and can asymptotically grow as a square root of the number of validators. We also study a complementary question of aggregating secure PoS protocols into a secure restaking graph and provide matching lower and upper bounds on the PoS savings.

Stefan Glock, David Munhá Correia, Benny Sudakov

An $n$-queens configuration is a placement of $n$ mutually non-attacking queens on an $n\times n$ chessboard. The $n$-queens completion problem, introduced by Nauck in 1850, is to decide whether a given partial configuration can be completed to an $n$-queens configuration. In this paper, we study an extremal aspect of this question, namely: how small must a partial configuration be so that a completion is always possible? We show that any placement of at most $n/60$ mutually non-attacking queens can be completed. We also provide partial configurations of roughly $n/4$ queens that cannot be completed, and formulate a number of interesting problems. Our proofs connect the queens problem to rainbow matchings in bipartite graphs and use probabilistic arguments together with linear programming duality.