General Information
| Student: | Peter Korcsok |
|---|---|
| Office: | CoRE 448 |
| School: | Charles University, Prague, Czech Republic |
| E-mail: | peter.korcsok guess_what_is_here rutgers.edu |
| Projects: | $k$-colored Point-set Embeddability of Graphs, , Algortithms for systems with embeded FPGA |
| Previous REU: | DIMACS REU 2014 |
I am trying to be a gruaduate coordinator of the Czech group which consists of Martin Hora, Václav Končický, Michael Skotnica, Ondřej Šplíchal, Aneta Šťastná, Jakub Tětek and myself. Our Rutgers advisor is Periklis Papakonstantinou.
Since we are a large group, we have a couple of problems from our mentor and we also brought some from Prague. There is a brief review:
$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.
See a weekly log for this problem on Michaels's page.
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.