Computer Science and Discrete Mathematics (CSDM)

We will go in-depth into the proof that for all functions t(n) greater than or equal to n, every multitape Turing machine running in time t can be simulated in space only O(tlogt‾‾‾‾‾√). We will attempt to be completely self-contained. To that end...

A linear extension of P is a linear ordering compatible with the poset relations. Let p(x less than y) be the probability that x

precedes y in a uniformly random linear extension, and let δ(x,y)=min(p(x less than y),p(y less than x)) and δ(P) be the...

I will describe a recent extension of the classical PAC (Probably Approximately Correct) learning framework [Vapnik and Chervonenkis, 1970s; Valiant, 1980s]. This extension makes it possible to model a wide range of common and practical data...

The r-colour Ramsey number Rr(k) is the minimum n∈ℕ such that every r-colouring of the edges of the complete graph Kn on n vertices contains a monochromatic copy of Kk. We prove, for each fixed r≥2, that

Rr(k)≤e−δkrrk

for some constant δ=δ(r)>0 and...

A valency argument is an elegant and well-known technique for proving impossibility results in distributed computing. It is an example of an extension-based proof, which is modelled as an interaction between a prover and a protocol. Even though...

This talk will be about two related results, one in complexity theory and one in learning.

On the learning side, we investigate the sample complexity of smooth boosters - These are boosting algorithms that do not place too much weight on any given...

In theoretical computer science, an increasingly important role is being played by sparse high-dimensional expanders (HDXs), of which we know two main constructions: "building" HDXs [Ballantine'00, ...] and "coset complex" HDXs [Kaufman--Oppenheim...

Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings...

High dimensional expansion comes in two flavors: spectral, which relates to random walks;  and cosystolic, which relates to chains of linear maps. The later is a more mysterious notion, which turns out related to a variety of applications such as...

A locally testable code (LTC) is an error-correcting code equipped with a tester T that, given an input string x, queries only a small number of positions and rejects x with probability proportional to its distance from the code. Classic examples of...