Talks & Seminars
Title: NC0 Proof Systems
Dr. Karteek Sreenivasaiah, Saarland University, Germany
Date & Time: April 14, 2017 15:30
Venue: Conference Room, C Block, 01st Floor, Dept. of CSE, Kanwal Rekhi (KReSIT) Bldg.
We study languages L for which membership of a string x in L has a certificate that can be verified very locally and more efficiently than polynomial time. In particular, we attempt to understand languages that have certificates of membership verifiable by circuit families of constant fan-in, constant depth, and polynomial size. Such circuit families are called NC0, and languages that have the property above are said to 'admit NC0 proof systems'. In the talk, we will begin with the main motivation to this branch of study and proceed to some constructions and lower bounds that serve as warmup. To conclude, we will look at one fairly non-trivial construction that is related to the main problem of interest.
Speaker Profile:
Karteek Sreenivasaiah is currently a postdoc in Saarland University, Germany. He completed his PhD in 2015 at The Institute of Mathematical Sciences, Chennai. His research interests lie broadly in Computational Complexity and Algorithms, and more specifically in areas that involve algebra or combinatorics
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback