Login
Talks & Seminars
Title: Fine-grained Complexity and Pushdown Automata
Prof. Rupak Majumdar, Max Planck Institute for Software Systems, Germany
Date & Time: March 14, 2019 14:00
Venue: Department of Computer Science and Engineering, Room No. 101, 01st Floor, New CSE/CC Building
Abstract:
We show subcubic equivalences between three fundamental problems in formal languages: (1) the recognition problem for two-way nondeterministic pushdown automata (2NPDA), (2) the emptiness problem for one-way pushdown automata (PDA), and (3) Dyck-2 reachability on edge labeled graphs. Problems (1), (2), and (3) have “textbook” algorithms that run in cubic time but, despite many attempts, have defied subcubic algorithms (beyond logarithmic factors). We isolate a combinatorial problem, the k-Triclique problem in 3-hypergraphs, and show that a subcubic algorithm for any of the above problems will yield a breakthrough O(n(1−δ)k) algorithm for k-Triclique. Our reduction from k-Triclique uses a novel encoding of arithmetic of small binary numbers on the stack by two-way deterministic pushdown automata, when the input string is suitably augmented with “advice.” This shows the surprising power of two-way nondeterministic devices in encoding nontrivial combinatorial problems. p.s: Note that the talk will be a informal but technical board talk.
Speaker Profile:
Rupak Majumdar is a Scientific Director at the Max Planck Institute for Software Systems. His research interests are in the verification and control of reactive, real-time, hybrid, and probabilistic systems, software verification and programming languages, logic, and automata theory. Dr. Majumdar received the President’s Gold Medal from IIT, Kanpur, the Leon O. Chua award from UC Berkeley, an NSF CAREER award, a Sloan Foundation Fellowship, an ERC Synergy award, “Most Influential Paper” awards from PLDI and POPL, and several best paper awards (including from SIGBED, EAPLS, and SIGDA). He received the B.Tech. degree in Computer Science from the Indian Institute of Technology at Kanpur and the Ph.D. degree in Computer Science from the University of California at Berkeley.
List of Talks

Webmail

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