BARC talk by Dhara Thakkar
Friday, September 5, 2025, Dhara Thakkar, Designated Assistant Professor at Nagoya University, Japan, will give a talk on "Group Order is in QCMA".
Abstract:
In this talk, Dhara will discuss recent progress on the role of classical proofs in quantum complexity theory, focusing on group-theoretic problems in the black-box model. We resolve two long-standing open questions in this area. First, we show that the Group Non-Membership problem—known to lie in QMA but not in MA—is in fact in QCMA, settling a 2006 conjecture by Aaronson and Kuperberg. This result follows from a more general result that the Group Order Verification problem lies in QCMA ∩ coQCMA, answering an open question posed by Watrous in 2000. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups settings.
Bio:
Dhara Thakkar is a Designated Assistant Professor at the Graduate School of Mathematics, Nagoya University in Japan, where she is working with François Le Gall's research group. Dhara completed her PhD in Theoretical Computer Science at IIT Gandhinagar, India, under the guidance of Bireswar Das. Even before that, she earned her M.Phil. degree (2019) and M.Sc. degree (2018) in (pure) mathematics from Sardar Patel University, Vallabh Vidyanagar, Gujarat, India.
Dhara’s research interests include Algebraic Computation, Computational Complexity, Group theory, Quantum Computation, Representation theory.
Host:
Nutan Limaye