43 citations · 179 across the 19 of their papers we have counts for
4 papers · 1 filter
On the power of nonstandard quantum oracles
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even…
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu +1
We study random constraint satisfaction problems (CSPs) in the unsatisfiable regime. We relate the structure of near-optimal solutions for any Max-CSP to that for an associated spi…
Non-Convex Optimization by Hamiltonian Alternation
Anuj Apte, Kunal Marwaha, Arvind Murugan
A major obstacle to non-convex optimization is the problem of getting stuck in local minima. We introduce a novel metaheuristic to handle this issue, creating an alternate Hamilton…
Fair allocation of a multiset of indivisible items
Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
We study the problem of fairly allocating a multiset of indivisible items among agents with additive valuations. Specifically, we introduce a parameter for the numb…