Research Experiences for Undergraduates 2018

May 28 - July 15, 2018, Rutgers, Piscataway, NJ, USA

July 20 - August 3, 2018, Charles University, Prague, Czech Republic

Group photo of the REU group at Rutgers
Group photo of REU participants taking part in the Prague part.

List of participants from Charles University

List of participants from the US

Research projects of the Czech group

Mentor of the Czech group: Periklis Papakonstantinou.

k-colored Point-set Embeddability of Graphs

Given a planar graph G = (V, E) and a point set S (|S| = |V|), we want to find an embedding of the graph into the point set such that:

For more colors, we assign colors to each vertex and each point such that, for each color, there is as many vertices as points. Each embedding can assign a vertex only to a point of the same color.

Our main goal is to find lower and upper bound on number of bends for the worst case tree in 2-color version.

Erdős-Faber-Lovász Conjecture and tetrices

Erdős-Faber-Lovász Conjecture: If n complete graphs, each having exactly n vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be colored with n colors.

Our goal is to read and traslate known results and proofs about EFL to tetris language and possibly to make some improvements and new discoveries.

Algortithms for systems with embeded FPGA

A field-programmable gate array (FPGA) is an integrated circuit that can be repeatadely reconfigured by a customer. It consists of programmable logic blocks which implements logic functions (AND, OR, XOR, etc.) and programmable routing that connects logic blocks.

A FPGA is usually used to speed up evaluation of functions such as SHA-256. A FPGA allows time multiplexing that means that it can simultaneously process multiple inputs as long as each computation is in a different phase.

Intel is about to release the first CPU with integrated FPGA. Our goal is to develop efficient algorithms for such systems.

Results of this project were accepted for TAMC 2019: Theory and Applications of Models of Computation held in April 2019 in Japan.

Prague part of REU

Conference during the Charles University program: Midsummer Combinatorial workshop.

REU volume (Brochure)

The report from REU 2018 is yet to be published in ITI-series.

Past REUs

List of sponsors

Logo KAM Logo IUUK Logo ITI Logo ITI Logo DIMACS Logo RSJ

Senior organizer: Jaroslav Nešetřil
Graduate coordinator: Peter Korcsok

Webmaster: kamweb@kam.mff.cuni.cz         Modified: 19. 02. 2019