Randomness in Computing

This one-day workshop aims to bring together theoretical computer scientists whose research involves randomness and pseudorandomness. There are five invited talks and a session with contributed talks by junior researchers.

Attendance is free of charge. However, registration is required (deadline 10th June 2026) to help us with logistics. You can register here. 

We encourage junior researchers to submit a proposal for a short contributed talk on any topic in theoretical computer science; please use the registration form above to indicate your interest.

Ioana O. Bercea - Locally Uniform Hashing

Hashing is a commonly used technique for getting improved randomized algorithms. Most analyses, however, assume access to fully-random hash functions, which is unrealistic in terms of the resources available to the algorithm. A fundamental line of work has thus been to design realistic hash functions (with small space and fast evaluation time) that make the algorithm perform almost as if it used fully-random hash functions. In this talk, we will review one such hash function, called a tornado tabulation hash function, that provides state-of-the-art randomness guarantees for several fundamental algorithms. In particular, we will define and discuss one key property that it exhibits, that of local uniformity.

Amin Coja-Oghlan - The random XORSAT decimation process

In this talk I present an analysis of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on random XORSAT. I will we derive an explicit threshold up to which the algorithm succeeds with a strictly positive probability, but beyond which the algorithm fails with high probability. In addition, we analyse a thought experiment called the decimation process for which we identify a (non-)reconstruction and a condensation phase transition. The main results of the present work confirm physics predictions from [J. Stat. Mech. 2009].

Oded Lachish - “A characterization of one-sided error testable graph properties in bounded degeneracy graphs”

We consider graph property testing in p-degenerate graphs under the random neighbour oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbours of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of p-degenerate graphs allows for high-degree “hubs” that can structurally hide forbidden subgraphs from local exploration.

In this work, we provide a complete structural characterization of all properties testable with one-sided error in p-degenerate graphs. We show that testability is fundamentally determined by the connectivity of the forbidden structures: a property is testable if and only if its violations cannot be fragmented across disjoint high-degree neighbourhoods. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behaviour of the properties they define.

Mark Jerrum - Efficient sampling from high-dimensional distributions: perfect and local

Historically, the most important approach to sampling from complex high-dimensional distributions has been Markov chain simulation, which dates back at least to the 1950s.  Such an approach provides a sample from a probability distribution arbitrarily close to the target one.  Although the error in the approximation decays exponentially fast with the length of the simulation, it is still of interest to devise and analyse perfect sampling algorithms that match the target distribution exactly.  Starting with Propp and Wilson's "Coupling From The Past" (CFTP), several such samplers are now known. 

In this talk I seek to impose the condition of locality in addition to perfection.  That is to say, given a large or even infinite problem instance, I aim to produce a portion of a perfect sample from the target distribution, as seen through a finite window onto the sample, in time linear in the size of the window. I will include joint work with Konrad Anand (Edinburgh).

Thomas Sauerwald - “Balanced Allocations: The Power of Choice versus Noise”

In the balanced allocation problem we wish to allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and average load. For the one-choice protocol, where each ball is allocated to a random bin, the gap diverges for large m. However, for the two-choice protocol, where each ball samples two bins and is placed in the least loaded of the two, it was shown more than 20 years ago that the gap is only O(log log n) for all m. This dramatic improvement is widely known as ``power of two choices’’, and similar effects have been observed in hashing and routing.

In this talk, we will present new results in settings where the load information is restricted or noisy. For example, the queried load information of bins might be (i) outdated, (ii) subject to some adversarial or random perturbation or (iii) only retrievable by binary queries. We also exhibit settings with strong noise and demonstrate that having more choices can lead to a worse performance.

This is based on joint works with Dimitrios Los and John Sylvester. More information and some illustrations of the results are also available under: dimitrioslos.com/research/phd-thesis/index.html

Parinya Chalermsook 

Or Meir

Swagato Sanyal

Navid Talebanfard

Maksim Zhukovskii