# Research Experiences for Undergraduates 2018

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

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

## List of participants from Charles University

- Peter Korcsok (Graduate coordinator)
- Martin Hora
- Václav Končický
- Michael Skotnica
- Ondřej Šplíchal
- Aneta Šťastná
- Jakub Tětek

## List of participants from the US

- Parker Hund (Graduate coordinator)
- Caitlin Guccione
- Rahul Ilango
- Ryan Rice
- Sherry Sarkar
- Michael Yang

## 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:

- Each vertex is represented by a distinct point from S.
- Each edge is partially linear with as little bends as possible.

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

- REU 2018 - May 28 - August 3, 2018
- REU 2017 - May 30 - August 1, 2017
- REU 2016 - May 30 - July 30, 2016
- REU 2015 - May 31 - August 1, 2015
- REU 2014 - June 1 - August 1, 2014
- REU 2013 - June 2 - August 7, 2013
- REU 2012 - June 3 - August 8, 2012
- REU 2011 - May 31 - August 3, 2011
- REU 2010 - June 2 - August 4, 2010
- REU 2009 - June 1 - August 5, 2009
- REU 2008 - June 2 - August 6, 2008
- REU 2007 - June 4 - August 8, 2007
- REU 2006 - June 5 - August 9, 2006
- REU 2005 - June 6 - August 10, 2005
- REU 2004 - June 7 - August 11, 2004
- REU 2003 - June 9 - August 13, 2003
- REU 2002 - June 10 - August 14, 2002
- REU 2001 - June 11 - August 17, 2001
- REU 2000 - June - August, 2000
- REU 1999 - June 6 - August 1, 1999

## List of sponsors

*Senior organizer:* Jaroslav Nešetřil

*Graduate coordinator:* Peter Korcsok

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