It is necessary to activate JavaScript to navigate this site.

Grantor: European Commission

**Programme type**: PEOPLE, MARIE CURIE ACTIONS, INTRA-EUROPEAN FELLOWSHIPS (IEF)

**Objectives**:

The project concerns research on the frontier between discrete mathematics and theoretical computer science. Discrete mathematics is an established mathematical discipline and is playing an increasing role in various fields of mathematics. Many real-life problems can be formulated using the language of discrete mathematics. Deep mathematics is hidden behind practical problems such as devising optimal schedules, or efficient routing of data packets through the internet. These problems also suggest that besides problems typical to pure mathematics (such as existence of a solution) one often seeks their efficient algorithmic counterparts (algorithm design).

The project goals are the following:

- To explore constructions of specialized families of expanders, in particular of monotone expanders
- To study the applications of dimension expanders (and related) in the area of explicit Ramsey graphs
- To study in detail the new concept of partition expanders
- To study the combinatorial construction of Mendel and Naor can yield explicit constructions of partition expanders, and to look for applications, especially in derandomization and communication complexity
- To understand the role of extractors in theoretical computer science
- To understand, extend, and simplify constructions of Ramsey graph of Barak et al
- To find a purely combinatorial construction of Ramsey graphs

Main investigator:

Participating institutions:

Institute of Mathematics, Czech Academy of Sciences