For a finitely presented group, the Word Problem asks for an
algorithm which declares whether or not words on the generators
represent the identity. The Dehn function is the time-complexity of
a direct attack on the Word Problem by applying the...
The study of Cayley graphs of finite groups is related to the
investigation of pseudo-random graphs and to problems in
Combinatorial Number Theory, Geometry and Information Theory. I
will discuss this topic, describing the motivation and focusing
on...
The Parallel Repetition Theorem upper-bounds the value of a
repeated (tensored) two prover game in terms of the value of the
base game and the number of repetitions. In this work we give a
simple transformation on games -- "fortification" -- and...
Finding large cliques in random graphs and the closely related
"planted" clique variant, where a clique of size \(k\) is planted
in a random \(G(n,1/2)\) graph, have been the focus of substantial
study in algorithm design. Despite much effort, the...
Start with a compact Riemann surface \(X\) and a complex reductive
group \(G\), like \(\mathrm{GL}(n,\mathbb C)\). According to
Hitchin-Simpson's ``non abelian Hodge theory", the pair \((X,G)\)
comes with two new complex manifolds: the character...
I will present an exciting new interaction between computer science
and fair division theory, with the goal of giving the audience a
taste of different fair division challenges and the role
computational thinking plays in addressing them. Among...
