From the 1 of 5 linked papers with an AI index.
5 papers
PCPOP.jl: A Julia package for partially commutative polynomial optimization
Moisés Bermejo Morán, Abhishek Mishra
PCPOP.jl is a Julia package for polynomial optimization that supports non‑commutative, tracial, trace, and state polynomial problems, offering exact arithmetic, Gröbner basis reduc…
Partially-Commutative Polynomial Optimization
Abhishek Mishra, Moisés Bermejo Morán, Stefano Pironio
Semidefinite programming hierarchies for commutative and non-commutative polynomial optimization represent a powerful computational tool with many applications in quantum informati…
Recovery Reductions, Conjectures, and Barriers
Tejas Nareddy, Abhishek Mishra
We introduce and initiate the study of a new model of reductions called the random noise model. In this model, the truth table of the function is corrupted on a randomly…
New Techniques for Constructing Rare-Case Hard Functions
Tejas Nareddy, Abhishek Mishra
We say that a function is rare-case hard against a given class of algorithms (the adversary) if all algorithms in the class can compute the function only on an -fraction of i…
Hardness Amplification via Group Theory
Tejas Nareddy, Abhishek Mishra
We employ techniques from group theory to show that, in many cases, counting problems on graphs are almost as hard to solve in a small number of instances as they are in all instan…