Login
Talks & Seminars
Title: Algebraic independence testing, approximate polynomials satisfiability, and the GCT chasm
Dr. Zeyu Guo, IIT Kanpur
Date & Time: March 6, 2019 16:00
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
Algebraic independence testing of polynomials over a field F is a basic problem with several applications in theoretical computer science. When char(F) = 0, this problem has an efficient randomized algorithm thanks to the classical Jacobian criterion. Over finite fields, however, no general subexponential-time algorithm is known due to the failure of the Jacobian criterion in positive characteristic. In this talk, I will show that algebraic independence testing over finite fields are in the intersection of AM and coAM. In particular, it is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, e.g. graph isomorphism & integer factoring. Our proof is based on a novel "point counting" approach that avoids the use of the Jacobian criterion. Next, I will talk about another problem called approximate polynomials satisfiability, which asks if a given system of polynomial equations has an approximate solution over an algebraically closed field. I will show that this problem can be solved in PSPACE using properties of projective spaces. As an unexpected application to approximative complexity theory, we prove that hitting-sets for the class "border VP" can be designed in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017), greatly mitigating the GCT Chasm (exponentially in terms of space complexity). This is joint work with Nitin Saxena and Amit Sinhababu.
Speaker Profile:
Dr, Zeyu Guo is a postdoctoral researcher at the CSE Department IIT Kanpur, working with Professor Nitin Saxena. He completed his Ph.D. in computer science at Caltech in 2017, under Professor Chris Umans. His research interests include algebraic methods in theoretical computer science, pseudorandomness and its connections with coding theory, algorithms in number theory and algebra.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback