Computer Science/Discrete Mathematics

The shuffle model is a widely used abstraction for non-interactive anonymous communication. It allows $n$ parties holding private inputs $x_1,\dots,x_n$ to simultaneously send messages to an evaluator, so that the messages are received in a random...

In the noisy $k$-XOR problem, one is given $y \in \bF_2^\constraints$ and must distinguish between $y$ uniform and $y = A x + e$, where $A$ is the adjacency matrix of a $k$-left-regular bipartite graph with variables and constraints, $x\in \bF_2^...

By combining sparse graphs with local constraints, expander codes offer a powerful framework for achieving fast decoding algorithms while maintaining asymptotically good rate and minimum distance. However, the standard constraint-counting arguments...

The random geometric graph Geo_d(n,p) is a probability distribution over graphs, constructed by placing n points uniformly on a d-dimensional sphere and connecting two points whenever they are sufficiently close — where the proximity threshold is...