2021-2022 Seminars

Consider the action of a group on a finite-dimensional vector space. Given some natural conditions on the group, Hilbert showed a famous "duality" between invariant polynomials and closures of group orbits. Namely, the orbit closure of a vector is...

Expander graphs are sparse and yet well-connected graphs. Several applications in theoretical computer science require explicit constructions of expander graphs, sometimes even with additional structure. One approach to their construction is to...

A binary code is simply any subset of 0/1 strings of a fixed length. Given two strings, a standard way of defining their distance is by counting the number of positions in which they disagree. Roughly speaking, if elements of a code are sufficiently...

The ABNNR encoding is a classical encoding scheme that amplifies the distance of an error correcting code. The encoding takes an error correcting code with a small distance and constructs an error correcting code with distance approaching one, by...

As solutions can be efficiently verified, any NP-complete problem can be solved by exhaustive search. Unfortunately, even for small instances the running time for exhaustive search becomes very high. 

On the bright side, for many NP-complete...

Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science, 3SAT being a prominent example.

Let $\Sigma$ be an alphabet and $P:\Sigma^k \rightarrow \{0,1\}$ be a fixed predicate. The assignments in $P^{-1}...