Talks & Seminars
Title: Octahedral Tucker is PPA-Complete
Ms. Rucha Kulkarni, Indian Institute of Science
Date & Time: May 2, 2017 11:00
Venue: Lecture Hall, B Block, 03rd Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in {±i : i = 1, 2, ..., n} computed using a polynomial size logic circuit which is also a component of the input. Given that antipodal vertices are assigned complementary colors, there is always an edge (equivalently, a 1-simplex of the triangulation) for which the two adjacent vertices are assigned complementary colors. The computational complexity to find one has been an outstanding challenging problem. In this paper, we resolve this problem by proving Octahedral Tucker to be PPA-complete.
Speaker Profile:
Rucha was a MTech student in IITB from 2014-2016. She is currently a research intern at IISc.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback