5 papers
PCPOP.jl: A Julia package for partially commutative polynomial optimization
Moisés Bermejo Morán, Abhishek Mishra
Here we present PCPOP, a Julia package for polynomial optimization that supports non-commutative optimization, tracial polynomial optimization, trace polynomial optimization and st…
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…
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…
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…