Research Experiences for Undergraduates 2016

May 30 - July 17, 2016, Rutgers, Piscataway, NJ, USA

July 18 - July 30, 2016, Charles University, Prague, Czech Republic

List of participants from Charles University

Mentor of the Czech group: Eric Allender.

Circuit Complexity: along with our mentor Eric Allender, we studied the Minimum Circuit Size Problem (MCSP) and its position in the complexity hierarchy.
Burning Number: A modification of the dominating set problem. Imagine the first vertex can dominate its neighbors, the second vertex dominates every vertex in distance two, the third one in distance three and so on. The minimum dominating number in this regime is called burning number of a graph. We tried to tackle the conjecture that for each graph G, its burning number is at most the square root of |V(G)|.
Complexity of embedding 2D simplicial complexes: Our aim was to prove that the problem of deciding whether a 2D simplicial complex is straight-line-embeddable into the Euclidean 3D space lies in the complexity class NP.

Conference during the Charles University program: Mathematics of Jiří Matoušek.

The report from REU 2016 is in preparation and will be published as part of the ITI-series.

Senior organizer: Jaroslav Nešetřil
Graduate coordinator: Martin Böhm

Webmaster: kamweb@kam.mff.cuni.cz Modified: 24. 03. 2018